Раздел: Документация

0 1 2 3 4 5 6 ... 119

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

хр

V/(*„,..., zp,...,хх) = хр V/(*„,..., l,...,*i), \ V f(xn,...,xp,...,Xl) = xpV f(xn,...,0,...,Xl). / {<1-бг>

Тождества (1.31) легко доказать методом перебора или с помощью теоремы разложения (1.29). Тождества (1.31) и (1.32) являются мощным средством для упрощения логических выражений. Легко доказать закон поглощения (1.15) и закон (1.18), используя второе тождество (1.32):

xVxy = xVOy=x; xVxy=xVOy = xVy. Пусть требуется упростить функцию

/(") = х2хг ф х3х2 Ф хх V х3х2 х2. Используя первое из тождеств (1.31) относительно х2, получим

f(v) = 0 • хх ф х3 0 ф хх V х3 • 0 • х2 = x3®xxV х3 х2.

Для упрощения выражения х3 ф ц V х3 можно использовать второе из тождеств (1.32), тогда

f(v) = 0 ф хх V х3 х2 = хх V х3 х2 = ххх2х3. По принципу подстановки можно записать

/iH-/k/iM] = /iH-/(o), \ /iM/k/iM] = /iM/(i). J

(1.33)

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

f(u) = х1х2® (хх V х3) [х2х3 ф ххх2 ф (хх V х3) V х2х3]. Обозначим fx =ххх2ф (хх V х3), тогда

/(") = 7i (*2*з Ф 7х V х2х3) = ~Jl (х2х3 Ф О V х2х3) = Jx (х2 V х3). Далее легко получить, что

f(u) = ххх2 ф (хх V х3) (х2 V х3) = хх (х2 ф х3).

Иногда целесообразно производить преобразования выражений с помощью тождеств (1.31) и (1.32) в обратном направлении, переходя от менее сложного выражения к более сложному. Так, функцию сумма по модулю два можно представить в виде

х у V х у = х~у у V х х~у = х~у (х V у).

Результат получился также простым, но за счет вынесения общего члена х у за скобки. Цель приведенного преобразования состояла в исключении инверсных сигналов хну.

С практической точки зрения переменные, являющиеся аргументами переключательной функции, иногда удобно подразделять на два типа: уч - информационные и Хр - управляющие. Функции f(yi,yo,zi) и /(уз,У2,Уг,Уо,х2,х1), имеющие по переменным хр разложения

/(2/1,2/0,жх) = yoXl V t/izj,(1.34)

/(2/3,3/2, J/i, 2/о, Z2,zi) = yox2xiV yiXiXiV y2x2xi\/ y3x2xi, (1.35)

называются мультиплексными функциями. Легко убедиться, что конъюнкция любых двух членов мультиплексной функции равна 0 за счет значений только управляющих переменных хр (основное свойство этих функций). Число управляющих переменных у мультиплексных функций может быть и более двух. Такие функции описывают коммутаторы сигналов, так как для каждой комбинации значений управляющих сигналов функция принимает значение одного из информационных сигналов. Данные коммутаторы называются мультиплексорами (Multiplexers).

Инверсные мультиплексные функции, соответствующие (1.34) и (1.35), определяются выражениями:

/(2/1,2/0,1) = Уо*1 V ViXU

!{Уг;У2,У\,Уо,х2Х1) = УоХ2хг \1у1Х2хг Уу2х2хх Vy3x2xv

Истинность данных соотношений легко доказывается с помощью теоремы разложения (1.29) по переменным х2 и Х\.

Представление переключательных функций в форме (1.34) или (1.35) часто позволяет лучше понять их практическое назначение. Например, разложим функцию /(у2,У1,х2,хг) = у\ х\ V г/2 • #2 V г/2 • 2/1 по переменным Х\ и i2:

1(У2,У1,х2,х1) = Xl(y2x2 V 2/22/1) V Х\{У\ V У2Х2) = = х2(Х1у2у! V Ж12/1) V x2[Xly2 V xi(j/i V у2)\ = = 2/22/121 V yix2xi V y2x2xi V (2/2 V yi)x2x1.

Полученная функция описывает функциональный коммутатор, называемый функциональным мультиплексором, так как производится коммутация не только самих информационных сигналов у2 и ух, но и некоторых функций от них (у2 2/1, 2/2 V у\). Понятие функциональных мультиплексоров имеет особое значение для аналитического описания интегральных микросхем. Например, выпускается 4-разрядный функциональный мультиплексор 1561КП4, реализующий функции

DOj = 0 • х2хг V DI3ix2xi V DIj2x2xx V DI}X ф DIj2x2xi,

---

где х2 и хх - управляющие сигналы, DIj2 и DIji - входные информационные сигналы, / Ю, - выходные сигналы, j - 0,1,2,3.,J

Рассмотрим другой тип разложения функций - разложение Рида. Если х • у = 0, то i V j/ = i ф у. Действительно, х ф у -xQ>yVx-y = x- yVx-y\/x-y = xVy. Поэтому разложение Шеннона

f(xn,...,xp,...,xi) = xp9qV xp9i,

где gQ = /(x„,...,0,...,xx), дх = /(&„,..., 1,... .агО, примет вид:

f(xn,..., хр,..., xi) = хрд0 V хрдх = хрд0 ф хр#х = = (18 a:p)ffo 8 xpgi = д0 ф ipffo ® жр0х = ffo 8 (до 8 ffi) • ay Полученное выражение

/(х„,..., хр,...,хх) = д0 8 (до 8 ffi) хр(1.36)

называется разложением Рида.

Выполним разложение Рида функции f(x2,xx) по двум переменным:

/(х2,хх) = /(0,хх) 9 [/(МО 8 /(0,хх)]х2 = /(0,0) 8 [/(1,0)8 8/(0,0)]х2 9 {/(0,1) 9 [/(1,1) 9 ДО, 1)]х2 9 Ф/(0,0)©[/(1,0)е/(0,0)]х2}х, = = ао Ф (а2 6 а0)х2 © [ах © (а3 ф ах)х2 ф а0 © (а2 ф а0)х2]хг = = а0 ф (а2фа0)х2 ф axXj ф (а3фах)х2хх ф a0xi 9 (а2фа0)х2Хх =

= а0 8 (а2 ф а0)х2 ф (ах ф a0)si 9 (а3 9 а2 9 аг 9 а0)х2хь где а, = /(f,), f, = (е„,..., ер,..., ei). Введя обозначения

bi = ai ф a0, b2 = а2 ф a0, 63 = a3 ф a2 ф аг ф а0, получим

/(х2,хх) = а0 фбххх ф62х2 Фбзх2хх.(1.37)

Данное выражение представляет собой полином второй степени от переменных х2 и Хх.

Аналогично можно показать, что любую функцию п переменных можно представить в виде полинома n-й степени. В таком представлении функций используются только операции к, Ф и константа а0 = 0 или 1. Функции, описываемые полиномом первой степени, называются линейными. Так, любая линейная функция двух переменных, как это следует из (1.37), представляется выражением

/(х2,хх) = а0 ф frxxx ф 62х2.(1.38)

Из трех двоичных коэффициентов Ь2, Ь\, и ао можно составить восемь комбинаций их значений, поэтому, как это следует из (1.38), имеется восемь различных линейных функций двух переменных: 0,1,хх,хх,х2,х2, х2 ф хх, х2 ф хх.

Линейные функции п переменных описываются полиномом первой степени

/(хп,...,хр,. ..,хх) = а0 9 аххх 9 ... 9 apxp ф ... 8а„х„ (1.39) (здесь коэффициенты ар не являются значениями функции f(v) в точках ,).

1.6. Решение систем логических уравнений

В общем случае равенство /( , ym,..-,yi) = g(v, ym, , yi), где v = (x„,..., xi), может задавать не тождество, а логическое уравнение, которое обращается в тождество только при определенных значениях yr = fri"), г = 1,2,..., т, т. е.

/["i Vm(")i • »ViM] = 9W, 4>m(v), , Vi(")l-Тогда исходное равенство можно рассматривать как уравнение с m неизвестными уг. Один из методов решения систем логических уравнений приведен в [9]. Рассмотрим универсальный метод решения, пригодный для систем с произвольным числом уравнений и любым числом переменных.

Системы логических уравнений с одним неизвестным. Пусть задана система логических уравнений с одним неизвестным у

f](v,y)g](u,y),(1.40)

где v = (хп,.. .,Xi), j = 1,2, ...,k. Необходимо решить ее относительно у, т. е. найти такие значения у - <p(v), которые обращают в тождества все уравнения системы (1.40):

№М")] = ФМ»)1 .(I-41)

Для этого рассмотрим сначала, какие операции можно выполнять над равенствами без нарушения логических связей, которые они выражают. Если х = у, iox*z = y*z(x-y=>x*z = у*z), где * - любая двухместная операция алгебры логики: &,

V ffl И ПО В чтпи norvQ vfinjTWTT.Ctf ТТЛттГТЯПИП П TrnaRVJQ часть на

основании принципа подстановки х вместо у. Однако в общем случае из равенства х * z = у * z вовсе не следует, что х = у, например, из равенства xVz = yVzne следует, что х = у, а также из равенства x-z = у-z не следует, что х = у. Поэтому такие операции нельзя применять для преобразования уравнений (1.40).

---

Возьмем теперь в качестве операции * операцию ®. Из равенства х = у следует, что х ® z = у ® z. Используем еще раз эту операцию:

(х 8 z) 8 z = (у ф г) ф z => х ф (г 8 г) = у ф (г 8 г) => =>а:80 = г/80=>а: = г/, т. е. из равенства а: 8 2 = у 8 2 следует, что х = у. Итак,

x = y&x®z = y@z,(1.42)

а значит, логические связи, выражаемые уравнениями, не нарушаются при преобразовании последних с помощью операции 8 (в качестве z можно взять и любую из переменных х или г/). На основании (1.42) уравнения (1.40) можно привести к виду

Л(*Л У) Ф 9j{v, у) = gj{v, у) 8 gj(v, у),

fj{»,y)®9j(v,y) = 0,(1.43)

где j = 1,2,..., к. Используя аксиомы (1.2) и (1.3), легко убедиться, что если х = 0 и у = 0, то а: V г/ = 0, и наоборот: если х V у = 0, то х = 0 и у - 0, т. е.

х = 0, y = 0&xvy = 0,(1.44)

а значит, операцию V можно использовать для преобразования уравнений, правая часть которых равна нулю. На основании (1.44) систему логических уравнений (1.43) можно представить в виде

к

V [/;("> У) Ф 9j(", У)} = f(v, У) = 0,(1.45)

3 = 1

т. е. любую систему логических уравнений можно свести к одному уравнению f(u, у) = 0, решение которого относительно у и нужно найти.

Разложив левую часть уравнения (1.45) по у, будем иметь У- V>i V уф2 = 0,(1.46)

где

кк

V>i = V [/»(". о) © яА", о)], ф2 = V 1) Ф 1)]

i=ii=i

и t/>i = i>\{v), ф2 = t/»2(). Решением данного уравнения может быть только некоторая функция р(ф2, фх) от переменных фх и ф2. Подставив в уравнение все возможные комбинации значений этих переменных, получим:

t/>2 = 0, 1/>! = 0=>0 = 0=>г/ = h{v) - произвольная (полностью неопределенная) функция; г/>2 = 0, фх = 1 => у = 1; ф2 = 1, фх = 0 => у = 0;

t/»2 = l,t/»i = l=>l = 0 - решение не существует или, другими словами, решение имеется только при выполнении условия ф1 ф2 = 0, а значит, при отсутствии решения можно взять произвольное значение у = с (0 или 1).

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

у{Фг,Ф\) = Цу) • Wi v 1 • v 0 • Ф2Ф1 V*c • ф2фг. Если положить с - 1, то

#)W = Vft(c))(1-47)

причем решение (1.47) существует лишь при выполнении условия

фх-ф2 = 0.(1.48)

Подстановка решения (1.47) в уравнение (1.46) дает

фх v h -ф2 фг v (фх v h ф2) ф2 = фх ф2, т. е., действительно, при выполнении условия (1.48) левая часть уравнения (1.46) обращается в нуль, и решение у(ф2, ф\) = - некоторая функция переменных хп,..., хх-

Если функция ф2(у) = 1, то решение у = <px(v) - полностью определенная функция (существует единственное решение). Если фх(ь) = 0 и ф2{у) = 0, то у = h(v) - полностью неопределенная функция. Это означает, что решаемое уравнение является тождеством, так как оно выполняется при любых значениях переменных у и и - (ж„,..., хх).

В общем случае решение у = фх{») V ho(v), где ho(v) - 0 или 1 в точках, в которых функция ф2(у) = 0, а в остальных точках ho(i>) = 0, т.е. решением является неполностью определенная функция, которой соответствут целый класс полностью определенных функций.

Несмотря на кажущуюся сложность выражения (1.47), его достаточно просто применять при решении многих практических задач. Это связано с тем, что при решении вместо неизвестных в уравнения подставляются константы 0 и 1.

Пример 1. Доказать тождество x-yVx-zVy-z = x- y\/x-z. Решим уравнение относительно х:

х = фх V h ф2 = (0 • у V 0 • z V у • z) ф (0 • у V 0 • z)V

Vftly viz V yz) ф(1-уфТ-г) = гфгУ h-уфу

0 1 2 3 4 5 6 ... 119