Нормальные конъюнктивная, дизъюнктивная формы не дают однозначного представления функции. Такое представление получается только при совершенных нормальных формах (СНФ).
Введем обозначения =, =.
Тогда в общем виде переменная может быть задана как некоторая функция
при этом
,
где – двоичная переменная.
Рассмотрим конъюнкцию вида …, где {1,2,… n } представляет собой двоичный набор; число наборов равно 2 n, т. е.:
0 0 … 0 0 0
0 0 … 0 0 1
0 0 … 0 1 0
0 0 … 0 1 1
и т. д.
Если задать всем 1значение 0 и 1, то можно получить, например, дизъюнкцию вида
.
Тогда справедлива следующая теорема.
Теорема 1.3. Любая ФАЛ может быть представлена в виде
.
Это выражение называют разложением функции алгебры логики по k переменным.
Следствие 1. Если k = 1, то функция алгебры логики представляется в виде
.
Следствие 2. Если k = n, то любая ФАЛ может быть представлена в виде
.
Совершенная нормальная дизъюнктивная форма (СНДФ) – ФАЛ, заданная в виде
Рассмотрим основные свойства СНДФ:
– в СНДФ нет двух одинаковых минтермов;
– в СНДФ ни один минтерм не содержит двух одинаковых множителей (переменных);
– в СНДФ ни один минтерм не содержит вместе с переменной и ее отрицание.
На основании этих свойств можно предложить следующий алгоритм получения СНДФ из таблицы истинности:
1. Положить номер строки в таблице i =1, номер элемента в строке j = 1.
2. Выбрать из таблицы набор с номером i. Если fi = 1, то перейти к п. 3, если fi 1, – к п. 5.
3. Сформировать терм fi. Выбрать элемент строки с номером j.
Если
4. Вычислить j:= j +1. Если i < n, то перейти к п. 3, если i n, – к п. 5.
5. Вычислить i:= i +1. Если i < 2 n, то перейти к п. 2, если i 2 n, – к п. 6.
6. Конец.
Пример. Представить функцию, заданную таблицей 1.14, в СНДФ.
Таблица 1.14
Решение. Решение проводится в соответствии с вышеприведенным алгоритмом.
Ответ: f (1,2,3)= 123+123+123.
Рассмотрим СНФ для других функций.
Пусть имеется терм вида, где
Если i = i и i – текущий элемент двоичного набора, то тогда возможны случаи:
В случае, когда для i = i, терм Ф i можно использовать в НКФ.
Теорема 1.4. Любая ФАЛ, кроме абсолютно истинной функции, может быть представлена в совершенной конъюнктивной нормальной форме (СНКФ):
.
Для представления логической функции используются операции И, ИЛИ, НЕ.
Следствие. Любая ФАЛ, кроме конституэнты 1, может быть представлена в виде
.
Здесь используются операции неравнозначности, дизъюнкции, отрицания.
Пример. Найти СНКФ для функции (см. табл. 1.11).
Решение. Решение производится по формуле
.
Это представление более громоздкое, чем представление этой функции в СНДФ, так как в таблице много строк, для которых f = 0.
В рассмотренных ранее объединениях термов были использованы для записи термов Fi jи Ф i jоперации ИЛИ, НЕ, а также И, НЕ. Можно использовать также набор из импликации и отрицания (НЕ).
Способы преобразования НФ в СНФ. Совершенная нормальная форма отличается от нормальной формы (НФ) тем, что всегда содержит термы только максимального ранга и дает однозначное представление функции.
Произвольная нормальная дизъюнктивная форма (НДФ) переводится в СНДФ следующим образом.
Пусть f нф= F 1. Тогда:
.
где i – переменная, которая не входит в данный терм fi.
Пример. Логическую функцию, заданную в НДФ:
f (1,2,3,4) = 122341341234
F 1 F 2 F 3 F 4
преобразовать в СНДФ.
Решение. Воспользуемся приемом преобразования поочередно к термам
F 1=12(33)= 123123.
Оба члена полученного выражения умножим на (44).
В результате получим
.
Аналогично:
F 2=234(11) = 12341234;
F 3=134(22) = 12341234.
После приведения подобных членов определяем СНДФ.
Ответ:
.
Если максимальный ранг для функции равен r, а минимальный ранг j -го терма равен k, то преобразование необходимо применить j -му терму (r - k) раз.
Произвольная НКФ переводится в СНКФ путем следующего преобразования.
Пусть f нкф=Ф1. Тогда
.
Пример. Преобразовать в СНКФ логическую функцию
Решение. Применяем правило преобразований поочередно к термам Ф1и Ф2:
.
После упрощений СНКФ примет окончательный вид.
Ответ:.
