3.Формулы. Вывод формул

Выражение (X/\У) —> Z также можно считать формулой — формулой схемы конструирования составных высказываний из более простых.

Понятие формулы алгебры высказываний. В формулу (X/\У) —> Z вместо переменных X, Y, Z можно подставлять конкретные высказывания, после чего вся формула будет превращаться в некоторое составное высказывание. Переменные, вместо которых можно подставлять высказывания, т.е. переменные, пробегающие множество высказываний, называют пропозициональными переменными, или высказывательными переменными, или переменными высказываниями. Будем обозначать пропозициональные переменные заглавными буквами латинского алфавита Р, Q, R, S, X, Y, Z или такими же буквами с индексами Р1 Р2 ..., Q1 Q2, ..., Х1 Х2.

Теперь дадим точное определение формулы алгебры высказываний. Определение 2.1

1. Каждая отдельно взятая пропозициональная переменная есть формула алгебры высказываний.

2. Если F1 и F2 — формулы алгебры высказываний, то выражения –F1, (F1/\ F2), (F1 v F2), (F1 -> F2), (F1 эквивалентность F2) также являются формулами алгебры высказываний.

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

Формулы А и В называются эквивалентными (обозначается А ~ В), если при любых значениях высказывательных переменных значение формулы А совпадает со значением формулы В.

Формула называется выполнимой, если существует такой набор значений переменных, при которых эта формула принимает значение И.

Формула называется опровержимой, если существует такой набор значений переменных, при которых эта формула принимает значение Л.

Формула называется тождественно истинной (ТИ-формулой) или тавтологией, если эта формула принимает значение И при всех наборах значений переменных.

Формула называется тождественно ложной (ТЛ-формулой) или противоречием, если эта формула принимает значение л при всех наборах значений переменных.