1. Логика высказываний

1.1. Высказывания и операции

«Если число π рационально, то π — алгебраическое число. Но оно не алгебраическое. Значит, π не рационально.» Мы не обязаны знать, что такое число π, какие числа называют рациональными и какие алгебраическими, чтобы признать, что это рассуждение правильно — в том смысле, что из двух сформулированных посылок действительно вытекает заключение. Такого рода ситуации — когда некоторое утверждение верно независимо от смысла входящих в него высказываний — составляют предмет логики высказываний.

Такое начало (особенно если учесть, что курс логики входил в программу философского факультета, где также изучалась «диалектическая логика») настораживает, но на самом деле наши рассмотрения будут иметь вполне точный математический характер, хотя мы начнём с неформальных мотивировок.

Высказывания могут быть истинными и ложными. Например, «2¹⁶ + 1 — простое число» — истинное высказывание, а «2³² + 1 — простое число» — ложное (это число делится на 641). Про высказывание «существует бесконечно много простых p, для которых p+2 — также простое» никто не берётся сказать наверняка, истинно оно или ложно. Заметим, что «x делится на 2» в этом смысле не является высказыванием, пока не сказано, чему равно x; при разных x получаются разные высказывания, одни истинные (при чётном x), другие — ложные (при нечётном x).

Высказывания можно соединять друг с другом с помощью «логических связок». Эти связки имеют довольно странные, но традиционные названия и обозначения (табл. 1.1). Отметим также, что в импликации A ⇒ B высказывание A называют посылкой, или антецедентом импликации, а B — заключением, или консеквентом.

Говорят также, что высказывание имеет истинностное значение И (истина), если оно истинно, или Л (ложь), если оно ложно. Иногда вместо И употребляется буква T (true) или число 1, а вместо Л — буква F (false) или число 0. (С первого взгляда идея произвольным образом выбрать числа 0 и 1 кажется дикой — какая бы польза могла быть от, скажем, сложения истинностных значений? Удивительным образом в последние годы обнаружилось, что такая польза есть, и если оперировать с истиной и ложью как элементами конечного поля, можно получить много неожиданных результатов.

Логические связки позволяют составлять сложные высказывания из простых. При этом истинность составного высказывания определяется истинностью его частей в соответствии с таблицей 1.2.

Те же правила можно изложить словесно. Высказывание A ∧ B истинно, если оба высказывания A и B истинны. Высказывание A∨B истинно, если хотя бы одно из высказываний A и B истинно. Высказывание A → B ложно в единственном случае: если A истинно, а B ложно. Наконец, ¬A истинно в том и только том случае, когда A ложно.

Из всех связок больше всего вопросов вызывает импликация. В самом деле, не очень понятно, почему надо считать, скажем, высказывания «если 2×2 = 5, то 2×2 = 4» и «если 2×2 = 5, то 3×3 = 1» истинными. (Именно так говорят наши таблицы: Л → И = Л → Л = = И.) На самом деле в таком определении есть свой резон. Все согласны, что если число x делится на 4, то оно делится на 2. Это означает, что высказывание

(x делится на 4) → (x делится на 2)

истинно при всех x. Подставим сюда x = 5: обе части ложны, а утверждение в целом истинно. При x = 6 посылка импликации ложна, а заключение истинно, и вся импликация истинна. Наконец, при x = 8 посылка и заключение истинны и импликация в целом истинна. С другой стороны, обратное утверждение (если x делится на 2, то x делится на 4) неверно, и число 2 является контрпримером. При этом посылка импликации истинна, заключение ложно, и сама импликация ложна. Таким образом, если считать, что истинность импликации определяется истинностью её частей (а не наличием между ними каких-то причинно-следственных связей), то все строки таблицы истинности обоснованы. Чтобы подчеркнуть такое узко-формальное понимание импликации, философски настроенные логики называют её «материальной импликацией».

ОСНОВНЫЕ ПРАВИЛА МАТЛОГИКИ

• операцию «импликация» можно выразить через «ИЛИ» и «НЕ»:

A → B = ¬ A V B

• иногда для упрощения выражений полезны формулы де Моргана:

¬ (A V B) = ¬ A V ¬ B        

¬ (A V B) = ¬ A V ¬ B        

• для упрощения выражений можно использовать формулы

A V B*A = A

A V ¬A*B = A V B

• некоторые свойства импликации
•  если в выражении нет скобок, сначала выполняются все операции «НЕ», затем – «И», затем – «ИЛИ», «импликация», и самая последняя – «эквивалентность»
• таблица истинности выражения определяет его значения при всех возможных комбинациях исходных данных
• если известна только часть таблицы истинности, соответствующее логическое выражение однозначно определить нельзя, поскольку частичной таблице могут соответствовать несколько разных логических выражений (не совпадающих для других вариантов входных данных);
• количество разных логических выражений, удовлетворяющих неполной таблице истинности, равно , где – число отсутствующих строк; например, полная таблица истинности выражения с тремя переменными содержит 2³=8 строчек, если заданы только 6 из них, то можно найти 2^8-6=2²=4 разных логических выражения, удовлетворяющие этим 6 строчкам (но отличающиеся в двух оставшихся)
• логическая сумма A + B + C + … равна 0 (выражение ложно) тогда и только тогда, когда все слагаемые одновременно равны нулю, а в остальных случаях равна 1 (выражение истинно)
• логическое произведение A B · C · … равно 1 (выражение истинно) тогда и только тогда, когда все сомножители одновременно равны единице, а в остальных случаях равно 0 (выражение ложно)
• логическое следование (импликация) А→В равна 0 тогда и только тогда, когда A (посылка) истинна, а B (следствие) ложно
• эквивалентность А~B равна 1 тогда и только тогда, когда оба значения одновременно равны 0 или одновременно равны 1

 

Источники:

Верещагин Н.К., Шень А.

В31 Лекции по математической логике и теории алгоритмов. 

К.Ю. Поляков