 |
Лекция 4. Логические тождества. Преобразование формул.. Нормальные формы в исчислении высказываний.
|
|
|
|
Лекция 4.
1. Логические тождества. Преобразования формул.
2. Нормальные формы.
3. ИВ как ФС. Аксиомы. Правила вывода
4. Свойства ИВ как формальной системы
Логические тождества. Преобразование формул.
Рассмотрим ряд равносильных формул, полезных при выполнении различных преобразований в исчислении высказываний.
Пусть X – простое высказывание (атом). Х может принимать только 2 значения { И, Л}
Справедливы следующие тождества.
X& X& X& … & X = X
XÚ XÚ XÚ … XÚ X = X
X& И = X XÚ И = И
X& Л = Л XÚ Л = X
X& Ø X = Л XÚ Ø X = И
Ø Ø X = X
Операции & и Ú по аналогии с алгебраическими операциями умножения и сложения допускают перестановку аргументов:
X& Y = Y& X XÚ Y = YÚ X
Следует учитывать, что это абсолютно неверно для операции импликации:
A®B ≠ B®A (проверьте это построением таблиц истинности).
Более сложными являются следующие правила.
1. XÚ X& Y = X правило поглощения
2. (XÚ Y)& Z = X& Z Ú Y& Z правило раскрытия скобок
3. XÚ Y& Z = (XÚ Y) & (XÚ Z)
4. XÚ Ø X & Y = XÚ Y
Формулы Де-Моргана
A®B = Ø A Ú B (правило замены импликации)
A~B = (A®B) & ( B®A) (правило замены эквивалентности)
Примечание. Операцию эквивалентности также можно обозначать символом «
Справедливость любого из тождеств доказывается с помощью таблиц истинности.
Пример 1. Докажем путём преобразований правило поглощения.
XÚ X& Y = X& ИÚ X& Y = X& (ИÚ Y) = X& И = X
На первом шаге заменяем X на X& И. Затем используем правило вынесения за скобки. Выражение в скобках (ИÚ Y) равно И.
|
|
|
На последнем шаге применяем тождество X& И = X
Пример 2. Упростить выражение A& Ø BÚ A& Ø CÚ B& Ø CÚ C
Решение
1) A& Ø BÚ A& Ø CÚ B& Ø CÚ C = A& Ø BÚ A& Ø CÚ BÚ C
К последним двум слагаемым применяем тождество 4: B& Ø C Ú C заменяем равносильной формулой BÚ C
2) A& Ø BÚ A& Ø CÚ BÚ C = A& Ø BÚ B Ú A& Ø C Ú C = A Ú B Ú A Ú C
Для наглядности меняем местами слагаемые. Затем два раза используем тождество 4: A& Ø BÚ B заменяем на A Ú B; A& Ø C Ú C заменяем на A Ú C.
3) A Ú B Ú A Ú C равносильно A Ú B Ú C (поскольку A Ú A = А)
4) Ответ A& Ø BÚ A& Ø CÚ B& Ø CÚ C = A Ú B Ú C
Нормальные формы в исчислении высказываний.
Любую формулу логики высказываний удобно представить в виде так называемой нормальной формы.
Атом или его отрицание будем называть литерой.
Говорят, что формула логики высказываний В представлена в конъюнктивной нормальной форме (КНФ) тогда и только тогда, когда она имеет форму B = B1 & B2 & … & Bm, где каждая из Bi (i = 
) есть дизъюнкция литер. Каждая Bi , входящая в КНФ, называется элементарной дизъюнкцией. Например, В = (Х1 Ú Ø Х2) & (Ø Х1 Ú Х2 Ú Ø Х3) & Х3 представлена в КНФ. Она содержит три элементарных дизъюнкции, соединённых знаками логического умножения &.
Аналогично говорят, что формула логики высказываний В представлена в дизъюнктивной нормальной форме (ДНФ) тогда и только тогда, когда она имеет форму B = B1 Ú B2 Ú … Ú Bm, где каждая из Bi (i = ) есть конъюнкция литер. Каждая Bi , входящая в ДНФ, называется элементарной конъюнкцией. Например, В = (Ø Х1 & Ø Х2 & Х3) Ú (Х1 & Х2) Ú Ø Х3 представлена в ДНФ. Она содержит три элементарных конъюнкции, соединённых знаками Ú.
Любая формула исчисления высказываний может быть преобразована в нормальную форму с помощью следующего алгоритма.
|
|
|
Шаг 1. А ~ В = (А ® В) & (В ® А).
А ® В = Ø А Ú В.
Шаг 2. Ø Ø А = А.
законы Де-Моргана.
Шаг 3. А Ú (В & С) = (А Ú В) & (А Ú С) (для КНФ).
А & (В Ú С) = А & В Ú А & С (для ДНФ).
Пример 3. Получим КНФ для формулы (A ® (B Ú Ø C)) ® D.
(A ® (B Ú Ø C)) ® D = (Ø A Ú B Ú Ø C) ® D = Ø (Ø A Ú B Ú Ø C) Ú D = (A & Ø B & C) Ú D = (A Ú D) & (Ø B Ú D) & (C Ú D).
Пример 4. Получим ДНФ для формулы Ø (A & B) & (A Ú B).
Ø (A & B) & (A Ú B) = (Ø A Ú Ø B) & (A Ú B) = ((Ø A Ú Ø B) & A) Ú ((Ø A Ú Ø B) & B) = (A & Ø B) Ú (B & Ø A).
Теперь ставим задачу: как с помощью приведения к нормальным формам решить проблему, является ли некая формула тавтологией, противоречием?
Пусть F -произвольная формула исчисления высказываний, представленная в нормальной форме.
Справедливы следующие теоремы.
Теорема 1. Формула F является тавтологией тогда и только тогда, когда любая элементарная дизъюнкция в её КНФ содержит пару литер, одна из которых является отрицанием другой.
Теорема 2. Формула F является противоречием тогда и только тогда, когда любая элементарная конъюнкция в её ДНФ содержит пару литер, одна из которых является отрицанием другой.
Приведённые теоремы очень просты, примем их без доказательства. С помощью этих теорем мы сможем убедиться в том, что некоторая формула является тождественно истинной (тождественно ложной) без построения таблиц истинности, исключительно за счёт анализа нормальных форм.
Пример 5.
Рассмотрим формулу F = A®AÚ B, приведенную ранее. Чтобы получить нормальную форму для этой формулы применим правило замены импликации: A®AÚ B = Ø AÚ AÚ B. Рассмотрим полученную формулу как КНФ, состоящую из единственной элементарной дизъюнкции. Поскольку по известному тождеству Ø AÚ A = И, выражение, содержащее такую пару литер всегда будет истинным: Ø AÚ AÚ B = И Ú B = И.
Формула F является тавтологией.
Самостоятельно докажите противоречивость формулы Ø (A ® A).
|
|
|
Рассмотрим формальную аксиоматическую систему ФС1 для исчисления высказываний.
Исходными термами ФС1 являются буквы латинского алфавита с индексами или без них. Исходные термы называются высказывательными переменными или атомами. Исходными символами логических связок являются, &, Ú, →, которые интерпретируются как отрицание, конъюнкция, дизъюнкция и импликация. Для удобства записи формул введем еще пару символов ( и ), называемых скобками. Других исходных символов исчисление высказываний не имеет.
Правила образования ППФ:
а) все атомы есть ППФ;
б) если A и B – ППФ, то A, A & B, A Ú B, A → B – также ППФ;
в) других правил образования ППФ нет.
Примеры ППФ: X → Y, X & Y → (Y Ú Z). Для удобства внешние скобки будем опускать, а применяя правила силы операций, перейдем к той же форме записи ППФ, что и формул исчисления высказываний. При интерпретации ППФ интерпретируются все атомы, в нее входящие, а затем производится интерпретация результатов логических операций. Окончательный результат интерпретаций операций считается результатом интерпретации всей ППФ. Понятие ППФ, как мы уже выяснили в 2. 1, является эффективным.
|
|
|
