Двойственное разложение Шеннона

Суть состоит в том, что в формуле, описывающей функцию, можно одновременно произвести следующие замены:

Ù Þ Ú, 0 Þ 1, ù х Þ х, Ú Þ Ù, 1 Þ 0, х Þ ù х.

Т.о. F (х₁, …, х_n) = x₁^s1 … x_n^sn = = x₁^s1 Ú… Ú x_n^sn

СДНФ СКНФ

и тем самым получим СКНФ – совершенную конъюктивную нормальную форму функции F. СКНФ содержит ровно столько дизъюнкций, сколько нулей в таблице истинности для F. Каждому нулевому набору (s₁, …, s_n) соответствует дизъюнкция всех переменных, в которой х_i взято без отрицания, если s_i = 0, и с отрицанием, если s_i = 1. Такие дизъюнкции называются конституентами нуля.

Переход от табличной формы представления /логической функции к аналитической

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

Таблица 2.10 – Функция 3-х переменных

х1 х2 х3	F	конституента 1	конституента 0
0 0 0			х1 Ú х2 Ú х3
0 0 1		ù х1 ù х2 х3
0 1 0		ù х1 х2 ù х3
0 1 1			х1 Ú ù х2 Úù х3
1 0 0			ù х1 Ú х2 Ú х3
1 0 1		х1 ù х2 х3
1 1 0		х1 х2 ù х3
1 1 1			ù х1 Ú ù х2 Ú ù х3

Отсюда переходим к аналитическим выражениям логической функции:

СДНФ: F = ù х₁ ù х₂ х₃ Ú ù х₁ х₂ ù х₃ Ú х₁ ù х₂ х₃ Ú х₁ х₂ ù х₃,

СКНФ: F = (х₁ Ú х₂ Ú х₃) (х₁ Ú ù х₂ Úù х₃) (ù х₁ Ú х₂ Ú х₃) (ù х₁ Ú ù х₂ Ú ù х₃).

Примечание: функция, для которой не существует СДНФ – константа 0, функция, для которой не существует СКНФ – константа 1.

Дата добавления: 2014-01-06