12. Исчисление высказываний. Общезначимость

Изложенное в предыдущих параграфах предназначено для того чтобы дать представление о характере исчисления высказываний как анализа логических связей между предложениями, зависящих исключительно от построения новых предложений из составляющих с помощью сентенциональных связок. Условия для такого анализа включают наличие исходного множества предложений («простых предложений») и два следующих допущения:

1) Каждое простое предложение есть высказывание, т. е. простому предложению можно приписать истинностное значение.

2) Каждое из рассматриваемых предложений составляется из простых с помощью сентенциональных связок и при данных истинностных значениях этих простых предложений получает истинностное значение в соответствии с приведенными выше истинностными таблицами для отрицания, конъюнкции и т. д.

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

О простых формулах, входящих в составную, говорят, что они содержатся в ней, и называют их ее простыми компонентами. Чтобы недвусмысленно записать составную формулу, применяют скобки. Однако, чтобы избежать чрезмерного числа скобок, мы будем пользоваться введенными ранее условными соглашениями.

В классическом исчислении высказываний, — а только его мы и рассматриваем,— принимается, что каждой простой формуле сопоставляется один элемент из {Т, F}. Далее принимается, что не имеет значения, какое из истинностных значений, Т или F, приписывается данной простой формуле. Этим достигаются наибольшее разнообразие и гибкость использования формул — истинностные значения можно приписывать в соответствии с конкретными условиями. Истинностное значение составной формулы определяется индуктивным способом в соответствии с приводимыми ниже таблицами.

Рис.1

Примеры А

1. Если простыми компонентами формулы А служат Р1, Р2,....,.РN,

То определение истинностного значения формулы А по истинностным значениям компонентов Р1, Р2,....,.РN можно представить в виде таблицы, как было описано выше. Такая таблица состоит из 2n строк, каждая из которых изображает одно из возможных распределений Т и F, приписываемых компонентам Р1, Р2,....,.РN .

2. Истинностная функция есть функция, определенная на VN со значениями в V, где V = {T, F} и N ≥ 1. Иными словами, истинностная функция есть функция от П аргументов, причем каждый аргумент может принимать значение Т или F и сама функция имеет значение Т или F. Мы будем обозначать истинностные функции символами

И т. д.

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

Самоочевидно; оно указывает на функцию, полученную из истинностных функций F с N аргументами и G с M аргументами. Мы будем говорить об этой функции, что она получена подстановкой функции G вместо I - той переменной в F. Ясно, что такие функции, составленные из истинностных функций, снова являются истинностными функциями.

Другой подход к исчислению высказываний можно получить, пользуясь истинностными функциями. Существует различных истинностных функций от П переменных. Из четырех, соответствующих N = 1, ту, которая имеет значение F при Т и Т при F, мы будем обозначать ~Р. Из шестнадцати функций истинности, соответствующих N = 2, мы выделяем четыре. Их определения и обозначения даны в следующей таблице:

Рис.2

Ясно, что мы просто подражаем здесь символам и истинностным таблицам конъюнкции, дизъюнкции и т. д. Наружное расположение символа в этих обозначениях кажется неестественным. Для упрощения мы будем в большинстве случаев применять привычное внутреннее расположение [например, РQ вместо (Р, Q)].

Везде далее мы ограничим употребление термина «истинностная функция» тем, что будем относить его только к элементам множества J, которому дается следующее индуктивное определение:

(I) Каждая из функций есть элемент множества J.

(II) Если FJ, то элементом множества J будет и функция, полученная подстановкой функции F вместо одной из переменных в любую из функций, перечисленных в (I).

(III) Функция является элементом множества J тогда и только тогда, когда она входит в J на основании (I) и (II).

Следующие выражения представляют собой примеры истинностных функций:

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

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

|= A

Для обозначения того, что «А общезначима» или «А есть тавтология». Представляет ли собой формула А тавтологию или нет, можно определить, рассмотрев ее истинностную таблицу. Если простые компоненты, входящие в А, суть Р1, Р2,....,.РN,То А представляет собой тавтологию тогда и только тогда, когда ее истинностное значение есть Т при каждом из 2n приписанных Р1, Р2,....,.РN распределений значений Т и F. Например, Р → Р и Р(Р→Q)→Q являются тавтологиями, тогда как Р→(Q→R) — не тавтология. Этот вывод основывается на рассмотрении помещенных ниже таблиц I, II и III.

Определение общезначимости дает нам механический способ для решения того, общезначима ли данная формула, путем вычисления и рассмотрения истинностной таблицы. Хотя такой метод может быть утомительным, но его всегда можно применить для исследования общезначимости предложенной формулы. Но ясно, что это непрактичный путь для обнаружения тавтологий. Такое положение привело к разработке правил образования тавтологий из тавтологий. Зная ограниченное число простых тавтологий и несколько таких правил, можно вывести большое число различных общезначимых формул. Мы сейчас выведем несколько таких правил, а затем дополним их списком удобных для использования тавтологий.

Теорема 2.1. Пусть В есть некоторая формула, а В* — формула, получаемая из В подстановкой формулы А вместо простого компонента Р везде, где он встречается в В. Тогда, если |=В, то |=B*.

Доказательство. Для произвольного распределения истинностных значений, приписываемых простым компонентам в В*, получаются значение V(А) формулы А и значение V(В*) формулы В*. Но V(B*) = V(B), где V(В) — истинностное значение формулы В для данных истинностных значений, приписываемых ее простым компонентам, включая и значение V(А) для Р. Если формула В общезначима, то V(B), а следовательно, и V(B*) всегда есть Т. Следовательно, если формула В общезначима, то общезначима и формула В*.

Примеры В

I. Из таблицы IV (см. ниже) вытекает |= Следовательно, на основании теоремы 2.1 |= Сказанное можно пояснить, если нужно, подвергнув результаты прямой проверке (табл. V) и пользуясь при этом тем же рассуждением, что и в доказательстве теоремы 2.1. Чтобы пояснить зависимость между таблицей V и таблицей IV, рассмотрим выделенную в таблице V строку.

Сначала в таблицу внесли (в двух местах) значение F для , так как R было приписано значение Т, а S — значение F. Затем дважды вписали приписываемое Q значение Т. Остальная часть вычисления представляет собой повторение того, что помещено в третьей строке таблицы IV после того, как были внесены подчеркнутые в ней истинностные ЗначеНия.

< Предыдущая		Следующая >