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

Исчисле́ние выска́зываний — это формальная теория \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

Формулы

  1. пропозициональные переменные являются формулами;
  2. если p, q\,\! — формулы, то (p\rightarrow q), (p \vee q) и (p \wedge q) — формулы.
  3. если 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 из истинных высказываний можно получить только истинные. Доказательство этой теоремы тривиально и сводится к непосредственной проверке. Куда более интересен тот факт, что все остальные тавтологии можно получить из аксиом с помощью правила вывода - это так называемая теорема полноты логики высказываний.


 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home