Теорема разложения (1.24) является удобным инструментом для преобразования логических выражений, содержащих операцию сумма по модулю два, так как в ряде практических случаев позволяет свести данную операцию над функциями к простейшим операциям (1.20) и (1.22), например:

Xi Xi © (л;з V Xi) ®ХзХ1® V Ч) = Xi [х-О ф (Хз У О) ® WxO е (ДГа V б)] V Xi [Xi- \ ® (ХзУ \) ® xy \ ® {х V Т)! = = XI (О ф 1 ф О © 1) V Afi ®Хз®Хз® х) == ii-1 V «I-1 = = it V «1 = I

Приведем доказательство дистрибутивного закона (1.21) для операции сумма по модулю два относительно операции конъюнкции

xy®xz = x (0-у ф 0-г) У х{1-у ф 1-г) = jc (у ф г).

С теоремой разложения (1.24) связаны тождества

Хр-1 {Xn,..-,Xp,...,Xi}= Xp-f (Хп,...,0,..., Xi), Xp-f {Хп.....Хр,..., Xi) = Xp-f(Xn.....1,..., Xt).

По принципу двойственности этим тождествам соответствуют двойственные тождества

ХрУ ! (Xn,---,Xp,...,Xi)-=Xp\/ f{Xn.....\,...,Xi),

Xj>yf{Xni.-.,Xp,...,x,) = Xpyf (Хп,..., О.....Xj).

Тождества (1.26) легко доказать методом перебора или с помощью теоремы разложения (1.24). Тождества (1.26) и (1.27) являются мощным средством для упрощения логических выражений. Легко доказать закон поглощения (1.15) я (\.IS), используя второе тождество (1.27):хуху = ху0-у = х; х У ху - х у йу - ху у.

Пусть требуется упростить функцию

(1.26)

(1.27)

{(V) = X, ф Хз х- ®х-ухз Xi -Хг-Используя первое из тождеств (1.26) относительно Хч, полу-

чаем

f(v)=0.A;i©«3.0©x, V«30-A-a = jcj©A;, У х-х.,.

Для упрощения выражения Хъ®Х\Ухз можно использовать второе из тождеств (1.27), тогда i(v)=<i®X\yXi-Xi=x{yXi- Xi=x\Xi.x%.

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

/ёрр VepJCp = epФ*p, (1.28)

где ер=0 или 1. Данное символическое обозначение объединяет в одном символе х оба первичных терма дгр и хр. Действительно, при подстановке в (1.28) значений ев=0 и 1 получается, что

хер = Рр* ?P = Oj " \хр-, если ер = I.

Талько- благодаря введению данного символического обоаваче-ния удается, формализовать вывод общих соотношений для пе{№клкк

чательны» функций; Очевидно что два. первичных терма Хр и Хр" равны только в том случае, если ер=ер (если еФвр, то 6=6,). Для пермчных. термов справедливы соотношения:

;.;р=г;р=;р; (1.29)

4р./ = 0, xvsyvx. (1.30)

если хтр = бр, (1.31)

если Хр - е-р.

Истинность этих соотношений элементарно проверяется на основании определения первичных термов (1.28).

Минтермы и макстермы. Мннтермом (констнтуентой единицы) называется функция п переменных

K{)=xy...x\=Vix\, (1.32)

где v= (jc„,jci), ер=0 или 1, i=en...e\. Из данного определения следует, что-имеете» 2" различных минтермов п переменных, так; как имеется; 2" различных «.-разрядных двоичных чисел i=0, I,..., 2"-1. Минтермы обладают следующими свойствами;

Kj (V)

П. если v = v,. 33

О, если v= V/ -fc v;

/C«(v)/<rj(v)0, если 1Ф\\ (1.34)

21-1

V /(i(v)l. с-35)

Свойство минтермов (1.33), заключающееся в том, что любой минтерм /Ci(v) равен 1 только в одной точке Vi области определения, состоящей из 2" точек, легко доказать, используя свойства первичных термов (1.31). Свойства (1.34) и (1.35) доказываются на основании свойства (sl.33).

Запишем все минтермы двух переменных jcj и х: Xo(v) =

= х\х\-хС К\{у)=х\х\чх\; Кг{у)=х\х\=хгХх\ Ki{\)x\x\ =

XiXx; где v= (atj, ti). Таким же способом можно записать любой минтерм Kiiy) большего, числа переменных. Пусть, например, «=4 и i=13, тогда /(i3(v)=3c4*3>;2-*i =Xk.X3XiX.

Макстермом (констнтуентой нуля) называется функция п пере-

менных Mi (V) = Kt (V). = П 4" == V х.р. 14

Согласно свойству первичных термов (1.29) можно записать

где v=(jc„.....xi), (=e„...ei. Макстермы обладают следующими свойствами:

M,(v)=r""="*

(1, если v = Vj Vji

Мj (v) V Mj (v) s 1 j если (• /;

2"-]

П Mj(v)=0. i=0

Свойства накстермов могут быть получены из свойств мнитер-мов (1.33)-(1.35) ка основании определения макстермов (1.36). Макстермы - это функции, равные нулю только в одной точке Vi области определения, состоящей из 2" точек.

Запишем все макстермы двух переменных Хз vi Xf. Mo(v) =

=xl\/x°i=X2\/Xi; Mi(v)=xl\/x\=X2\/~Xi; M2(v) =jcVJC=J2V«i;

Мз(\)=х1\/х\=Х2\/х1, где v={xi, Xi). Запишем макстерм Mi3(v)

для ,1=4: Mn{v)x\\/xlyxl\yx\ =7\/XiVxVxt.

Для большей наглядности в табл. 1.3 (таблица истинности) приведены все минтермы и макстермы двух переменных х и Хи

Табл,ица 1.3

Минтермы (макстермы) представляют собой функции, принимающие минимальное (максимальное) значение из значений своих

первичных термов дГр, т. е. если хотя бы один из первичных термов

ХрР равен 0(1), то и мннтерм (макстерм) равен 0(1).

Совершенная дизъюнктивная нормальная форма (СДНФ). Теорему разложения (1.24) для функций п переменных можно использовать п раз, т. е. функцию можно разложить по всем п переменным Хр, где р= 1,..., п. В качестве примера рассмотри.м разложение функции f(v)=f{xi, Ki) двух переменных «а и дгь По теореме разложения (1.24) получим f{X2, X\)=Xi-f{0, Xi)\/X2-f{\, Xi).

Далее каждую из функций /(О, Xi) и /(1, Xi) можно разложить