Представление логических функций в виде СДНФ (СКНФ)

Если булева функция не равна тождественному нулю, то ее можно представить в виде СДНФ по ее таблице истинности следующим образом: берем только те наборы переменных (х1, х2, …, хn), для которых f (х1, х2, …, хn)=1, и составляем простую конъюнкцию для этого набора так: если хi = 0, то берем в этой конъюнкции xi, если хi = 1, то берем хi. Составляя дизъюнкцию этих простых конъюнкций, придем к СДНФ. Любую логическую (булеву) функцию можно выразить через три логические функции: конъюнкцию, дизъюнкцию и отрицание. По аналогии с представлением любой функции (не равной тождественному нулю) в виде СДНФ можно функцию (не равную тождественной 1) представить в виде СКНФ: простая дизъюнкция составляется для тех наборов переменных (х1, х2, …, хп), для которых f (x1, x2,…, xn) = 0, причем если хi = 1, то в этой дизъюнкции берем xi, если же хi = 0, то берем хi.

Пример 1. Составить для импликации и сложения по модулю 2 СДНФ и СКНФ. Составим таблицу истинности для рассматриваемых функций.

Таблица 4.

СДНФ для этих функций: f (x, y) = x > y = xy? xy? xy 1;

f (x, y) = x + y = x y? xy 2.

СКНФ для этих функций: f (x, y) = x > y = x? y 1.

f (x, y) = x + y = (x? y)(x? y) 2.

Пример 2. Составить СДНФ и СКНФ на примере мажоритарной системы подсчета голосов, т. е. системы, дающей сигнал «1» на выходе, если более половины сигналов на входе «1». Составим таблицу истинности для рассматриваемой функции (табл. 5).

Таблица 5.

В совершенной дизъюнктивной нормальной форме заданная функция записывается в виде:

у (a, b, c) = а? в ?с? а? в? с? а? в ?с? а? в ?с ,.

т.е. функция записана для тех строк, где она обращается в 1.

В совершенной конъюнктивной нормальной форме заданная функция записывается в виде:

у (a, b, c) = (а? в? с)? (а? в? с)? (а? в? с)? (а? в? с),.

т.е. функция записана для тех строк, в которых она обращается в 0.

Как указано выше, в таблице 3 приведен полный набор логических функций для 2-х переменных.

Покажем эквивалентность СНДФ и СКНФ на примере функции НЕ ИЛИ (это функция f8 таблицы 3). Таблица истинности функции имеет следующий вид:

Таблица 6.

Отсюда имеем СДНФ в виде f (x, y) = x? y 8 и СКНФ в виде ;

f (x, y) = (x? y)? (x? y)? (x? y) 8.

Добавим в выражение для СКНФ член (x? y) и получим:

f (x, y) = (x? y)? (x? y)? (x? y)? (x? y)= x? y 8,.

т.к.

(x? y)? (x? y)= x? x? x? y? x? y? y? y = x (y? y)= x, x? x = 0;

y? y = 0 Аналогично (x? y)? (x? y)= y. Таким образом, СДНФ и СКНФ эквивалентны. Набор функций, через которые можно выразить любые другие функции, называется полным набором. Таким образом, конъюнкция, дизъюнкция и отрицание является полным набором. Упрощение логических выражений можно произвести с помощью методов минимизации. Для несложных функций используются алгебраические преобразования. Для более сложных с числом переменных от 3 до 6 применяют карты Карно.