1. Преобразование исходной формулы в кнф.

Шаг 1.

Преобразовать исходную формулу к равносильному ей виду, в котором есть лишь операции конъюнкции, дизъюнкции и отрицания (перейти в сигнатуру алгебры логики), причём отрицания могут стоять лишь над элементарными переменными высказываниями.

Шаг 2.

Преобразовать полученную формулу к равносильному ей виду, в котором все дизъюнкции выполняются раньше, чем конъюнкции (применить дистрибутивный закон), т.е. построить КНФ для исходной формулы.

2.Преобразование кнф в скнф.

Шаг 3.

Если в КНФ есть несколько одинаковых элементарных дизъюнкций , то оставляем только одну - это преобразование приводит к равносильной формуле ,т.к. x&x=x.

Шаг 4.

Делаем все элементарные дизъюнкции правильными с помощью следующих двух преобразований:

- если в элементарной дизъюнкции переменная входит со своим отрицанием, то удаляем эту дизъюнкцию из КНФ.

- если некоторая переменная входит в элементарную дизъюнкцию несколько раз, причём либо во всех случаях без отрицаний, либо во всех случаях с отрицаниями, то оставляем только одну эту переменную.

Шаг 5.

Преобразуем правильные дизъюнкции в полные. Пусть в некоторую элементарную дизъюнкцию не входит переменная x, тогда рассмотрим выражение (x ) и повторим шаги 2 и 3. Если недостающих переменных несколько, то проделать аналогичные преобразования со всеми недостающими переменными.

Построение совершенных нормальных форм с помощью таблиц истинности

Для построения СДНФ или СКНФ, исходя из теоремы о разложении функции алгебры логики от n переменных по k переменным (k=n), можно воспользоваться таблицами истинности.

Для построения СДНФ отметим в таблице истинности те наборы значений переменных, на которых функция равна 1. Для каждого такого набора построим полную правильную элементарную конъюнкцию по следующей схеме: если значение некоторой компоненты равно 1, то соответствующая переменная входит в элементарную конъюнкцию без отрицания, если значение компоненты 0, то соответствующая переменная входит в элементарную конъюнкцию с отрицанием. Объединив, таким образом, построенные правильные полные элементарные конъюнкции знаками дизъюнкции, получим совершенную дизъюнктивную нормальную форму.

Для построения СКНФ отметим в таблице истинности те наборы значений переменных, на которых функция равна 0. Для каждого такого набора построим полную правильную элементарную дизъюнкцию по следующей схеме: если значение некоторой компоненты равно 1, то соответствующая переменная входит в элементарную дизъюнкцию с отрицанием, если значение компоненты 0, то соответствующая переменная входит в элементарную дизъюнкцию без отрицания. Объединив, таким образом, построенные правильные полные элементарные дизъюнкции знаками конъюнкции, получим совершенную конъюнктивную нормальную форму.

Построение совершенных нормальных форм, используя принцип двойственности.

Построение совершенной конъюнктивной нормальной формы.

Пусть задана некоторая функция алгебры логики от n переменных. Рассмотрим отрицание этой функции и , так как полученная формула будет формулой алгебры логики, то разложим её по n переменным. Полученное выражение, после возможных упрощений, представляет собой совершенную дизъюнктивную нормальную форму. Возьмём отрицания от левой и правой частей полученного выражения. Слева будет исходная функция, а справа (после применения, если это необходимо, закона де Моргана и возможных упрощений) её совершенная конъюнктивная нормальная форма.

Построение совершенной дизъюнктивной нормальной формы.

Рассмотрим вместо исходной функции её отрицание и построим для полученной формулы алгебры логики её совершенную конъюнктивную нормальную форму. Взяв затем отрицания от левой и правой частей полученного выражения и применив, если это необходимо. закон де Моргана, а так же возможно упростив полученное выражение, получим совершенную дизъюнктивную нормальную форму для исходной функции.