5. Теорема разложения логических функций

Мы рассмотрели элементарные логические функции, которые равны 1 или 0 только при одном наборе значений переменных, В общем случае произвольная логическая функция может принимать значение 1 ( или 0) на нескольких наборах значений аргумента. Для таких функций докажем теорему разложения.

Теорема разложения логических функций.

Любую логическую функцию F(X₁,X₂,...,X_p,...,X_n) можно разложить по переменной X_p:

__

F(X₁,X₂,..., X_P,...,X_n)= X_pF(X₁,X₂,...,0,...,Х_n)  X_pF(X₁,X₂,...,1,...,X_n) .

Докажем теорему методом перебора:

а) пусть переменная X_p=0, тогда

F(X₁,X₂,...,0,...,X_n)=1F(X₁,X₂,...,0,...,X_n)  0F(X₁,X₂,...,1,...,X_n)=

=F(X₁,X₂,...,0,...,X_n),

т.е. теорема справедлива независимо от значений других переменных;

б) пусть переменная X_p=1, тогда

F(X₁,X₂,...,X_p,...,X_n)=0F(X₁,X₂,...,0,...,X_n)  1F(X₁,X₂,...,1,...,X_n)=

=F(X₁,X₂,...,1,...,X_n),

и в этом случае теорема справедлива независимо от значений других переменных.

В результате получаем функцию, которая уже зависит от (n-1) переменной.

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

где: i=0,1, ..., (N-1); N=2ⁿ.;

C¹_i=X^b1₁X^b2₂...X^bn_n - минтерм;

F(Ai)-значение функции ( 0 или 1), которое она принимает на наборе Ai.

Например, разложение логической функции И будет иметь вид:

F(X₁,X₂)=C¹₀F(0)+C¹₁F(1)+C¹₂F(2)+C¹₃F(3)=C¹₃1 .

Форма записи, когда логическая функция представляется в виде дизъюнкции (логической суммы) минтермов, называется совершенной дизъюнктивной нормальной формой (СДНФ).Причем для представления логической функции достаточно рассматривать только те наборы переменных Ai, при которых F(A_i)=1 , т.к. C¹_iF(A_i)=0 при F(A_i)=0 .

Так для логической функции Исключающее ИЛИ:

__ __ F(X₁,X₂)=C¹₀0+C¹₁1+C¹₂1+C¹₃0=C¹₁+C¹₂=X₁X₂+X₁X_{2 .}

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

i	X1	X2	X3	F
0	0	0	0	0
1	0	0	1	1
2	0	1	0	1
3	0	1	1	0
4	1	0	0	0
5	1	0	1	1
6	1	1	0	0
7	1	1	1	1

Например, для произвольной логической

функция с заданной таблицей истинности:

__ __ __ __ __

F(X₁,X₂,X₃)=X₁X₂X₃+X₁X₂X₃+X₁X₂X₃+X₁X₂X_3.

F(A₀)=F(A₃)=F(A₄)=F(A₆)=0 , их не учитываем.

Иногда СДНФ называют формой представ-

ления логической функции по единицам.

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

__

F(X₁,X₂,...,X_p,...,X_n)=[ X_pF(X₁,X₂,...,1,...,X_n) ]  [ X_pF(X₁,X₂,...,0,...,X_n) ] ,

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

Здесь существенными являются только те наборы A_i, при которых F(A_i)=0, т.к. С⁰_i 1=1 независимо от значения C⁰_i .

Это будет совершенная конъюнктивная нормальная форма (СКНФ),или форма представления по нулям.

Для рассмотренного выше примера представления функции в СДНФ эта же функция в СКНФ будет иметь вид:

__ __ __ __ __

F(X₁,X₂,X₃)=(X₁+X₂+X₃)(X₁+X₂+X₃)(X1+X2+X3)(X1+X2+X3).

Здесь рассматриваются только те строчки таблицы истинности, где функция равна нулю.