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

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

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

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

при этом

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

Рассмотрим конъюнкцию вида … , где {1,2,…n} представляет собой двоичный набор; число наборов равно 2n, т. е.:

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 < 2n, то перейти к п. 2, если i  2n, – к п. 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 .

В рассмотренных ранее объединениях термов были использованы для записи термов Fijи Фijоперации ИЛИ, НЕ, а также И, НЕ. Можно использовать также набор из импликации и отрицания (НЕ).

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

Произвольная нормальная дизъюнктивная форма (НДФ) переводится в СНДФ следующим образом.

Пусть fнф= F1. Тогда:

где i– переменная, которая не входит в данный терм fi.

Пример. Логическую функцию, заданную в НДФ:

f(1,2,3,4) = 122341341234

F1 F2 F3 F4

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

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

F1=12(33)= 123123.

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

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

Аналогично: