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

Кроме пропозициональных переменных, в ИВ используются так называемые логические связки. Если ${\displaystyle p\!}$  - высказывание, то через ${\displaystyle \neg p}$  будем обозначать отрицание этого высказывания. Зададим его таблицей:

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

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

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

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

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

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

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

${\displaystyle (p\rightarrow q)\leftrightarrow (\neg q\rightarrow \neg p)}$ ;

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

1) ${\displaystyle p\vee (p\wedge q)\leftrightarrow p}$ ;

2) ${\displaystyle p\wedge (p\vee q)\leftrightarrow p}$ ;

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

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

1) ${\displaystyle p\vee (q\wedge r)\leftrightarrow (p\vee q)\wedge (p\vee r)}$ .

${\displaystyle A_{1}:(A\rightarrow (B\rightarrow A))}$ ;

${\displaystyle A_{2}:((A\rightarrow (B\rightarrow C))\rightarrow ((A\rightarrow B)\rightarrow (A\rightarrow C)))}$ ;

${\displaystyle A_{3}:A\wedge B\rightarrow A}$ ;

${\displaystyle A_{4}:A\wedge B\rightarrow B}$ ;

${\displaystyle A_{5}:A\rightarrow (B\rightarrow (A\wedge B))}$ ;

${\displaystyle A_{6}:A\rightarrow (A\vee B)}$ ;

${\displaystyle A_{7}:B\rightarrow (A\vee B)}$ ;

${\displaystyle A_{8}:(A\rightarrow C)\rightarrow ((B\rightarrow C)\rightarrow ((A\vee B)\rightarrow C))}$ ;

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

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

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

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

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