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

Логика высказываний, пропозициональная логика (лат. propositio — «высказывание»^[1]) или исчисление высказываний^[2], также логика нулевого порядка — это раздел символической логики, изучающий сложные высказывания, образованные из простых, и их взаимоотношения. В отличие от логики предикатов, пропозициональная логика не рассматривает внутреннюю структуру простых высказываний, она лишь учитывает, с помощью каких союзов и в каком порядке простые высказывания сочленяются в сложные^[3].

Несмотря на свою важность и широкую сферу применения, логика высказываний является простейшей логикой и имеет очень ограниченные средства для исследования суждений^[2].

Язык логики высказываний

Язык логики высказываний (пропозициональный язык^[4]) — формализованный язык, предназначенный для анализа логической структуры сложных высказываний^[1].

Синтаксис логики высказываний

Исходные символы, или алфавит языка логики высказываний^[5]:

множество пропозициональных переменных (пропозициональных букв):

[math]\displaystyle{ Var = \{ p, q, r ... \} }[/math]

пропозициональные связки (логические союзы):

Символ	Значение
[math]\displaystyle{ \neg }[/math]	Знак отрицания
[math]\displaystyle{ \land }[/math] или &	Знак конъюнкции («логическое И»)
[math]\displaystyle{ \vee }[/math]	Знак дизъюнкции («логическое ИЛИ»)
[math]\displaystyle{ \rightarrow }[/math]	Знак импликации

Вспомогательные символы: левая скобка (, правая скобка ).^[6]

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

Пропозициональная формула — слово языка логики высказываний^[7], то есть конечная последовательность знаков алфавита, построенная по изложенным ниже правилам и образующая законченное выражение языка логики высказываний^[1].

Индуктивное определение множества формул [math]\displaystyle{ Fm }[/math] логики высказываний:^[4]^[1]

Если [math]\displaystyle{ p \in Var }[/math], то [math]\displaystyle{ p \in Fm }[/math] (всякая пропозициональная переменная есть формула);
если [math]\displaystyle{ A }[/math] — формула, то [math]\displaystyle{ \neg A }[/math] — тоже формула;
если [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math] — произвольные формулы, то [math]\displaystyle{ (A \wedge B) }[/math], [math]\displaystyle{ (A \vee B) }[/math], [math]\displaystyle{ (A \to B) }[/math] — тоже формулы.

Других формул в языке логики высказываний нет.

Форма Бэкуса — Наура, определяющая синтаксис логики высказываний, имеет запись:

[math]\displaystyle{ A ::= p \;|\; (\neg A) \;|\; (A \land A) \;| \;(A \lor A) \;|\; (A\to A) }[/math]

Заглавные латинские буквы [math]\displaystyle{ A }[/math], [math]\displaystyle{ B }[/math] и другие, которые употребляются в определении формулы, принадлежат не языку логики высказываний, а его метаязыку, то есть языку, который используется для описания самого языка логики высказываний. Содержащие метабуквы выражения [math]\displaystyle{ \neg A }[/math], [math]\displaystyle{ (A \to B) }[/math] и другие — не пропозициональные формулы, а схемы формул. Например, выражение [math]\displaystyle{ (A \wedge B) }[/math] есть схема, под которую подходят формулы [math]\displaystyle{ (p \wedge q) }[/math], [math]\displaystyle{ (p \wedge (r \vee s)) }[/math] и другие^[1].

Относительно любой последовательности знаков алфавита языка логики высказываний можно решить, является она формулой или нет. Если эта последовательность может быть построена в соответствии с пп. 1—3 определения формулы, то она формула, если нет, то не формула^[1].

Соглашения о скобках

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

Если опущены внешние скобки, то они восстанавливаются.
Если рядом стоят две конъюнкции или дизъюнкции (например, [math]\displaystyle{ A \wedge B \wedge C }[/math]), то в скобки заключается сначала самая левая часть (то есть эти связки левоассоциативны).
Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: [math]\displaystyle{ \neg, \wedge, \vee }[/math] и [math]\displaystyle{ \to }[/math] (от высшего к низшему).

Когда говорят о длине формулы, имеют в виду длину подразумеваемой (восстанавливаемой) формулы, а не сокращённой записи.

Например: запись [math]\displaystyle{ A \vee B \wedge \neg C }[/math] означает формулу [math]\displaystyle{ (A \vee (B \wedge ( \neg C))) }[/math], а её длина равна 12.

Формализация и интерпретация

Как и любой другой формализованный язык, язык логики высказываний можно рассматривать как множество всех слов, построенных с использованием алфавита этого языка^[8]. Язык логики высказываний можно рассматривать как множество всевозможных пропозициональных формул^[4]. Предложения естественного языка могут быть переведены на символический язык логики высказываний, где они будут представлять собой формулы логики высказываний. Процесс перевода высказывания в формулу языка логики высказываний называется формализацией. Обратный процесс подстановки вместо пропозициональных переменных конкретных высказываний называется интерпретацией^[9].

Аксиомы и правила вывода формальной системы логики высказываний

Одним из возможных вариантов (гильбертовской) аксиоматизации логики высказываний является следующая система аксиом:

[math]\displaystyle{ A_1 : A \rightarrow (B \rightarrow A) }[/math];

[math]\displaystyle{ A_2 : (A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)) }[/math];

[math]\displaystyle{ A_3 : A \wedge B \rightarrow A }[/math];

[math]\displaystyle{ A_4 : A \wedge B \rightarrow B }[/math];

[math]\displaystyle{ A_5 : A \rightarrow (B \rightarrow (A \wedge B)) }[/math];

[math]\displaystyle{ A_6 : A \rightarrow (A \vee B) }[/math];

[math]\displaystyle{ A_7 : B \rightarrow (A \vee B) }[/math];

[math]\displaystyle{ A_8 : (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C)) }[/math];

[math]\displaystyle{ A_9 : \neg A \rightarrow (A \rightarrow B) }[/math];

[math]\displaystyle{ A_{10} : (A \rightarrow B) \rightarrow ((A \rightarrow \neg B)\rightarrow \neg A) }[/math];

[math]\displaystyle{ A_{11} : A\vee\neg A }[/math].

вместе с единственным правилом:

[math]\displaystyle{ \frac{A \quad (A \rightarrow B)}{B} }[/math] (Modus ponens)

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

Таблицы истинности основных операций

Основной задачей логики высказываний является установление истинностного значения формулы, если даны истинностные значения входящих в неё переменных. Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок^[10].

Пусть [math]\displaystyle{ \mathbb{B} }[/math] — множество всех истинностных значений [math]\displaystyle{ \{0, 1\} }[/math], а [math]\displaystyle{ Var }[/math] — множество пропозициональных переменных. Тогда интерпретацию (или модель) языка логики высказываний можно представить в виде отображения

[math]\displaystyle{ M\colon Var \to \mathbb{B} }[/math],

которое каждую пропозициональную переменную [math]\displaystyle{ p }[/math] сопоставляет с истинностным значением [math]\displaystyle{ M(p) }[/math]^[10].

Оценка отрицания [math]\displaystyle{ \neg p }[/math] задаётся таблицей:

[math]\displaystyle{ p }[/math]	[math]\displaystyle{ \neg p }[/math]
[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 0 }[/math]

Значения двухместных логических связок [math]\displaystyle{ \rightarrow }[/math] (импликация), [math]\displaystyle{ \vee }[/math] (дизъюнкция) и [math]\displaystyle{ \wedge }[/math] (конъюнкция) определяются так:

[math]\displaystyle{ p }[/math]	[math]\displaystyle{ q }[/math]	[math]\displaystyle{ p\rightarrow q }[/math]	[math]\displaystyle{ p \wedge q }[/math]	[math]\displaystyle{ p \vee q }[/math]
[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]
[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 0 }[/math]	[math]\displaystyle{ 1 }[/math]
[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]	[math]\displaystyle{ 1 }[/math]

Тождественно истинные формулы (тавтологии)

Формула является тождественно истинной, если она истинна при любых значениях входящих в неё переменных (то есть, при любой интерпретации)^[11]. Далее перечислены несколько широко известных примеров тождественно истинных формул логики высказываний:

законы де Моргана:

[math]\displaystyle{ \neg (p \vee q) \leftrightarrow (\neg p \wedge \neg q) }[/math];

[math]\displaystyle{ \neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q) }[/math];

закон контрапозиции:

[math]\displaystyle{ (p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p) }[/math];

законы поглощения:

[math]\displaystyle{ p\vee(p\wedge q)\leftrightarrow p }[/math];

[math]\displaystyle{ p\wedge(p\vee q)\leftrightarrow p }[/math];

законы дистрибутивности:

[math]\displaystyle{ p\wedge(q\vee r)\leftrightarrow(p\wedge q)\vee(p \wedge r) }[/math];

[math]\displaystyle{ p\vee(q\wedge r)\leftrightarrow(p\vee q)\wedge(p \vee r) }[/math].

См. также

Примечания

↑ ^1,0 ^1,1 ^1,2 ^1,3 ^1,4 ^1,5 Чупахин, Бродский, 1977, с. 203—205.
↑ ^2,0 ^2,1 Кондаков, 1971, статья «Исчисление высказываний».
↑ НФЭ, 2010.
↑ ^4,0 ^4,1 ^4,2 Герасимов, 2011, с. 13.
↑ Войшвилло, Дегтярев, 2001, с. 91—94.
↑ Ершов Ю. Л., Палютин Е. А. Математическая логика. — М., Наука, 1979. — с. 24
↑ Эдельман, 1975, с. 130.
↑ Эдельман, 1975, с. 128.
↑ Игошин, 2008, с. 32.
↑ ^10,0 ^10,1 Герасимов, 2011, с. 17—19.
↑ Герасимов, 2011, с. 19.

Литература

Кондаков Н. И. Логический словарь / Горский Д. П.. — М.: Наука, 1971. — 656 с.
Эдельман С. Л. Математическая логика. — М.: Высшая школа, 1975. — 176 с.
Чупахин И. Я., Бродский И. Н. Формальная логика. — Ленинград: Издательство Ленинградского университета, 1977. — 357 с.
Войшвилло Е. К., Дегтярев М. Г. Логика. — М.: ВЛАДОС-ПРЕСС, 2001. — 528 с. — ISBN 5-305-00001-7.
Игошин В. И. Математическая логика и теория алгоритмов. — 2-е изд., стереотип.. — М.: Издательский центр «Академия», 2008. — 448 с. — ISBN 978-5-7695-4593-1.
А. С. Карпенко. Логика высказываний // Новая философская энциклопедия : в 4 т. / пред. науч.-ред. совета В. С. Стёпин. — 2-е изд., испр. и доп. — М. : Мысль, 2010. — 2816 с.
Герасимов А. С. Курс математической логики и теории вычислимости. — СПб.: Издательство «ЛЕМА», 2011. — 284 с. — ISBN 978-5-98709-292-7.

[_1312820659fc7165-1] 1,0 ^1,1 ^1,2 ^1,3 ^1,4 ^1,5 Чупахин, Бродский, 1977, с. 203—205.

[_41b0bd0f0dbaeca0-2] 2,0 ^2,1 Кондаков, 1971, статья «Исчисление высказываний».

[_75847a36b7650f70-3] НФЭ, 2010.

[_a31cb2b63ef048e4-4] 4,0 ^4,1 ^4,2 Герасимов, 2011, с. 13.

[_b3010e589e57f830-5] Войшвилло, Дегтярев, 2001, с. 91—94.

[Erch-6] Ершов Ю. Л., Палютин Е. А. Математическая логика. — М., Наука, 1979. — с. 24

[_a8b4f1a4216d896c-7] Эдельман, 1975, с. 130.

[_a8b4f2a4216d8b37-8] Эдельман, 1975, с. 128.

[_a42eeb454b1ab539-9] Игошин, 2008, с. 32.

[_1d9844f87fcba5a0-10] 10,0 ^10,1 Герасимов, 2011, с. 17—19.

[_a31cb2b63ef048ee-11] Герасимов, 2011, с. 19.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]