Кортунов Вадим Вадимович kortunov@live.com

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

 

Сколько должно быть строк в таблице? Количество строк вычисляется формулой 2n, где n – количество переменных в формуле. В данном случае у нас две переменные – «a» и «b». Соответственно 22 =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 b c) (a ¬c ¬b))

 

Поскольку у нас 3 переменные, число строк равно 23=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 строчек. Понятно, что невыполнимых задач не существует. Но подобное исчисление может стоить студенту адского труда в течение многих суток, и, что более существенно, необратимой деградации умственного здоровья.

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