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

• Разделы:
  • Формулы
  • Тавтологии
  • Аксиомы
  • Правило вывода

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

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

Содержание

• 1 Логические связки
• 2 Формулы
• 3 Тавтологии
• 4 Аксиомы
• 5 Правило вывода

Логические связки

Кроме пропозициональных переменных, в ИВ используются так называемые логические связки. Если p{displaystyle p!}

  — высказывание, то через ¬p{displaystyle neg p}  будем обозначать отрицание этого высказывания. Зададим его таблицей:

p{displaystyle p!}	¬p{displaystyle neg p}
0{displaystyle 0!}	1{displaystyle 1!}
1{displaystyle 1!}	0{displaystyle 0!}

Значение двуместных логических связок →{displaystyle rightarrow }

  (импликация), ∨{displaystyle vee }  (дизъюнкция)и ∧{displaystyle wedge }  (конъюнкция) определются так:

p{displaystyle p!}	q{displaystyle q!}	p→q{displaystyle prightarrow q}	p∧q{displaystyle pwedge q}	p∨q{displaystyle pvee q}
0{displaystyle 0}	0{displaystyle 0}	1{displaystyle 1}	0{displaystyle 0}	0{displaystyle 0}
0{displaystyle 0}	1{displaystyle 1}	1{displaystyle 1}	0{displaystyle 0}	1{displaystyle 1}
1{displaystyle 1}	0{displaystyle 0}	0{displaystyle 0}	0{displaystyle 0}	1{displaystyle 1}
1{displaystyle 1}	1{displaystyle 1}	1{displaystyle 1}	1{displaystyle 1}	1{displaystyle 1}

Формулы

1. пропозициональные переменные являются формулами;
2. если p,q{displaystyle p,q,!}  — формулы, то (p→q){displaystyle (prightarrow q)} , (p∨q){displaystyle (pvee q)}  и (p∧q){displaystyle (pwedge q)}  — формулы.
3. если p{displaystyle p!}  — формула, то (¬p){displaystyle (neg p)}  — формула.

Тавтологии

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

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

1) ((p∧q)∨(p∧r))↔(p∧(q∨r)){displaystyle ((pwedge q)vee (pwedge r))leftrightarrow (pwedge (qvee r))}

 ;

2) ((p∨q)∧(p∨r))↔(p∨(q∧r)){displaystyle ((pvee q)wedge (pvee r))leftrightarrow (pvee (qwedge r))}

 ;

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

(p→q)↔(¬q→¬p){displaystyle (prightarrow q)leftrightarrow (neg qrightarrow neg p)}

 ;

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

1) p∨(p∧q)↔p{displaystyle pvee (pwedge q)leftrightarrow p}

 ;

2) p∧(p∨q)↔p{displaystyle pwedge (pvee q)leftrightarrow p}

 ;

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

1) p∧(q∨r)↔(p∧q)∨(p∧r){displaystyle pwedge (qvee r)leftrightarrow (pwedge q)vee (pwedge r)}

 ;

1) p∨(q∧r)↔(p∨q)∧(p∨r){displaystyle pvee (qwedge r)leftrightarrow (pvee q)wedge (pvee r)}

 .

Аксиомы

A1:(A→(B→A)){displaystyle A_{1}:(Arightarrow (Brightarrow A))}

 ;

A2:((A→(B→C))→((A→B)→(A→C))){displaystyle A_{2}:((Arightarrow (Brightarrow C))rightarrow ((Arightarrow B)rightarrow (Arightarrow C)))}

 ;

A3:A∧B→A{displaystyle A_{3}:Awedge Brightarrow A}

 ;

A4:A∧B→B{displaystyle A_{4}:Awedge Brightarrow B}

 ;

A5:A→(B→(A∧B)){displaystyle A_{5}:Arightarrow (Brightarrow (Awedge B))}

 ;

A6:A→(A∨B){displaystyle A_{6}:Arightarrow (Avee B)}

 ;

A7:B→(A∨B){displaystyle A_{7}:Brightarrow (Avee B)}

 ;

A8:(A→C)→((B→C)→((A∨B)→C)){displaystyle A_{8}:(Arightarrow C)rightarrow ((Brightarrow C)rightarrow ((Avee B)rightarrow C))}

 ;

A9:¬A→(A→B){displaystyle A_{9}:neg Arightarrow (Arightarrow B)}

 ;

A10:(A→B)→((A→¬B)→¬A){displaystyle A_{10}:(Arightarrow B)rightarrow ((Arightarrow neg B)rightarrow neg A)}

 ;

A11:A∨¬A{displaystyle A_{11}:Avee neg A}

 .

Правило вывода

A→B,AB{displaystyle {frac {Arightarrow B,A}{B}}}

  (Modus ponens)

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