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

Любую логическую функцию 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

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

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

__ __ __ __ __

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).

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

Дата добавления: 2015-07-11