§ 1. Операции над высказываниями

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

Пусть имеются высказывания: «На улице светит солнце», «В классе идут занятия». Из этих простых высказываний можно различными способами построить сложные выска­зывания:

1. На улице светит солнце, и в классе идут занятия.

2. На улице не светит солнце.

3. На улице светит солнце, однако в классе идут за­нятия.

4. В классе идут занятия, а на улице светит солнце.

5. На улице светит солнце, или в классе идут занятия.

6. Или на улице светит солнце, или в классе идут за­нятия.

7. Если на улице светит солнце, то в классе идут за­нятия.

8. Если в классе идут занятия, то на улице светит солнце.

9. На улице не светит солнце, или в классе идут за­нятия.

10. На улице светит солнце тогда и только тогда, когда в классе идут занятия.

Читатель без труда продолжит список сложных выска­зываний, и мы не сомневаемся, что ему удастся получить высказывания, еще более абсурдные, чем 8) или 10). Самый простой способ добиться этого — взять в качестве простых высказываний как можно более далекие друг от друга по смыслу предложения, например: «Семнадцатая страница в книге начинается с буквы „в”», «Наш город стоит на бере­гу Волги». В связи с этим отметим первую особенность алгебры высказываний. В ней допускаются любые грам­матически правильные способы образования сложных вы­сказываний и совершенно игнорируется смысловая характеристика по пучившегося предложения. Любое из приведенных десяти сложных предложений допустимо с точ­ки зрения алгебры высказываний.

В алгебре высказываний интересуются лишь истин­ностью или ложностью (истинностным значением) высказываний. Более точно: в ней ис­следуется вопрос об истинности сложного высказывания в зависимости от истинности входящих в него простых вы­сказываний и с этой точки зрения и исследуются различные логические связки.

Пока что мы не делали различия между «предложения­ми» и «высказываниями». Однако с точки зрения сформу­лированной задачи такое различие удобно провести. Не про каждое предложение можно сказать, истинно оно или лож­но. Примерами являются предложения, выражающие при­казание («Подоиди ко мне!»), сожаление («Если бы я раньше знал. . .»), вопрос («Был ли ты дома?»), поздравления (<-С новым годом!») и т. д. Не останавливаясь на описании этого класса предложений, договоримся, что под высказываниями мы будем понимать предложения, для которых имеет смысл говорить об их истинности или ложности.

Фиксация высказывания («На улице светит солнце») еще не приводит, вообще говоря, к фиксации его истинност­ного значения. Нужно еще фиксировать ситуацию (в дан­ном примере — точное время и место действия). Поэтому точнее надо говорить, что высказывание А истинно (или ложно) в такой-то ситуации. Ситуация может быть однозначно определена в самом высказывании («4 фев­раля 1971 г. в 5 часов 01 минуту по московскому времени была проведена вторая коррекция траектории корабля»). Иногда в алгебре высказываний ограничиваются рассмотре­нием только таких высказываний, но мы этого делать не будем. Существуют высказывания, истинные (соответст­венно ложные) во всех возможных ситуациях. Такие вы­сказывания мы будем называть абсолютно истинными (со­ответственно абсолютно ложными). Высказывания «Волга впадает в Каспийское море», «Через две различные точки евклидовой плоскости проходит единственная прямая»—аб­солютно истинны; «2а=а, где а — положительное число» — абсолютно ложно. Абсолютно истинные и абсолютно лож­ные высказывания будем называть логическими константа­ми. Если ситуация однозначно определена в самом выска­зывании, то оно является логической константой. Теперь мы можем уточнить, что при изучении логических связок мы будем сопоставлять истинностные значения простых высказываний и полученного сложного высказывания в од­ной и той же ситуации. При этом один из главных вопросов, который нас будет интересовать, заключается в том, при каких условиях на простые высказывания логическая связ­ка приводит к абсолютному истинному высказыванию.

Рассмотрим примеры логических связок (операций).

1. Логическая связка, соответствующая союзу «и», на­зывается конъюнкцией и обозначается знаком & *).

Высказывание А & В, называемое конъюнкцией А и В, истинно тогда и только тогда, когда истинны оба высказывания А я В (ср. пример 1). Это обстоятельство мож­но выразить с помощью так называемой истинностной таб­лицы для конъюнкции:

А	в	А & В
И	и	и
И	л	л
л	и	л
л	л	л

*) Часто вместо & употребляется знак д. Отметим также, что конъюнкцию иногда называют логическим умножением.

В этой таблице символом И обозначается истинное выска­зывание, символом Л — ложное. В ней перечислены все­возможные истинностные значения (И и Л) высказываний А и В и соответствующее им истинностное значение выска­зывания А & В. С точки зрения алгебры высказываний ло­гическая связка (операция) конъюнкция полностью опре­деляется приведенной таблицей. Высказывание А & В абсолютно истинно тогда и только тогда, когда абсолютно истинны оба высказывания А и В.

При построении таблицы мы исходили из союза «и». Но мы пришли бы к той же самой истинностной таблице, если бы исходили из союзов «а», «но», «однако», «хотя» и т. п. (ср. примеры 3, 4). Таким образом, хотя соответствующие этим союзам логические связки имеют различные смысловые оттенки, с точки зрения алгебры высказываний они неразли­чимы. Кроме того, связка, соответствующая конъюнкции, осуществляется иногда бессоюзным образом (например: «На улице светит солнце, в классе идут занятия»). Анало­гичное сокращение мы будем ниже (стр. 35) практиковать и по отношению к знаку конъюнкции.

2. Отрицание А высказывания А (см. пример 2) задается таблицей

А	А
И	Л
л	и

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

3. Двуместная логическая операция, соответствующая союзу или», называется дизъюнкцией ¹) (она обозначается знаком V)- Надо иметь в виду, что в обычной речи союз «или» употребляется по крайней мере в двух различных смыслах: неальтернативное (неисключающее) «или» и аль­тернативное (исключающее) «или». В высказываниях перво­го типа утверждается истинность по крайней мере одного из участвующих в нем простых высказываний; во втором случае — в точности одного (здесь иногда используется более точный оборот «или. . . ,или...»). Дизъюнкция соответствует неальтернативному «или»; она задается следующей истинностной таблицей:

А	в	A v в
И	и	и
И	л	и
л	и	и
л	л	л

Абсолютная истинность А \/В означает, что в каждой ситуации хотя бы одно из высказываний А, В истинно.

1. Логическую операцию, соответствующую альтер­нативному «или», мы назовем альтернативной дизъюнк­цией (обозначение: Л ДБ). Составить для нее истинностную таблицу и выразить эту операцию через уже знакомые нам логические операции. ▲

4. Мы будем называть логическую операцию тождест­венной истиной (ложью), если для любых простых вы­сказываний полученное сложное высказывание является абсолютно истинным (абсолютно лож- н ы м). Это равносильно тому, что при любых истинностных значениях простых высказываний сложное высказывание истинно (ложно). Следует уяснить отличие тождественной истины от абсолютной: первая относится к логической опе­рации, вторая — к индивидуальному высказыванию. В сле­дующей задаче приводятся примеры одноместных операций, являющихся тождественной истиной (тождественной ложью).

2. Показать, что операция А\/А есть тождественная истина, а А & А — тождественная ложь. ▲

В рассмотренных нами пока двуместных логических опе­рациях простые высказывания А и В входили симмет­рично (коммутативно: <р (А, В)—<р (В, А)). Сейчас мы рассмотрим операции с несимметричным вхождением про­стых высказываний (это аналогично переходу от сложносочи­ненных предложений к сложноподчиненным).

5. Двуместная логическая операция, соответствующая обороту «если. . то. . .», посредством которого образуются условные предложения, называется импликацией. При этом сложное высказывание «если А, то В» записывается в виде А -*■ В. Простое высказывание А называется посыл­кой импликации, В — ее заключением. Мы приведем вначале истинностную таблицу для импликации, а затем дадим не­которые пояснения.

А	в	А —* В
И	и	и
и	л	л
л	и	и
л	л	и

В случае импликации несоответствие между обычным пониманием истинности сложного высказывания и идеали­зированной точкой зрения алгебры высказываний еще за­метнее, чем для других логических операций. Главное от­личие состоит в том, что при учете смыслового содержания высказываний (а не только значения истинности) оборот «если. . ., то. . .» подразумевает причинную связь между посылкой и заключением. Сточки же зрения алгебры высказываний истинность импликации в некоторой ситуации означает лишь, что если в этой ситуации истинна посылка, то истинно заключение. В результате истинными могут ока­заться импликации «Если в доме пять этажей, то в квартире номер три проживает Иванов», «Если в Воронеже идет дождь, то книга серого цвета», а то и еще более «удивительные» высказывания. Более внимательный анализ показывает, что в нашей обычной речи мы не ставим вопрос об истинности высказывания «из А следует В» для какой-то конкретной ситуации, интересу ясь лишь вопросом об абсолютной истинности А -*■ В, и лишь в этом случае говорим, что В есть следствие А. С этой точки зрения вид истинност­ной таблицы для импликации совершенно естествен. Дейст­вительно, в силу нашего интуитивного представления вы­сказывание А В абсолютно истинно тогда и только тогда, когда в каждой ситуации, в которой высказывание А истинно, истинно В, т. е. не существует ситуации, когда А истинно, а В ложно. С другой стороны, истинност­ная таблица должна быть такова, что в каждой возмож­ной ситуации А -> В истинно. Из сопоставления этих двух фактов следует, что таблица должна иметь указанный выше вид. Отметим одну терминологическую тонкость. Мы обычно говорим «из А не следует В» в том слу­чае, когда высказывание А —+ В не является абсолютно истинным, т. е. А -> В ложно в некоторой ситуации; это не следует путать с абсолютной ложностью А —»- В.

Для иллюстрации отметим, что вопрос об абсолютной истинности импликации решается при доказательстве тео­рем. Действительно, всякая теорема имеет вид импликации А В, у которой в посылке (А) стоит то, «что дано», а в за­ключении (В) то, «что требуется доказать». Обратной теоре­ме отвечает импликация В А; противоположной тео­реме — импликация А-*- В.

Заметим, что чаще принимается более широкое определение обрат­ной теоремы: если (Л&С)->В — прямая теорема, то обратной называется не только теорема В-*(А&С), но и теоремы (В&А)-*С, (В&С)->И (т. е. из «части» посылки и заключения следует другая «часть» посылки). В качестве примера рассмотрим «теорему о трех перпендикулярах»: «Прямая I, принадлежащая плоскости Р и перпендикулярная проекции m прямой п на плоскость Р, перпендикулярна п». Рассмотрим структуру этой теоремы. Обозначим через А высказывание «прямая I принадлежит плоскости Р», через В — «прямая m является проекцией прямой я на плоскость Р», через С — «прямая / перпендикулярна т», через D — «прямая I перпендикулярна п». Теорема имеет вид высказывания ((A&B)&C)-*D. Ясно, что импликация D—>((Л&В)&С), вообще говоря, ложна, т. е. не является абсолютно истинной. Однако абсолютно истинно высказывание ((AkB)kD)~*C: «Прямая I, принадлежащая плоскости Р и перпендикулярная прямой п, перпендикулярна проекции m прямой п на плоскость Р». Эту теорему и называют обычно теоремой, обратной к теореме о трех перпендикулярах.

При доказательстве теоремы мы в предположении истинности посылки устанавливаем истинность заключения, т. е. исключаем един­ственный случай (см. истинностную таблицу для А—>В), когда имплика­ция может быть ложной, и доказываем тем самым абсолютную истинность импликации А—»В, отвечающей теореме. При этом следует различать истинность импликации, которая имеет место всегда (вне зависимости от истинности посылки), если теорема доказана, от истинности заключе­ния, которую в этом случае можно утверждать, лишь если истинна по­сылка. В случае же ложной посылки из справедливости теоремы никаких выводов об истинности или ложности заключения делать нельзя. Об­ратно, из ложности В следует ложность А, а из истинности В никаких выводов об А сделать нельзя.

Непонимание этих фактов приводит к ошибкам при применении теорем. Пусть доказанной теореме отвечает абсолютно истинная имплн- кация А-¹В. Правильное ее применение состоит в том, что если в какой- то ситуации А справедливо, то делается вывод о справедливости В. Например, возьмем теорему: «Если четырехугольник — прямоугольник, то его диагонали равны» *). Для всякого квадрата посылка истинна; значит, в квадрате диагонали равны. Распространенная ошибка в мате­матических рассуждениях состоит в том, что к высказыванию А, истин­ность которого не установлена, применяется правильная теорема А-*В и из истинности предложения В делается вывод об истинности А. Оши­бочность такого рассуждения следует из третьей строки истинностной таблицы Л—>В (в истинной импликации с истинным заключением может быть ложной посылка). Приведем пример такого неправильного рассуж­дения. Высказывание А: «Число 6 делится на 4»; А-*В: «Если число де­лится на 4, то оно делится на 2». Имеем: А->В — истинная теорема, В — истинное высказывание, однако нельзя делать вывод об истинно­сти А. О возникающей здесь ситуации можно сказать еще так: «Из неверного утверждения верными методами можно получить верный ре­зультат» (но нельзя, конечно, верными методами получить из верного утверждения неверный результат!). Другой пример, в котором часто допускаются ошибки из-за непонимания свойств импликаций,— это исследование решений уравнений (и еще в большей степени неравенств). Пусть имеется уравнение Р(х)=0, и уравнение Q(x)=0 является его следствием, т. е. истинна импликация «если х₀— корень уравнения Р{х)=0, то х_п— корень уравнения Q(x)— О» (А->В). Если мы нашли кор­ни уравнения Q(x)=0, то среди них содержатся все корни уравнения Р(х)—0 (из истинности А следует истинность В), но среди корней второго уравнения могут быть посторонние, т. е. не являющиеся корнями пер­вого (из истинности В не следует, вообще говоря, истинность А). Таким образом, корни уравнения Q{x)—0 нужно подвергнуть проверке, прежде чем сделать вывод о том, что они являются корнями уравнения Р(х)= 0. Обратно, если нам известны все корни первого уравнения, то это не означает, что мы знаем все корни второго уравнения: переход от урав­нения Q(x)=0 к уравнению Р(х)=0 может сопровождаться потерей кор­ней. Посторонних корней не возникает в первом случае и не произойдет потери корней во втором случае тогда и только тогда, когда наряду с указанной выше импликацией А-*В истинна импликация В-*А. В этом случае уравнения называются равносильными; множества корней таких уравнений совпадают.

3. Показать, что логические связки В -> А; (Л&В) -+- -»-Л; (Л&Б)->£; (Л&В)->-А, где А — фиксированное абсолютно ложное высказывание, имеют ту же истинност­ную таблицу, что и импликация А —*- В. ▲

В силу этой задачи вместо доказательства абсолютной истинности А-*В можно доказать абсолютную истинность одного из четырех перечисленных высказываний. Возьмем, например, импликацию В-*А. Нужно в предположении истинности В доказать истинность А. Но это есть простейший способ доказательства от противного теоремы А->В. Мы предполагаем противное тому, что требуется доказать, и по- лучаеи противоречие с тем, что дано. При доказательстве при помощи остальных трех связок мы предполагаем не только^ противное тому, что требуется доказать, но и также то, что дано (А8сВ). Тогда для доказа­тельства теоремы А-+В достаточно или прийти к противоречию с тем, что дано (А), или вывести то, что требуется доказать (В), или, наконец, получить любое абсолютно ложное высказывание (Л). В качестве по­следнего в силу задачи 1.2 достаточно вывести какое-нибудь высказы­вание С и его отрицание С, так как тогда должно быть истинным выска­зывание С & С. Последний способ доказательства является в некотором смысле наиболее общим способом доказательства от противного.

4. Показать, что абсолютная истинность имплика­ции А-+В равносильна тому, что истинность В является необходимым признаком истинности А, а истинность А — достаточным признаком истинности В. ▲

В результате абсолютную истинность импликации А-у В можно принять за определение необходимости В для А (соответственно, доста­точности А для В).

6. В качестве последнего примера логической операции рассмотрим связку, называемую эквивалентностью ¹) (обо­значение: ~). Она соответствует оборотам типа «тогда и только тогда, когда...», «для того чтобы..., необходимо и достаточно...» и др. Приведем истинностную таблицу для эквивалентности:

А	в	А~ в
И	И	И
и	л	л
л	и	л
л	л	и

К эквивалентности в той же мере, что и к импликации, относится замечание о том, что ее использование в алгебре высказываний не учитывает смысловое содержание выска­зываний. И здесь наши интуитивные представления об эк­вивалентности относятся к случаю, когда сложное выска­зывание А~В является абсолютно истинным (только в этом случае мы привыкли говорить «А и В эквивалентны»).

В дальнейшем мы будем иногда говорить «Л и В а б со­лю т н о эквивалентны», если высказывание Л~£ абсо­лютно истинно.

5. Показать, что ту же истинностную таблицу, что и эквивалентность, имеет логическая операция (Л -*• В)& &(В Л). ▲

Из задачи 1.5 и истинностной таблицы для конъюнкции следует, что абсолютная истинность эквивалентности равно­сильна абсолютной истинности импликаций Л -> В и В -*■ Л, т. е. что в этом случае справедливы и прямая теорема Л —у- В и обратная В Л. Чтобы доказать абсолютную истинность Л ~ В, нужно показать, что истинность Л вле­чет истинность В и, обратно, истинность В влечет истинность Л (во всех ситуациях Л и В или одновременно истинны, или одновременно ложны). Если эквивалентность А~В абсо­лютно истинна, то Л является необходимым и достаточным условием для В и обратно.

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

6. Сколько имеется различных (т. е. отличающихся истинностными таблицами) двуместных логических опера­ций? ▲

7. Сколько имеется различных коммутативных дву­местных логических операций? Выразить их через уже вве­денные операции. ▲

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

Естественно считать равносильными формулы, которым со­ответствуют одинаковые истинностные таблицы. Дадим точное определение:

Определение 1.1¹). Пусть §( и 23 — две фор­мулы алгебры высказываний, а А_и . ., А_п— набор про­стых высказываний, входящих по крайней мере в одну из формул 51, 23. Формулы §( и 23 называются равносиль­ными, если при всех значениях истинности А_и . . ., А_п зна­чения истинности §'( и 23 совпадают. Равносильность St и 23 обозначается посредством обычного знака равенства: §1 = 23.

8. Доказать следующие равносильности: а) А \/А — А; б) (АуА)&В=В; в) А \/А^В\/В; г) А \/(А & В)=А. А

Из определения видно, что наборы простых высказыва­ний, входящих в равносильные формулы §( и 23, могут быть различными. В этом случае простые высказывания, входящие лишь в одну из формул, входят в нее фиктивным образом, т. е. истинность этой формулы не зависит от ис­тинности этих простых высказываний.

9. Попытайтесь аккуратно определить, что означает утверждение, что простое высказывание В входит в формулу

существенно (нефиктивно). ▲

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

10. В каком случае простое высказывание В входит в формулу §1 фиктивно? ▲

Теперь мы можем аккуратно доказать упомянутое выше утверждение:

11. Если §1 = 23 и простое высказывание А входит в формулу §(, но не входит в 23, то оно входит в §1 фик­тивно. ▲

12. Доказать, что формулы §1 и 23 равносильны тогда и только тогда, когда формула 93 ~ $ — тождественная истина (см. п. 4). ▲

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

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

Приведем несколько задач такого рода.

13. Выразить (т. е. найти равносильные формулы) все основные операции через дизъюнкцию, конъюнкцию и отрицание. ▲

14. Выразить все основные операции через конъюнк­цию и отрицание; через дизъюнкцию и отрицание. А

15. Выразить все основные операции через имплика­цию и отрицание. ▲

16. Назовем операциями Шеффера следующие опера­ции:

ф(Л, В) = А\/В —А&В; я1)(Л, В) = А& В = А\/ В.

Показать, что через каждую из них выражаются все основ­ные операции. ▲

17. Выразить А\/В через А В. А

Отметим, что возможны такие парадоксальные конструкции слож­ных высказываний, для которых не удается найти истинностные значе­ния (хотя они и выражаются, в отличие от примеров, упомянутых в на­чале параграфа, повествовательными предложениями). Один из возмож­ных примеров: «То, что я сейчас говорю, неправда». Ясно, что попытки считать это высказывание истинным или ложным одинаково приводят к противоречию. Другой пример, построенный на той же идее: «На одной стороне листа бумаги написано, что на обратной стороне написана прав­да, а на другой стороне написано, что на обратной стороне написана ложь». Весьма распространены различные задачи-шутки такого типа. Читателю, вероятно, известна история про царя, который за правду отрубал чужеземцу голову, а за ложь — вешал, и про то, в какое безвыходное положение поставил царя путешественник, заявивший, что его повесят. Причина возникающих парадоксов состоит в том, что здесь высказывание в целом неявно «содержится в самом себе» как простое высказывание и при определении значения истинности выска­зывания уже нужно знать заранее это значение. Такого рода ситуации невозможны для сложных высказываний, являющихся формулами при принятой нами индуктивной конструкции формул с помощью основных логических операций.

Сложные высказывания, являющиеся формулами, стро­ятся при помощи введенных нами пяти основных операций. Иногда используется какой-либо другой список основных операций. В любом случае возникает существенный вопрос: сколь велико множество логических связок ¹), которые можно построить, комбинируя эти основные операции. Ока­зывается, что любую логическую операцию можно выразить через основные операции (с точностью до равносильности); более того, для этого даже достаточно дизъюнкции, конъ­юнкции и отрицания. В силу же задачи 1.14 можно огра­ничиться дизъюнкцией и отрицанием или конъюнкцией и отрицанием.

Пусть имеется некоторая логическая операция 81 над простыми высказываниями А_г, . . А_п. Операция 91 с точ­ностью до равносильности характеризуется истинностной таблицей. Для определенности возьмем некоторую конкрет­ную операцию над тремя простыми высказываниями:

Л,	Л*	А»	а
И	и	л	И
И	л	И	и
л	л	и	и
л	л	л	и
и	И	и	л
л	И	и	л
л	И	л	л
и	л	л	л

Таблицу для 9( мы специально записали так, чтобы вначале шли строчки, для которых 31 истинно. Тогда операцию, имеющую данную истинностную таблицу, можно получить, просто перечисляя ситуации, в которых высказывание SI истинно (мысленно произносите вместо &, V» названия логических связок: «и», «или», «не»):

(Л_х& А ₂& Л₃) V (Л_х& ЛД Л₃) V (Л_х& Л ₂& Л ₃) V ( Л_х& Л ₂& Л ₃).

18. Проверить, что построенная операция действи­тельно имеет заданную истинностную таблицу. ▲

19. Обобщить приведенную конструкцию на случай произвольных логических операций §1. ▲

Конструкция, полученная при решении задачи 1.19, называется совершенной дизъюнктивной нормальной формой (сокращенно: СДНФ). Мы будем более подробно говорить о ней в следующем параграфе.

Логическую операцию по таблице можно строить, ис­ходя не только из тех строчек, в которых SX истинна, но и из тех, в которых S1 ложна. Здесь надо исключить те воз­можности, для которых §1 ложна:

(X,v ад/л;) & (л^ лд/л;) & (лд лд/ л₃)

&(л;ул_аул₃)

(здесь опять-таки удобно вместо &, V. мысленно назы­вать соответствующие связки).

20. Проверить, что построенная операция имеет за­данную истинностную таблицу. ▲

21. Обобщить приведенную конструкцию на случай произвольных связок 21. ▲

Конструкция из решения задачи 1.21 называется со­вершенной конъюнктивной нормальной формой (сокращенно СКНФ).

22. Найти СДНФ и СКНФ для основных логических операций. ▲

Простейшие факты из алгебры высказываний часто по­могают при решении элементарных логических задач. Мы приведем здесь лишь один пример такого рода задачи.

23. Путешественник находится в одном из городов А или Б, но в каком именно — ему неизвестно. Он задает собеседнику один вопрос, на который может получить от­вет «да» или «нет», причем ответ его собеседника может являться правдой или ложью (чем именно, ему тоже неиз­вестно). Придумать вопрос, по ответу на который можно безошибочно судить, в каком городе находится путешест­венник. ▲