Если взять с=1, то

г/= 1 V ft (V) tpa. (1.45)

Решение (1.45) существует лишь при

Ij52-l)l=0. (1.46)

Несмотря иа кажущуюся сложность выражения (1.45), его достаточно просто применять при решении многих практических задач. Докажем, например, тождество хууxz\fyz=xy\/хг. Решим уравнение относительно х : дг= (О-gVO-г\/уг) ®(0-y\/fi-z)\/H(\&

&у\/1-г\/уг) ф {\-y\/l-z) =z®z\/hy®y=h{y, z). Решение существует, так как ¥2-¥i=0-0=0. Уравнение имеет решение x=ft, т.е. оно справедливо для произвольных значений х независимо от значений остальных переменных,, а значит, является тождеством.

Решение систем логических уравнений с двумя иеизвестиымн

fj(-v,y,2)=gj{v,y,z), (1.47)

где у и 2 - неизвестные, j=l...k, \=(.Хп, х) сводится к их последовательному решению относительно неизвестных у н г. Решив систему (1.47) относительно t/, в соответствии с (1.45) и Cl!.46) получим

(1.48)

y=i?i(v, г) V fti 112(,г), i>2 (V, z)-ti (V, г) (V, г),

i. (V, г) = Uj (V, О, г) © gj (V, О, z)I; k

(V,?) = y(y(V, l,2)©gry(V, 1,Z>}, ft,,= ft,(V),

Если функция ¥(v, z)=0, to это означает, что решение системы (1.47) относительно у существует независимо от значений z. ГГоэтому можно взять 2= hiiv).

Рассмотрим случай, когда функция (v, г) #0. Так как условием существования решени-я системы логических уравнений (1.47) относительно у является уравнение (v, z)=0, то, возможно, оно будет удовлетворено соответствующим выбором неизвестного z. Следовательно, нужно найти решение данного уравнения относительно Z: 2=V(v, 0)Vi2*(v, 1), которое существует только в том случае, если BbmoflHHfCTCH услоние V(v, l)-4(v„ 0)=0 (ft) и ftj - независимые произвольные функпии). Если данное условие выполняется, то решение системы логических уравнений (1,47) относительно у находится нодстановкай в (1.48) найденного значения г, В результате будут получены функции г/ = ф(v) и z=ф2(v), не зависящие от неизвестных у в z.

Пусть требуется иайти решение уравнения Q+ = QJ\/QK относительно неизвестных J н К. Тогда

Q-f = ду V Q К => У = Q+ Ф QK V fti Q+ Ф (Q V /О, 1-%= (Q+ Ф QK) IQ+ Ф (QVK)]. Приравняв последнее уравнение нулю, находим 2» 19

K = (Q+® Q) (Q+ © 1) V й2 Q+ (Q+ Ф Q) = Q+ Q V la Q-Подставив найденное значение К в функцию для /, получим

= Q+ Ф Q Q+ Q V й2 Q V fti Q+ ® (Q V Q+ Q V fts Q) =

= Q+ Ф QQ+ V fti Q+ Ф (Q V Q+) = Q+ Q V ft, Q.

1.3. Минимизация переключательных функций

Одной из основных задач, возникающих при синтезе комбинационных схем (КС), является минимизация переключательных функций, которые эти КС реализуют. Чем проще логическое выражение, описывающее функцию, тем ироще и дещевле реализующая ее КС. Аналитический метод минимизации в общем случае весьма трудоемок, поэтому наибольшее распространение получил графический метод минимизации с помощью диаграмм Вейча, несомненным достоинством которого является наглядность и простота использования при небольшом числе переменных (п<6).

В качестве критерия сложности логического выражения, описывающего функцию, целесообразно принять число первичных термов

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

Конъюнктивные и дизъюнктивные термы. Конъюнктивным термом (контермом, элементарной конъюнкцией) называется конъюнкция любого числа первичных термов xj, если каждый первичный терм с индексом р входит в нее не более одного раза. Любой кон-терм представляет собой функцию п переменных /((,j(v), которую можно записать в виде

/(i,,(v)=n (рр*/] (1-49)

где v=(jc„, xi)\ ер = 0 или 1; ер = 0 или 1; ер<ер\ ien-Ci, 1=е„...е\.

Действительно, в соответствии с выражением (1.30)

/ру/р 1 V е-И «р = р,

[1. если ерФер[ер = ер), поэтому функция Kt,j{v), будет представлять собой конъюнкцию г<п первичных термов xjl Запишем, например, в явном виде кон-терм Kij{v) трех переменных. Для этого воспользуемся символической схемой

*з 9, А

Если ео = ер для всех р, то i=j и хРух=х" для всех

р - \...п, поэтому, как следует из (1.49), fdj (v) = (v) = О х =

- Ki (v), т.е. контерм Ki,i{v) является минтермом Ki{v),

Если же ерфер для всех р(ер<ер, т.е. ер = 0, ер = 1), то t=3

=0, /=2"-I в д:рР\/Жр=1 для всех р, поэтому ,2п , (v) = 1.

Из определения (1.49) и рассмотренных частных примеров следует, что все контермы, за исключением Ki.i(v)=Ki(v), являются вырожденными функциями п переменных.

Всего имеется 3" различных контермов п переменных. Действительно, так как хухр" = Хр,Хр или 1 (дизъюнкция первичных термов может принимать любое из этих трех значений), то каждой функции Ki,i{\) можно поставить в соответствие одно из «-разрядных чисел с основанием системы счислении д=3, а поскольку имеется 3" различных п-разрядиых чисел при ?=3, то и число различных контермов равно 3".

Дизъюнктивным термом (дизтермом) называется функция п переменных

Дизтермы представляют собой дизъюнкцию любого числа г<п первичных термов ЖрР, причем каждый первичный терм с индексом р входит в иее только один раз. Всего имеется 3" различных диз-термов, так как имеется 3" различных контермов.

Правила минимизации переключательных функций. Общие правила минимизации можно установить только для случаев, когда в результате минимизации получаются так называемые минимальные нормальные формы (МИФ) функций (термин «нормальные формы» означает, что в логическом выражении, определяющем функцию /(v), последовательно выполняются не более чем две операции из совокупности операций И, ИЛИ, И - НЕ и ИЛИ - НЕ).

Два мннтерма Ki(\) и Kj(v) будем называть соседними, если

они различаются только одним первичным термом Хр , т. е. если для одного из миитермов ер -О, а для другого ер = 1 (все же остальные первичные термы одинаковые). Так, например, если п = 3, то минтермы Кз{)=ХзХ2Х\ и ((v) =жз«2*1 являются соседними, так как они различаются только одним первичным термом х. Для мннтерма Kd(v) соседними являются также минтермы y(i(v) = <=хзХ2Х1 и Кг()=хзХ2Х1. Понятно, что каждый минтерм л переменных Kt(v) имеет по п соседних миитермов из общего числа 2" минтермов.

Рассмотрим контерм п переменных Ki,i{v), не зависящий от одной переменной Хр, т.е. случай, когда контерм является конъюнкцией (л-1)-го первичного терма. Данный контерм можно предста-