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

Материал из Википедии — свободной энциклопедии

Исчисле́ние выска́зываний — это формальная теория $\mathcal{L}$ , в которой осуществляется попытка формализации понятий логического закона и логического следования.

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

[править] Логические связки

Кроме пропозициональных переменных, в ИВ используются так называемые логические связки. Если $p\!$ - высказывание, то через $\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$

[править] Формулы

пропозициональные переменные являются формулами;
если $p, q\,\!$ — формулы, то $(p\rightarrow q)$ , $(p \vee q)$ и $(p \wedge q)$ — формулы.
если $p\!$ - формула, то $(\neg p)$ - формула.

[править] Тавтологии

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

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

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

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

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

$(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)$ ;

1) $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 из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода - это так называемая теорема полноты логики высказываний.