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

Пример. Рассмотрим формулу $$(p\land (q\land \lnot r))$$. Она истинна в единственном случае — когда $$p$$ и $$q$$ истинны, а $$r$$ ложно (см.таблицу 1.3).

Некоторые формулы выражают логические законы — составные высказывания, истинные независимо от смысла их частей. Такие формулы (истинные при всех значениях входящих в них переменных) называют тавтологиями.

Пример. Формула $$((p \land q)\to p)$$ является тавтологией (это можно проверить, например, составив таблицу). Она выражает такой логический закон: из конъюнкции утверждений следует первое из них.

1. Как выглядит симметричное утверждение для дизъюнкции и какая формула его выражает?

Две формулы называют эквивалентными,если они истинны при одних и тех же значениях переменных (другими словами, если они задают одну и ту же булеву функцию). Например, формула $$(p \land (p\to q))$$ истинна лишь при $$p=q=И$$, и потому эквивалентна формуле $$(p\land q)$$.

Рассмотрим формулу $$((p\land q)\lor q)$$. Она истинна, если переменная $$q$$ истинна, и ложна, если переменная $$q$$ ложна. Хотелось бы сказать, что она эквивалентна формуле $$q$$, но тут есть формальная трудность: она содержит две переменные и потому задает функцию от двух аргументов (типа $$\mathbb B\times\mathbb B\to\mathbb B$$ ), в то время как формула $$q$$ задает функцию одного аргумента. Мы не будем обращать на это внимания и будем считать эти формулы эквивалентными. Вообще, если есть список переменных $$p_1,\dots,p_n$$, содержащий все переменные некоторой формулы $$\varphi$$ (и, возможно, еще какие-то переменные), можно считать, что формула $$\varphi$$ задает функцию от $$n$$ аргументов, возможно, на деле зависящую не от всех аргументов (постоянную по некоторым аргументам)

После сделанных оговорок легко проверить следующий факт: формулы $$\varphi$$ и $$\psi$$ эквивалентны тогда и только тогда, когда формула $$((\varphi\to\psi)\hm\land{(\psi\to\varphi))}$$ является тавтологией. Используя сокращение $$(p\leftrightarrow q)$$ для $$((p\to q)\hm\land{(q\to p)})$$, можно записывать утверждения об эквивалентности формул в виде тавтологий. Вот несколько таких эквивалентностей:

Теорема 1. Формулы$$(p\land q) \leftrightarrow (q \land p);$$ $$((p\land q) \land r) \leftrightarrow (p\land (q \land r));$$ $$(p\lor q) \leftrightarrow (q \lor p);$$ $$((p\lor q) \lor r) \leftrightarrow (p\lor (q \lor r));$$ $$(p\land(q\lor r)) \leftrightarrow ((p\land q)\lor (p\land r));$$ $$(p\lor(q\land r)) \leftrightarrow ((p\lor q)\land (p\lor r));$$ $$\lnot(p\land q) \leftrightarrow (\lnot p\lor \lnot q);$$ $$\lnot(p\lor q) \leftrightarrow (\lnot p\land \lnot q);$$ $$(p\lor (p \land q)) \leftrightarrow p;$$ $$(p\land (p \lor q)) \leftrightarrow p;$$ $$(p\to q) \leftrightarrow (\lnot q\to \lnot p);$$ $$p \leftrightarrow \lnot\lnot p$$ являются тавтологиями.

Первые четыре эквивалентности выражают коммутативность и ассоциативность конъюнкции и дизъюнкции. Проверим, например, вторую: левая и правая части истинны в единственном случае (когда все переменные истинны), и потому эквивалентны. (Для дизъюнкции удобнее смотреть, когда она ложна.)

Две следующие эквивалентности утверждают дистрибутивность— заметим, что в отличие от сложения и умножения в кольцах здесь верны оба свойства дистрибутивности. Проверить эквивалентность легко, если отдельно рассмотреть случаи истинного и ложного $$p$$.

Следующие два свойства, законы Де Моргана, легко проверить, зная, что конъюнкция истинна, а дизъюнкция ложна лишь в одном случае. Эти свойства иногда выражают словами: "конъюнкция двойственна дизъюнкции".

Далее следуют два очевидных закона поглощения (один из них мы уже упоминали).

За ними идет правило контрапозиции, которое говорит, в частности, что утверждения "если $$x$$ совершенно, то $$x$$ четно"и "если $$x$$ нечетно, то $$x$$ несовершенно"равносильны. Хотя оно и очевидно проверяется с помощью таблиц истинности, с ним связаны любопытные парадоксы. Вот один из них.

Биолог А выдвинул гипотезу: все вороны черные. Проверяя ее, он вышел во двор и обнаружил на дереве ворону. Она оказалось черной. Биолог А радуется — гипотеза подтверждается. Биолог Б переформулировал гипотезу так: все не-черные предметы — не вороны (применив наше правило контрапозиции) и не стал выходить во двор, а открыл холодильник и нашел там оранжевый предмет. Он оказался апельсином, а не вороной. Биолог Б обрадовался — гипотеза подтверждается — и позвонил биологу А. Тот удивляется — у него тоже есть апельсин в холодильнике, но с его точки зрения никакого отношения к его гипотезе апельсин не имеет...

Другой парадокс: с точки зрения формальной логики утверждения "кто не с нами, тот против нас"и "кто не против нас, тот с нами"равносильны.

Последнее (и очевидное) правило $$p\leftrightarrow \lnot\lnot p$$ называется снятием двойного отрицания.

2. Перечисленные эквивалентности соответствуют равенствам для множеств: например, первая гарантирует, что $$P\hm\cap Q\hm=Q\hm\cap P$$ для любых множеств $$P$$ и $$Q$$. Какие утверждения соответствуют остальным эквивалентностям?

3. Две формулы, содержащие только переменные и связки $$\land$$, $$\lor$$ и $$\lnot$$, эквивалентны. Докажите, что они останутся эквивалентными, если всюду заменить $$\land$$ на $$\lor$$ и наоборот.

Далеко не все тавтологии имеют ясный интуитивный смысл. Например, формула $${(p\to q)}\hm\lor{(q\to p)}$$ является тавтологией (если одно из утверждений $$p$$ и $$q$$ ложно, то из него следует все, что угодно; если оба истинны, то тем более формула истинна), хотя и отчасти противоречит нашей интуиции — почему, собственно, из двух никак не связанных утверждений одно влечет другое? Еще более загадочна тавтология$$((p\to q)\to p)\to p$$ (хотя ее ничего не стоит проверить с помощью таблиц истинности).

Отступление о пользе скобок.На самом деле наше определение истинности содержит серьезный пробел. Чтобы обнаружить его, зададим себе вопрос: зачем нужны скобки в формулах? Представим себе, что мы изменим определение формулы, и будем говорить, что $$P \land Q$$ и $$P \lor Q$$ являются формулами для любых $$P$$ и $$Q$$. Останутся ли наши рассуждения в силе?

Легко понять, что мы столкнемся с трудностью при определении булевой функции, соответствующей формуле. В этом определении мы подставляли нули и единицы на место переменных и затем вычисляли значение формулы с помощью таблиц истинности для связок. Но теперь, когда мы изменили определение формулы, формула $$p\land q \lor r$$ может быть получена двумя способами — из формул $$p\land q$$ и $$r$$ с помощью операции $$\lor$$ и из формул $$p$$ и $$q\lor r$$ спомощью операции $$\land$$. Эти два толкования дадут разный результат при попытке вычислить значение $$0 \land 0 \lor 1$$.

Из сказанного ясно, что скобки нужны, чтобы гарантировать однозначность синтаксического разбора формулы. Точнее говоря, верно такое утверждение:

Теорема 2 (однозначность разбора). Пропозициональная формула, не являющаяся переменной, может быть представлена ровно в одном из четырех видов $$(A\land B)$$, $$(A\lor B)$$, $$(A\to B)$$ или $$\lnot A$$, где $$A$$ и $$B$$ — некоторые формулы, причем $$A$$ и $$B$$ (в первых трех случаях) восстанавливаются однозначно.

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

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

Слова "индукцией по построению"означают, что мы проверяем утверждение для переменных, а также доказываем, что если оно верно для формул $$A$$ и $$B$$, то оно верно и для формул $$(A\land B)$$, $$(A\lor B)$$, $$(A\to B)$$ и $$\lnot A$$.

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

Нет смысла вдаваться в подробности этого (несложного) рассуждения: вообще-то алгоритмы разбора формул — это отдельная большая и практически важная тема (в первую очередь в связи с компиляторами). Приведенный нами алгоритм далеко не оптимален. С другой стороны, мы вообще можем обойти эту проблему, потребовав, чтобы при записи формул левая и правая скобки, окружающие формулу, связывались линией — тогда однозначность разбора формулы не вызывает вопросов, и больше ничего нам не надо.

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

4. Польский логик Лукасевич предлагал обходиться без скобок, записывая в формулах сначала знак операции, а потом операнды (без пробелов и разделителей). Например, $$(a+b)\hm\times(c+(d\times e))$$ в его обозначениях запишется как $${{\times}{+}ab{+}c{\times}{d} {e}}$$. Эту запись еще называют польской записью. Обратная польская запись отличается от нее тем, что знак операции идет после операндов. Покажите, что в обоих случаях порядок действий восстанавливается однозначно.

Полные системы связок

Рассматриваемая нами система пропозициональных связок ( $$\land$$, $$\lor$$, $$\to$$, $$\lnot$$ ) полна в следующем смысле:

Теорема 3 (Полнота системы связок). Любая булева функция $$n$$ аргументов может быть записана в виде пропозициональной формулы.

Проще всего пояснить это на примере. Пусть, например, булева функция $$\varphi(p,q,r)$$ задана таблицей 1.4

В таблице есть три строки с единицами в правой колонке — три случая, когда булева функция истинна (равна $$1$$ ). Напишем три конъюнкции, каждая из которых покрывает один случай (а в остальных строках ложна), и соединим их дизъюнкцией. Нужная формула построена.

Ясно, что аналогичная конструкция применима для любой таблицы (с любым числом переменных).

Для формул подобного вида есть специальное название: формулы в дизъюнктивной нормальной форме. Более подробно: литералом называется переменная или отрицание переменной, конъюнктом называется произвольная конъюнкция литералов, а дизъюнктивной нормальной формой называется дизъюнкция конъюнктов. В нашем случае в каждый конъюнкт входит $$n$$ литералов (где $$n$$ — число переменных), а число конъюнктов равно числу строк с единицами и может меняться от нуля (тогда, правда, получается не совсем формула, а "пустая дизъюнкция", и ее можно заменить какой-нибудь всегда ложной формулой типа $$p\land \lnot p$$ ) до $$2^n$$ (если булева функция всегда истинна).

5. Длина построенной в доказательстве теоремы 3 формулы зависит от числа единиц: формула будет короткой, если единиц в таблице мало. А как написать (сравнительно) короткую формулу, если в таблице мало нулей, а в основном единицы?

Иногда полезна конъюнктивная нормальная форма, которая представляет собой конъюнкцию дизъюнктов. Каждый дизъюнкт состоит из литералов, соединенных дизъюнкциями. Теорему 3 можно теперь усилить так:

Теорема 4. Всякая булева функция может быть выражена формулой, находящейся в дизъюнктивной нормальной форме, а также формулой, находящейся в конъюнктивной нормальной форме.

Первая часть утверждения уже доказана. Вторая часть аналогична первой, надо только для каждой строки с нулем написать подходящий дизъюнкт.

Можно также представить функцию $$\lnot \varphi$$ в дизъюнктивной нормальной форме, а затем воспользоваться законами Де Моргана, чтобы внести отрицание внутрь.

6. Проведите второй вариант рассуждения подробно.

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

7. Приведите пример булевой функции $$n$$ аргументов, у которой любая дизъюнктивная или конъюнктивная нормальная форма содержит лишь члены длины $$n$$. (Указание: рассмотрите функцию, которая меняет свое значение при изменении значения любой переменной.)

Заметим, что при доказательстве теоремы 3 мы обошлись без импликации. Это и не удивительно, так как она выражается через дизъюнкцию и отрицание:$$(p\to q) \ \leftrightarrow \ (\lnot p \lor q)$$ (проверьте!). Мы могли бы обойтись только конъюнкцией и отрицанием, так как$$(p\lor q) \ \leftrightarrow \ \lnot(\lnot p \land \lnot q),$$ или только дизъюнкцией и отрицанием, так как$$(p\land q) \ \leftrightarrow \ \lnot(\lnot p \lor \lnot q)$$ (обе эквивалентности вытекают из законов Де Моргана; их легко проверить и непосредственно). Как говорят, система связок $$\land, \lnot$$, а также система связок $$\lor, \lnot$$ являются полными. (По определению это означает, что с их помощью можно записать любую булеву функцию.)

8. Докажите, что система связок $$\lnot, \to$$ полна. (Указание: как записать через них дизъюнкцию?)

А вот без отрицания обойтись нельзя. Система связок $$\land, \lor,\to$$ неполна — и по очень простой причине: если все переменные истинны, то любая их комбинация, содержащая только указанные связки, истинна. (Как говорят, все эти связки "сохраняют единицу".)

9. Легко понять, что любая формула, составленная только с помощью связок $$\land$$ и $$\lor$$, задает монотонную булеву функцию (в том смысле, что от увеличения значения любого из аргументов значение функции может только возрасти — или остаться прежним). Покажите, что любая монотонная булева функция может быть выражена формулой, содержащей только $$\land$$ и $$\lor$$.

10. Пусть $$\varphi\to\psi$$ — тавтология. Покажите, что найдется формула $$\tau$$, которая включает в себя только общие для $$\varphi$$ и $$\psi$$ переменные, для которой формулы $$(\varphi\to\tau)$$ и $$(\tau\to\psi)$$ являются тавтологиями. (Более общий вариант этого утверждения, в котором рассматриваются формулы с кванторами, называется леммой Крейга.)

В принципе мы не обязаны ограничиваться четырьмя рассмотренными связками. Любая булева функция может играть роль связки. Например, можно рассмотреть связку $$(p \texttt{ notand } q)$$, задаваемую эквивалентностью$$(p \texttt{ notand } q) \ \leftrightarrow \ \lnot(p\land q)$$ (словами: $$(p\texttt{ notand }q)$$ ложно, лишь если $$p$$ и $$q$$ истинны). Через нее выражается отрицание ( $$p \texttt{ notand }p$$ ), после чего можно выразить конъюнкцию, а затем, как мы знаем, и вообще любую функцию. (Знакомые с цифровыми логическими схемами малого уровня интеграции хорошо знакомы с этим утверждением: достаточно большой запас схем И-НЕ позволяет реализовать любую требуемую зависимость выхода от входов.)

Другая интересная полная система связок — сложение по модулю $$2$$, конъюнкция и константа $$1$$ (которую можно считать $$0$$ -арной связкой, задающей функцию от нуля аргументов). Представленные в этой системе булевы функции становятся полиномами с коэффициентами в кольце вычетов по модулю $$2$$. Идея рассматривать булевы функции как полиномы (оказавшаяся неожиданно плодотворной в последние годы) была высказана в 1927 г. российским математиком Иваном Ивановичем Жегалкиным.

Назовем мономом конъюнкцию любого набора переменных или константу $$1$$ (которую естественно рассматривать как конъюнкцию нуля переменных). Название это естественно, так как при наших соглашениях ( $$1$$ обозначает истину, $$0$$ — ложь) конъюнкция соответствует умножению.

Назовем полиномом сумму таких мономов по модулю $$2$$ (это значит, что $$0\oplus0\hm =0$$, $$0\oplus 1\hm=1\oplus 0\hm=1$$ и $$1\oplus1\hm=0$$ ). Ясно, что два повторяющихся монома можно сократить (ведь сложение по модулю $$2$$ ), так что будем рассматривать только полиномы без повторяющихся мономов. При этом, естественно, порядок членов в мономе (как и порядок мономов в полиноме) роли не играет, их можно переставлять.

Теорема 5 (о полиномах Жегалкина). Всякая булева функция однозначно представляется таким полиномом.

Существование искомого полинома следует из теоремы 4, так как конъюнкция есть умножение, отрицание — прибавление единицы, а дизъюнкцию можно через них выразить (получится $$p+q+pq$$ ). Надо только заметить, что степени не нужны: переменные принимают значения $$0$$ и $$1$$, так что $$x^n$$ можно заменить на $$x$$.

Можно также сослаться на известное из алгебры утверждение о том, что всякая функция с аргументами из конечного поля (в данном случае это двухэлементное поле вычетов по модулю $$2$$ ) задается полиномом. (Отсюда, кстати, получается новое доказательство теоремы 3.)

Далее можно заметить, что полиномов столько же, сколько булевых функций, а именно $$2^{2^n}$$. В самом деле, булева функция может принимать любое из двух значений в каждой из $$2^n$$ точек булева куба $$\mathbb B^n$$, а многочлен может включать или не включать любой из $$2^n$$ мономов. (Мономов ровно $$2^n$$, потому что каждый моном включает или не включает любую из $$n$$ переменных.) Поэтому избытка полиномов нет, и если любая функция представима полиномом, то единственным образом.

Можно и не ссылаться на сведения из алгебры и теорему 4, а дать явную конструкцию. Это удобно сделать индукцией по $$n$$. Пусть мы уже умеем представлять любую булеву функцию от $$n-1$$ аргументов с помощью полинома. Тогда $$\varphi(p_1,\dots,p_n)$$ можно представить как$$\varphi(p_1,\dots,p_n) = \varphi(0, p_2,\dots,p_{n})+[\varphi(0,p_2,\dots,p_{n})+\varphi(1,p_2,\dots,p_{n})]p_1$$ (проверьте). Остается заметить, что правую часть можно представить полиномом по предположению индукции.

Для единственности также есть другое доказательство: пусть два многочлена (имеющие степень $$1$$ по каждой переменной) равны при всех значениях переменных. Тогда их сумма (или разность — вычисления происходят по модулю $$2$$ ) является ненулевым многочленом (содержит какие-то мономы), но тождественно равна нулю. Так не бывает, и это легко доказать по индукции. В самом деле, любой многочлен $$A(p_1,\dots,p_n)$$ можно представить в виде$$A(p_1,\dots,p_n)=B(p_2,\dots,p_n)+p_1C(p_2,\dots,p_n),$$ где $$B$$ и $$C$$ — многочлены от меньшего числа переменных. Подставляя сначала $$p_1\hm=0$$, а затем $$p_1\hm=1$$, убеждаемся, что многочлены $$B$$ и $$C$$ равны нулю во всех точках, и потому (согласно предположению индукции) равны нулю как многочлены (не содержат мономов).

11. Пусть $$F$$ — произвольное поле.Назовем мультилинейной функцией полином от $$n$$ переменных с коэффициентами из $$F$$, в котором все показатели степеней равны либо $$0$$, либо $$1$$. (Таким образом, каждый моном в ней есть произведение коэффициента и некоторого набора переменных без повторений.) Будем рассматривать $$\mathbb B=\{0,1\}$$ как подмножество $$F$$. Докажите, что всякая булева функция $$\mathbb B^n\to\mathbb B$$ однозначно продолжается до мультилинейной функции $$F^n\to F$$, и коэффициенты мультилинейной функции можно считать целыми числами.

Если рассматривать произвольные булевы функции в качестве связок, возникает вопрос: в каком случае набор булевых функций образует полный базис? (Это значит, что любая булева функция представляется в виде композиции функций из набора, т. е. записывается в виде формулы, где связками служат функции набора.) Подобные вопросы вызывали в свое время большой интерес и были хорошо изучены. Начальным этапом явилось такое утверждение:

Теорема 6 (критерий Поста). Набор булевых функций является полным тогда и только тогда, когда он не содержится целиком ни в одном из пяти следующих "предполных классов":

(Функция $$f$$ монотонна, если она монотонно неубывает по каждому из своих аргументов. Функция $$f$$ сохраняет нуль/единицу, если $$f(0,\dots,0)\hm=0$$ (соответственно $$f(1,\dots,1)\hm=1$$ ). Функция $$f$$ линейна, если она представима многочленом, в котором все мономы содержат не более одной переменной. Наконец, функция $$f$$ называется самодвойственной, если $$f(1-p_1,\dots,1-p_n)\hm=1-f(p_1,\dots,p_n)$$.)

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

У нас есть функция, не сохраняющая нуль. Подставим вместо всех аргументов одну и ту же переменную. Получится функция от одного аргумента, отображающая нуль в единицу, то есть либо константа $$1$$, либо отрицание. Сделав то же самое с функцией, не сохраняющей единицу, получим либо константу нуль, либо отрицание. Таким образом, у нас либо есть отрицание, либо обе константы $$0$$ и $$1$$.

Если есть обе константы, то все равно можно получить отрицание. Возьмем немонотонную функцию. Легко понять, что она должна менять значение с единицы на нуль при изменении какого-то одного аргумента с нуля на единицу (в самом деле, будем увеличивать аргументы по одному, в какой-то момент значение функции уменьшится.) Зафиксировав значения остальных аргументов (ведь мы считаем, что константы есть), получаем отрицание.

Имея отрицание и несамодвойственную функцию, легко получить константы (если их не было). В самом деле, несамодвойственность означает, что $$f(x_1,\dots,x_n)\hm=f(1\hm-x_1,\dots,1\hm-x_n)$$ для каких-то значений $$x_1,\dots,x_n\hm\in\{0,1\}$$. Вместо нулевых значений переменных $$x_1,\dots,x_n$$ подставим $$p$$, вместо единиц подставим $$\lnot p$$, получится одна из констант. Вторая получится отрицанием.

Теперь у нас есть константы, отрицание и нелинейная функция $$f(p_1,\dots,p_n)$$. Нелинейность означает, что в ее представлении в виде многочлена есть моном, состоящий более чем из одной переменной. Пусть, например, этот моном содержит переменные $$p_1$$ и $$p_2$$. Сгруппируем члены по четырем группам и получим выражение$$p_{1p2} A(p_3,\dots)+p_1B(p_3,\dots)+p_2C(p_3,\dots)+D(p_3,\dots).$$ При этом многочлен $$A(p_3,\dots)$$ заведомо отличен от нуля, поэтому можно так подставить константы вместо $$p_3,\dots,p_n$$, чтобы первое слагаемое не обратилось в нуль. Тогда получим либо $$p_1p_2+d$$, либо $$p_{1p2} + p_1+d$$, либо $$p_1p_2+p_2+d$$, либо $$p_1p_2+p_1+p_2+d$$. Свободный член $$d$$ можно менять, если нужно (у нас есть отрицание), так что получается либо $$p_1p_2$$ (конъюнкция, и все доказано), либо $$p_1p_2+p_1\hm=p_1(p_2+1)\hm= p_1\land\lnot p_2$$ (убираем отрицание, получаем конъюнкцию, все доказано), либо $$p_1p_2+p_2$$ (аналогично), либо $$p_1p_2+p_1+p_2\hm= (1+p_1)(1+p_2)-1\hm=\lnot(\lnot p_1\land\lnot p_2)\hm=p_1\lor p_2$$ (дизъюнкция, все доказано).