Высказывания и операции
"Если число рационально, то — алгебраическое число. Но оно не алгебраическое. Значит, не рационально." Мы не обязаны знать, что такое число, какие числа называют рациональными и какие алгебраическими, чтобы признать, что это рассуждение правильно — в том смысле, что из двух сформулированных посылок действительно вытекает заключение. Такого рода ситуации — когда некоторое утверждение верно независимо от смысла входящих в него высказываний — составляют предмет логики высказываний.
Такое начало (особенно если учесть, что курс логики входил в программу философского факультета, где также изучалась "диалектическая логика") настораживает, но на самом деле наши рассмотрения будут иметь вполне точный математический характер, хотя мы начнем с неформальных мотивировок.
Высказывания могут быть истинными и ложными. Например, "— простое число "— истинное высказывание, а "— простое число"— ложное (это число делится на ). Про высказывание " существует бесконечно много простых , для которых — также простое "никто не берется сказать наверняка, истинно оно или ложно. Заметим, что " делится на" в этом смысле не является высказыванием, пока не сказано, чему равно; при разных получаются разные высказывания, одни истинные (при четном), другие— ложные (при нечетном).
Высказывания можно соединять друг с другом с помощью " логических связок". Эти связки имеют довольно странные, но традиционные названия и обозначения (табл. 1.1). Отметим также, что в импликации высказывание называют посылкой, или антецедентом импликации, а — заключением, или консеквентом.
| и |
& and | конъюнкция | |||
| или |
or | дизъюнкция | |||
|
не неверно |
not | отрицание | |||
|
из следует если , то влечет — следствие |
then |
импликация следование |
Говорят также, что высказывание имеет истинностное значение И (истина), если оно истинно, или Л (ложь), если оно ложно. Иногда вместо И употребляется буква T (true) или число , а вместо Л — буква F (false) или число . (С первого взгляда идея произвольным образом выбрать числа и кажется дикой — какая бы польза могла быть от, скажем, сложения истинностных значений? Удивительным образом в последние годы обнаружилось, что такая польза есть, и если оперировать с истиной и ложью как элементами конечного поля, можно получить много неожиданных результатов.
Но это выходит за рамки нашей книги.)
Логические связки позволяют составлять сложные высказывания из простых. При этом истинность составного высказывания определяется истинностью его частей в соответствии с таблицей 1.2.
| Л | Л | Л | Л | И |
| Л | И | Л | И | И |
| И | Л | Л | И | Л |
| И | И | И | И | И |
| Л | И |
| И | Л |
истинно, если оба высказывания и истинны. Высказывание истинно, если хотя бы одно из высказываний и истинно. Высказывание ложно в единственном случае: если истинно, а ложно. Наконец, истинно в том и только том случае, когда Наложно.
Из всех связок больше всего вопросов вызывает импликация. В самом деле, не очень понятно, почему надо считать, скажем, высказывания "если , то "и "если , то " истинными. (Именно так говорят наши таблицы: .) Следующий пример показывает, что в таком определении есть смысл.
Общепризнано, что если число делится на , то оно делится на . Это означает, что высказывание истинно при всех . Подставим сюда : обе части ложны, а утверждение в целом истинно. При посылка импликации ложна, а заключение истинно, и вся импликация истинна. Наконец, при
посылка и заключение истинны и импликация в целом истинна. С другой стороны, обратное утверждение (если делится на , то делится на ) неверно, и число является контрпримером. При этом посылка импликации истинна, заключение ложно, и сама импликация ложна. Таким образом, если считать, что истинность импликации определяется истинностью ее частей (а не наличием между ними каких-то причинно-следственных связей), то все строки таблицы истинности обоснованы. Чтобы подчеркнуть такое узко-формальное понимание импликации, философски настроенные логики называют ее "материальной импликацией".
Теперь от неформальных разговоров перейдем к определениям. Элементарные высказывания (из которых составляются более сложные) мы будем обозначать маленькими латинскими буквами и называть пропозициональными переменными. Из них строятся пропозициональные формулы по таким правилам:
- Всякая пропозициональная переменная есть формула.
- Если — пропозициональная формула, то — пропозициональная формула.
- Если и— пропозициональные формулы, то , и — пропозициональные формулы.
Можно еще сказать так: формулы образуют минимальное множество, обладающее указанными свойствами (слово "минимальное" здесь существенно: ведь если бы мы объявили любую последовательность переменных, скобок и связок формулой, то эти три свойства были бы тоже выполнены).
Пусть формула содержит пропозициональных переменных . Если подставить вместо этих переменных истинностные значения (И или Л), то по таблицам можно вычислить истинностное значение формулы в целом. Таким образом, формула задает некоторую функцию от аргументов, каждый из которых может принимать значения Л и И. Значения функции также лежат в множестве , которое мы будем обозначать. Мы будем следовать уже упоминавшейся традиции и отождествлять И с единицей, а Л — с нулем, тем самым есть. Формула задает отображение типа . Такие отображения называют также булевыми функциями аргументов.
Пример. Рассмотрим формулу . Она истинна в единственном случае — когда и
истинны, а ложно (см.таблицу 1.3).
| 0 | 0 | 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 | 0 |
Пример. Формула является тавтологией (это можно проверить, например, составив таблицу). Она выражает такой логический закон: из конъюнкции утверждений следует первое из них.
1. Как выглядит симметричное утверждение для дизъюнкции и какая формула его выражает?
Две формулы называют эквивалентными,если они истинны при одних и тех же значениях переменных (другими словами, если они задают одну и ту же булеву функцию). Например, формула истинна лишь при , и потому эквивалентна формуле .
Рассмотрим формулу .
Она истинна, если переменная истинна, и ложна, если переменная
ложна. Хотелось бы сказать, что она эквивалентна формуле, но тут есть формальная трудность: она содержит две переменные и потому задает функцию от двух аргументов (типа ), в то время как формула задает функцию одного аргумента. Мы не будем обращать на это внимания и будем считать эти формулы эквивалентными. Вообще, если есть список переменных , содержащий все переменные некоторой формулы (и, возможно, еще какие-то переменные), можно считать, что формула задает функцию от аргументов, возможно, на деле зависящую не от всех аргументов (постоянную по некоторым аргументам)
После сделанных оговорок легко проверить следующий факт: формулы и эквивалентны тогда и только тогда, когда формула является тавтологией. Используя сокращение для , можно записывать утверждения об эквивалентности формул в виде тавтологий. Вот несколько таких эквивалентностей:
Теорема 1. Формулы являются тавтологиями.
Первые четыре эквивалентности выражают коммутативность и ассоциативность конъюнкции и дизъюнкции. Проверим, например, вторую: левая и правая части истинны в единственном случае (когда все переменные истинны), и потому эквивалентны. (Для дизъюнкции удобнее смотреть, когда она ложна.)
Две следующие эквивалентности утверждают дистрибутивность— заметим, что в отличие от сложения и умножения в кольцах здесь верны оба свойства дистрибутивности. Проверить эквивалентность легко, если отдельно рассмотреть случаи истинного и ложного.
Следующие два свойства, законы Де Моргана, легко проверить, зная, что конъюнкция истинна, а дизъюнкция ложна лишь в одном случае. Эти свойства иногда выражают словами: "конъюнкция двойственна дизъюнкции".
Далее следуют два очевидных закона поглощения (один из них мы уже упоминали).
За ними идет правило контрапозиции, которое говорит, в частности, что утверждения "если совершенно, то четно"и "если нечетно, то несовершенно"равносильны. Хотя оно и очевидно проверяется с помощью таблиц истинности, с ним связаны любопытные парадоксы.
Вот один из них.
Биолог А выдвинул гипотезу: все вороны черные. Проверяя ее, он вышел во двор и обнаружил на дереве ворону. Она оказалось черной. Биолог А радуется — гипотеза подтверждается. Биолог Б переформулировал гипотезу так: все не-черные предметы — не вороны (применив наше правило контрапозиции) и не стал выходить во двор, а открыл холодильник и нашел там оранжевый предмет. Он оказался апельсином, а не вороной. Биолог Б обрадовался — гипотеза подтверждается — и позвонил биологу А. Тот удивляется — у него тоже есть апельсин в холодильнике, но с его точки зрения никакого отношения к его гипотезе апельсин не имеет...
Другой парадокс: с точки зрения формальной логики утверждения "кто не с нами, тот против нас"и "кто не против нас, тот с нами"равносильны.
Последнее (и очевидное) правило
называется снятием двойного отрицания.
2. Перечисленные эквивалентности соответствуют равенствам для множеств: например, первая гарантирует, что
для любых множеств и. Какие утверждения соответствуют остальным эквивалентностям?
3. Две формулы, содержащие только переменные и связки , и , эквивалентны. Докажите, что они останутся эквивалентными, если всюду заменить на и наоборот.
Далеко не все тавтологии имеют ясный интуитивный смысл. Например, формула является тавтологией (если одно из утверждений и ложно, то из него следует все, что угодно; если оба истинны, то тем более формула истинна), хотя и отчасти противоречит нашей интуиции — почему, собственно, из двух никак не связанных утверждений одно влечет другое? Еще более загадочна тавтология (хотя ее ничего не стоит проверить с помощью таблиц истинности).
Отступление о пользе скобок.На самом деле наше определение истинности содержит серьезный пробел. Чтобы обнаружить его, зададим себе вопрос: зачем нужны скобки в формулах? Представим себе, что мы изменим определение формулы, и будем говорить, что и
являются формулами для любых и. Останутся ли наши рассуждения в силе?
Легко понять, что мы столкнемся с трудностью при определении булевой функции, соответствующей формуле.
В этом определении мы подставляли нули и единицы на место переменных и затем вычисляли значение формулы с помощью таблиц истинности для связок. Но теперь, когда мы изменили определение формулы, формула может быть получена двумя способами — из формул и с помощью операции и из формул и спомощью операции . Эти два толкования дадут разный результат при попытке вычислить значение.
Из сказанного ясно, что скобки нужны, чтобы гарантировать однозначность синтаксического разбора формулы. Точнее говоря, верно такое утверждение:
Теорема 2 (однозначность разбора). Пропозициональная формула, не являющаяся переменной, может быть представлена ровно в одном из четырех видов , ,
или , где и — некоторые формулы, причем
и (в первых трех случаях) восстанавливаются однозначно.
Формальное доказательство можно провести так: назовем скобочным итогом разницу между числом открывающихся и закрывающихся скобок. Индукцией по построению формулы легко доказать такую лемму:
Лемма. Скобочный итог формулы равен нулю. Скобочный итог любого начала формулы неотрицателен и равен нулю, лишь если это начало совпадает со всей формулой, пусто или состоит из одних символов отрицания.
Слова "индукцией по построению"означают, что мы проверяем утверждение для переменных, а также доказываем, что если оно верно для формул и , то оно верно и для формул , , и .
После того как лемма доказана, разбор формулы проводится так: если она начинается с отрицания, то может быть образована лишь по третьему правилу. Если же она начинается со скобки, то надо скобку удалить, а потом искать непустое начало, имеющее нулевой скобочный итог и не оканчивающееся на знак логической операции. Такое начало единственно (как легко проверить, используя лемму). Это начало и будет первой частью формулы. Тем самым формула разбирается однозначно.
Нет смысла вдаваться в подробности этого (несложного) рассуждения: вообще-то алгоритмы разбора формул — это отдельная большая и практически важная тема (в первую очередь в связи с компиляторами).Приведенный нами алгоритм далеко не оптимален. С другой стороны, мы вообще можем обойти эту проблему, потребовав, чтобы при записи формул левая и правая скобки, окружающие формулу, связывались линией — тогда однозначность разбора формулы не вызывает вопросов, и больше ничего нам не надо.
В дальнейшем мы будем опускать скобки, если они либо не играют роли (например, можно написать конъюнкцию трех членов, не указывая порядок действий в силу ассоциативности), либо ясны из контекста.
4. Польский логик Лукасевич предлагал обходиться без скобок, записывая в формулах сначала знак операции, а потом операнды (без пробелов и разделителей). Например, в его обозначениях запишется как . Эту запись еще называют польской записью. Обратная польская запись отличается от нее тем, что знак операции идет после операндов. Покажите, что в обоих случаях порядок действий восстанавливается однозначно.
