Опр. 1. Пусть формула А зависит от списка переменных <Xi1, , Xik> и А не тождественно-ложная функция

Пусть формула А зависит от списка переменных <X_i1, …, X_ik> и А не тождественно-ложная функция. Тогда такая формула В, что А В и В находится в СДНФ относительно списка переменных <X_i1, …, X_ik>.

Пусть А₁ находится в ДНФ, причем А₁ А. итак, приведем ее к СДНФ.

1. Пусть в элементарную конъюнкцию одновременно входят какая-нибудь переменная Х_il и ее отрицание. Если это единственна элементарная конъюнкция формулы, то она на всех оценках принимает значение Л, а следовательно, и вся формула, что невозможно, так как предполагается, что формула не тождественно-ложная. Значит, имеются другие элементарные конъюнкции, и формула будет иметь вид (Х_il Х_il С) D, где С – остальные члены элементарной конъюнкции; D – остальные дизъюнктивные члены всей формулы. Но (Х_il Х_il С) D D, т.к левый член всегда принимает значение Л. Следовательно формула равносильна D, а рассматриваемую элементарную конъюнкцию можно отбросить.

2. Пусть в некоторой элементарной конъюнкции переменная Х_il (или она же, но с отрицанием) встречается несколько раз. Тогда в силу идемпотентности можно оставить только одно вхождение Х_il.

3. После проведенной обработки каждая элементарная конъюнкция С будет содержать какую-нибудь переменную не более одного раз (включая отрицание). Если какая либо переменная Х_il не содержится в С то мы разлагаем С на (С Х_il) (С

Х_il) (первая формула расщепления).

4. Переупорядочим в каждой элементарной конъюнкции члены так, что на l месте будет стоять Х_il член.

5. Если в результате всех преобразований остаются повторяющиеся элементарные конъюнкции, то мы их выбрасываем.

Поиск по сайту: