Дискретная математика

67 Пример. Пусть имеем конституенту единицы; Xi& ]Х2&ХЗ&...&Х„. Ясно, что эта конституента единицы принимает значение I на наборе и значение О на остальных наборах. § 9. Дизъюнктивные и конъюнктивные нормальные формы Дизъюнктивной нормальной формой (д.н.ф.) называется дизъюнкция элементарных произведений. Одно элементарное произведение тоже будем считать д.н.ф. Примерыд . н . ф . x y y & z , Ixvx&zvx&y&lz. Теорема ЗЛО. Для каждой формулы существует равносильная ей д.н.ф. (не единственная). Доказательство. Ранее было показано, что для любой формулы существует равносильная ей формула, содержащая только связки 1, v, причем связка 7 относится только к отдельным переменным. Еще раньше было замечено, что с формулой, содержащей связки &, к можно проводить операции раскрытия скобок (см. законы дистрибутивности). В результате получаем дизъюнкцию элементарных произведений, т.е. д.н.ф. Пример. Пусть задана формула Исключим связку затем =>•. 1((x=^yJ&(y=:px ))&Z, J(lxvy)&(lyvx))&z. Теперь добьемся, чтобы 1 относилась только к переменным: (х& 1у\/у&. ]x)&z. Раскрыв скобки, получим х&] y&zvy&l x&z. Последнее и есть д.н.ф. Полученная д.н.ф., очевидно, равносильна следующей д.н.ф.: х& ly&zv x&y&zv Х &1 х. Из примера видно, что д.н.ф., равносильная заданной формуле, определяется не единственным образом. Конъюнктивной нормальной формой (к.н.ф.) называется конъюнкция элементарных сумм. Одну элементарную сумму тоже будем считать к.н.ф. Легко доказать следующую теорему. Теорема 3.11. Для каждой формулы существует равносильная ей к.н.ф. (не единственная). Можно сформулировать правила для нахождения д.н.ф. и к.п.ф., равносильных заданной формуле. Пусть задана формула/4: 1) исключить из А все связки, кроме 7, &, 2) добиться, чтобы 7 относилась только к переменным,