0
0 0 ... 0
A(0, 0, ..., 0)
1
0 0 ... 1
A(0, 0, ..., 1)
. . .
. . .
i
S1 s2 ... sn
A(s1, s2, ..., sn)
. . .
. . .
2n-1
1 1 ... 1
A(1, 1, ..., 1)
Пример. Истинностные значения формулы
Ø(x É y) Ù (x Ú z)
и ее составных частей при всевозможных значениях переменных x, y, z приведены в табл.3.
Таблица 3
x
y
z
x É y
Ø(x É y)
x Ú z
Ø(x É y)Ù(x Ú z)
0
0
0
1
0
0
0
0
0
1
1
0
1
0
0
1
0
1
0
0
0
0
1
1
1
0
1
0
1
0
0
0
1
1
1
1
0
1
0
1
1
1
1
1
0
1
0
1
0
1
1
1
1
0
1
0
Упражнение 1. Доказать, что следующие пары формул определяют совпадающие функции:
а) X Y и Y X, где Î {Ú, Ù} (коммутативность дизъюнкции и конъюнкции);
б) X (Y Z) и (X Y) Z , где Î {Ú, Ù} (ассоциативность дизъюнкции и конъюнкции);
в) X É Y и ØY É Ø X (закон контрапозиции);
г) X Ù (Y Ú Z) и (X Ù Y ) Ú (X Ù Z) (первый закон дистрибутивности);
д) X Ú (Y Ù Z) и (X Ù Y) Ù (X Ù Z) (второй закон дистрибутивности);
е) Ø(X Ù Y) и`X Ú`Y (первый закон Де Моргана);
ж) Ø(X Ú Y) и`X Ù`Y (второй закон Де Моргана);
з) (X ÉY) É X и X (закон Пирса);
и) X Ú Y и `X É Y (выразимость дизъюнкции через импликацию);
к) X Ù Y и Ø(X É ØY) (выразимость конъюнкции через импликацию);
Из последних двух пунктов легко вытекает, что дизъюнкция и конъюнкция могут быть выражены через импликацию. Таким образом, предложенный базис избыточен, но мы используем именно его для большей наглядности.
Из вида логических значений, приведенного в табл.1, вытекает, что верные высказывания суть такие, логические значения которых есть истина не зависимо от значений их переменных. И логически безупречными можно полагать умозаключения, которые сохраняют значение истина, т.е. когда из истинных посылок вытекают истинные заключения. Это дает представление о том, что такое логически правильные высказывания, но не предоставляет правила для того, чтобы определить, как по истинным высказываниям получать новые истинные высказывания.
Для ответа на этот вопрос введем правило вывода modus ponens: формула В есть непосредственное следствие формул А и А É В. Легко проверить, что это правило обладает свойством сохранять истинность заключения при истинности обеих его посылок. Действительно, если формулы А и А É В истинны при некоторых значениях их переменных, то при этих же значениях переменных заключение В также истинно.
В итоге мы обладаем механизмом построения умозаключений для получать новых истинных высказываний (именно - логических следствий) из известных.
Введем следующее определение.
Противоречием будем называть всякую формулу A ÙØA, так как в ней утверждается нечто и его отрицание.
Сформулируем первый результат, который будет использоваться при объяснении многих психологических фактов.
Пусть D есть произвольное множество логических формул. Назовем множество D непротиворечивым, если совокупность всех формул, которые принадлежат D или выводятся из них с помощью правила modus ponens (обозначим такую совокупность C(D)) не содержит противоречия. В противном случае, оно называется противоречивым.
Для нас нагляднее мыслить множество D как систему высказываний, связанную какими-то условиями. Как правило, такие условия вытекают из контекста. Если их объединить (что подразумевает их конъюнкцию), то получим одно высказывание, быть может, бесконечное, для которого также можно представить таблицу истинности, отображающую совокупности значений ее переменных в значения истина, ложь. Если D конечно, то представить такую конъюнкцию не составляет труда; при бесконечном множестве необходимо более богатое воображение. Но в любом случае можно говорить о логической функции (будем также обозначать ее D), которая реализуется этим множеством. Это позволяет нам ввести такое определение.
Множество D высказываний называется совместным, если представляемое им высказывание не тождественно ложное.
Оказывается, что множество высказываний совместно тогда и только тогда, когда оно непротиворечиво.
Поясним, что здесь имеется в виду. Формулы суть идеальные объекты, и на их запись не накладывается никаких ограничений, кроме синтаксических. С другой стороны, представление формулы как отображения с областью значений {истина, ложь} вводит определенный предметный аспект. Действительно, только по виду формулы чаще всего не ясно, является ли она осмысленной, т.е. истинной всегда или иногда, или полностью бессмысленной, т.е. всегда ложной. Приведенный результат связывает непротиворечивость формулы с ее выполнимостью (или реализуемостью), или, по-другому, ее непротиворечивость с осмысленностью в предметном мире: осмысленными являются только непротиворечивые множества, в точности так же, как непротиворечивые множества обладают определенным смыслом. Здесь под смыслом (или по-другому семантикой) формулы понимается реализуемое ею отображение (т.н. логическая функция).