Формулы алгебры высказываний

Алгебра высказываний (АВ) – это учение о высказываниях.

Отвлечемся от содержания высказывания и даже от его структуры. Будем ограничиваться только тем его свойством, что оно представляет собой или истину, или ложь. Тогда высказывание можно рассматривать как величину, которая может принимать два значения: «истина» (И) и «ложь» (Л).

Теперь рассматривая высказывания как величины, принимающие значения И и Л, мы определим над ними операции, которые позволяют из данных высказываний получать новые.

Пусть даны два произвольных высказывания А и В.

1. ¬А есть высказывание, которое ложно, когда А истинно, и истинно, когда А ложно. Высказывание ¬А называется отрицанием А.

2. Операция конъюнкции (или логического умножения) дает новое высказывание АВ, которое истинно тогда и только тогда, когда А и В истинны.

3. Операция дизъюнкции (или логического сложения) дает высказывание АВ, которое истинно тогда и только тогда, когда хотя бы одно из первоначальных высказываний истинно.

4. Операция импликации (или логического следования) дает высказывание А→В, которое ложно тогда и только тогда, когда А истинно, а В ложно. А называется посылкой, В – следствием.

5. А~В есть высказывание, истинное тогда и только тогда, когда А и В оба истинны или оба ложны. Это высказывание называется эквивалентностью.

Определение. Всякое сложное высказывание, составленное из некоторых исходных высказываний посредством применения логических операций 1- 5, называется формулой алгебры высказываний.

Формулы АВ будем обозначать через F_а.

Определение. Формула F_а называется:

1. тавтологией, если на всех наборах значений переменных ее значения равны 1;

2. выполнимой, если хотя бы одно ее значение равно 1;

3. опровержимой, если хотя бы одно ее значение равно 0;

4. противоречием, если все ее значения равны 0.

Пример. Из таблицы истинности видно, что

формула А В→А - тавтология,

формулы А  В, А  В, А→В выполнимы и опровержимы,

формула А  ¬А – противоречие.

Определение. Формула F_а называется приведенной, если она содержит только операции ¬, ,  (не обязательно все), причем знак отрицания относится только к переменным.

Пример. F_а=A (¬А¬ В) - приведенная формула;

F_а= ¬ (А→ ¬ В) - не является приведенной формулой.

Соответствие между формулами ав и ив

Между формулами ИВ F и АВ F_а можно установить соответствие. Для этого

1. переменные ИВ трактуются как переменные АВ;

2. логическим связкам ИВ ¬, , , → ставятся в соответствие операции ¬(отрицание),  (конъюнкция),  (дизъюнкция), → (импликация) в АВ;

3. операции ↔ (эквиваленция) в АВ ставится в соответствие запись (А→В) (В→А) в ИВ;

4. константу И (истинное высказывание) в АВ заменяем на запись (А  ¬А) в ИВ;

5. константу Л (ложное высказывание) в АВ заменяем на запись

(А  ¬А) в ИВ.

Следовательно, каждая формула F_а в АВ будет иметь соответствующую формулу F в ИВ. В дальнейшем формулы F и F_а отождествляем.