Дизъюнктивные нормальные формы и теорема о разложении

Введём понятие степени булевой переменной. Будем считать, что x¹=x, x⁰=`x.

Из определения следует, что х^a=1, если х=a, и х^a=0, если х¹a. В справедливости этого можно убедиться простым перебором значений.

Конъюнкция x1^a1x₂2^a2...x_nn^an называется элементарной, если в ней каждая переменная встречается не более одного раза.

Рангом элементарной конъюнкции называется число букв, образующих эту конъюнкцию.

Дизъюнктивной нормальной формой (ДНФ) называется дизъюнкция элементарных конъюнкций.

Длиной ДНФназывается число элементарных конъюнкций, образующих эту ДНФ. Длину ДНФбудем обозначать буквой L.

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

Дизъюнктивная нормальная форма, содержащая наименьшее число букв x_i^ai по сравнению со всеми другими ДНФ, эквивалентными данной функции, называется минимальной ДНФ (МДНФ).

Теорема о разложении. Для любой функции f(x₁,x₂,…,x_n,) f(x₁,x₂,…,x_i,…,x_n)=Úx1^a1× x2^a2 … xiai^{× ×}f(a₁,a₂,…,a_i,x_i+1…,x_n)

"a₁a₂…a_i

Доказательство. Возьмём произвольный набор значений переменных (b₁,b₂,…,b_n) и подставим его в выражение справа и слева от равенства. Получим

f(b₁,b₂,…,b_n)=Úb₁^a1× b₂^a2 … b_i^{ai× ×}f(a₁, a₂,…, a_i, b_i+1, …, b_n)

"a₁a₂…a_i

Справа для любого набора значений (a₁, a₂, …, a_i), не равного (b₁,b₂,…,b_i), соответствующая конъюнкция будет равна нулю, так как она в силу условия x^a = 0, если x¹a,будет содержать нулевой сомножитель. Останется единственная конъюнкция, где (a₁, a_2, …, a_i)=(b₁, b₂, …, b_i), то естьт.е. получим равенство f(b₁,b₂,…,b_n)= f(b₁,b₂,…,b_n), что и доказывает теорему.

Следствия из теоремы.

2.1. f(x₁,x₂ …)=x₁f(x₁=1)Ú`x₁×f(x₁=0). Это равенство известно как формула разложения К. Шеннона.

2. f(x₁,x₂,…,x_n)=Úx₁^a1× … x_n^{an× ×}f(a₁,a₂,…,a_n) =Úх₁^a1× х₂^a2 … х_n^an×

"a₁a₂…a_n "(a₁a₂…a_n)ÎT1

Это равенство получается из формулы при i=n, здесь Т1 –множество наборов значений аргументов, на которых функция равна 1. Оно известно как представление функции в виде совершенной дизъюнктивной нормальной формы (СДНФ).

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

Любую функцию можно представить в виде СДНФи это представление единственно, так как оно однозначно сопоставляется таблице истинности функции.

ПримерПример. Рассмотрим Найдём разложение функциюи f=(aÅb)®`ac, найдём её разложение по переменной а:
.F=a×f(a=1)) Ú`a×f(a=0) =a×((1Å b)® 0)Ú `a×((0 Å b)® c)=

a×(`b®0)Ú `a(b®c). Здесь мы учли, что (1Åх)=`х, (0 Å х)=х. Если ещё учесть, что (х®0)=`х, что следует из таблицы истинности импликации, то получим окончательную формулу для функции
f =a×b Ú`a× (b®c).

ПримерПример. Представим функцию импликации в виде СДНФ, для чего запишем её табличное представление (табл.5.5). Здесь в множестве Т1 три набора 000, 001 и 111, поэтому в СДНФ будет три конъюнкции

х®у=`х×`уÚ` х×уÚ х×у