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

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

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

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

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

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

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

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

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

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

 

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

Второй этап

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

Третий этап

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

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

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

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

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

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

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

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

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

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

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

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

(

(

А

É

В

)

˄

(

В

˅

С

)

)

É

(

А

É

С

)

 

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

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

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

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

 

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

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

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

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

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

 

 

(

(

А

É

(

В

˅

С

)

)

˄

(

А

˄

В

)

)

É

С

 

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

Формализация логики высказываний методом аналитических таблиц. Метод аналитических таблиц является еще одной разрешающей процедурой. По существу, она представляет собой некоторое уточнение указанного выше сокращенного метода установления общезначимости формул. Поиск обоснования общезначимости формулы осуществляется по определенным правилам редукции и начинается с предположения, что формула не общезначима. Это предположение ведет к противоречию, если формула на самом деле общезначима. Аналитические таблицы на основании рассуждения от противного позволяют найти модель с конечной областью, в которой формула опровергается, если она общезначима.

Правила редукции.

Ù:

А Ù В

~(Ù)®:

~(А Ù В)

Ú:

А Ú В

~(Ú):

~(А Ú В)

~(~):

~~А

А, В

~А | ~В

А | В

~А, ~В

А

 

É:	АÉ В			~(É):	~(АÉ В)
	~А | В				А, ~В

 

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

Определение 1 (аналитической таблицы). Аналитической таблицей называется конечная или бесконечная последовательность строк С₁, …С_к, … списков формул такая, что каждая последующая строка получается из предыдущей применением правила редукции.

Замечание. Отметим, что если мы применяем правило редукции с ветвлением, то мы получаем два списка формул.

Определение 2 (замкнутого списка формул). Список формул называется замкнутым, если в списке встречается некоторая формула и ее отрицание, т.е. А и ~А (противоречие).

Определение 3 (завершенного списка). Список формул называется завершенным, если к формулам этого списка невозможно применять правила редукции, т.е в списке встречаются атомарные формулы или отрицание атомарных формул.

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

Определение 5 (завершенной таблицы). Аналитическая таблица называется завершенной, если она замкнута или имеет завершенные списки формул.

Определение 6 (общезначимой формулы в терминах аналитической таблицы). Формула А называется общезначимой, если ее аналитическая таблица замкнута.

Замечание. Завершенный список или завершенная таблица не обязательно замкнута, т.е. может быть замкнутой, но не являться противоречивой. Достаточно построить аналитическую таблицу для выполнимой формулы, чтобы в этом убедиться.