1.8. Совершенные нормальные формы представления функций

Теорему разложения (1.29) для функций переменных можно использовать раз, т.е. функцию можно разложить по всем переменным где . В качестве примера

рассмотрим разложение функции двух переменных По теореме разложения (1.29) получим:

Далее каждую из функций можно разложить по переменной

где минтермы двух переменных Так как или 1 (значение функции в точке то

Такая форма представления функции двух переменных называется совершенной дизъюнктивной нормальной формой (СДНФ). Термин "совершенная форма" означает, что все члены имеют одинаковую размерность, а термин "нормальная форма" — что в выражении, задающем функцию, последовательно выполняются не более двух базовых операций алгебры логики (операция отрицания в расчет не принимается). Полученная СДНФ функции двух переменных эквивалентна выражению (1.35) для мультиплексной функции.

Разложение функции переменных представляет собой дизъюнкцию членов вида

Выражение (1.71) представляет собой СДНФ функции переменных, т. е. СДНФ является полным разложением (по всем переменным) функции по теореме Шеннона (1.29). Так как значения функции или 1, то если если Поэтому СДНФ функции можно представить в виде

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

В качестве примера рассмотрим функцию трех переменных заданную таблицей истинности (табл. 1.5), из которой следует, что Поэтому на основании (1.72)

Это и есть СДНФ функции заданной табл. 1.5.

Таблица 1.5. (см. скан) Функция трех переменных

СДНФ полностью неопределенной функции имеет вид:

где с — неопределенные значения функции или 1).

Совершенную конъюнктивную нормальную форму (СКНФ) функции переменных можно получить на основании двойственной теоремы разложения (1.33). Однако предпочтительнее более простой способ, основанный на записи СДНФ инверсной функции Инверсия функции в каждой точке должна иметь инверсные значения по отношению к значениям а самой функции, т.е. если На основании (1.72) запишем СДНФ инверсной функции:

Из данного соотношения на основании закона

двойственности получим:

Из определения макстермов следует, что

Данная форма представления функции переменных называется СКНФ. Так как значения функции или 1, то если если Поэтому СКНФ можно представить в виде

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

В качестве примера рассмотрим функцию трех переменных, заданную табл. 1.5. Так как только значения функции то на основании (1.74)

Это и есть СКНФ функции, заданной табл. 1.5.

Совокупность элементарных функций, с помощью которых можно записать любую функцию называется функционально полной системой функций, или базисом. Из (1.72) и (1.74) следует, что для представления любой функции в виде СДНФ или СКНФ достаточно использовать только функции (операции) И, ИЛИ и НЕ (операция НЕ необходима для получения первичных термов входящих в минтермы и макстермы), т.е. эти три функции составляют базис.

Преобразуем СДНФ функции (1.72) с помощью закона двойного отрицания и закона двойственности:

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

Преобразуем теперь СКНФ функции (1.73) с помощью закона двойного отрицания и закона двойственности:

Данная форма представления функций называется совершенной нормальной формой в базисе ИЛИ-НЕ, так как она требует использования только функций (операций) ИЛИ-НЕ.

На основании (1.75) и (1.76) из СДНФ и СКНФ функции, заданной табл. 1.5, можно получить СНФ этой функции в базисах И-НЕ и ИЛИ-НЕ:

На основании свойства минтермов (1.68) справедливо соотношение поэтому

Такое представление функции позволяет записать ее в виде полинома степени. Пусть, например, задана СДНФ функции трех переменных Тогда

Такой же результат можно получить и с помощью разложения Рида (1.36) функции трех переменных. Полученная форма представления функции называется разложением Рида — Маллера [8].