3 Логика Высказываний: Синтаксис и Семантика

3.1 I.1 Введение в Логику Высказываний

Логика высказываний (propositional logic) используется для выражения утверждений с помощью “высказываний” (propositions) или “предложений” (sentences), принимающих значения “истина”/“ложь”. Логику высказываний иногда называют “логикой предложений” (sentential logic) или “булевой логикой” (Boolean logic); последнее название связано с тем, что она оперирует булевыми значениями “Истина” и “Ложь”.

В качестве простого примера рассмотрим три высказывания, обозначенные переменными r, s, w:
- r: “Идёт дождь”
- s: “Светит солнце”
- w: “Трава мокрая”

Как высказывания, они предполагают определённые значения истинности. Например, предполагается, что r примет определённое значение “Истина” или “Ложь”, указывающее на то, идёт дождь или нет (скажем, в конкретное время или месте, без неоднозначности, которая может возникнуть из-за вопросов вроде того, считается ли лёгкая морось дождём). Аналогично предполагается, что s и w примут определённые значения истинности относительно того, светит ли солнце и мокрая ли трава.
Более сложные высказывания формируются путём комбинирования пропозициональных переменных с операторами, такими как “не” (¬), “и” (∧), “или” (∨). Например:
- ¬r - “Не идёт дождь”
- r ∧ w - “Идёт дождь и трава мокрая”
- r ∨ s - “Идёт дождь или светит солнце”
- ¬(r ∧ s) - “Неверно, что одновременно идёт дождь и светит солнце”

Оператор ¬ (“не”) также называется логическим отрицанием (logical negation) или просто отрицанием. Оператор ∧ (“и”) называется конъюнкцией (conjunction). Оператор ∨ (“или”) называется дизъюнкцией (disjunction). Связка ∨ обозначает “включающее или” (inclusive or), поскольку допускает возможность истинности обоих аргументов. Таким образом, формула r ∨ s также истинна, когда истинны и r, и s.

Другие распространённые связки включают “если…, то…” (→) и “тогда и только тогда” (↔︎). Оператор → часто называют импликацией (implication), а оператор ↔︎ - оператором эквивалентности (equivalence). Например:
- r → w - “Если идёт дождь, то трава мокрая”
- w → r - “Трава мокрая, только если идёт дождь”
- r → w - “Трава мокрая, если идёт дождь”
- w ↔︎ r - “Трава мокрая тогда и только тогда, когда идёт дождь”

При переводе предложений естественного языка в пропозициональные формулы следует проявлять осторожность, поскольку естественные языки (такие как английский) допускают множество нюансов, полностью теряемых в логике высказываний. Однако, как показано в некоторых примерах выше, “B, если A” обычно означает то же самое, что “если A, то B”. Это также означает то же самое, что “A, только если B”.

Менее явные случаи использования пропозициональных связок встречаются с “но” и “если не”; например:
- r ∧ ¬w - “Идёт дождь, но трава не мокрая”
- (¬w) ∨ r - “Трава не мокрая, если не идёт дождь”

Эти примеры иллюстрируют, что “но” может переводиться как пропозициональная связка ∧ (“и”), а “A, если не B” может переводиться как A ∨ B. Последнее также можно перевести как (¬A) → B, поскольку это означает то же самое, что “если ¬A, то B” или “если A ложно, то B истинно”. В связи с этим, “Если A, то B” в логике высказываний означает то же самое, что (¬A) ∨ B.

Для более проблемных соответствий между утверждениями на естественном языке и логикой высказываний рассмотрим:
- b - “Вы можете купить билет”
- e - “Вам больше восемнадцати лет”

которые используются для формирования составных высказываний:
- e → b - “Вы можете купить билет, если вам больше восемнадцати”
- b → e - “Вы можете купить билет, только если вам больше восемнадцати”
- b ↔︎ e - “Вы можете купить билет тогда и только тогда, когда вам больше восемнадцати”
Если бы кто-то делал эти утверждения в реальной ситуации, он, вероятно, использовал бы любое из трёх для обозначения b ↔︎ e, т.е. что вы можете купить билет тогда и только тогда, когда вам восемнадцать.⁵ Однако мы используем “если” и “только если” в более специализированном смысле, как это принято в логике и математике в целом. Это иллюстрирует необходимость осторожности при переводе с естественного языка на язык логики высказываний.

Математическая логика избегает неоднозначности английского языка. Вместо этого пропозициональные связки ¬, ∧, ∨, →, ↔︎ и т.д. являются чисто истинностными (truth functional), их значения показаны на Рисунке I.1. Например, истинность формулы p → q определяется исключительно истинностью или ложностью p и q, и не имеет значения, существует ли какая-то причина, по которой истинность p должна подразумевать истинность q.

Действительно, p → q всегда будет иметь то же значение истинности, что и (¬p) ∨ q.

Это иногда может сбивать с толку, поскольку несколько контринтуитивно, что “если p, то q” должно быть истинным, когда p ложно, независимо от того, истинно q или ложно. Это контринтуитивно по той простой причине, что в английском языке обычно есть различие между “если A, то B” и “B или не A”. Например, рассмотрим довольно драматическую разницу в значениях двух предложений:

“Если ты пойдешь в свой дом сегодня, то найдешь свой паспорт сегодня”

и

“Ты найдешь свой паспорт сегодня, или ты не пойдешь в свой дом сегодня”

Форма “если A, то B” звучит как полезный совет о том, как найти потерянный паспорт. С другой стороны, форма “B или не A” звучит как угроза от пограничника. Эти нюансы полностью теряются при переводе утверждений с английского на язык логики высказываний, поскольку A → B означает в точности то же самое, что B∨¬A в логике высказываний.

В естественных языках утверждение “если A, то B” обычно означает, что существует причина, по которой истинность A подразумевает истинность B. В логике высказываний, однако, утверждения типа “Если у свиней есть крылья, то лошади могут летать” могут быть истинными (поскольку у свиней нет крыльев), несмотря на то, что крылья у свиней, предположительно, не имеют ничего общего с летающими лошадьми!

В качестве примера, объясняющего, почему такая трактовка импликации имеет смысл при работе с математическими утверждениями, рассмотрим пропозиции:

• P(x) - “x - простое число больше 2”
• O(x) - “x - нечетное”

Конечно, мы хотим, чтобы утверждение ∀x(P(x) → O(x)), “Для всех x, если x - простое число больше 2, то x нечетное”, было истинным для x, пробегающего все целые числа. Рисунок I.2 дает значения истинности P(x) и O(x) и P(x) → O(x) при x = 1, x = 2 и x = 3. Мы хотим, чтобы P(x) → O(x) было истинным во всех трех случаях, включая два случая, когда P(x) ложно. Таким образом, мы хотим, чтобы “F → F” и “F → T” оба оценивались как истинные, чтобы дать правильные результаты в случаях, когда x равен 1 или 2.

3.2 I.2 Пропозициональные формулы

Теперь мы дадим формальные определения синтаксиса пропозициональных формул. После этого в следующем разделе будет определено значение истинности формулы в терминах значений истинности её переменных.

Таблица истинности:

p	¬p
T	F
F	T

p	q	p∨q	p∧q	p→q	p↔︎q
T	T	T	T	T	T
T	F	T	F	F	F
F	T	T	F	T	F
F	F	F	F	T	T

Рисунок I.1: Значения пропозициональных связок. “T” и “F” обозначают булевы значения “Истина” (True) и “Ложь” (False).

x	P(x)	O(x)	P(x)→O(x)
1	F	T	T
2	F	F	T
3	T	T	T

Рисунок I.2: Таблица значений для P(x) → O(x)

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

1. Переменные: p₁, p₂, p₃, …
2. Пропозициональные связки: ¬, ∧, ∨, →, ↔︎
3. Скобки: ( и )

Определение I.1. Множество пропозициональных формул определяется индуктивно:

1. pᵢ является пропозициональной формулой для любого i ≥ 1.
2. Если A - пропозициональная формула, то ¬A также является пропозициональной формулой.
3. Если A и B - пропозициональные формулы, то (A∨B), (A∧B), (A→B) и (A↔︎B) также являются пропозициональными формулами.

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

Пример I.2. Примеры пропозициональных формул:

• p₁
• p₂
• p₁₀₀₀
• ¬p₂
• ¬¬p₂
• (p₁ → (¬p₂ → p₁))
• ((p₁ → ¬p₂) → p₁)
• ¬((p₁ ↔︎ ¬¬¬p₂) → (¬p₂ ∨ (p₁ ∧ p₁)))

Следующие записи НЕ являются пропозициональными формулами:

• p₁ ∧ p₂ (отсутствуют скобки)
• (¬p₃) (лишние скобки)
• p ∨ r (использованы переменные, отличные от pᵢ)

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

● Знак отрицания ¬ имеет наивысший приоритет
● Связки ∧ и ∨ имеют средний приоритет
● Связки → и ↔︎ имеют наименьший приоритет
● Если скобки опущены у операторов одинакового приоритета, ассоциативность правая

Примеры сокращений:

Сокращение	Полная форма
¬p₁ ∨ ¬p₂ ∨ p₃	(¬p₁ ∨ (¬p₂ ∨ p₃))
¬p₁ → ¬p₂ → p₃	(¬p₁ → (¬p₂ → p₃))
p₁ ∨ ¬p₂ → ¬p₃ ∧ p₄	((p₁ ∨ ¬p₂) → (¬p₃ ∧ p₄))

В дополнение к опусканию скобок, вместо p₁, p₂, p₃,… часто используют имена переменных p, q, r,… Это делается только для улучшения читаемости; формально в формулах могут появляться только переменные pᵢ.

Функции истинности для ∧, ∨ и ↔︎ ассоциативны, поэтому соглашение о правосторонней ассоциативности для них не так важно. Однако → не ассоциативна, так как p → (q → r) не эквивалентна (p → q) → r. Формула p → (q → r), однако, функционально эквивалентна формуле p ∧ q → r. Это часто удобный и полезный способ записи формулы, и именно по этой причине мы выбрали правостороннюю ассоциативность.

Лучше избегать записей типа A ∨ B ∧ C или A → B ↔︎ C, чтобы не запутывать читателей. Согласно нашим соглашениям они означают A ∨ (B ∧ C) или A → (B ↔︎ C), но другие авторы могут использовать иные соглашения.

Доказательства по индукции и рекурсивные определения. Причина столь тщательного формального математического определения пропозициональных формул заключается в том, что мы будем использовать его для доказательства теорем о пропозициональных формулах. То есть мы не просто используем формулы, но и доказываем теоремы о формулах.

Определение I.1 дало индуктивное определение формул. Это позволяет доказывать свойства формул по индукции. Конкретно, предположим, мы хотим доказать, что каждая пропозициональная формула удовлетворяет некоторому свойству Q. Для доказательства этого по индукции достаточно показать, что:

1. Каждая формула pᵢ удовлетворяет свойству Q,
2. Если A - пропозициональная формула, удовлетворяющая свойству Q, то формула ¬A также удовлетворяет свойству Q, и
3. Если A и B - пропозициональные формулы, каждая из которых удовлетворяет свойству Q, то формулы (A ∧ B), (A ∨ B), (A → B) и (A ↔︎ B) все удовлетворяют свойству Q.

Первый случай (a) служит базовым случаем. Случаи (b) и (c) служат шагами индукции. Это означает, что нужно доказать два шага индукции, или даже пять шагов индукции, если случай (c) нужно рассматривать как четыре различных шага индукции.

Третий случай (c) Определения I.1 для пропозициональных формул рассматривает случай, когда главной связкой является ∧, ∨, → или ↔︎. Он требует включения скобок, чтобы формула имела вид (A ○ B), где ○ - одна из четырёх бинарных связок. Наличие всех этих скобок означает, что существует единственный способ разбора любой пропозициональной формулы. То есть, если C - пропозициональная формула, то существует единственный способ выразить её в одной из форм (a)-(c) Определения I.1. Это называется свойством уникальной читаемости и означает, что пропозициональные формулы могут быть однозначно разобраны.

Индуктивное определение пропозициональных формул в Определении I.1 и свойство уникальной читаемости вместе позволяют использовать индуктивные определения (также называемые “рекурсивными определениями”) для определения функций пропозициональных формул. Общая схема для определения функции h(A) рекурсией по сложности формулы A следующая:

1. Для базового случая мы определяем значение h для пропозициональной формулы pᵢ.
2. Для первого случая рекурсии мы предполагаем, что значение h для формулы A уже определено. Мы используем это для определения значения h для формулы ¬A.
3. Для других случаев рекурсии мы предполагаем, что значения h на формулах A и B уже определены. Мы используем их для определения значения h для формулы (A ○ B), где ○ - одна из связок ∧, ∨, → или ↔︎.

Свойство уникальной читаемости означает, что существует ровно один способ выразить пропозициональную формулу в одной из форм pᵢ, ¬A или (A○B), чтобы рекурсивно применить один из случаев (a), (b) или (c). Таким образом, значение h однозначно определено для всех формул.

Яркий пример определения по рекурсии - Определение I.4, данное в следующем разделе, для значения истинности пропозициональной формулы. В разделе I.9 приведены некоторые примеры доказательств по индукции по сложности формул.

3.3 I.3 Определение истинности в логике высказываний

Предыдущий раздел определил синтаксис пропозициональных формул; теперь мы определим их семантику, а именно, что означает, что пропозициональная формула истинна или ложна. Истинность или ложность формулы зависит от значений истинности переменных, входящих в неё. Например, формула p₁ → p₂ может иметь значение либо Истина (T), либо Ложь (F) в зависимости от значений p₁ и p₂. Соответственно, мы начинаем с присваивания φ значений истинности пропозициональным переменным.

Определение I.3. Присваивание истинности φ - это отображение

φ: {p₁, p₂, p₃, …} → {T,F}

из множества пропозициональных переменных в множество значений истинности T и F.

Присваивание истинности φ переменным даёт значение истинности φ(pᵢ) каждой переменной pᵢ. Мы можем расширить φ, чтобы дать значения истинности всем пропозициональным формулам:

Определение I.4 (Определение истинности для пропозициональных формул). Предположим, что φ - присваивание истинности. Функция φ расширяется на множество всех пропозициональных формул рекурсивным определением:

\[\begin{array}{ll} \text{(a)} & \text{Если } A = \lnot B,\ \varphi(A) = \left\{ \begin{array}{ll} \text{F}, & \text{если } \varphi(B) = \text{T} \\ \text{T}, & \text{в противном случае} \end{array} \right. \\[1.2em] \text{(b)} & \text{Если } A = (B \lor C),\ \varphi(A) = \left\{ \begin{array}{ll} \text{T}, & \text{если } \varphi(B) = \text{T} \text{ или } \varphi(C) = \text{T} \\ \text{F}, & \text{в противном случае} \end{array} \right. \\[1.2em] \text{(c)} & \text{Если } A = (B \land C),\ \varphi(A) = \left\{ \begin{array}{ll} \text{T}, & \text{если } \varphi(B) = \text{T} \text{ и } \varphi(C) = \text{T} \\ \text{F}, & \text{в противном случае} \end{array} \right. \\[1.2em] \text{(d)} & \text{Если } A = (B \rightarrow C),\ \varphi(A) = \left\{ \begin{array}{ll} \text{T}, & \text{если } \varphi(B) = \text{F} \text{ или } \varphi(C) = \text{T} \\ \text{F}, & \text{в противном случае} \end{array} \right. \\[1.2em] \text{(e)} & \text{Если } A = (B \leftrightarrow C),\ \varphi(A) = \left\{ \begin{array}{ll} \text{T}, & \text{если } \varphi(B) = \varphi(C) \\ \text{F}, & \text{в противном случае} \end{array} \right. \end{array}\]

Заметим, как определение истинности следует неформальным значениям, обсуждавшимся в разделе I.1.

Пример I.5. Пусть A - формула (p ∨ q) → (q ∧ p). В этой формуле только две переменные p, q, поэтому значение истинности φ(A) зависит от φ(p) и φ(q); однако φ(A) не зависит от φ(r) для любой другой переменной r. Поскольку φ(p) и φ(q) могут быть только T или F, есть только четыре способа установить значения истинности p и q. Они показаны в первых двух столбцах таблицы истинности на Рисунке I.3. Предпоследний столбец таблицы истинности даёт соответствующие значения φ((p ∨ q) → (q ∧ p)).

Во второй строке Рисунка I.3 φ(p) = T и φ(q) = F. Следовательно, согласно двум применениям определения истинности, φ(p ∨ q) = T и φ(p ∧ q) = F. С ещё одним применением определения истинности, φ((p ∨ q) → (q ∧ p)) = F. То есть A ложно, когда p истинно, а q ложно.

Пусть B - формула (p ∧ q) → (q ∨ p). Последний столбец Рисунка I.3 показывает значения φ(B) для всех возможных присваиваний значений p и q. Поскольку φ(B) = T для всех четырёх присваиваний, мы называем B “тавтологией” или говорим, что B “тавтологически общезначима”. С другой стороны, φ(A) равно T для некоторых присваиваний истинности и F для других. Поэтому A не является тавтологией; однако она “выполнима”, поскольку существует присваивание истинности, которое делает A истинным.

Следующий раздел обсуждает тавтологии и выполнимость более подробно.

p	q	p∨q	p∧q	p∨q→p∧q	p∧q→p∨q
T	T	T	T	T	T
T	F	T	F	F	T
F	T	T	F	F	T
F	F	F	F	T	T

Рисунок I.3: Таблица истинности для r (p ∨ q) → (p ∧ q) и (p ∧ q) → (p ∨ q).

3.4 I.4 Выполнимость, тавтологии и импликация

Выполнимость и тавтологии. Формула называется “тавтологией”, если она всегда истинна; она “выполнима”, если может быть истинной в некоторых случаях. Формально:

Определение I.6. Формула A является тавтологией, если φ(A) = T для всех присваиваний истинности φ. В этом случае мы также говорим, что A тавтологически общезначима.

Формула A выполнима, если существует некоторое присваивание истинности φ, такое что φ(A) = T. В этом случае мы говорим, что φ является выполняющим присваиванием для A или что A выполняется при φ. Если не существует выполняющего присваивания для A, то A невыполнима.

Обозначение “⊧ A” также используется для обозначения того, что A является тавтологией. См. Определение I.10 ниже.

Пример I.7. Формула p₁ выполнима, но не является тавтологией, поскольку φ(p₁) может быть равно либо T, либо F. Формулы p₁ ∨ ¬p₁ и p₁ → (p₂ → p₁) являются тавтологиями и, следовательно, выполнимы. Формула p₁ ∧ ¬p₁ невыполнима.

Как уже обсуждалось, Рисунок I.3 показывает, что p ∧ q → p ∨ q является тавтологией, а p ∨ q → p ∧ q выполнима, но не является тавтологией.

Может быть не сразу очевидно, что формула p₁ → p₂ → p₁ является тавтологией; один из способов проверить это - метод таблиц истинности. Рисунок I.4 показывает таблицу истинности, которая демонстрирует, что p₁ → p₂ → p₁ истинна при всех четырех возможных комбинациях значений φ(p₁) и φ(p₂).

В общем случае, если формула A содержит k различных переменных pᵢ₁, …, pᵢₖ, существует 2ᵏ способов установить значения φ(pᵢⱼ). Таблица истинности для A будет содержать 2ᵏ строк. Это дает алгоритм для определения, является ли данная формула A выполнимой и/или тавтологией: необходимо рассмотреть все возможные 2ᵏ присваиваний истинности φ переменным в A и вычислить φ(A). Тогда A является тавтологией тогда и только тогда, когда φ(A) = T для всех 2ᵏ присваиваний. И A выполнима тогда и только тогда, когда φ(A) = T хотя бы для одного присваивания истинности.

Пусть Γ обозначает множество пропозициональных формул. Часто интересно узнать, существует ли присваивание истинности, которое делает все формулы в Γ истинными.

Определение I.8. Множество Γ пропозициональных формул выполнимо, если существует присваивание истинности φ, такое что φ(A) = T для всех A ∈ Γ. Для такого φ мы говорим, что φ удовлетворяет (satisfies) Γ или что φ является выполняющим присваиванием для Γ, или что Γ выполняется при φ.

p₁	p₂	p₂→p₁	p₁→(p₂→p₁)
T	T	T	T
T	F	T	T
F	T	F	T
F	F	T	T

p₁	p₂	p₁→(p₂→p₁)
T	T	T
T	F	T
F	T	T
F	F	T

Рисунок I.4: Таблицы истинности, показывающие, что p₁ → p₂ → p₁ является тавтологией. Таблицы идентичны, но правая представлена в компактной форме. Значения, обведенные кружками, представляют значения истинности для всей формулы.

Множество Γ может быть как конечным, так и бесконечным. Если Γ конечно, Γ = {A₁, A₂, …, Aₖ}, то Γ выполняется при φ тогда и только тогда, когда φ удовлетворяет A₁ ∧ A₂ ∧ ⋯ ∧ Aₖ.

Если Γ конечно, то для определения его выполнимости можно использовать метод таблиц истинности. Однако если Γ бесконечно, метод таблиц истинности неприменим, поскольку в общем случае в Γ может быть бесконечно много переменных и потребовалось бы рассмотреть бесконечно много присваиваний истинности.

Пример I.9. Пусть Γ - множество формул: Γ = {pᵢ ↔︎ ¬pᵢ₊₁ ∶ i ≥ 1} = {p₁ ↔︎ ¬p₂, p₂ ↔︎ ¬p₃, p₃ ↔︎ ¬p₄, …}.

Существует ровно два выполняющих присваивания для Γ. Первое, φ₁, имеет:

φ₁(p₂ⱼ₋₁) = T и φ₁(p₂ⱼ) = F для всех j ≥ 1. Второе, φ₂, имеет: φ₂(p₂ⱼ₋₁) = F и φ₂(p₂ⱼ) = T для всех j ≥ 1.

Тавтологическая импликация. Тавтологическая импликация - это импликация, которая истинна при любом присваивании истинности. Формально это определяется следующим образом:

Определение I.10. Пусть A и B - формулы, а Γ - множество формул.

1. Мы говорим, что A тавтологически влечёт B (или просто A влечёт B для краткости), если каждое присваивание истинности, удовлетворяющее A, также удовлетворяет B. Мы пишем A ⊧ B, чтобы обозначить, что A тавтологически влечёт B.

2. Мы говорим, что Γ тавтологически влечёт B (или просто Γ влечёт B для краткости), если каждое присваивание истинности, удовлетворяющее Γ, также удовлетворяет B. Мы пишем Γ ⊧ B, чтобы обозначить, что Γ тавтологически влечёт B.

Разворачивая Определения I.8 и I.10(b), Γ ⊧ A означает то же, что: Для всех φ: если φ(B) = T для всех B ∈ Γ, то φ(A) = T.

Или, эквивалентно:

Для всех φ: если φ удовлетворяет Γ, то φ удовлетворяет A.

Символ “⊧” называется знаком “двойной турникет”. Заметим, что A ⊧ B означает то же самое, что {A} ⊧ B. Общепринято вольное обращение с обозначениями (стр. 16 “Логика высказываний: Синтаксис и семантика (Черновик B.2.e)”) и запись вида A, B ⊧ C вместо {A, B} ⊧ C, и Γ, A ⊧ B вместо Γ∪{A} ⊧ C. Во всех случаях это означает, что любое присваивание истинности, удовлетворяющее всем формулам и множествам формул слева от знака ⊧, также удовлетворяет формуле справа от знака ⊧. Наконец, мы пишем просто ⊧ A для ∅ ⊧ A, где ∅ - пустое множество формул. Условие ⊧ A выполняется тогда и только тогда, когда A является тавтологией.

Мы пишем Γ ⊭ A, чтобы обозначить, что Γ ⊧ A ложно.

Пример I.11. Некоторые примеры тавтологической (не)импликации с конечным множеством Γ включают:

1. p₁, p₁ → p₂ ⊧ p₂.
2. p₁, p₂ ⊧ p₂ ∧ p₁.
3. p₁ ⊭ p₂.
4. ⊧ p₁ → p₂ → p₁.
5. ⊭ (p₁ → p₂) → p₁.

Эти примеры могут быть проверены с помощью таблиц истинности. Заметим, что (a) означает то же самое, что {p₁, p₁ → p₂} ⊧ p₂, и аналогично для (b).

Пример I.12. Пусть Γ - множество формул из Примера I.9, а φ₁ и φ₂ - его два выполняющих присваивания. Тогда:

1. Γ ⊭ p₁ и Γ ⊭ ¬p₁.
2. Γ ⊧ p₁ ↔︎ p₃.

Условие (a) выполняется, поскольку φ₂(p₁) = F и φ₁(¬p₁) = F. Условие (b) выполняется, поскольку φ₁ и φ₂ - единственные выполняющие присваивания, и поскольку φᵢ(p₁) = φᵢ(p₃) и, следовательно, φᵢ(p₁ ↔︎ p₃) = T для обоих i = 1 и i = 2.

Теорема I.13. Предположим, что Γ и Δ - множества формул, и Γ ⊆ Δ.

1. Если φ удовлетворяет Δ, то φ удовлетворяет Γ.
2. Если Δ выполнимо, то Γ также выполнимо.
3. Если Γ ⊧ A, то Δ ⊧ A.

Теорема I.13 является непосредственным следствием определений.

Импликация из невыполнимого множества. Невыполнимое множество Γ тавтологически влечёт все формулы B:

Теорема I.14.

1. Пусть A и B - формулы. Тогда A,¬A ⊧ B.
2. Пусть B - формула, а Γ - невыполнимое множество формул. Тогда Γ ⊧ B.

Часть (a) является частным случаем части (b), поскольку {A,¬A} невыполнимо. Часть (b) доказывается наблюдением, что поскольку не существует присваивания истинности, удовлетворяющего Γ, определение тавтологической импликации означает, что Γ ⊧ B выполняется тривиально.

Тавтологически эквивалентные формулы. Две формулы “тавтологически эквивалентны”, если они тавтологически влекут друг друга:

Определение I.15. Мы пишем A ⊧= B, чтобы обозначить, что одновременно A ⊧ B и B ⊧ A. В этом случае мы говорим, что A и B тавтологически эквивалентны. Непосредственно из определений следует, что A ⊧= B выполняется тогда и только тогда, когда φ(A) = φ(B) для всех присваиваний истинности.

Семантическая теорема о дедукции. Следующая теорема является семантической версией того, что позже будет называться Теоремой о дедукции (см. раздел II.3).

Теорема I.16 (Семантическая теорема о дедукции). Пусть A и B - формулы, а Γ - множество формул. Тогда:

1. A ⊧ B тогда и только тогда, когда ⊧ A → B.
2. Γ, A ⊧ B тогда и только тогда, когда Γ ⊧ A → B.

Доказательство. Часть (a) является частным случаем (b) при Γ, равном пустому множеству. Докажем (b). Доказательство по сути просто раскрывает определения. Условие Γ, A ⊧ B означает, что для любого присваивания истинности φ, если φ удовлетворяет Γ∪{A}, то φ(B) = T. Эквивалентно это означает, что если φ удовлетворяет Γ и φ(A) = T, то φ(B) = T. По определению истинности для →, условие “если φ(A) = T, то φ(B) = T” эквивалентно φ(A → B) = T. Следовательно, Γ, A ⊧ B эквивалентно условию, что для всех φ, если φ удовлетворяет Γ, то φ(A → B) = T. Другими словами, это эквивалентно Γ ⊧ A → B.

Пример I.17. Возвращаясь к множеству Γ из примеров I.9 и I.12, имеем: Γ, p₁ ⊧ p₃ и Γ, p₃ ⊧ p₁.

Теорема I.18. Пусть Γ - конечное множество формул, Γ = {A₁, …, Aₖ}. Тогда Γ ⊧ B тогда и только тогда, когда A₁ ∧ A₂ ∧ ⋯ ∧ Aₖ ⊧ B.

Доказательство. Присваивание истинности φ удовлетворяет Γ тогда и только тогда, когда оно удовлетворяет A₁∧A₂∧⋯∧Aₖ. Следовательно, Γ ⊧ B тогда и только тогда, когда A₁ ∧ A₂ ∧ ⋯ ∧ Aₖ ⊧ B.

Теорема I.19. A ⊧= B тогда и только тогда, когда ⊧ A ↔︎ B.

Теорема I.19 непосредственно следует из Семантической теоремы о дедукции и того факта, что ⊧ A ↔︎ B выполняется тогда и только тогда, когда одновременно ⊧ A → B и ⊧ B → A.

Двойственность между выполнимостью и общезначимостью. Следующие две теоремы показывают, как свойство выполнимости двойственно свойству быть тавтологией.

Теорема I.20. Пусть A - формула. Тогда A является тавтологией тогда и только тогда, когда ¬A невыполнима.

Теорема I.20 является частным случаем следующей теоремы при Γ = ∅. Это предвестник теорем II.19 и II.21 о доказательстве от противного.

Теорема I.21. Пусть Γ — множество формул, и A — формула. Тогда Γ ⊧ A тогда и только тогда, когда Γ ∪ {¬A} невыполнимо.

Доказательство. Условие Γ ⊧ A означает, что каждое присваивание истинности φ, удовлетворяющее Γ, имеет φ(A) = T. Условие, что Γ∪{¬A} невыполнимо, эквивалентно условию, что каждое присваивание истинности, удовлетворяющее Γ, имеет φ(¬A) = F. Эти два условия очевидно эквивалентны.

3.5 I.5 Таблицы истинности

Мы уже видели несколько примеров таблиц истинности. Этот раздел обсудит, как записывать таблицы истинности более компактно, как формировать “сокращённые” таблицы истинности, которые могут требовать меньше строк, и как сокращённые таблицы истинности соответствуют деревьям решений.

Главная цель таблицы истинности - определить, является ли формула выполнимой или тавтологически общезначимой, или ни тем, ни другим. Для тавтологии A таблица истинности может служить доказательством, что A общезначима.

Существуют прямые алгоритмы для построения таблиц истинности и проверки их правильности. Алгоритм построения таблиц истинности работает примерно так. Входные данные - формула A. Алгоритм сначала разбирает A на подформулы и определяет различные переменные, появляющиеся в A. Если есть k различных переменных, алгоритм затем выписывает таблицу истинности с 2^k строками, по одной для каждого возможного присваивания значений истинности k переменным. Для каждого из 2^k присваиваний алгоритм использует определение истинности, чтобы вычислить значения истинности всех подформул A, начиная с пропозициональных переменных и продвигаясь к значению всей формулы A. Если значение A оказывается Истина (T) для всех 2^k присваиваний истинности, алгоритм выводит, что A - тавтология. В противном случае он выводит, что A не тавтология. Аналогично, если хотя бы одно присваивание делает значение A истинным, тогда A выполнима.

Это пример “эффективного” алгоритма, поскольку алгоритм даёт ответ, и правильный ответ, для любой входной формулы A. К сожалению, это не очень быстрый алгоритм, так как его время работы оказывается не менее 2^k просто потому, что он должен создать 2^k строк таблицы истинности. Таким образом, это так называемый алгоритм “экспоненциального времени”, и по мере роста k он быстро становится неосуществимым для выполнения, потому что слишком медленный.

Например, возраст Вселенной оценивается примерно в 13 миллиардов лет, что составляет примерно 4 × 10^26 наносекунд. Поэтому 2^88 примерно равно возрасту Вселенной в наносекундах. Таким образом, таблица истинности для формулы A с более чем примерно 100 переменными потребовала бы больше строк в своей таблице истинности, чем возраст Вселенной, измеренный в наносекундах. Это явно неосуществимо!

p	q	r	p → (q → r)	(p ∧ q) → r	(p → (q → r)) ↔︎ ((p ∧ q) → r)
T	T	T	T	T	T
T	T	F	F	F	T
T	F	T	T	T	T
T	F	F	T	T	T
F	T	T	T	T	T
F	T	F	T	T	T
F	F	T	T	T	T
F	F	F	T	T	T

Рисунок I.5: Компактная таблица истинности. Сплошная рамка показывает значения всей формулы. Пунктирные рамки показывают значения двух подформул p → q → r и (p ∧ q) → r. Необрамлённые столбцы дают значения истинности q → r и p ∧ q.

Компактная форма таблиц истинности. Рисунок I.3 и левая часть Рисунка I.4 дают два примера таблиц истинности в традиционной нотации. В этих таблицах истинности есть отдельный столбец для каждой подформулы оцениваемой формулы A. Правая часть Рисунка I.4 даёт таблицу истинности в более компактной форме. В этой таблице формула A (в данном случае p1 → p2 → p1) записана вверху правого столбца, но её подформулы не переписаны в отдельные столбцы. Значения истинности подформул A записаны под их главными связками. В этом случае значения истинности для подформулы p2 → p1 записаны под главной связкой → для подформулы. Аналогично, значения истинности для всей формулы записаны под главной связкой всей формулы, а именно под первым знаком → в A.

Рисунок I.5 показывает ещё один пример компактной таблицы истинности, для формулы (p → q → r) ↔︎ (p ∧ q → r). (I.1) Это показывает, что (I.1) - тавтология. Отсюда следует, что p → (q → r) и (p ∧ q) → r тавтологически эквивалентны (см. Теорему I.19).

Сокращённые таблицы истинности. Большой недостаток таблиц истинности в том, что они могут быть неудобно большими, с 2^k строками, когда есть k переменных. Во многих случаях возможно формировать “сокращённые” таблицы истинности с меньшим количеством строк. Сокращённые таблицы истинности основаны на том факте, что иногда установка значений всего нескольких переменных как Истина или Ложь достаточна, чтобы определить значение всей формулы. Например, на Рисунке I.5 формула будет истинной всякий раз, когда r истинно. Таким образом, когда r истинно, значения p и q не важны.

Это понимание позволяет нам сформировать сокращённую таблицу истинности, показанную на Рисунке I.6. Первая строка сокращённой таблицы истинности рассматривает случай, где φ(r) = T, а φ(p) и φ(q) не определены. В этой первой строке определение истинности утверждает, что φ(p ∧ q → r) должно равняться T независимо от значения истинности p ∧ q. Аналогично, φ(q → r) и φ(p → q → r) должны равняться T. Это позволяет нам заполнить достаточно записей в первой строке, чтобы определить, что вся формула имеет значение истинности T. Вторая строка рассматривает случай, где φ(r) = F и φ(q) = F и φ(p) не определено. Третья и четвёртая строки рассматривают два случая, где φ(r) = F и φ(q) = T и где φ(p) равно либо T, либо F.

Рисунок I.6 имеет вдвое меньше строк, чем Рисунок I.5, и всё же охватывает все релевантные случаи того, как установлено присваивание истинности.

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

Сокращённые таблицы истинности и деревья решений. Каждая строка в сокращённой таблице истинности для формулы A соответствует «частичному присваиванию истинности». Частичное присваивание истинности означает присвоение истинностных значений некоторому подмножеству пропозициональных переменных, входящих в A. Важным свойством сокращённых таблиц истинности является то, что частичные присваивания охватывают все возможные присваивания истинности, в том смысле, что каждое возможное присваивание истинности расширяет хотя бы одно из частичных присваиваний. Однако это порождает вопрос: как мы знаем, что частичные присваивания из сокращённой таблицы истинности охватывают все возможные присваивания.⁶

Поэтому желательно, чтобы сокращённые таблицы истинности использовали некоторый шаблон частичных присваиваний истинности, который гарантирует покрытие всех возможных присваиваний истинности. Один естественный способ сделать это — требовать, чтобы частичные присваивания истинности в сокращённой таблице соответствовали бинарному дереву решений. Бинарное дерево решений — это процедура, которая запрашивает истинностные значения переменных по одной: когда запрашивается переменная pᵢ, процедура получает истинностное значение φ(pᵢ) переменной pᵢ.

Вместо формального определения мы иллюстрируем это примером, основанным на сокращённой таблице истинности на рисунке I.6.

Бинарное дерево решений показано на рисунке I.7. Оно представляет процедуру, которая проходит по ветке дерева, начиная с корневого узла, запрашивая истинностное значение переменной в каждом узле и переходя по ребру, помеченному значением переменной, к дочернему узлу. Когда достигается листовой узел, значение формулы A становится известным.

Рисунок I.7: Дерево решений, соответствующее сокращённой таблице истинности из Рисунка I.6. Формула A имеет вид (p → q → r) → (p ∧ q → r). То, что все листья помечены φ(A) = T, указывает на то, что A является тавтологией.

Дерево решений на рисунке I.7 имеет корень с меткой r; это первая запрашиваемая переменная. От r исходят два ребра, следовательно, у r два потомка. Первое ребро помечено T, что означает, что по этому ребру переходят, когда φ(r) = T. Второе ребро помечено F, и по нему переходят, когда φ(r) = F. Один из потомков r — лист с меткой «φ(A) = T»: это указывает, что, достигнув этого листа, простые вычисления показывают, что вся формула A принимает значение T (а именно, вычисления из первой строки таблицы истинности на рисунке I.6).

Другой потомок r имеет метку q, значит, следующей переменной, которую запрашивают при φ(r) = F, является q. При запросе q её значение φ(q) может быть либо T, либо F. Процесс продолжается аналогично, пока не достигнут лист. В данном примере все листья помечены «φ(A) = T», поскольку формула является тавтологией.

Нам всё ещё нужно описать, какие «простые вычисления» можно использовать в листе дерева решений, чтобы определить значение A. Некоторые переменные формулы A уже будут иметь определённые истинностные значения T или F. Обозначим теперь «T» и «F» как подформулу A, значение которой уже определено как истинное или ложное. Мы допускаем следующие два способа определения дальнейших истинностных значений подформул A (пусть B — любая подформула A):

1. Любая подформула вида ¬F или (T ∨ B) или (B ∨ T) или (T ∧ T) или (F → B) или (B → T) или (F ↔︎ F) или (T ↔︎ T) может быть определена как истинная (T).

2. Любая подформула вида ¬T или (F ∨ F) или (F ∧ B) или (B ∧ F) или (T → F) или (F ↔︎ T) или (T ↔︎ F) может быть определена как ложная (F).

Если в конце значение истинности A определено, то текущий узел является допустимым листом дерева решений. Если же значение истинности A таким образом не определяется, требуется запросить дополнительные переменные.

3.6 I.6 Примеры тавтологий и тавтологических эквивалентностей

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

Простые тавтологии на одной переменной.

\(p \lor \neg p\) — Закон исключённого третьего

\(\neg (p \land \neg p)\) — Закон непротиворечия

\(p \to p\) — Самоимпликация

\(p \leftrightarrow p\) — Самоэквивалентность

\(\neg \neg p \leftrightarrow p\) — Двойное отрицание

\((\neg p \to p) \leftrightarrow p\) — Эквивалентность с импликацией из отрицания

Простые тавтологические эквивалентности.

\(\neg (p \lor q) \vDash= (\neg p \land \neg q)\) — Закон де Моргана

\(\neg (p \land q) \vDash= (\neg p \lor \neg q)\) — Закон де Моргана

\(p \lor p \vDash= p\) — Идемпотентность \(\lor\)

\(p \land p \vDash= p\) — Идемпотентность \(\land\)

\(p \land q \vDash= q \land p\) — Коммутативность \(\land\)

\(p \lor q \vDash= q \lor p\) — Коммутативность \(\lor\)

\(p \leftrightarrow q \vDash= q \leftrightarrow p\) — Коммутативность \(\leftrightarrow\)

\(p \land (q \land r) \vDash= (p \land q) \land r\) — Ассоциативность \(\land\)

\(p \lor (q \lor r) \vDash= (p \lor q) \lor r\) — Ассоциативность \(\lor\)

\(p \leftrightarrow (q \leftrightarrow r) \vDash= (p \leftrightarrow q) \leftrightarrow r\) — Ассоциативность \(\leftrightarrow\)

\(p \land (q \lor r) \vDash= (p \land q) \lor (p \land r)\) — Дистрибутивность \(\land\) относительно \(\lor\)

\(p \lor (q \land r) \vDash= (p \lor q) \land (p \lor r)\) — Дистрибутивность \(\lor\) относительно \(\land\)

\(p \to q \vDash= \neg q \to \neg p\) — Контрапозиция (или транспозиция)

\(p \to (q \to r) \vDash= (p \land q) \to r\) — Экспортирование

Некоторые тавтологии, часто используемые в качестве аксиом.
Здесь перечислены некоторые тавтологии, которые также используются как аксиомы в пропозициональных системах доказательств в стиле Гильберта. Они записаны с явными переменными \(p, q, r\); однако обычно система в стиле Гильберта допускает любую подстановку аксиомы как аксиому.

Существует множество других возможных аксиом, использовавшихся в системах пропозициональных доказательств; ниже перечислены лишь некоторые из них.

Глава II определяет систему доказательств в стиле Гильберта PL, которая использует (все подстановочные экземпляры) первых четырёх приведённых ниже тавтологий в качестве своих аксиом. Для второй аксиомы (и других) важно внимательно понимать, как следует расставить скобки, чтобы получить полностью скобочную формулу!

\(p \to (q \to p)\) — Аксиома для \(\to\). Аксиома PL (исчисления высказываний)

\((p \to q \to r) \to (p \to q) \to (p \to r)\) — Аксиома для \(\to\). Аксиома PL

\(\neg p \to (p \to q)\) — Аксиома для \(\neg\). Аксиома PL

\((\neg p \to p) \to p\) — Аксиома для \(\neg\). Аксиома PL

\((p \to q) \to (p \to \neg q) \to \neg p\) — Аксиома для \(\neg\)

\(p \land q \to p\) — Аксиома для \(\land\)

\(p \land q \to q\) — Аксиома для \(\land\)

\(p \to q \to (p \land q)\) — Аксиома для \(\land\)

\(p \to (p \lor q)\) — Аксиома для \(\lor\)

\(q \to (p \lor q)\) — Аксиома для \(\lor\)

\((p \to r) \to (q \to r) \to (p \lor q \to r)\) — Аксиома для \(\lor\)

\((p \to q) \to (r \lor p) \to (r \lor q)\) — Принцип суммирования (из Principia Mathematica)

\(((p \to q) \to p) \to p\) — Закон Пирса

Тавтологические эквивалентности, определяющие \(\lor\), \(\land\) и \(\leftrightarrow\). Следующие три тавтологические импликации могут быть использованы для определения \(\lor\), \(\land\) и \(\leftrightarrow\) через \(\neg\) и \(\to\).
Это соответствует факту, что множество связок \(\{ \neg, \to \}\) является полным,
как будет рассмотрено далее в Разделе I.7.

\(p \lor q \vDash= \neg p \to q\) — Определение \(\lor\) в PL

\(p \land q \vDash= \neg(p \to \neg q)\) — Определение \(\land\) в PL

\(p \leftrightarrow q \vDash= (p \to q) \land (q \to p)\) — Определение \(\leftrightarrow\) в PL

Некоторые тавтологические импликации, часто используемые при выводах. Любая корректная тавтологическая импликация может использоваться при выводах;следовательно, существует множество допустимых правил вывода.Некоторые из часто используемых приведены ниже:

\(p, \quad p \to q \vDash q\) — Modus Ponens

\(\neg q, \quad p \to q \vDash \neg p\) — Modus Tollens

\(p \to q, \quad q \to r \vDash p \to r\) — Гипотетический силлогизм

Система доказательств PL допускает только Modus Ponens в качестве правила вывода. Вывод по Modus Ponens записывается в форме:

\[ \begin{aligned} & A \\ & A \to B \\ \hline & B \end{aligned} \]

где \(A\) и \(B\) могут быть любыми правильно построенными формулами.Это правило вывода означает: если формулы \(A\) и \(A \to B\) уже выведены,то можно также вывести формулу \(B\).

Аналогично, Modus Tollens и гипотетический силлогизм соответствуют правилам вывода:

\[ \begin{aligned} & A \to B \\ & \neg B \\ \hline & \neg A \end{aligned} \quad\quad \begin{aligned} & A \to B \\ & B \to C \\ \hline & A \to C \end{aligned} \]

3.7 I.7 Булевы функции (Boolean Functions) и ДНФ (DNF) и КНФ (CNF)

В этом разделе будет показано, как булевы функции (Boolean functions) могут быть представлены пропозициональными формулами, и введены дизъюнктивная нормальная форма (Disjunctive Normal Form, DNF) и конъюнктивная нормальная форма (Conjunctive Normal Form, CNF).

Мотивация для рассмотрения булевых функций заключается в обосновании использования пяти связок ¬, ∧, ∨, → и ↔︎ для пропозициональных формул. Как первое наблюдение, на самом деле нет необходимости использовать все пять. Фактически, мы могли бы использовать только две связки ¬ и ∨, и всё равно смогли бы выразить всё, что можно выразить с помощью ¬,∧,∨, →,↔︎. Аналогично, мы могли бы использовать только ¬ и ∧, или только ¬ и →, без потери выразительности. (Эти факты будут доказаны позже в Теоремах I.36 и I.37.) С другой стороны, мы не могли бы опустить ¬, так как нет способа выразить отрицание, используя только ∧,∨, →,↔︎. (Для этого см. Теорему I.38 и Упражнение I.20.)

Это поднимает вопрос: достаточно ли использовать только ¬,∧,∨, →,↔︎? Может ли существовать какая-то другая связка помимо этих, которую нельзя выразить с помощью ¬,∧,∨, →,↔︎? Ответ на этот вопрос отрицательный: пять связок ¬,∧,∨, →,↔︎ могут выразить любую булеву функцию. Чтобы формализовать это, мы определяем понятие “булевой функции”. k-арная булева функция (k-ary Boolean function) может рассматриваться как тип k-арной пропозициональной связки. Наша первая цель будет доказать, что каждая булева функция может быть представлена пропозициональной формулой.

Определение I.22. Пусть k ≥ 1. k-арная булева функция (k-ary Boolean function) f принимает на вход k значений истина/ложь и выдает значение истина/ложь; а именно, это отображение f ∶ {T,F}^k → {T,F}.

Пример I.23. Следующие определения задают три булевы функции f¬p₁, fp₁∧p₂ и fp₁⊕p₂⊕p₃: \[\begin{array}{ll} f_{\lnot p_1}(x) = & \left\{ \begin{array}{ll} \text{T}, & \text{если } x = \text{F} \\ \text{F}, & \text{если } x = \text{T} \end{array} \right. \\[1.2em] f_{p_1 \land p_2}(x_1, x_2) = & \left\{ \begin{array}{ll} \text{T}, & \text{если } x_1 \text{ и } x_2 = \text{T} \\ \text{F}, & \text{в противном случае} \end{array} \right. \\[1.2em] f_{p_1 \oplus p_2 \oplus p_3}(x_1, x_2, x_3) = & \left\{ \begin{array}{ll} \text{T}, & \text{если нечётное число из } x_1, x_2, x_3 = \text{T} \\ \text{F}, & \text{если чётное число из } x_1, x_2, x_3 = \text{T} \end{array} \right. \end{array}\]

Заметим, что f¬p₁ является унарной (1-арной, unary), fp₁∧p₂ является бинарной (2-арной, binary), а fp₁⊕p₂⊕p₃ является 3-арной (3-ary).

Функции в примере названы fA, где подстрочный индекс A представляет собой формулу. Третья функция, p₁ ⊕ p₂ ⊕ p₃, использует “связку чётности” ⊕ (parity connective), также называемую “исключающее ИЛИ” или сокращённо “xor” (exclusive or). Связка чётности будет подробнее рассмотрена в следующем разделе; обозначение “⊕” происходит из того факта, что если T и F отождествить с константами 1 и 0, то ⊕ становится сложением по модулю 2.

Достаточность ¬,∨,∧,→,↔︎ (Adequacy of ¬,∨,∧,→,↔︎). Идея заключается в том, что формулы A в подстрочных индексах в предыдущем примере “представляют” булеву функцию.Это формализуется в следующем определении.

Определение I.24. Пусть k ≥ 1 и пусть A - пропозициональная формула, использующая (не более) переменные p₁, …, pₖ. k-арная булева функция (k-ary Boolean function) fₐ(x₁, x₂, …, xₖ) определяется как fₐ(x₁, …, xₖ) = φ(A), где φ(pᵢ) = xᵢ для i = 1, 2, …, k. Говорят, что пропозициональная формула A представляет (represents) булеву функцию fₐ.

Важно отметить, что это даёт корректное определение fₐ, поскольку значения оценки истинности (truth assignment) φ на p₁, …, pₖ однозначно определяют значение истинности φ(A) формулы A.⁷

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

Теорема I.25 (Достаточность ¬,∨,∧,→,↔︎ (Adequacy of ¬,∨,∧,→,↔︎)). Пусть f - k-арная булева функция. Тогда существует пропозициональная формула A, представляющая f, т.е. такая, что fₐ = f.

Сначала приведём пример, иллюстрирующий идею доказательства, а затем дадим общее доказательство. Рассмотрим булеву функцию f, определённую как

\[\begin{array}{ll} f(x_1, x_2) = & \left\{ \begin{array}{ll} \text{T}, & \text{если } x_1 = \text{T} \text{ или } x_2 = \text{F} \\ \text{F}, & \text{в противном случае} \end{array} \right. \end{array}\]

Можно заметить, что f совпадает с f_{p₂→p₁}, но предположим, что мы этого не заметили. Полная таблица значений f:

x₁	x₂	f(x₁, x₂)
T	T	T
T	F	T
F	T	F
F	F	T

В таблице три строки, где f(x₁, x₂) = T. Это говорит нам, что f(x₁, x₂) истинна точно тогда, когда x₁ = x₂ = T, когда x₁ = T и x₂ = F, и когда x₁ = x₂ = F. Другими словами, f(x₁, x₂) представляется формулой (p₁ ∧ p₂) ∨ (p₁ ∧ ¬p₂) ∨ (¬p₁ ∧ ¬p₂). (I.2)

Первый дизъюнкт формулы (I.2) - p₁ ∧ p₂; он истинен точно тогда, когда применима первая строка таблицы значений f. Второй и третий дизъюнкты аналогично соответствуют двум другим случаям, когда f истинна.

Кстати, формула (I.2) вероятно не является “наилучшей” формулой, представляющей f. Например, p₁ ∨ ¬p₂ вероятно был бы лучшим выбором. Но (I.2) - это формула, представляющая f, которая получается из общего доказательства, которое мы приведём далее.

Доказательство Теоремы I.25. Пусть f - k-арная булева функция (k-ary Boolean function). Если f(x₁, …, xₖ) = F для всех входов x₁, …, xₖ ∈ {T, F}, то f представляется формулой p₁ ∧ ¬p₁.

Предположим, что существует хотя бы один вход, где значение f равно T. Поскольку f имеет k входов, каждый из которых может принимать два значения, существует 2ᵏ различных входов для f. Пусть φ₁, …, φ₂ₖ - все возможные оценки истинности (truth assignments) для p₁, …, pₖ. Хотя это не важно для доказательства, может быть полезно представлять φ₁ как оценку, которая устанавливает каждое pᵢ в T, а φ₂ₖ - как оценку, устанавливающую каждое pᵢ в F, а остальные φᵢ - как оценки, перечисленные в обычном порядке строк таблицы истинности.

Для 1 ≤ i ≤ 2ᵏ и 1 ≤ j ≤ k определим формулу Lᵢⱼ как:

\[ L_{ij} = \left\{ \begin{array}{ll} p_j, & \text{если } \varphi_i(p_j) = \text{T} \\ \lnot p_j, & \text{если } \varphi_i(p_j) = \text{F} \end{array} \right. \]

(Буква “L” означает “литерал” (literal)). Очевидно, Lᵢⱼ - это либо pⱼ, либо ¬pⱼ, и φᵢ(Lᵢⱼ) = T. Теперь определим⁸:

\[\begin{array}{ll} C_i = \bigwedge_{j=1}^k L_{ij} := L_{i1} \wedge L_{i2} \wedge \cdots \wedge L_{ik} \end{array}\]

Мы имеем φᵢ(Cᵢ) = T, так как φᵢ(Lᵢⱼ) = T для всех j. Более того, если i ≠ i’, то φᵢ’(Cᵢ) = F. Это потому что φᵢ’(pⱼ) ≠ φᵢ(pⱼ) хотя бы для одного значения j, и следовательно φᵢ’(Lᵢ’ⱼ) = F хотя бы для одного j.

Пусть I - множество значений i таких, что: f(φᵢ(p₁), φᵢ(p₂), …, φᵢ(pₖ)) = T.

Мы можем записать I = {i₁, i₂, …, iℓ}. Заметим, что ℓ ≥ 1, так как f не тождественно равна F для всех входов. Тогда определим формулу A как:

\[\begin{array}{ll} A = \bigvee_{m=1}^\ell C_m & := C_{i1} \vee C_{i2} \vee \cdots \vee C_i \end{array}\]

(I.3)

При проверке видно, что A представляет функцию f: это потому что Cᵢₘ и соответствующие им оценки истинности φᵢₘ перечисляют случаи, когда f истинна, и потому что каждая Cᵢ удовлетворяется уникальной φᵢ. Это завершает доказательство Теоремы I.25.

Дизъюнктивная и конъюнктивная нормальные формы (Disjunctive and conjunctive normal forms). Теорема I.21 показала, что каждая функция может быть представлена формулой, использующей только связки ¬, ∨ и ∧. Фактически, она показывает, что достаточно “дизъюнктивных нормальных форм” (disjunctive normal form). Любая формула A, выраженная в виде: A₁ ∨ A₂ ∨ ⋯ ∨ Aₖ,

с произвольной расстановкой скобок, называется дизъюнкцией (disjunction). Допускается случай, когда k = 1. Каждая Aᵢ называется дизъюнктом (disjunct) формулы A.

Мы будем использовать обозначение “большого ИЛИ” ⋁ᵢ₌₁ᵏ Aᵢ для обозначения A; однако это обозначение часто зарезервировано для случая, когда расстановка скобок соответствует обычному порядку справа налево.

Аналогично, любая формула B, выраженная в форме: B₁ ∧ B₂ ∧ ⋯ ∧ Bₖ, также с произвольной расстановкой скобок, не обязательно ассоциированной справа налево, называется конъюнкцией (conjunction). Каждая Bᵢ называется конъюнктом (conjunct) формулы B. Мы будем использовать обозначение “большого И” ⋀ᵢ₌₁ᵏ Bᵢ для обозначения B; однако, опять же, часто с расстановкой скобок в обычном порядке справа налево.

Определение I.26. Литерал (literal) - это формула вида pᵢ или ¬pᵢ. Другими словами, литерал - это переменная или отрицание переменной.

Определение I.27. Конъюнкция литералов (conjunction of literals) - это формула вида⁹: L₁ ∧ L₂ ∧ ⋯ ∧ Lₖ, где k ≥ 1 и каждый Lᵢ - литерал.

Дизъюнктивная нормальная форма (Disjunctive Normal Form, DNF) - это любая формула вида: C₁ ∨ C₂ ∨ ⋯ ∨ Cℓ, где ℓ ≥ 1 и каждая Cᵢ - конъюнкция литералов.

Определение I.28. Клоз (clause) - это дизъюнкция литералов, а именно формула вида: L₁ ∨ L₂ ∨ ⋯ ∨ Lₖ, где k ≥ 1 и каждый Lᵢ - литерал.

Конъюнктивная нормальная форма (Conjunctive Normal Form, CNF) - это любая формула вида: C₁ ∧ C₂ ∧ ⋯ ∧ Cℓ, где ℓ ≥ 1 и каждая Cᵢ - клоз.

Теорема I.25 показывает, что каждая булева функция f может быть представлена пропозициональной формулой. Фактически, доказательство показывает, что пропозициональная формула, представляющая f, может быть взята в форме DNF. То есть, мы уже доказали следующую теорему.

Теорема I.29 (Достаточность DNF формул (Adequacy of DNF Formulas)). Пусть f - k-арная булева функция. Тогда существует формула в дизъюнктивной нормальной форме (DNF) A, которая представляет f, т.е. такая, что fₐ = f.

Доказательство. Доказательство Теоремы I.25 уже установило этот факт. Если f - константная функция F, то p₁ ∧ ¬p₁ представляет f; эта формула является DNF-формулой (и также CNF-формулой). В противном случае, формула (I.3) является DNF-формулой, представляющей f.

Аналогичное утверждение верно и для CNF-формул:

Теорема I.30 (Достаточность CNF-формул (Adequacy of CNF Formulas)). Пусть f - k-арная булева функция. Тогда существует формула в конъюнктивной нормальной форме (CNF) A, которая представляет f, т.е. такая, что fₐ = f.

Доказательство. (Набросок) Доказательство Теоремы I.25 может быть переработано для непосредственного доказательства этого утверждения, используя строки таблицы истинности для f, где f принимает значение F. Однако вместо этого мы набросаем, как получить Теорему I.30 как следствие Теоремы I.29.

Пусть f¬ - k-арная булева функция, являющаяся отрицанием f. То есть:

\[\begin{array}{ll} f_{^\neg}(x_1, \ldots, x_k) = \begin{cases} \mathrm{T}, & \text{если } f(x_1, \ldots, x_k) = \mathrm{F} \\ \mathrm{F}, & \text{если } f(x_1, \ldots, x_k) = \mathrm{T} \end{cases} \end{array}\]

Мы только что доказали, что f¬ представляется DNF-формулой A. Следовательно, f представляется формулой ¬A. Формула ¬A - это отрицание дизъюнкции конъюнкций литералов. По законам де Моргана (см. Раздел I.6), отрицание конъюнкции формул тавтологически эквивалентно дизъюнкции отрицаний тех же формул. Аналогично, отрицание дизъюнкции формул тавтологически эквивалентно конъюнкции отрицаний тех же формул. Более того, отрицание литерала очевидно эквивалентно литералу (возможно, с сокращением двух знаков отрицания).

Это позволяет переписать ¬A как тавтологически эквивалентную CNF-формулу, используя законы де Моргана для “проталкивания” знака отрицания внутрь формулы. Детали мы оставляем читателю.

Следствие I.31. Любая пропозициональная формула A тавтологически эквивалентна некоторой дизъюнктивной нормальной форме (DNF) формуле, а также тавтологически эквивалентна некоторой конъюнктивной нормальной форме (CNF) формуле.

Доказательство. Пусть p₁, …, pₖ включают все переменные в A. Пусть fₐ - k-арная булева функция, представляемая A. По Теореме I.29, fₐ представляется некоторой DNF-формулой B. Тогда, поскольку A и B представляют одну и ту же булеву функцию, должно выполняться φ(A) = φ(B) для всех оценок истинности. Следовательно, A и B тавтологически эквивалентны.

Доказательство того, что A тавтологически эквивалентна некоторой CNF-формуле C, аналогично, за исключением того, что используется Теорема I.30 для получения CNF-формулы C, определяющей fₐ.

Пример I.32. Пусть f_{p₁↔︎p₂} - булева функция, представляемая p₁ ↔︎ p₂. Мы имеем f(x₁, x₂) = T точно тогда, когда либо x₁ и x₂ оба равны T, либо x₁ и x₂ оба равны F. Следовательно, используя конструкцию из доказательства Теоремы I.25, f_{p₁↔︎p₂} представляется формулой: (p₁ ∧ p₂) ∨ (¬p₁ ∧ ¬p₂). (I.4)

Следовательно, p₁ ↔︎ p₂ тавтологически эквивалентна этой формуле (I.4).

Аналогичные рассуждения показывают, что f¬{p₁↔︎p₂} = f{¬(p₁↔︎p₂)} представляется DNF-формулой: (¬p₁ ∧ p₂) ∨ (p₁ ∧ ¬p₂). (I.5)

Отрицание этого выражения представляет f_{p₁↔︎p₂}. Мы можем использовать законы де Моргана, чтобы получить CNF-формулу, представляющую f_{p₁↔︎p₂}, следующим образом: ¬[(¬p₁ ∧ p₂) ∨ (p₁ ∧ ¬p₂)] Отрицание (I.5) ⊧= [¬(¬p₁ ∧ p₂) ∧ ¬(p₁ ∧ ¬p₂)] Закон де Моргана ⊧= [(¬¬p₁ ∨ ¬p₂) ∧ (¬p₁ ∨ ¬¬p₂)] Закон де Моргана ⊧= [(p₁ ∨ ¬p₂) ∧ (¬p₁ ∨ p₂)] Двойное отрицание

Таким образом, (p₁∨¬p₂)∧(¬p₁∨p₂) является CNF-формулой, представляющей f_{p₁↔︎p₂}, и поэтому тавтологически эквивалентна p₁ ↔︎ p₂.

Теорема I.30 была доказана путем начала с DNF-формулы, представляющей отрицание функции f¬, добавления знака отрицания и использования законов де Моргана для преобразования ее в эквивалентную CNF-формулу. Альтернативный способ доказательства этой теоремы состоял бы в том, чтобы начать с DNF-формулы для f (не для отрицания функции f¬), а затем применить дистрибутивные законы для ∨ и ∧ и закон исключенного третьего для преобразования в CNF.

В качестве примера мы только что видели, что (p₁ ∧ p₂) ∨ (¬p₁ ∧ ¬p₂) является DNF-формулой, представляющей f_{p₁↔︎p₂}. Это может быть преобразовано с использованием дистрибутивных законов следующим образом, используя ⊺ как константу со значением истины T: [p₁ ∧ p₂] ∨ (¬p₁ ∧ ¬p₂) DNF-формула (I.5) ⊧= ([p₁ ∧ p₂] ∨ ¬p₁) ∧ ([p₁ ∧ p₂] ∨ ¬p₂), Дистрибутивный закон ⊧= (p₁ ∨ ¬p₁) ∧ (p₂ ∨ ¬p₁) ∧ (p₁ ∨ ¬p₂) ∧ (p₂ ∨ ¬p₂), Дистрибутивный закон ⊧= ⊺ ∧ (p₂ ∨ ¬p₁) ∧ (p₁ ∨ ¬p₂) ∧ ⊺, Закон исключенного третьего ⊧= (p₂ ∨ ¬p₁) ∧ (p₁ ∨ ¬p₂), ⊺ ∧ A ⊧= A

Итоговая формула является другой CNF-формулой для f_{p₁↔︎p₂}; она совпадает с полученной в предыдущем примере после применения коммутативности ∨.

Бинарные деревья решений для нетождественно истинных формул. Пример на Рисунке I.7 дал сокращенное дерево решений для тавтологии. Также возможно дать дерево решений для формул, которые не являются тавтологиями; например, см. Рисунок I.8. Поскольку A выполнима, но не является тавтологией, некоторые листья помечены как φ(A) = T, а некоторые как φ(A) = F.

Легко преобразовать функцию с деревом решений типа показанного на Рисунке I.8 в DNF-формулу. Мы оставляем детали Упражнению I.40, но идея состоит в том, что каждая ветвь в дереве решений, ведущая к листу с пометкой φ(A) = T, соответствует дизъюнкту в дизъюнктивной нормальной форме, тавтологически эквивалентной A.

Рисунок I.8: Упрощённая таблица истинности и бинарное дерево решений для формулы, которая не является тавтологией. Формула тавтологически эквивалентна DNF-формуле r ∨ (¬r ∧ ¬q ∨ p).

3.8 I.8 Пропозициональные языки (Propositional Languages)

Языки и достаточность (Languages and adequacy). Множество L пропозициональных связок называется языком. До сих пор мы работали с языком L = {¬,∧,∨,→,↔︎}; однако мы уже упоминали несколько других связок, таких как ⊕ (чётность, parity), ⊺ (константа T) и ⊥ (константа F).

Определение I.33. Пусть L - (пропозициональный) язык. L-формула (L-formula) - это пропозициональная формула, использующая только пропозициональные связки из L.

До сих пор в этой главе “формула” всегда означала “{¬,∨,∧,→,↔︎}-формулу”. В Главе II будет использоваться другое соглашение; там “формула” будет означать “{¬,→}-формулу”.

Определение I.34. Язык L называется достаточным (adequate), если каждая булева функция представляется некоторой L-формулой.

Мы уже доказали, что несколько языков являются достаточными:

Теорема I.35. Языки {¬,∨,∧,→,↔︎} и {¬,∨,∧} оба являются достаточными.

Доказательство. Первая часть теоремы уже была сформулирована как Теорема I.25. Вторая часть является следствием Теорем I.29 или I.30.

Заметим, что если L₁ ⊂ L₂ и L₁ достаточен, то и L₂ также достаточен. Это непосредственно следует из того факта, что каждая L₁-формула является L₂-формулой.

Последняя теорема может быть усилена:

Теорема I.36. Языки {¬,∨} и {¬,∧} оба являются достаточными.

Доказательство. Пусть f - булева функция. Покажем, что f представляется некоторой {¬,∨}-формулой. По Теореме I.30, f представляется CNF-формулой A, которая имеет вид C₁ ∧ C₂ ∧ … ∧ Cₖ, где все Cᵢ являются дизъюнктами (clauses) и, следовательно, все являются {¬,∨}-формулами. Используя закон де Моргана, A тавтологически эквивалентна ¬(¬C₁ ∨ ⋯ ∨ ¬Cₖ}. Это {¬,∨}-формула, которая представляет f.

Тот факт, что f также представляется некоторой {¬,∧}-формулой, доказывается аналогично.

Теорема I.37. Язык {¬,→} является достаточным (adequate).

Доказательство. Поскольку {¬,∨} достаточен, достаточно показать, что каждая {¬,∨}-формула A тавтологически эквивалентна {¬,→}-формуле. Для этого мы используем тот факт, что B ∨ C тавтологически эквивалентно ¬B → C для любых B и C.

Конкретно, преобразуем формулу A, многократно выбирая подформулу вида (B ∨ C) и заменяя её на (¬B → C). Каждая такая замена удаляет одну связку ∨ и добавляет связку ¬ и связку →. Таким образом, процедура завершается {¬,→}-формулой, тавтологически эквивалентной A.¹⁰

Теперь приведём примеры нескольких языков, которые не являются достаточными.

Теорема I.38.

1. {¬} не является достаточным.
2. {∧,∨} не является достаточным.

Доказательство. Для (a) заметим, что {¬}-формула A должна иметь вид ¬⋯¬pᵢ (с нулём или более символами ¬, применёнными к переменной). Поскольку только одна переменная появляется в A, она не может быть тавтологически эквивалентна формуле типа p₁ ∧ p₂, которая зависит от более чем одной переменной. Следовательно, никакая {¬}-формула не может представлять, например, f_{p₁∧p₂}.

Для (b) пусть A - любая {∧,∨}-формула. Мы утверждаем, что если φ(pᵢ) = T для всех i, то φ(A) = T. Это утверждение подразумевает, что A не может представлять f_{¬p₁}, поскольку f_{¬p₁} = F, когда φ(pᵢ) = T для всех i.

Зафиксируем φ как оценку, для которой φ(p₁) = T для всех i. Нам нужно доказать утверждение, что для любой {∧,∨}-формулы A, φ(A) = T. Доказательство проводится индукцией по сложности A.

Базовый случай: A - переменная pᵢ. Тогда φ(A) = T по выбору φ.

Шаг индукции: A имеет вид (B∨C) или (B∧C). Есть две индукционные гипотезы - для B и для C: они утверждают, что φ(B) = T и φ(C) = T. Следовательно, по определениям истинности для ∨ и для ∧, мы должны иметь φ(A) = T.

Это завершает доказательство утверждения и части (b) теоремы.

Другие пропозициональные связки. Существует множество других пропозициональных связок, которые могут использоваться в дополнение к стандартным ¬, ∨, ∧, → и ↔︎.

Связка чётности (parity connective) ⊕ определяется так:

\[\begin{array}{ll} \varphi(A \oplus B) = \begin{cases} \mathrm{T}, & \text{если } \varphi(A) \ne \varphi(B) \\ \mathrm{F}, & \text{если } \varphi(A) = \varphi(B) \end{cases} \end{array}\]

Обозначение “⊕” отражает тот факт, что при отождествлении T и F с 1 и 0 (соответственно), ⊕ соответствует сложению по модулю два. Другое название для связки чётности ⊕ - “исключающее ИЛИ” (exclusive or), поскольку φ(A ⊕ B) истинно тогда и только тогда, когда ровно одно из φ(A) или φ(B) истинно. В Упражнении I.26 требуется показать, что A ⊕ B ⊧= ¬(A ↔︎ B).

Ещё одна очень интересная связка - nand, обозначаемый “∣”. Она также называется штрихом Шеффера (Sheffer stroke) в честь её первооткрывателя Г. Шеффера. “Nand” означает “не-и” (not-and). Как следует из названия, p∣q имеет значение истинности, равное отрицанию конъюнкции p и q, так что для всех φ:

φ(A∣B) = φ(¬(A ∧ B)).

Примечательным аспектом связки ∣ является то, что она достаточна сама по себе:

Теорема I.39. {∣} является достаточным (adequate).

Доказательство. Легко проверить, что ¬A тавтологически эквивалентно A∣A. Более того, A ∧ B тавтологически эквивалентно ¬(A∣B), а значит и (A∣B)∣(A∣B). Таким образом, любая {¬,∧}-формула может быть преобразована в тавтологически эквивалентную {∣}-формулу путём замены подформул вида ¬A на (A∣A) и подформул вида (A ∧ B) на ((A∣B)∣(A∣B)).

Теорема I.36 показала, что {¬,∧} достаточен; следовательно, {∣} также достаточен.

В Упражнении I.24 определяется двойственная связка nor (↓) и предлагается доказать, что {↓} достаточен.

Две очень простые связки - это константы ⊺ и ⊥. Это 0-арные (nullary) связки, которые не принимают аргументов. Их значения истинности определяются как φ(⊺) = T и φ(⊥) = F.

Теорема I.40. {⊥, →} является достаточным.

Доказательство. Любая отрицательная формула ¬A тавтологически эквивалентна A →⊥. Поскольку {¬, →} достаточен (по Теореме I.37), следует, что {⊥, →} также достаточен.

До сих пор мы рассматривали примеры 0-арных, 1-арных и 2-арных связок. Также возможны k-арные связки для k > 2. Один пример - 3-арная связка Case(⋅, ⋅, ⋅); её также можно назвать связкой “if-then-else” (если-то-иначе). Значение истинности Case(A, B, C) определяется как:

\[\begin{array}{ll} \varphi(\mathrm{Case}(A, B, C)) = \begin{cases} \varphi(B), & \text{если } \varphi(A) = \mathrm{T} \\ \varphi(C), & \text{если } \varphi(A) = \mathrm{F} \end{cases} \end{array}\]

Это означает, что Case(A, B, C) можно интерпретировать как “Если A, то B, иначе C”. Легко проверить, что Case(p, q, r) тавтологически эквивалентна: - DNF-формуле (p∧q)∨(¬p∧r) - Ввиду эквивалентности с “Если A, то B, иначе C”, также тавтологически эквивалентна (p → q) ∧ (¬p → r) - Следовательно, тавтологически эквивалентна CNF-формуле (¬p ∨ q) ∧ (p ∨ r)

В Упражнении I.28 предлагается доказать, что {¬, Case} достаточен, но {Case} не является достаточным.

Примером k-арной связки для произвольного фиксированного k ≥ 1 является мажоритарная связка (majority connective) Majₖ. Семантика для мажоритарных связок определяется следующим образом: Majₖ(A₁, …, Aₖ) истинна в точности тогда, когда количество истинных Aᵢ ≥ k/2.

Упражнение I.29 рассматривает вопрос достаточности (adequacy) Majₖ в сочетании с ¬.

3.9 I.9 Примеры доказательств по индукции (Proofs by Induction)

В этом разделе приведены некоторые примеры доказательств по индукции на сложности формул. Доказательство Теоремы I.38 уже использовало доказательство по индукции. Кроме того, мы уже использовали некоторые “очевидные” свойства формул, которые, строго говоря, должны были быть доказаны по индукции. Наиболее важными из них являются:

1. Свойство уникальной читаемости (unique readability property) (которое необходимо для рекурсивных определений)
2. Факт, что истинность формулы A зависит только от значений истинности переменных, фактически присутствующих в A

Последний факт использовался несколько раз (например, в Определении I.24 и Теореме I.38(a)), и что более важно - для обоснования того, что таблицы истинности требуют только конечного числа строк. Мы начинаем с доказательства того, что истинность A зависит только от значений истинности переменных, присутствующих в A.

Теорема I.41.. Пусть A - пропозициональная формула. Предположим, что φ и φ’ - оценки истинности, такие что для каждой pᵢ, присутствующей в A, выполняется φ(pᵢ) = φ’(pᵢ). Тогда φ(A) = φ’(A).

Альтернативная формулировка гипотезы: φ(pᵢ) ≠ φ’(pᵢ) только если pᵢ не появляется в A.

Доказательство (по индукции на сложности A):

Базовый случай: A - переменная pᵢ. Очевидно, pᵢ присутствует в A, поэтому φ(A) = φ’(A) по условию на φ и φ’.

Шаг индукции #1: A имеет вид ¬B. Любая переменная из B присутствует в A, поэтому φ и φ’ совпадают на всех переменных из B. По предположению индукции φ(B) = φ’(B), следовательно φ(A) = φ’(A) по определению истинности для ¬.

Шаг индукции #2: A имеет вид B ○ C, где ○ ∈ {∨, ∧, →, ↔︎}. Любая переменная из B или C присутствует в A. Имеем две индукционные гипотезы:
- φ(B) = φ’(B)
- φ(C) = φ’(C)

Следовательно, φ(A) = φ’(A) по определению истинности для ○.

Заметим, как базовый случай и шаги индукции соответствуют индуктивному определению пропозициональных формул (Определение I.1). Доказательство охватывает четыре бинарные связки одним аргументом.

Теорема I.42.. Для любой формулы A количество открывающих скобок равно количеству закрывающих скобок. Эта теорема, конечно, очевидна просто потому, что индуктивное определение пропозициональных формул парно согласовывает открывающие и закрывающие скобки. Однако формальное доказательство использует индукцию.

Доказательство. Мы будем использовать mₐ и nₐ для обозначения количества открывающих и закрывающих скобок в A (соответственно). Доказательство проводится по индукции.

Базовый случай: Предположим, A - это pᵢ. Скобок нет, и mₐ = 0 = nₐ.

Шаг индукции #1: Предположим, A - это ¬B. Индукционная гипотеза гласит, что m_B = n_B. Очевидно, A имеет то же количество открывающих и закрывающих скобок, что и B. Следовательно, mₐ = nₐ.

Шаг индукции #2: Предположим, A - это (B ○ C), где ○ - одна из связок ∨, ∧, → или ↔︎. Есть две индукционные гипотезы: - m_B = n_B - m_C = n_C

В A на одну пару открывающих/закрывающих скобок больше, чем в B и C вместе взятых. Таким образом:

mₐ = m_B + m_C + 1 nₐ = n_B + n_C + 1

Откуда следует, что mₐ = nₐ.

Следующая теорема менее тривиальна и также служит основой для доказательства свойства уникальной читаемости (unique readability property). Напомним, что формула A - это выражение, то есть строка символов. Непустое собственное начальное подвыражение (non-empty, proper initial subexpression) A - это любой префикс строки символов в A, который содержит хотя бы один символ, но не совпадает со всей A. Например: - “(”, - “(p₁”, - “(p₁∧”, - “(p₁ ∧ p₂”

являются всеми непустыми собственными начальными подвыражениями для “(p₁ ∧ p₂)”.

Теорема I.43. Пусть A - формула, первый символ которой - открывающая скобка. Пусть B - непустое собственное начальное подвыражение A. Тогда B содержит больше открывающих скобок, чем закрывающих. Следовательно, B не является пропозициональной формулой.

Упражнения I.36-I.38 предлагают доказать Теорему I.43 и свойство уникальной читаемости.

Последний пример теоремы, которая может быть доказана по индукции:

Теорема I.44. Пусть A - формула. Предположим, A содержит m вхождений бинарных связок и n вхождений пропозициональных переменных. Докажите, что n = m + 1.

Упражнение I.39 предлагает доказать эту теорему.

3.10 I.10 Пропозициональная подстановка (Propositional Substitution)

Подстановка в пропозициональные формулы означает подстановку формулы B вместо переменной pᵢ внутри некоторой формулы A. Другими словами, это означает замену переменной p в A формулой B.

Существует несколько причин, чтобы внимательно рассмотреть подстановку. Во-первых, нам нужно доказать, что если A — тавтология, то формула, полученная подстановкой B вместо каждого вхождения p в A, также будет тавтологией. Это будет важно для системы доказательств PL, определённой в следующей главе.

Во-вторых, нам нужно доказать, что если B и C тавтологически эквивалентны, и мы заменим вхождение B в качестве подформулы формулы A на C, то результат будет тавтологически эквивалентен A. Это — факт, который мы уже использовали более одного раза, в частности в разделе I.8 при обсуждении адекватных множеств связок (adequate sets of connectives). Например, доказательство Теоремы I.37 заменяло подформулы B ∨ C на ¬B → C и утверждало, что это сохраняет тавтологическую эквивалентность.

Третья причина состоит в том, что изучение подстановки пропозициональных формул вместо переменных даст нам представление о проблемах, с которыми мы столкнёмся при подстановке в логике первого порядка (first-order logic) в последующих главах.

Мы используем обозначение A(B/p), чтобы обозначить формулу, полученную из A после замены каждого вхождения переменной p в A формулой B. Более общо, мы пишем A(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ), чтобы обозначить результат параллельной замены каждого вхождения каждой pᵢ в A на Bᵢ. Формальное определение приводится ниже, но сначала рассмотрим несколько примеров.

Пример I.45 Пусть A — формула (p₁ → (p₂ → p₁)). Если взять B = ((p₂ ∧ p₃) → p₁), то A(((p₂ ∧ p₃) → p₁)/p₁) — это формула

(((p₂ ∧ p₃) → p₁) → (p₂ → ((p₂ ∧ p₃) → p₁))).

Как показывает этот пример, допустимо, чтобы p₁ появлялась в B.

Другой пример: A(p₁/p₁) совпадает с A.

Наконец, пусть C = (p₂ ∧ p₃) и D = (p₁ ∧ p₄). Тогда A(C, D/p₁, p₂) — это формула

((p₂ ∧ p₃) → ((p₁ ∧ p₄) → (p₂ ∧ p₃))).

Обратите внимание, что оба p₁ в A были заменены на C, а p₂ в A был заменён на D. Но p₁ и p₂, появляющиеся в C и D, не изменяются. Это отражает тот факт, что подстановка C и D вместо вхождений p₁ и p₂ выполняется «параллельно».

Если бы подстановки выполнялись последовательно (sequentially), а не параллельно, мы бы использовали обозначение A(C/p₁)(D/p₂). Это означало бы сначала подставить C вместо p₁ в A, а затем подставить D вместо p₂ в полученной формуле. Убедитесь сами, что это то же самое, что и A(C′/p₁, D/p₂), где C′ = C(D/p₂).

Определение I.46 Пусть k ≥ 1, и A, B₁, …, Bₖ — пропозициональные формулы, а pᵢ₁, …, pᵢₖ — (разные) пропозициональные переменные. Тогда формула A(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ) определяется рекурсивно следующим образом:

(a) Если A — это переменная pᵢⱼ для некоторого 1 ≤ j ≤ k, тогда
A(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ) есть Bⱼ.

(b) Если A — переменная p_ℓ, где ℓ ∉ {i₁, …, iₖ}, тогда
A(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ) есть p_ℓ. Другими словами, A не изменяется подстановкой.

(c) Если A есть ¬C, тогда
A(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ) есть
¬C(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ).
Иными словами, это ¬C′, где C′ есть C(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ).

(d) Если A есть C ○ D для некоторой бинарной связки ○, тогда
A(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ) есть
C(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ) ○ D(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ).
Другими словами, это C′ ○ D′, где C′ определена как выше, а D′ = D(B₁, …, Bₖ/pᵢ₁, …, pᵢₖ).

Читателю следует учесть, что иногда используются различные обозначения для подстановки (substitution). Например, некоторые авторы могут ввести формулу A как A = A(p) и затем писать A(B), чтобы обозначить то, что мы называем A(B/p). Такое обозначение A(B) менее загромождено и более читаемо, но оно имеет недостаток в виде некоторой неоднозначности — означает ли A(B) замену всех вхождений p на B или только некоторых. Пока что мы будем придерживаться обозначения A(B/p), и оно всегда означает замену всех вхождений p.

Определение I.47. Любая формула вида A(B/pᵢ) называется экземпляром (instance) формулы A.

Следующая теорема утверждает, что если B и C имеют одно и то же значение истинности, тогда формулы A(B/p) и A(C/p) также имеют одинаковое значение истинности. Это простой результат, но он представляет собой ключевой факт, необходимый для доказательства остальных наших теорем о подстановке пропозициональных формул.

Теорема I.48 Пусть A, B и C — формулы, а pᵢ — переменная. Также пусть φ — присваивание истинности. Если
φ(B) = φ(C), тогда
φ(A(B/pᵢ)) = φ(A(C/pᵢ)).

Доказательство Пусть B, C, pᵢ и φ заданы. Докажем, что теорема выполняется для всех A, используя индукцию по A.

Базовый случай №1: Предположим, что A — это пропозициональная переменная pᵢ. Тогда A(B/pᵢ) и A(C/pᵢ) — это просто B и C. Следовательно, по предположению, что φ(B) = φ(C), мы немедленно получаем φ(A(B/pᵢ)) = φ(A(C/pᵢ)).

Базовый случай №2: Предположим, что A — это переменная pⱼ, где j ≠ i. Тогда A(B/pᵢ) и A(C/pᵢ) — это обе просто A, и, конечно, φ(A(B/pᵢ)) = φ(A(C/pᵢ)).

Шаг индукции №1: Предположим, что A = ¬D, тогда A(B/pᵢ) есть ¬D(B/pᵢ), а A(C/pᵢ) есть ¬D(C/pᵢ). Индукционное предположение утверждает, что φ(D(B/pᵢ)) = φ(D(C/pᵢ)). По определению истинности для ¬, мы немедленно имеем, что φ(A(B/pᵢ)) = φ(A(C/pᵢ)).

Шаг индукции №2: Предположим, что A = D ○ E, где ○ — одна из связок ∧, ∨, →, ↔︎. Тогда
A(B/pᵢ) есть D(B/pᵢ) ○ E(B/pᵢ),
а A(C/pᵢ) есть D(C/pᵢ) ○ E(C/pᵢ).
Существует два индукционных предположения:
что φ(D(B/pᵢ)) = φ(D(C/pᵢ)) и
что φ(E(B/pᵢ)) = φ(E(C/pᵢ)).

Теорема I.48 была сформулирована относительно одного присваивания истинности. Если мы усилим предположение, сказав, что φ(B) = φ(C) для всех присваиваний истинности, то получим следующий королларий.

Королларий I.49 Пусть B ⊧ C. Тогда
A(B/pᵢ) ⊧ A(C/pᵢ).

Этот королларий уже использовался ранее, например, в доказательстве Теоремы I.37. В том доказательстве мы утверждали, что если подформула (B ∨ C) формулы A заменяется на (¬B → C), то полученная формула A′ тавтологически эквивалентна A. Конечно, до сих пор мы обсуждали только подстановку формулы вместо переменной, а не вместо подформулы. Тем не менее, мы можем переформулировать (recast) подстановку так, чтобы применить её к замене подформулы другой формулой.

А именно, пусть p_ℓ — переменная, которая не появляется в A, и пусть A∗ — формула, полученная из A заменой подформулы (B ∨ C) на p_ℓ. Тогда A совпадает с A∗((B ∨ C)/p_ℓ), а A′ совпадает с A∗((¬B → C)/p_ℓ). Королларий утверждает, что A∗((B ∨ C)/p_ℓ) и A∗((¬B → C)/p_ℓ) тавтологически эквивалентны. То есть, A и A′ тавтологически эквивалентны. Это именно то, что было нужно для доказательства Теоремы I.37.

Приведённый выше королларий касался подстановки двух тавтологически эквивалентных формул в одну и ту же формулу A. Следующая теорема касается подстановки одной и той же формулы A в две тавтологически эквивалентные формулы.

Теорема I.50. Пусть B ⊧ C. Тогда
B(A/pᵢ) ⊧ C(A/pᵢ).

Доказательство Пусть φ — произвольное присваивание истинности (arbitrary truth assignment). Нам нужно показать, что
φ(B(A/pᵢ)) = φ(C(A/pᵢ)).

Пусть p_ℓ — переменная, которая не появляется ни в одной из A, B или C. Определим φ′ как присваивание истинности, такое что
φ′(p_ℓ) = φ(A),
а в остальном φ′ совпадает с φ. Другими словами,

’(p_j) = \[\begin{cases} \varphi(A), & \text{если } j = \ell \\ \varphi(p_j), & \text{если } j \neq \ell \end{cases} \tag{I.6}\]

(формула I.6)

Мы называем φ′ «p_ℓ-вариантом» присваивания φ, поскольку φ и φ′ совпадают на всех переменных, кроме, возможно, p_ℓ.

Заметим, что φ и φ′ совпадают на всех переменных, которые появляются в B(A/pᵢ) или C(A/pᵢ).

Имеем:

\[\begin{aligned} \varphi(B(A/p_i)) &= \varphi'(B(A/p_i)) && \text{по Теореме I.41, так как } p_\ell \text{ не появляется в } B(A/p_i) \\ &= \varphi'(B(p_\ell/p_i)) && \text{по Теореме I.48, поскольку } \varphi'(A) = \varphi'(p_\ell) \\ &= \varphi'(C(p_\ell/p_i)) && \text{по } B \vDash= C, \text{ так как } p_\ell \text{ не появляется ни в } B, \text{ ни в } C \\ &= \varphi'(C(A/p_i)) && \text{снова по Теореме I.48} \\ &= \varphi(C(A/p_i)) && \text{снова по Теореме I.41} \\ \end{aligned}\]

¹¹

Следствие I.51. (a) Любая подстановка тавтологии является тавтологией.
(b) Если A ⊧ B, то A(C/pᵢ) ⊧ B(C/pᵢ)
(c) Если A₁, …, Aₖ ⊧ B, то A₁(C/pᵢ), …, Aₖ(C/pᵢ) ⊧ B(C/pᵢ)

Доказательство. Пусть A — тавтология, а A(B/pᵢ) — подстановка A. Чтобы доказать (a), мы должны показать, что A(B/pᵢ) — тавтология.
Пусть p_ℓ — переменная, которая не встречается в A.
Мы имеем A ⊧= (p_ℓ ∨ ¬p_ℓ), поскольку и A, и p_ℓ ∨ ¬p_ℓ являются тавтологиями.
Следовательно, по предыдущей теореме, при подстановке B вместо pᵢ,
A(B/pᵢ) ⊧= (p_ℓ ∨ ¬p_ℓ),
поскольку pᵢ не встречается в (p_ℓ ∨ ¬p_ℓ).
Следовательно, A(B/pᵢ) — тавтология.

Часть (b) напрямую следует из части (a).
Во-первых, A ⊧ B выполняется тогда и только тогда, когда ⊧ A → B.
Аналогично, A(C/pᵢ) ⊧ B(C/pᵢ) выполняется тогда и только тогда, когда ⊧ A(C/pᵢ) → B(C/pᵢ).
Наконец, A(C/pᵢ) → B(C/pᵢ) равносильно (A → B)(C/pᵢ).
Таким образом, (a) влечёт (b).

Часть (c) доказывается аналогично части (b) с использованием факта, что A₁, …, Aₖ ⊧ B.

---

5. Это игнорирует другие возможные условия, такие как открыта ли касса и есть ли у вас достаточно денег.↩︎

6. Для читателей, знакомых с теорией P и NP: нетрудно показать, что определение, покрывает ли множество частичных присваиваний истинности все возможные присваивания истинности, является NP-трудной задачей.↩︎

7. Неофициально, B(p_ℓ/pᵢ) и C(p_ℓ/pᵢ) получаются из B и C путём переименования pᵢ в p_ℓ, и, следовательно, B ⊧ C влечёт B(p_ℓ/pᵢ) ⊧ C(p_ℓ/pᵢ). Строго говоря, мы должны ввести другое присваивание истинности φ′′, которое является pᵢ-вариантом присваивания φ.↩︎

8. Обозначение “большой конъюнкции” (big and), ⋀, аналогично знаку суммирования (∑): оно означает указанную конъюнкцию формул от Lᵢ,₁ до Lᵢ,ₖ↩︎

9. В компьютерных науках конъюнкцию литералов иногда называют “термом” (term); однако мы избегаем этой терминологии, поскольку понятие “терм” имеет другое, устоявшееся значение в логике первого порядка.↩︎

10. Смотри Следствие I.49.↩︎

11. Строго говоря, нам следовало бы использовать обозначение f_{A,k} вместо fₐ, поскольку не требуется, чтобы pₖ действительно присутствовала в A. Однако мы используем более простое обозначение fₐ, так как это никогда не должно вызывать путаницы.↩︎