Пример. Теорема о конъюнктивном разложении булевой функции по переменным

Теорема о конъюнктивном разложении булевой функции по переменным.

Пример.

Запишем дизъюнктивное разложение функции по всем переменным.

Определим значение функции на каждой интерпретации:

,

,

,

,

,

,

,

.

Запишем формулу, используя следствие 2 теоремы о разложении функций:

.

СДНФ функции является результатом дизъюнктивного разложения функции по всем переменным. СДНФ функции содержит только , следовательно, применив к СДКФ принцип двойственности, можно получить двойственное представление, которое называется конъюнктивным разложением.

Любую булеву функцию можно представить в следующей форме .

Запись означает многократную конъюнкцию, которая берется по всем возможным наборам значений при любом .

Запишем конъюнктивное разложение функции по переменным .

Воспользуемся теоремой о разложении функций

.

Вычислим функции:

;

;

;

.

Подставим полученные значения , , , в формулу конъюнктивного разложения по переменным :

Дата добавления: 2014-10-22