Математическая логика и теория алгоритмов

Теорема 1.8. Для того, чтобы элементарное произведение А было противоречием, необходимо и достаточно, чтобы в нем содержалась хотя бы одна пара множителей, из которых один мно.житель является отрицанием другого. Дизъюнктивной нормальной формой (д.н.ф.) называется дизъ­ юнкция элементарных произведений. Одно элементарное произведе­ ние тоже будем считать д.н.ф. Примеры д.н.ф.: AV]B,AVB&C, livA&CvA&B&lC. Теорема 1.9. Для каждой пропозициональной формы сущест­ вует равносильная ей д.н.ф. (не единственная). Доказательство. Ранее было показано, что для любой формы существует равносильная ей форма, содержащая только связки 1 , &, V, причем связка 1 относится только к отдельным буквам. Еще раньше было замечено, что с формой, содержащей связки &, v , можно проводить операции раскрытия скобок (см. законы дист]зибу- тивности). В результате получаем дизъюнкцию элементарных произ­ ведений, т.е. д.н.ф. Пример. Пусть задана формула \А=В)&.С. Исключим связку s , затем =>•. 1 ((А=>В)&(В=>А))&С, 1(1Лv5)&(1 BWA))&.C. Теперь добьемся, чтобы 1 относилась только к пропозициональным буквам: {А&Л В^В&\А)&.С. Раскрыв скобки, получим А&] B&CVB&IA&C. Последнее и есть д.н.ф. Полученная д.н.ф., очевидно, равносильна следующей д.н.ф.; A&^ S&Cv Из примера видно, что д.н.ф., равносильная заданной форме, определяется неединственным образом. 32