3 Chapter I.Propositional Logic: Syntax and Semantics

3.1 I.1 Introduction to Propositional Logic

Логика высказываний (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, т.е. что вы можете купить билет тогда и только тогда, когда вам восемнадцать.3 Однако мы используем “если” и “только если” в более специализированном смысле, как это принято в логике и математике в целом. Это иллюстрирует необходимость осторожности при переводе с естественного языка на язык логики высказываний.

Математическая логика избегает неоднозначности английского языка. Вместо этого пропозициональные связки ¬, ∧, ∨, →, ↔︎ и т.д. являются чисто истинностными (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 (Определение истинности для пропозициональных формул). Предположим, что φ - присваивание истинности. Функция φ расширяется на множество всех пропозициональных формул рекурсивным определением:

  1. Если A имеет вид ¬B, то φ(A) = {

    F, если φ(B) = T

    T в противном случае }

  2. Если A имеет вид (B ∨ C), то φ(A) = { T, если φ(B) = T или φ(C) = T F в противном случае }

  3. Если A имеет вид (B ∧ C), то φ(A) = { T, если φ(B) = T и φ(C) = T F в противном случае }

  4. Если A имеет вид (B → C), то φ(A) = { T, если φ(B) = F или φ(C) = T F в противном случае }

  5. Если A имеет вид (B ↔︎ C), то φ(A) = { T, если φ(B) = φ(C) F в противном случае }

Заметим, как определение истинности следует неформальным значениям, обсуждавшимся в разделе 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).

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