Алгоритм построения таблицы истинности.

1) Определить число строк в таблице, используя формулу k = 2ⁿ, где k – число строк в таблице, а n – число пропозициональных переменных, входящих в формулу.

2) Задать все комбинации совместной истинности/ложности пропозициональных переменных.

3) Установить последовательность определения значений связок (порядок действий), при этом последняя связка называется главной, т.к. ее значения указывают на вид формулы.

4) Вычислить (построчно) значение каждой подформулы и формулы в целом, используя данное выше табличное определение пропозициональных связок.

Например, переводом на язык КЛВ сложного высказывания «Если Ромео любит Джульетту, а Джульетта любит Ромео, то неправда, что по крайней мере одни из них не любит другого» будет формула (А ˄ В) É (А ˅ В). Таблица истинности для этой формулы выглядит следующем образом:

А	В	А	В	А ˄ В	А ˅ В	(А˅ В)	(А˄ В) É (А ˅ В)

 

В этой таблице всего четыре строки, поскольку формула формула содержит две переменные – А и. Первые два столбца задают все возможные комбинации совместной истинности и ложности этих переменных, а следующие пять столбцов показывают значение каждой подформулы в той или иной строчке. Последний столбец показывает значение всей формулы в целом. Согласно этим значениям формула является тождественно истинной или общезначимой, т.к. она принимает значение «истина» при любых значениях истинности входящих в нее пропозициональных переменных. Формула, принимающая значение «ложь» при любых значениях истинности входящих в нее пропозициональных переменных, называется тождественно ложной или противоречивой. Формула, принимающая значение «истина» по крайней мере при одном наборе значений входящих в нее пропозициональных переменных, называется логически случайной или выполнимой.

Построение полных таблиц истинности бывает весьма трудоемким процессом, поскольку число строк в таблице увеличивается по указанной выше формуле с увеличением числа пропозициональных переменных: так, при трех переменных строк будет 8, при четырех – 16, при пяти – 32. Поэтому возможно использовать два пути: путь «сжатия» записи полной таблицы или использование метода сокращенных таблиц. Рассмотрим их.

Пусть нам дана формула ((АÉВ) ˄ (В˅С)) É (АÉС). Ясно, что число строк в ней будет 8. Будем заполнять таблицу значениями истинности как переменных, так и полученных результатов значений истинности сложных формул (от простого к сложному), ставя их под соответствующими переменными и логическими операторами. Заметим, что значения истинности переменных в формуле и их сочетания достаточно просто: первая по перечню слева направо переменная получит в данной формуле подряд четыре значения «истинно», четыре значения «ложно», вторая переменная – два «истинно», два «ложно», вновь два «истинно» и два «ложно». Истинностные значения для третьей переменной будут чередоваться. Если, скажем, формула будет содержать четыре переменных, то схема повторится: для первой будет подряд восемь значений «истинно», восемь «ложно», для второй они будут записываться по четыре подряд, для третьей – по два, для четвертой будут просто чередоваться. Такое мнемоническое правило позволяет легко заполнить «входную» часть таблицы. Поэтапно это будет выглядеть следующим образом:

 

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

Второй этап

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

Третий этап

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

Теперь полностью заполним входную часть: под одинаковыми переменными должны стоять одинаковые значения истинности, а, поскольку перед В имеется знак отрицания во второй скобке, то сразу применим операцию отрицания и изменим значение истинности в соответствии с действием оператора отрицания. В итоге получим:

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

Следующим шагом определим значение истинности выражения ((АÉВ) в соответствии с действием оператора импликации. Таблица примет следующий вид:

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

Проделаем ту же операцию для выражения (В˅С). Таблица примет вид:

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

Теперь определим значение истинности посылок, то есть в данной формуле, которая представляет собой импликацию, значение истинности ее антецедента, ((АÉВ) ˄ (В˅С)). Таблица будет выглядеть как

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

Определим значение истинности выражения (АÉВ):

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

Теперь, сравнивая значения истинности всего антецедента и консеквента, получим итоговое

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

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

Вопрос о тождественной истинности (общезначимости) формулы может быть достаточно просто решен сокращенным методом: необходимо подобрать значения переменных формулы так, чтобы она приняла ложное значение. Если это не удается, а именно возникает противоречие (когда некоторая переменная и ее отрицание имеет одинаковое истинностное значение), то формула является тождественно истинной.

Продемонстрируем на примере той же самой формулы метод сокращенных таблиц. По сути он представляет собой прием рассуждения от противного. Правда, если с помощью построения полных таблиц истинности можно определить, какой именно – тождественно-истинной, тождественно-ложной ли случайно истинной – является данная формула, то сокращенные таблицы позволяют ответить на вопрос только о том, является или нет формула тождественно-истинной. Впрочем, как увидим далее, для использования логики высказываний в определении корректности некоторых рассуждений именно и требуется. Итак, предположим, что формула ((АÉВ) ˄ (В˅С)) É (АÉС) не является тождественно-истинной, то есть в итоговом столбце встречается хоть одно значение «ложно». Поскольку формула представляет собой импликацию, это значит, что ((АÉВ) ˄ (В˅С)) истинна, а (АÉС) – ложна. Ложность последней возможна только тогда, когда А истинно, а С ложно. Истинность же конъюнкции ((АÉВ) ˄ (В˅С)) означает, что истинны как ((АÉВ), так и (В˅С). В первую из упомянутых формул подставим истинно значение А, тогда В может принимать значение только «истинно». Во второй формуле (В˅С) С ложно, а сама формула истинна. Дизъюнкция истинна, если истинен по меньшей мере один дизъюнкт; ясно, что истинно (В), тогда В ложно. Получаем противоречие: В одновременно приобретаем взаимоисключающие значения «истинно» и «ложно», что невозможно по определению. Наличие данного противоречия означает, что наше исходное предположение ложно, и данная формула является тождественно-истинной. (Противоречие может быть обнаружено и в каком-либо ином варианте – важно то, что если оно есть, оно непременно будет обнаружено.) Все наше рассуждение может быть записано следующим образом (каждая нижеследующая строка означает шаг рассуждения, хотя на самом деле мы разбираем всего одну строку таблицы):

(	(	А	É	В	)	˄	(		В	˅	С	)	)	É	(	А	É	С	)
				1

 

Замечание. В логике высказываний логические законы представляют собой класс тождественных формул. А в рассуждениях, имеющих форму логических законов, между посылками и заключением устанавливается отношение логического следования. Таким образом, логика высказывания, построенная табличным способом, дает возможность определить правильность (корректность) рассуждения, т.е. наличие в рассуждении отношения логического следования.

Тождественная истинность формулы говорит о наличии логического следования заключения из посылки. Если, применительно к некоторому рассуждению, сделанному на естественно языке, можно сказать, что заключение в нем является логическим следованием из посылок, то говорят, что такое рассуждение является корректным. Понятие корректности используется по отношению к естественноязыковым рассуждениям, а тождественная истинность – к формулам; связывает же их воедино понятие логического следования.

Рассмотрим решение следующей учебной задачи: Определите корректность рассуждения средствами логики высказываний «Если человек говорит неправду, то он заблуждается или сознательно вводит в заблуждение других. Этот человек говорит неправду, но явно не заблуждается. Следовательно, он сознательно вводит в заблуждение других.»

Определим с помощью квадратных скобок пропозициональные переменные, подчеркнем выражения, соответствующие логическим операторам. Получим: «Если [ человек говорит неправду], то [он заблуждается] или [сознательно вводит в заблуждение других]. [Этот человек говорит неправду], но [явно не заблуждается]. Следовательно,[он сознательно вводит в заблуждение других].» Пусть А есть «человек говорит неправду», В – «он заблуждается», С – «сознательно вводит в заблуждение других». При переводе рассуждения в логическую нотацию, посылки рассуждения обычно связываются с помощью оператора конъюнкции, между совокупностью посылок и заключением обычно ставится импликация, по смыслу наиболее точно отражающая переход от посылок к заключению рассуждения. В результате получим формулу следующего вида, отражающую структуру (форму) данного рассуждения: ((АÉ (В˅С)) ˄ (А˄

В)) É С. Построим сокращенную таблицу истинности для данной формулы.

 

 

(

(

А

É

(

В

˅

С

)

)

˄

(

А

˄

В

)

)

É

С

 

Видим противоречие (указано стрелкой). Следовательно, наше предположение было неверно, данная формула является тождественно-истинной (общезначимой). Заключение С логически следует из посылок ((АÉ (В˅С)) ˄ (А˄ В)). Отсюда заключаем, что рассуждение, структура которого была проанализирована средствами логики высказываний, является корректным, q.e.d.