2. Формулы алгебры высказываний
Определение. Пропозициональными переменными называются такие переменные, вместо которых можно подставлять конкретные высказывания1.
Определение. Формула алгебры высказываний определяется индуктивным образом так:
а) всякая пропозициональная переменная есть формула;
б) если F1 и F2 – формулы, то выражения:
┐F1,
также являются формулами;
в) других формул, кроме построенных по правилам а), б), нет.
Иными словами, логическая формула алгебры высказываний суть запись сложного высказывания в виде простых высказываний, соединенных логическими связками.
Значением формулы алгебры высказываний F(X1, X2,…Xn) на конкретном наборе высказываний A1, A2, … An является значение составного высказывания F(A1, A2, … An), получающегося подстановкой в формулу указанного набора.
Пример. Пусть имеется формула
F(X1,
X2,
X3)=((X1X2)
X3)
(X1
X3).
Составим таблицу истинности для этой формулы, отождествляя для упрощения записи (Xi) c Xi2.
X1 |
X2 |
X3 |
X1X2 |
(X1X2) X3 |
(X1 X3) |
((X1X2) X3) (X1 X3) |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Пусть далее A1, A2, A3 – некоторый конкретный набор высказываний, причем (A1)=1, (A2)=0, (A3)=1. Тогда значением формулы F(X1, X2, X3)= F(A1, A2, A3) будет число 1 (см. строку в таблице, выделенную жирным шрифтом).
Порядок выполнения логических операций в формуле задается с помощью скобок. При их отсутствии приоритеты (порядок выполнения операций) логических операций таковы:
– отрицание;
– конъюнкция и дизъюнкция;
– импликация и эквивалентность.
Например, формула ┐A B C B – бесскобочная запись формулы ((┐A) B) (C B). В то же время, следует отметить, далеко не всегда скобки «убираются» просто.
Например, формулы (┐(A С)) (C B) и (┐A С) (C B) – две разные формулы.
Разными будут и формулы (┐(A С)) (C B) и (┐(A С)) C B.
Определение. Формула алгебры высказываний F(X1, X2,…Xn) называется выполнимой (опровержимой), если существует такой набор высказываний A1, A2, … An, который обращает эту формулу в истинное (ложное) высказывание F(A1, A2, … An).
Пример. Пусть F(X1, X2)=┐(X1 X2) формула алгебры высказываний. Тогда при A1=0, A2=0 F(A1, A2)=1. Это означает, что формула F(X1, X2) – выполнима. Поскольку при A1=1, A2=1 F(A1, A2)=0, то эта же формула F(X1, X2) – опровержима.
Определение. Формула алгебры высказываний F(X1, X2,…Xn) называется тождественно истинной или тавтологией, если она обращается в истинное высказывание при всех наборах значений переменных.
Доказательство того, что формула является тавтологией, осуществляется с помощью таблицы истинности. Например, формула:
F(X1, X2, X3)=((X1X2) X3) (X1 X3).
является тавтологией, и доказательством тому служит приведенная выше таблица истинности для этой формулы.
Теорема. Если формулы:
F(X1, X2,…Xn) и F(X1, X2,…Xn) (X1,X2,…Xn) – тавтологии, то
формула (X1,X2,…Xn) – тавтология.
Определение. Формула алгебры высказываний F(X1, X2,…Xn) называется тождественно ложной или противоречием, если она обращается в ложное высказывание при всех наборах значений переменных.
Теорема. Формула алгебры высказываний F(X1, X2,…Xn) является противоречием тогда и только тогда, когда формула алгебры высказываний ┐F(X1, X2,…Xn) является тавтологией.
Определение. Формулы алгебры высказываний F(X1, X2,…Xn) и (X1,X2,…Xn) называются равносильными (пишут F или F), если при любом наборе высказываний набор высказываний A1, A2, … An, значения истинности формул F и совпадают.
Для доказательства равносильности двух формул достаточно составить их таблицы истинности и убедиться в том, что они совпадают.
Пример. Пусть F(X1, X2)=┐(X1 X2), (X1, X2) =(┐X1) (┐X2).
Составим таблицу истинности для этих формул.
X1 |
X2 |
F(X1, X2)=┐(X1 X2) |
(X1, X2) =(┐X1) (┐X2) |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
Убедившись, что значения истинности F и совпадают, делаем вывод о том, что F.