Математическая логика и теория алгоритмов. Для изучающих компьютерные науки

Дизъюнктивной нормальной формой (д.н.ф.) называется дизъюнкция элементарных произведений. Одно элементарное произведение тоже будем считать д.н.ф. Примеры д.н.ф.: А v —tB, А vB&C, -А vA&C vA&B&^C. Теорема 1.11. Для каждой пропозициональной формы существует равносильная ей д.н.ф. (не единственная). Доказательство. Ранее было показано, что для любой формы существует равносильная ей форма, содержащая только связки —i, &, v, причем связка —i относится только к отдельным буквам. Еще раньше было замечено, что с формой, содержащей связки &, v, можно проводить операции раскрытия скобок (см. законы дистрибутивности). В результате получаем дизъюнкцию элементарных произведений, т.е. д.н.ф. Пример. Пусть задана форма ^(А=В)&С. Исключим =, затем ^ ((А^В)&(В^А))&С, -п((-^ vB)&(^BvA)) &С. Теперь добьемся, чтобы —i относилась только к буквам: {А&—^В v В&—Л)&С. Раскрыв скобки, получим А&—В&С v В&—А&С. Последнее и есть д.н.ф. Полученная д.н.ф., очевидно, равносильна следующей д.н.ф.: А&—В&С v -А&В&С V А&—А. Из примера видно, что д.н.ф., равносильная заданной форме, определяется не единственным образом. Теорема 1.12. Для того, чтобы форма А была противоречием, необходимо и достаточно, чтобы равносильная ей д.н.ф. содержала в каждом слагаемом хотя бы одну пару множителей, из которых один - некоторая пропозициональная буква, а второй - отрицание этой буквы. Доказательство. Пусть для Л равносильной ей д.н.ф. является форма BjyB2 v...vBk(k>l), (1.10) где Bi ( 1< i< к ) есть элементарное произведение. Дизъюнкция (1.10) будет противоречием тогда и только тогда, когда будет противоречием каждая Bi (1< i<к); Bi - элементарное произведение и по теореме 1.8 будет противоречием тогда и только тогда, когда содержит хотя бы одну пару множителей, из которых один - некоторая буква, а второй - отрицание этой буквы. Теорема доказана. Следствие. Форма А будет выполнимой, если равносильная ей д.н.ф. содержит хотя бы одно слагаемое, в котором нет таких множителей, что один из них - некоторая я буква, а другой множитель - отрицание этой буквы. Пропозициональная форма называется конъюнктивной нормальной формой (к.н.ф.), если она представляет собой конъюнкцию элементарных сумм. Легко доказать следующую теорему. 17