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

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

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

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

__ __ __ __ __

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

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

КАРТЫ КАРНО

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

Карта Карно состоит из q=2ⁿ клеток, причем каждой из клеток соответствует один из q минтермов. Карта представляется в виде квадрата или прямоугольника. Переменные разбиваются на две группы. Переменным одной группы ставят в соответствие столбцы, другой - строки. Переменные первой группы остаются постоянными в пределах каждого столбца, второй - постоянными в пределах строки. Каждой клетке ставится в соответствие определенный набор переменных.

Например, для двух переменных (n=2) имеем q= 2²=4 клетки. На рисунках последовательно представлена карта Карно для двух переменных, клетам которой поставлены в соответствие алгебраическое выражение минтерма (рис.12), наборы значений переменных, при которых минтерм равен 1 (рис.13), и числовое (десятичное) представление набора переменных (рис.14).

	Х1 0				Х1 0				Х1 0
Х2	Х1Х2	Х1Х2		Х2				Х2
	Х1Х2	Х1Х2

Рис. 12. Рис.13. Рис.14

Значение переменной обычно задается в виде

черты по периметру карты:

черта есть – переменная в пределах строки или

столбца равна 1,

черты нет – переменная равна 0.

Рис.15.

Для трех переменных имеем карту Карно из 2³=8 клеток, которым соответствуют следующие наборы переменных в двоичном и десятичном представлении. Здесь расположение переменных по битам принято Х₁Х₂Х₃.

Рис.16. Рис.17.

Для четырех переменных имеем карту Карно из 2⁴=16 клеток.

Рис.19. Рис.20.

Здесь каждой клетке карты поставлены в соответствие выражение минтерма (рис.18), двоичное (рис.19) и десятичное (рис.20) представления набора переменных при расположении переменных по битам Х₁Х₂Х₃Х₄. При изменении порядка расположения битов изменится десятичное представление.

Аналогично, при n=5 имеем 32 клетки, при n=6 - 64 клетки.

Приведенное распределение переменных по строкам и столбцам не является единственным. Обязательным требованием является только то, что переменные по сторонам распределяются так, чтобы при переходе из клетки в клетку по вертикали или горизонтали происходила инверсия только одной переменной.

Для представления логической функции в виде карты Карно в соответствующую клетку карты вписывается 1, если логическая функция равна 1 на данном наборе переменных, и вписывается 0 или клетка оставляется пустой, если логическая функция равна 0.

Логическая функция “И”:

Y = X₁ Ù X₂.

Рис.21.

Логическая функция “ИЛИ”:

Y = X₁ Ú X₂ =

= X₁ Ù X₂ Ú X₁ Ù X₂ Ú X₁ Ù X₂.

Рис.22.

Логическая функция “Исключающее ИЛИ”:

Рис.23.

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

Например: Х₁

__ __ __ __

F (X1,X2 ,X3,X4) = X₁ X₂ X₃ X₄+

__ __ __ __ __X₃

+X₁X₂X₃X₄ + X₁X₂X₃X₄ + X₁X₂X₃X₄ .

Рис. 24. Функция и ее карта Карно.Х₂

Клетки, содержащие 1, называются “1-клетками”, а клетки, содержащие 0, - “0-клетками”. Логические функции, имеющие определенные значения (0 или 1) при всех возможных наборах переменных, называются полностью определенными. Имеются функции, значения которых определены только для части наборов переменных. Такие логические функции называются частично определенными. Те наборы значений аргументов, для которых значение функции не определено, будем называть безразличными, на карте Карно эти клетки будем указывать знаком “х”. Этим наборам соответствуют ситуации, которые на практике никогда не реализуются. Частично определенную функцию можно доопределить, приписав безразличным значениям произвольно 0 или 1. Обычно доопределение проводят таким образом, чтобы, используя законы алгебры логики, упростить выражение.