III. Построение таблиц истинности

Урок III.

Построение таблиц истинности.

Построение таблиц истинности является первой и основополагающей задачей студента, который впервые знакомится с логикой. Таблицы истинности строятся для логики высказываний. Эти таблицы автоматизированы в том смысле, что их результат зависит от алгоритмических действий. Читатель может зайти на множество сайтов, где представлены он-лайн калькуляторы для подобных исчислений. Однако мастерство создавать этих таблицы «вручную» способствует развитию логического мышления.

Дополнительная информация

Логика высказываний и логика предикатов считаются двумя разделами классической логики. В некоторых источниках – логика предикатов считается расширением логики высказываний (её развитием).

Теперь по порядку.

Логика высказываний анализирует отношения между высказываниями.

Логика предикатов анализирует отношения внутри одного высказывания.

Суждение «Все люди млекопитающие» в логике высказываний может обозначаться одним символом, например, символом «a». В логике предикатов это выражение будет обозначаться значительно сложнее, учитывая его внутреннюю структуру — ∀xS(x).

В предыдущем разделе мы попытались вывести формулу словесного выражения «Если кто-то любит кого-то, и никто не любит всех, значит, некто любит всех или все не любят кое-кого». И получили формулу ∃x∃yL(x,y)∧∀x∀y¬L(x,y)⊃∃x∀yL(x,y)∨∀x∃y¬L(x,y). Это формула логики предикатов. Если бы мы хотели выразить это суждение в логике высказываний, мы бы получили более емкую запись: a∧b⊃c∨d.

Логика высказываний даёт возможность анализировать большие массивы высказываний и отношения между ними.

Ещё одно отличие логики высказываний от логики предикатов заключается в том, что она (логика высказываний) не использует операторы – знаки кванторов – «∃» и «∀».

Важно

Каждый школьник помнит, что в арифметике сначала выполняются умножение и деление, а затем – сложение и вычитание.

В логике также существует соглашение о порядке действий. Сначала конъюнкция «∧, затем дизъюнкция «∨», затем импликация «⊃», и затем эквивалентность «≡». Такое соглашение позволяет избегать лишних скобок (именно поэтому данное соглашение иногда называется «соглашением о скобках»). Если бы мы не приняли такого соглашения, то формулу «a∧b∨c⊃d≡e» нам бы пришлось записывать так: «(((a∧b)∨c)⊃d)≡e».

Начнём с какого-нибудь очень простого примера. Предположим, нам предлагается построить таблицу истинности для формулы

a⊃a∨b

Мы видим, что в данной формуле два логических знака — «⊃» и «∨». Какой из них главный, какова последовательность наших действий? Для этого мы должны восстановить скобки. Вспоминаем соглашение о скобках: сначала конъюнкция «∧, затем дизъюнкция «∨», затем импликация «⊃», и затем эквивалентность «≡»

Значит формулу «a⊃a∨b» можно представить как «a⊃(a∨b)» (но, ни в коем случае, как «(a⊃a)∨b»!) В целом – это импликация.

Затем приступаем к построению таблицы истинности. Сколько должно быть в не столбцов? Ровно столько, сколько знаков в формуле, считая логические термины. В нашем случае пять знаков:

1	2	3	4	5
a	⊃	a	∨	b

Сколько должно быть строк в таблице? Количество строк вычисляется формулой 2ⁿ, где n – количество переменных в формуле. В данном случае у нас две переменные – «a» и «b». Соответственно 2²=4. Значит, рисуем четыре строчки:

	1	2	3	4	5
	a	⊃	a	∨	b
1
2
3
4

Для удобства мы пронумеровали столбцы и строки. Однако в дальнейшем это делать не обязательно.

Следующим шагом мы должны присвоить переменным значение «истина» и «ложь». Причём таким образом, чтобы перебрать все возможные комбинации. Для этого мысленно делим количество строк пополам, и в первой половине пишем значение «истина», а во второй «ложно».

	1	2	3	4	5
	a	⊃	a	∨	b
1	И
2	И
3	Л
4	Л

Поскольку переменная «a» у нас встречается два раза, то просто переписываем значение «И» и «Л» еще раз:

	1	2	3	4	5
	a	⊃	a	∨	b
1	И		И
2	И		И
3	Л		Л
4	Л		Л

Как присвоить значение «И» и «Л» второй переменной? У второй переменной чередование «И» и «Л» в строках должна быть вдвое чаще, чем в предыдущей:

	1	2	3	4	5
	a	⊃	a	∨	b
1	И		И		И
2	И		И		Л
3	Л		Л		И
4	Л		Л		Л

Поскольку мы договорились о порядке действий, то сначала мы проверяем на истинность дизъюнкцию «∨», а только затем импликацию «⊃». Делаем это по таблицам истинности для логических знаков, которые были подробно описаны в предыдущем разделе. Приведём еще раз эти таблицы, для удобства объединив их воедино:

переменные		результат их сравнения
A	B	∧	∨	⊃	≡
И	И	И	И	И	И
И	Л	Л	И	Л	Л
Л	И	Л	И	И	Л
Л	Л	Л	Л	И	И

Итак, для начала мы сравниваем значения дизъюнкцию «∨». То есть, сравниваем столбцы 3 и 5 и вписываем результат в столбец 4:

	1	2	3	4	5
	a	⊃	a	∨	b
1	И		И	И	И
2	И		И	И	Л
3	Л		Л	И	И
4	Л		Л	Л	Л

Завершающим шагом должно быть выписывание значение импликации «⊃» во втором столбце. Для этого сравниваем значения первого столбца с результатом дизъюнкции (со значениями четвёртого столбца):

	1	2	3	4	5
	a	⊃	a	∨	b
1	И	И	И	И	И
2	И	И	И	И	Л
3	Л	И	Л	И	И
4	Л	И	Л	Л	Л

Из проведённого исчисления делаем вывод: формула «a⊃a∨b» принимает значение «истина» при любых значениях, входящих в неё переменных. Такая формула называется тождественно-истинной.

Важно

Если формула принимает значение «истина» при любых значениях, входящих в неё переменных, она называется тождественно-истинной (или законом логики).

Если формула принимает значение «ложь» при любых значениях, входящих в неё переменных, она называется тождественно-ложной.

Если формула принимает значение как «ложь», так и «истина», она называется выполнимой или опровержимой (в зависимости от поставленной задачи).

Обращаем внимание читателя, что отрицание тождественно-истинной формулы имеет своим результатом тождественно-ложную формулу. И, наоборот, отрицание тождественно-ложной формулы имеет своим результатом тождественно-истинную формулу.

В этом легко убедиться, построив таблицу. Предположим, нам дано не «a⊃a∨b», а «¬(a⊃a∨b)». Поскольку эта формула уже не импликация, а отрицание импликации, последним действием становится отрицание всей формулы. Для этого мы в столбце «¬» переписываем значения импликации (столбца 3), меняя эти значения на противоположные:

	1	2	3	4	5	6
	¬	a	⊃	a	∨	b
1	Л	И	И	И	И	И
2	Л	И	И	И	И	Л
3	Л	Л	И	Л	И	И
4	Л	Л	И	Л	Л	Л

Усложним задачу.

Предположим, нам предлагается построить таблицу истинности для выражения: «Данное рассуждение неправильное: Если я выучу логику и высплюсь перед экзаменом, то непременно получу пятёрку. Я выучил логику, но на экзамене пятёрку не получил. Следовательно, я не выспался».

Постараемся перевести это выражение на формальный язык логики:

a – я выучил логику;

b – я выспался;

¬b – я не выспался;

c – я получил пятёрку;

¬c — я не получил пятёрку.

«Если я выучу логику и высплюсь перед экзаменом, то непременно получу пятёрку»: a∧b⊃c.

«Я выучил логику, но на экзамене пятёрку не получил. Следовательно, я не выспался»: a∧¬c⊃¬b.

Объединим эти две формулу воедино: (a∧b⊃c)⊃(a∧¬c⊃¬b).

Поскольку мы эту формулу отрицаем, то берём её в скобки и ставим перед ней знак отрицания: ¬((a∧b⊃c)⊃(a∧¬c⊃¬b)).

Стоим таблицу (для удобства сохраняя скобки):

((a

∧

⊃

∧

¬c

⊃

¬b))

Поскольку у нас 3 переменные, число строк равно 2³=8.

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))

Присваиваем значение первой переменно «a». Дели количество строк пополам и получаем четыре. Вписываем четыре5 значения «И» и четыре значения «Л»:

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))
	И						И
	И						И
	И						И
	И						И
	Л						Л
	Л						Л
	Л						Л
	Л						Л

Присваиваем значения второй переменной «b». Чередуем значение «И» и «Л» вдвое чаще, по отношению к первой переменной «a». Поскольку у нас есть столбец «b» и «¬b», значения в них должны быть противоположными:

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))
	И		И				И				Л
	И		И				И				Л
	И		Л				И				И
	И		Л				И				И
	Л		И				Л				Л
	Л		И				Л				Л
	Л		Л				Л				И
	Л		Л				Л				И

Аналогично присваиваем значения переменно «c»:

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))
	И		И		И		И		Л		Л
	И		И		Л		И		И		Л
	И		Л		И		И		Л		И
	И		Л		Л		И		И		И
	Л		И		И		Л		Л		Л
	Л		И		Л		Л		И		Л
	Л		Л		И		Л		Л		И
	Л		Л		Л		Л		И		И

Начинаем вводить значения конъюнкций:

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))
	И	И	И		И		И	Л	Л		Л
	И	И	И		Л		И	И	И		Л
	И	Л	Л		И		И	Л	Л		И
	И	Л	Л		Л		И	И	И		И
	Л	Л	И		И		Л	Л	Л		Л
	Л	Л	И		Л		Л	Л	И		Л
	Л	Л	Л		И		Л	Л	Л		И
	Л	Л	Л		Л		Л	Л	И		И

Затем – импликаций:

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))
	И	И	И	И	И		И	Л	Л	И	Л
	И	И	И	Л	Л		И	И	И	Л	Л
	И	Л	Л	И	И		И	Л	Л	И	И
	И	Л	Л	И	Л		И	И	И	И	И
	Л	Л	И	И	И		Л	Л	Л	И	Л
	Л	Л	И	И	Л		Л	Л	И	И	Л
	Л	Л	Л	И	И		Л	Л	Л	И	И
	Л	Л	Л	И	Л		Л	Л	И	И	И

Выполняем заключительную импликацию:

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))
	И	И	И	И	И	И	И	Л	Л	И	Л
	И	И	И	Л	Л	И	И	И	И	Л	Л
	И	Л	Л	И	И	И	И	Л	Л	И	И
	И	Л	Л	И	Л	И	И	И	И	И	И
	Л	Л	И	И	И	И	Л	Л	Л	И	Л
	Л	Л	И	И	Л	И	Л	Л	И	И	Л
	Л	Л	Л	И	И	И	Л	Л	Л	И	И
	Л	Л	Л	И	Л	И	Л	Л	И	И	И

И, наконец, отрицаем всю формулу:

¬	((a	∧	b	⊃	c)	⊃	(a	∧	¬c	⊃	¬b))
Л	И	И	И	И	И	И	И	Л	Л	И	Л
Л	И	И	И	Л	Л	И	И	И	И	Л	Л
Л	И	Л	Л	И	И	И	И	Л	Л	И	И
Л	И	Л	Л	И	Л	И	И	И	И	И	И
Л	Л	Л	И	И	И	И	Л	Л	Л	И	Л
Л	Л	Л	И	И	Л	И	Л	Л	И	И	Л
Л	Л	Л	Л	И	И	И	Л	Л	Л	И	И
Л	Л	Л	Л	И	Л	И	Л	Л	И	И	И

Формула ¬((a∧b⊃c)⊃(a∧¬c⊃¬b)) оказалась тождественно-ложной. Значит ее противоположность — (a∧b⊃c)⊃(a∧¬c⊃¬b) — тождественно-истинная формула, или закон логики. В данном случае речь идёт о законе сложной контрапозиции.

Дополнительная информация

_________________________________________________________________________________

Существует более краткий метод построения таблиц истинности. Он менее монотонный и нудный, но более сложный и, одновременно, интересный.

Предположим, нам надо доказать закон экспортации — (a∧b⊃c)⊃(a⊃(b⊃c)).

Смысл в том, что мы строим своё доказательство от противного (предполагая, что формула ложна) и меняем порядок действий на противоположный: начинаем с эквивалентности «≡», затем переходим к импликации «⊃», затем к дизъюнкции «∨», и, в последнюю очередь, к конъюнкции «∧. Для этого нам понадобится лишь одна строчка:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))

Поскольку мы пытаемся доказать формулу от противного, мы предполагаем, что она ложна:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))
					Л

Импликация ложна в одном случае, когда истинен антецедент (условие), а консеквент (вывод)– ложен, т.е.:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))
			И		Л		Л

Если формула (a⊃(b⊃c)) мы посчитали ложной, это значит, что ее антецедент «a» истинен, консеквент «b» — ложен:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))
			И		Л	И	Л		Л

Если формула (b⊃c) ложна, то по закону (по таблице истинности для импликации) «b» должно быть истинным, а «с» — ложным:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))
			И		Л	И	Л	И	Л	Л

Поскольку переменные «a» и «b» у нас уже имеют истинные значения, мы эти значения переносим в пустые клетки:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))
И		И	И		Л	И	Л	И	Л	Л

Когда конъюнкция верна? Когда верны оба её члена:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))
И	И	И	И		Л	И	Л	И	Л	Л

Поскольку антецедент формулы (a∧b⊃c) у нас уже обозначен как истинный, нам ничего не остается, как вписать в колонку «с» значение «И»:

(a	∧	b	⊃	c)	⊃	(a	⊃	(b	⊃	c))
И	И	И	И	И	Л	И	Л	И	Л	Л

Исчисление завершено. Теперь давайте посмотрим, что мы получили в итоге. Переменная «с» у нас получила значение «И» и «Л». Таким образом, предположив, что формула (a∧b⊃c)⊃(a⊃(b⊃c)) ложна, мы пришли к противоречию. Значит наше предположение ложно, а формула – истинна.

Важно

Если, применяя краткий метод построения таблицы истинности, мы доказываем её истинность и нам это удается – формула выполнима. Если нам это не удаётся – формула тождественно-ложная.

Если, применяя краткий метод построения таблицы истинности, мы доказываем её ложность и нам это удается – формула опровержима. Если нам это не удаётся – формула тождественно-истинная.

Краткий метод построения таблиц используется, когда в формуле присутствует много переменных. Представьте, что Вам необходимо произвести табличное исчисление с шестью, семью или двенадцатью переменными. В этом случае Вам придётся нарисовать 64, 128 и, соответственно, 4096 строчек. Понятно, что невыполнимых задач не существует. Но подобное исчисление может стоить студенту адского труда в течение многих суток, и, что более существенно, необратимой деградации умственного здоровья.

Впрочем, выбор за Вами…

	1	2	3	4	5	6
	¬	a	⊃	a	∨	b
1	Л	И	И	И	И	И
2	Л	И	И	И	И	Л
3	Л	Л	И	Л	И	И
4	Л	Л	И	Л	Л	Л

	1	2	3	4	5	6
	¬	a	⊃	a	∨	b
1	Л	И	И	И	И	И
2	Л	И	И	И	И	Л
3	Л	Л	И	Л	И	И
4	Л	Л	И	Л	Л	Л

	1	2	3	4	5	6
	¬	a	⊃	a	∨	b
1	Л	И	И	И	И	И
2	Л	И	И	И	И	Л
3	Л	Л	И	Л	И	И
4	Л	Л	И	Л	Л	Л