Математическая логика
жүктеу/скачать 0.93 Mb.
|
| Теорема 2.4. Каждый класс эквивалентности [U] может быть представлен приведенной формулой, т.е. для любой формулы U M существует приведенная формула V.
Приведенная формула для данного класса эквивалентности не является единственной. Определим порядок построения приведенной формулы. Удаляются операции импликация и эквиваленция по формулам 11, 12. Операции отрицания спускаются до высказывательных переменных с помощью законов де Моргана и двойного отрицания. Если это возможно, то полученная приведенная формула упрощается с помощью свойств 3, 4, 5, 6, 9, 10. Таким образом, проверить эквивалентность формул, тождественную истинность и ложность формулы или упростить ее можно с помощью этого алгоритма. Задание. Упростить формулу . Решение. ( ) ( ) ( ) A. Формула U* называется двойственной к приведенной формуле U, если она получена заменой операций конъюнкции на дизъюнкции и наоборот. Теорема 3.5 (принцип двойственности). Пусть U( ) – приведенная формула, тогда U*( ) = U( ). Доказательство. Обозначим k – число логических операций в формуле U. Проведем доказательство индукцией по k. 10. k = 0. В этом случае U = Xi , следовательно, Ud = Xi U ( ). 2 0. Предположим, что теорема верна при k m. 3 0. Покажем, что она верна при k = m + 1. Пусть U1 и U2 – подформулы U. Каждая из них образована посредством не более, чем m операций, и следовательно, для них теорема верна. Возможны следующие случаи а) U = U1; б) U = U1 U2; в) U = U1 U2. Случай а) эквивалентен условию 10 и при нем теорема верна. В случаях б) и в) заменим в каждой из Ui конъюнкцию на дизъюнкцию и наоборот. По определению двойственности будем иметь, соответственно, б): Ud = U U и в): Ud = U U . В силу законов де Моргана и предположения индукции будем иметь в случае б): жүктеу/скачать 0.93 Mb. Достарыңызбен бөлісу:
|