Построение таблиц истинности для формул оялв как разрешающая процедура для ЛВ

Поскольку в ЛВ не накладываются ограничения на длину формул, то очевидно, что ЛВ имеет дело с бесконечным множеством формул. Отсюда следует, что в ЛВ имеется бесконечное множество законов.

Однако это обстоятельство не должно вызывать умонастроение скептицизма у лиц, изучающих ЛВ, в том смысле, что полностью ЛВ познать нельзя, так как она содержит бесконечное множество законов, ведь бесконечное множество законов нельзя обозреть.

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

В ЛВ существует несколько разрешающих процедур. Это и приведение формулы к определённому нормальному виду (приведение формул к конъюнктивной нормальной либо дизъюнктивной нормальной форме), и, наконец, построение таблиц истинности для формул.

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

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

Выписывание всех подформул данной формулы осуществляется справа налево по следующему принципу. Сначала на правой стороне формата бумажного листа выписывается анализируемая формула, слева от неё проводится первая вертикальная линия, намечающая столбцы таблицы, затем формула и пространство для выписывания подформул подчеркиваются справа налево горизонтальной линией, которая намечает строки таблицы. Далее анализируется структура формулы с целью нахождения в ней главного логического союза. Главным логическим союзом формулы является логический союз, который введен в формулу на последнем шаге её построения. При этом возможны следующие пути выписывания подформул. Если главнымлогическим союзом окажется «» (отрицание), то первая подформула есть выражение, стоящее после знака отрицания. Если формула не имеет отрицания в качестве главного логического союза, то находим в ней главный бинарный логический союз. Бинарные союзы делят подформулу на левую и правую части, т.е. левую и правую подформулы. Для удобства вычисления истинностного значения всей формулы сначала выписывается в качестве первой подформулы правая часть анализируемой формулы, а затем – левая. Эта процедура продолжается до тех пор, пока разложение формулы на подформулы закончится выписыванием во входных столбцах таблицы всех пропозициональных переменных, входящих в формулу в качествеэлементарных подформул.

После этого по формуле К_с = 2ⁿ определяется количество строк в таблице, где n – число различных пропозициональных переменных, входящих в формулу; выбор в качестве основания степени числа 2 объясняется тем, что ЛВ является двузначной логикой, т.е. в ней любое высказывание может быть либо истинным, либо ложным. При этом нужно отличать пропозициональную переменную от её вхождений в формулу. Так, формула (p p) имеет одну пропозициональную переменную «p» и её два вхождения в подформулу p p, т.е. левое и правое вхождение. Поэтому для этой формулы показатель степень n равен 1, т. е. n = 1. Это означает, что таблица истинности для данной формулы имеет глубину в две строки.

 

Таблица истинности для (p p).

p	p	p p	(p p)
И Л	Л И	Л Л	И И

 

Таблица показывает, что данная формула является тождественно-истинной и, следовательно, является законом ЛВ. Как мы уже видели выше (см. раздел 2.1. §2 Главы 4), эта формула имеет прочтение «Неверно, что p и не-p» и представляет закон противоречия.

Понятно, что чем бòльшее число различных пропозициональных переменных входит в формулу, тем бòльшую глубину она имеет. При этом глубина таблицы нарастает по экспоненте.

Так, для формулы с двумя различными пропозициональными переменными, например p, q, таблица истинности будет иметь 4 строки, для формулы с переменными p, q, r – 8 строк, для формулы с четырьмя переменными – 16 строк, с пятью – 32 строки, с шестью – 64 строки, с семью – 128 строк. Очевидно, что построение таблицы с 32 строками представляет уже техническую трудность, которая нарастает по мере увеличения числа различных пропозициональных переменных. Поэтому для теоретической части ЛВ применение этого метода имеет принципиальное техническое ограничение. Однако для практической части ЛВ это ограничение снимается: в ней, как мы уже отмечали выше, мы будем иметь дело с формулами, содержащими не более 4 различных пропозициональных переменных, так что таблица истинности в 16 строк легко строится, хорошо обозрима и, следовательно, табличный метод вычисления истинностного значения формул вполне адекватен для практической части ЛВ.

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

Во избежание этих случаев следует применять метод систематического приписывания наборов истинностных значений для пропозициональных переменных. Так, для формулы с переменными p, q, r мы имеем 2³ строк, т. е. 8 строк в таблице. Чтобы систематически перебрать все сочетания и перестановки по истине и лжи в 8 строках таблицы, нужно в столбец для p приписать 4 истины и 4 лжи, для q чередовать парами истину и ложь, а для r последовательно чередовать истину и ложь. Соответственно для четырех переменных – p, q, r, s имеем 2⁴ строк, т. е. 16 строк. Тогда для p истину и ложь чередуем восьмерками, для q – четверками, для r – парами, а для s – последовательно чередуем истину и ложь на глубину таблицы в 16 строк.

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

Таблица истинности нейтральной формулы

 

p	q	p q	q	(p q) q
И И Л Л	И Л И Л	И И И Л	И Л И Л	И Л И И

 

Таблица истинности для закона

«удаление конъюнкции»

 

p	q	p q	q	(p q) q
И И Л Л	И Л И Л	И Л Л Л	И Л И Л	И И И И

 

Таблица истинности для закона

«введение дизъюнкции»

 

p	q	p q	p (p q)
И И Л Л	И Л И Л	И И И Л	И И И И

 

Таблица истинности

для закона «простая конструктивная дилемма»

 

p	q	p q	p r	q r	(p q) (p r) (q r)	r	((p q) (p r) (q r)) r
И И И И Л Л Л Л	И И Л Л И И Л Л	И И И И И И Л Л	И Л И Л И И И И	И Л И И И Л И И	И Л И Л И Л Л Л	И Л И Л И Л И И	И И И И И И И И

 

Таблица истинности

для закона «Сложная конструктивная дилемма»

 

p	q	r	s	p q	r s	p r	p r	q s	((p q) (r s) (p r) (q s)
И И И И И И И И Л Л Л Л Л Л Л Л	И И И И Л Л Л Л И И И И Л Л Л Л	И И Л Л И И Л Л И И Л Л И И Л Л	И Л И Л И Л И Л И Л И Л И Л И Л	И И И И Л Л Л Л И И И И И И И И	И Л И И И Л И И И Л И И И Л И И	И И И И И И И И И И Л Л И И Л Л	И Л И И Л Л Л Л И Л Л Л И Л Л Л	И И И И И Л И Л И И И И И Л И Л	И И И И И И И И И И И И И И И И