Приведение формул к СДНФ(СКНФ) равносильными преобразованиями

1. Сначала найдём ДНФ, равносильную данной формуле.

2. Если в элементарную конъюнкцию несколько раз входит переменная x_i, то оставим только одно вхождение.

3. Если в элементарную конъюнкцию одновременно входят x_i и _i, то она равносильна 0, а потому выбросим её.

4. Если какая-то элементарная конъюнкция А не содержит переменную x_i, то заменим А на Аx_iÚА _i.

5. Если ДНФ содержит одинаковые, с точностью до порядка сомножителей, конъюнкции, то оставим только одну из них.

Алгоритм построения СКНФ аналогичен. Исходя из произвольной КНФ, проводим аналогичные преобразования, заменяя слово "конъюнкция" на слово "дизъюнкция". Дизъюнкцию, содержащую одновременно x_i и _iзаменяем на 1 и исключаем. Если какая-то дизъюнкция А не содержит переменную x_i, то заменяем её на (АÚ x_i)(АÚ _i).

Пример. Найти СДНФ и СКНФ, равносильные формуле F=(ab®`aÚc)®aÚ`b.

Fº ºaba`cÚaÚ`bºab`cÚaÚ`bºaÚ`b

Формула aÚ`b является одновременно и ДНФ и СКНФ. Построим СДНФ.

aºabÚa`b, `bºa`bÚ`a`b. Тогда FºabÚa`bÚ`a`b

Замечание. Переменная с оказалась несущественной.

Построим СКНФ и СДНФ с тремя переменными:

- это СКНФ

Теперь abºabcÚab`c, a`bºa`bcÚa`b`c, `a`bº`a`bcÚ`a`b`c

Тогда СДНФ для Fºa`bcÚa`b`cÚ`a`bcÚ`a`b`cÚabcÚab`c

Пусть теперь формулы F и G равносильны, т.е. равны как булевы функции. Всегда ли существует цепочка равносильных преобразований, переводящих F в G?

Теорема. Если формулы F и G равны как булевы функции, то существует последовательность равносильных преобразований, переводящих F в G.

В самом деле, формулы F и G имеют одинаковую СДНФ (СКНФ). Каждую из формул можно равносильными преобразованиями перевести в совершенную нормальную формулу.

Задача. Убедившись, что формулы F=(xÚy®yz)Ú`z и G=`xÚyÚ`z равны как функции, построить цепочку преобразований, переводящих F в G.

F=(xÚy®yz)Ú`zº( Úyz)Ú`zº`x`yÚyzÚ`zº

º`x`yÚ(yÚ`z)(zÚ`z)º`x`yÚyÚ`zº(`xÚy)(`yÚy)Ú`zº

º`xÚyÚ`z