Совершенные нормальные формы функций алгебры логики

 

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

Введем обозначения =, =.

Тогда в общем виде переменная может быть задана как некоторая функция

 

 

при этом

,

 

где  – двоичная переменная.

Рассмотрим конъюнкцию вида …, где {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) = 122341341234

F 1 F 2 F 3 F 4

 

преобразовать в СНДФ.

Решение. Воспользуемся приемом преобразования поочередно к термам

F 1=12(33)= 123123.

 

Оба члена полученного выражения умножим на (44).

В результате получим

 

.

 

Аналогично:

F 2=234(11) = 12341234;

F 3=134(22) = 12341234.

После приведения подобных членов определяем СНДФ.

Ответ:

.

 

Если максимальный ранг для функции равен r, а минимальный ранг j -го терма равен k, то преобразование необходимо применить j -му терму (r - k) раз.

Произвольная НКФ переводится в СНКФ путем следующего преобразования.

Пусть f нкф=Ф1. Тогда

 

.

 

Пример. Преобразовать в СНКФ логическую функцию

 

Решение. Применяем правило преобразований поочередно к термам Ф1и Ф2:

 

 

.

 

После упрощений СНКФ примет окончательный вид.

Ответ:.