Исчисление высказываний

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

Основные понятия

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

1. Если P — пропозициональная переменная, то P — формула.
2. Если A — формула, то $\neg A$ — формула.
3. Если A и B — формулы, то $(A \wedge B)$, $(A \vee B)$ и $(A \to B)$ — формулы.
4. Каждая формула может быть получена за конечное число шагов при помощи предыдущих трёх правил.

Знаки $\neg, \wedge, \vee$ и $\to$ (отрицание, конъюнкция, дизъюнкция и импликация) называются пропозициональными связками. Подформулой называется часть формулы, сама являющаяся формулой. Собственной подформулой называется подформула, не совпадающая со всей формулой.

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

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

• Если опущены внешние скобки, то они восстанавливаются.
• Если рядом стоят две конъюнкции или дизъюнкции (например, $A \wedge B \wedge C$), то в скобки заключается сначала самая левая часть (т.е. две подформулы со связкой между ними). (Говорят также, что эти связки левоассоциативны.)
• Если рядом стоят разные связки, то скобки расставляются согласно приоритетам: $\neg, \wedge, \vee$ и $\to$ (от высшего к низшему).

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

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

Истинностное значение

Оценкой пропозициональных переменных называется функция из множества всех пропозициональных переменных в множество {0, 1} (т.е. множество истинностных значений). Основной задачей логики высказываний является установление истинностного значения формулы, если дана оценка (т.е. определены истинностные значения входящих в неё переменных). Истинностное значение формулы в таком случае определяется индуктивно (с шагами, которые использовались при построении формулы) с использованием таблиц истинности связок.

Оценка отрицания $\neg p$ задаётся таблицей:

$p\!$	$\neg p$
$0\!$	$1\!$
$1\!$	$0\!$

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

$p\!$	$q\!$	$p\rightarrow q$	$p \wedge q$	$p \vee q$
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	1	1	1

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

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

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

1) $\neg (p \vee q) \leftrightarrow (\neg p \wedge \neg q)$;

2) $\neg (p \wedge q) \leftrightarrow (\neg p \vee \neg q)$;

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

$(p\rightarrow q)\leftrightarrow(\neg q\rightarrow \neg p)$;

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

1) $p\vee(p\wedge q)\leftrightarrow p$;

2) $p\wedge(p\vee q)\leftrightarrow p$;

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

1) $p\wedge(q\vee r)\leftrightarrow(p\wedge q)\vee(p \wedge r)$;

2) $p\vee(q\wedge r)\leftrightarrow(p\vee q)\wedge(p \vee r)$.

Исчисление высказываний

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

$A_1 : (A \rightarrow (B \rightarrow A))$;

$A_2 : ((A \rightarrow (B \rightarrow C)) \rightarrow ((A \rightarrow B) \rightarrow (A \rightarrow C)))$;

$A_3 : A \wedge B \rightarrow A$;

$A_4 : A \wedge B \rightarrow B$;

$A_5 : A \rightarrow (B \rightarrow (A \wedge B))$;

$A_6 : A \rightarrow (A \vee B)$;

$A_7 : B \rightarrow (A \vee B)$;

$A_8 : (A \rightarrow C) \rightarrow ((B \rightarrow C) \rightarrow ((A \vee B) \rightarrow C))$;

$A_9 : \neg A \rightarrow (A \rightarrow B)$;

$A_{10} : (A \rightarrow B) \rightarrow ((A \rightarrow \neg B)\rightarrow \neg A)$;

$A_{11} : A\vee\neg A$.

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

$\frac{A \rightarrow B, A}{B}$ (Modus ponens)

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

См. также

• Логика первого порядка
• Дизъюнктивная нормальная форма
• Конъюнктивная нормальная форма

Ссылки

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