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

С помощью логических операций над высказываниями можно строить различные, более сложные высказывания. Определим понятие формулы алгебры высказываний.

Формулой алгебры высказываний (формулой) называется

1) любое высказывание (высказывательное переменное);

2) если и – формулы, то , , , , – тоже формулы;

3) кроме формул приведенных в п.п 1) и 2) других формул в алгебре высказываний нет.

Если формула образована, например, из формул (переменных) , и , то используем следующую запись: .

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

Формула называется тавтологией (тождественно истинной), если она принимает только истинное значение на всех наборах значений входящих в неё переменных.

Формула называется противоречием (тождественно ложной), если она принимает только ложное значение на всех наборах значений входящих в неё переменных.

Формула называется выполнимой, если она не является ни тавтологией и ни противоречием.

Для того, чтобы формулы и , образованные из одних и тех же переменных являлись равносильными, необходимо и достаточно, чтобы формула являлась тавтологией.