Формулы алгебры высказываний.
Эквивалентность и преобразование формул
Напомним определение формулы алгебры высказываний. Формулами алгебры высказываний являются:
1) логические константы 0 и 1;
2) пропозициональные переменные;
3) если А и В – формулы, то каждое из выражений Ø(А), (А) Ù (В), (А) Ú (В), (А) ® (В), (А) ~ (В) есть формула;
4) других формул, кроме построенных по пп. 1) - 3), нет.
Для проверки свойств эквивалентности, выполнимости, опровержимости, тождественной истинности и ложности формул могут использоваться таблицы истинности. Для построения таблицы истинности формулы воспользуемся следующим алгоритмом.
1. Пронумеровать простые высказывания в алфавитном порядке.
2. Для каждого элементарного высказывания рассмотреть все возможные наборы значений истинности. Всего возможно 2n комбинаций, где n - число элементарных высказываний. Это количество строк в таблице.
3. Пронумеровать сложные высказывания, содержащие одну логическую операцию, затем сложные высказывания, содержащие две логических операции, и т.д., увеличивая сложность высказываний в соответствии с порядком выполнения операций.
4. Вычислить значения истинности всех сложных высказываний. Столбец с последним номером будет содержать значение истинности для всей логической формулы.
Задание. Построить таблицу истинности формулы
Ø(А Ù В) ® ØА Ú С.
Решение.
1. Пронумеруем простые высказывания в алфавитном порядке А-1, В-2, С-3.
2. Каждый набор значений истинности элементарных высказываний изобразится набором 000, 001, 010 и т. д. Для нашего примера число комбинаций равно 8-ми, то есть таблица истинности будет содержать 8 строк.
3. Пронумеруем сложные высказывания формулы: АÙВ - 4; Ø(AÙB) - 5; ØA - 6; ØAÚС - 7; конечная операция ® - 8.
4. Вычислим последовательно значения истинности сложных высказываний.
| Ø (A Ù B) | ® | Ø A Ú С | ||||||
Анализируя истинностные значения формулы, содержащиеся в столбце 8, получим, что данная формула является и выполнимой, и опровержимой, и, следовательно, не тавтология и не противоречие. Для проверки эквивалентности формул строятся их таблицы истинности на одинаковых интерпретациях.
Однако такой способ очень громоздок, поэтому в дальнейшем для решения таких задач будем использовать эквивалентные преобразования, используя основные тавтологии 1-13.
Задание. Доказать эквивалентность формул (задание 3(а))
.
Решение.
º 
Формула 3(b) доказывается аналогично. В дальнейшем при проведении преобразований формул эти законы, называемые законами обобщенного склеивания, будут часто использоваться, поэтому добавим их под номером 14 в список основных тавтологий.
Задание. Доказать эквивалентность формул (задание 4(d))
(AÚ B) Ù (B Ú C) Ù (C Ú A) º (A Ù B) Ú (B Ù C) Ú (C Ù A).
Решение.
(AÚ B) Ù (B Ú C) Ù (C Ú A) º (BÚ (A Ù C)) Ù (C Ú A) º
º (B Ù (C Ú A)) Ú (A Ù C Ù (C Ú A)) º (B Ù C) Ú (B Ù A) Ú (A Ù C).
Как легко видеть, последняя формула цепочки эквивалентна формуле правой части задания в силу коммутативности операций Ù и Ú. Данные формулы являются самодвойственными.
Для того чтобы воспользоваться тавтологиями 1-14 требуется привести формулу к приведенному виду. Определим порядок построения приведенной формулы.
1. Удаляются операции импликация и эквиваленция по формулам 11, 12.
2. Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания.
В дальнейшем, если это возможно, полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10.
Задание. Доказать тождественную истинность формулы (задание 6(а)) (P ® R) ® ((Q ® R) ® ((P Ú Q) ® R)).
Решение.
(P ® R) ® ((Q ® R) ® ((P Ú Q) ® R)) º
º Ø(
) Ú (Ø(
) Ú (Ø(P Ú Q) Ú R) º
º (
) Ú (
) Ú (
) Ú R º R Ú P Ú () Ú () º º R Ú P Ú Q Ú () º R Ú P Ú Q Ú 
º R Ú Q Ú 1 º 1.
Начиная с 3-й, все формулы цепочки преобразований являются приведёнными.
Задание. Упростить схему
Решение. Запишем формулу, соответствующую схеме, по приведенным выше правилам
U = 
.
