12. Отношение логического следования и его связь с общезначимостью

Рассмотрим истинностные таблицы формул P Q и P Q (табл. 1.11). Из них видно, что при всех

Таблица 5

P	Q	P Q	P Q
И	И	Л	Л
И	Л	И	И
Л	И	И	И
Л	Л	Л	И

наборах значений Р и Q, при которых формула P Q принимает значение И (вторая и третья строки), это же значение имеет и формула P Q. В таких случаях говорят, что из P Q логически следует P Q.

Определение 12. Из формулы А (логически) сле­дует формула В, если по крайней мере при всех тех набо­рах значений атомов, входящих в А или В, при которых формула А имеет значение И, формула В также имеет значение И.

Следование формулы В из формулы А обозначается А |=В.

По установленному выше P Q|= P Q

Если А |=В, то А называется посылкой, В — заклю­чением.

Следование P Q|= P Q обратное рассмотрен­ному следованию, неверно, так как при (Р, Q)=(Л, Л) формула P Q имеет значение И, а формула P Q — значение Л. Если из А не следует В, то пишут А|=В. Значит, P Q|= P Q .

Обобщим определение 1.16 на случай п посылок.

Определение 13. Из формул А₁, ...., А_п следует фор­мула В, если формула В имеет значение И по крайней мере при всех тех наборах значений атомов, входящих хотя бы в одну из формул А₁, ..., А_n, В, при которых зна­чение И имеют формулы А₁, ..., А_n одновременно.

Использование для обозначения общезначимости и следования одного и того же символа объясняется тем, что между этими понятиями имеется глубокая связь, которая устанавливается следующим предложением.

Предложение 1.10. A₁, ..., А_n-1, А_п|= В тогда и только тогда, когда A₁, ..., А_n-1 |= А_п В. В частности, А |= В то­гда и только тогда, когда |= A B.

Следствия.

а) A₁, ..., А_n-1, А_n|= В тогда и только тогда, когда |= A ₁ (…(А_n-1( A_n B))…).

б) A₁, ..., А_n-1, А_n|= В тогда и только тогда, когда A₁ ... А_n-1 А_n|= В.

Предложение 7.

а) A₁, ..., А_n-1, А_n|= A_i (i=1, …, n).

б) Если A₁, ..., А_n-1, А_n|= В₁, …, A₁, ..., А_n-1, А_n|= В_k, а B₁, ..., B_k|= C, то A₁, ..., А_n|= C.

Для сокращения записей обозначим Г любое множе­ство формул, возможно пустое.

Предложение 8.

а) Если Г, А |=С и Г, В|= С, то Г, АВ |= С.

б) Если Г |=AB и Г, А |= C и Г, B |= C, то Г|= C

в) Если Г, А |= В и Г, А |= В, Г|=А

13. Применения языка алгебры высказываний

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

Пример 9. Записать формулой алгебры высказываний пред­ложение:

«Числовые выражения, а также выражения с переменными, в которых используются операции сложения, вычитания, умноже­ния, деления и возведения в степень, являются рациональными».

Предложение представляет собой описание понятия рацио­нального выражения. Класс R рациональных выражений, согласно предложению, есть объединение классов С и Р; R=CP, где С — класс числовых выражений, в которых используются операции сложения, вычитания, умножения, деления и возведения в степень, Р — класс выражений с переменными, в которых используются тс же операции.

Итак, всякий элемент х класса R принадлежит либо классу С, либо классу Р. Приведенное разъяснение показывает, что оборот «а также» выражает альтернативную связь. Легко понять, что под­черкнутые запятые и слово «и» выражают дизъюнк­тивную связь. Чтобы убедиться в этом, распишем подробнее пред­ложение:

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

Для записи предложения в виде формулы введем обозна­чения:

Р — А — числовое выражение,

Q — А — выражение с переменными,

R — в выражении А используется операция сложения,

S — в выражении А используется операция вычитания,

Т — в выражении А используется операция умножения,

U — в выражении А используется операция деления,

V — в выражении А используется операция возведения в степень,

W — А — рациональное выражение.

Тогда предложение запишется формулой

W~ (PQ)(PQ)(RSTUV).

В данном примере оборот «X, а также Y» используется в смысле «X или Y, но не X и Y одновременно», который соответствует фор­муле алгебры высказываний (XY)(XY). Истинностная функ­ция, описываемая этой формулой, имеет более краткое обозначение , называетсяальтернативой (строгой дизъюнкцией) и задается табл. 2

Таблица 6

X	Y
И	И	Л
И	Л	И
Л	И	И
Л	Л	Л

Использовав альтернативу, формулу можно переписать короче:

W~()(RSTUV).