4. Пропозициональная теория
В третьих, определим некоторое подмножество Т языка L. Для этого необходимо вспомнить, что использованные буквы – не только символы, но и обозначения для обычных булевых операций (хотя и нестандартные).
Определение 1.2. (1) Пусть . Слово u называется тавтологией, если булева функция, реализуемая соответствующей формулой, тождественно равна 1.
(2) Множество всех тавтологий обозначим буквой Т.
(3) Пара
,
а также (менее точно) множество Т,
называется пропозициональной
теорией.
Замечание. Описания, аналогичные определению 1.2, называются семантическими, то есть – «основанными на смысле».
Повторимся. Множество L есть множество формул, т.е. осмысленных выражений, а множество Т – множество теорем (теория), истинных осмысленных утверждений. Основной вопрос, рассматриваемый в описанном контексте, – вопрос принадлежности некоторого элемента языка L языку Т, то есть – об истинности некоторого осмысленного утверждения.
В данном случае
этот вопрос тривиально решается при
помощи составления таблицы истинности.
Причина, по которой можно составить
таблицу истинности, проста, но заслуживает
того, чтобы её сформулировали: множество
Ω
является очень большим и сложно
устроенным, но про его элементы нам
требуется знать отнюдь не всё, достаточно
только знать, истинно ли некоторое
высказывание или оно ложно. Поэтому
можно отождествить все истинные
высказывания, равно как и все ложные, и
вместо плохого множества Ω
рассмотреть хорошее и простое множество
.
Следовательно,
таблицу истинности сложного высказывания,
зависящего от n
простых (кстати, не вполне ясно, что это
такое ),
можно составить перебором всего лишь
возможных наборов аргументов. На каждом
наборе аргументов вычисление проводится
непосредственно, притом – чисто
«грамматическими» средствами (далее
мы будем называть такие вычисления
«синтаксическими»). Поэтому можно
сказать, что существует алгоритм проверки
того, является ли слово u
языка L
также словом языка Т.
Пример.
Покажем, что уже рассмотренная формула
не есть тавтология. Рассмотрим набор
значений переменных
,
,
.
Проведём непосредственное вычисление:
.
Формула не является тавтологией, так как на одном, по меньшей мере, наборе аргументов принимает значение 0.
Естественно, соответствующий набор аргументов для любой рассматриваемой формулы, если он существует, не угадывается, а находится в процессе полного перебора (который определённо закончится в некоторый момент). Совершенно очевидно, что для любой осмысленной формулы соответствующие вычисления происходят аналогично и не могут «не получиться». Как раз это и означает, что существует алгоритм проверки того, является ли некоторая формула тавтологией.
В подобных случаях говорят, что теория Т разрешима. Итак, имеет место теорема:
Теорема 1.2. Пропозициональная теория разрешима.
QED
Стоит отметить, что разрешима далеко не любая теория. Причиной разрешимости конкретно пропозициональной теории является её крайняя простота.
5. Общая картина
Какое место в общей картине занимают рассмотренные объекты? В рассматриваемой модели они играют роль реального мира, в котором есть вещи мыслимые, но неизвестно, верные ли (язык L), а есть – «правда жизни» (язык Т). Теории, заданные ссылкой на «объективную реальность», называются семантическими. В следующем параграфе будет сформулировано понятие, играющее в рассматриваемой модели роль мышления.