Раздел: Документация
0 1 2 3 4 5 6 7 ... 119 (при выполнении этих вычислений упрощение функций ф\ и Ф2 можно производить только по отдельности). Решение существует, так как ipi = z ® z = Q, ф2- уфу = 0и ф\ф2 = 0-0 = 0. Дальнейшее упрощение полученного решения дает: х = ft = h(y, z), т.е. уравнение справедливо для произвольных значений х независимо от значений остальных переменных, а значит, является тождеством. Из данного примера следует общий вывод: разработанный метод решения логических уравнений можно использовать в качестве универсального метода для доказательства любых теорем и тождеств алгебры логики, формулируемых в виде равенств логических выражений (решением логического уравнения должна быть полностью неопределенная функция ft). Пример 2. Найдем решение уравнения х • у V а? • у - у: у = (х ф 0) V ft • жф 1 = х V ft • х, Vi • Ф2 = х ф 0, следовательно, решение отсутствует. Пример 3. Найдем решение уравнения х у V х у - х: у = (х ф х) V ft • ж ф х = 0 V ft • Т = 0, фх ф2 = 0, т. е. имеется единственное решение у = 0. Пример 4. Докажем высказанное в начале данного раздела утверждение, что из равенства х у = х z не следует, что у = z. Для этого решим первое равенство относительно у: у = (0 ф х z) V ft • х ф х z = х z V ft • x 2, ф\ ф2 = 0, поэтому у = х z V ft • (ж V z) = х z V ft • ж, т. е. у z. Пример 5. Докажем теорему, утверждающую, что если х у = x-z и xVy - xVz, то у - z. Для этого решим систему двух логических уравнений относительно у: У = (0 в х z) V х ф (х V z) V ft • (х ф ж • 2) V [1 ф (х V z)} = = z- 2V5"-zVft-£zVa7-2 = 2Vftz"=z, так как фх ф2 - z - Т = 0. Действительно, получили, что у = z. Алгебраическое представление логических уравнений. Если символы 0 и 1 считать числами, то все логические операции можно»заменить на арифметические операции или алгебраические формулы на основании очевидных соотношений х = х, х = 1 - х, х2к.хх - х2 х хх, хкх = х х х - х (в левой части используются логические переменные и операции, а в правой - алгебраические). Так, можно получить Х2 V Хх = Х2 Хх = Х2 + Хх - Х2 Хх, х2 Ф Хх = х2 Хх V Х2 Хх = х2 + хх - 2 • Х2 Хх (здесь знаки конъюнкции & и алгебраического умножения х заменены точками - какая из этих операций используется, устанавливается по другим имеющимся в выражении операциям). На основании приведенных соотношений логическое уравнение (1.46) преобразуется в алгебраическое Ф\ - У {Ф\ - Ф2) = о, решением которого будет у = фх/{Ф\ ~ V)- Легко заметить, что при = 2 = 1 решения не существует и у = -Ьfi.-(1 - фх~ф2) при фхф2 = 0. Системы логических уравнений с более чем одним неизвестным. Решение систем логических уравнений с двумя неизвестными fj(v,ytz) = g3{v,y,z),(1.49) где у и z - неизвестные, j = 1,2,..., к, v = (хп,..., хх), сводится к их последовательному решению относительно неизвестных у и z. При этом следует найти такие функции у = tpx{v) и z = (p2{v), что /Л"» ViH 4>г{у)] = 9j[v, (fi(v), VJ2(f )]• Решив систему (1.49) относительно у в соответствии с (1-47) и (1.48), получим: у = фх(у,г) V hi ф2(1/,г), 1(\Ь$) Ф\{г) ф2(1/,г) = ф{и,г), J где ФЛ,г)= V [/>,o,z)©KM)L j=i к Ф2{»,*) = V [/Л*лМ)©£,(1/,1,2)], hx = hx{v). Если функция ф(у, z) = 0, это означает, что решение системы (1.49) относительно у существует независимо от значений z. Поэтому можно взять z = h2(v). Тогда, подставив это значение z в (1.50), получим: у - фх{у,Ь,2) V hx ф2,%2) = <px(v). Рассмотрим случай, когда функция ф(г/, z) ф 0. Так как условием существования решения системы логических уравнений (1.49) относительно у является уравнение ф(у,г) - 0, то, возможно, оно будет удовлетворено соответствующим выбором неизвестного z. Поэтому нужно найти относительно него решение уравнения ф[у,z) = фх,*) • ф2(1>,г) - 0: z = ф(у, 0) V h2 ф(у, 1) = ip2(v), которое существует только в том случае, если выполняется условие где t/>(i/,0) = t/>i(f,0) 2(,0), t/>(i/,l) = 1(1/, 1) • t/>2(i/, 1) и /i2 = /12(1/) - независимая от /ii = /11(f) полностью неопределенная функция. Если данное условие выполняется, то решение системы логических уравнений (1.49) относительно у находится подстановкой в функцию (1.50) найденного значения z: У = ФЛ",<P2(v)] V ф2[у,4>2{v)] - 4>\(v)- В результате получены функции у = (pi(v) и z = tp2(v), не зависящие от неизвестных у и z. Таким образом, решение системы логических уравнений с двумя неизвестными сводится к последовательному решению одного или двух уравнений с одним неизвестным. Точно так же решаются системы логических уравнений и с большим числом неизвестных. В общем случае в зависимости от порядка решения систем логических уравнений относительно неизвестных получаются различные формы функций. Однако все эти формы являются эквивалентными, т.е. различным формам полученных неполностью определенных функций соответствует один и тот же класс полностью определенных функций. Пример 1. Решим относительно неизвестных у и г уравнение х © у 0 z = х V у V z. Найдем решение уравнения сначала относительно у: у = х ф z ф (х V г) V Й1 • х ф z = х V J V hi х ф г, ф1 ф2 ф 0, поэтому решаем уравнение (х V Г) • х ф z = 0 относительно г: z = х V h2 х х = х V h2 0, t/>i • 2 = 5" • 0 = 0. Значит, г = ж V й2 и у = JViVA2 Vfti • [ж© (ж V ft2)] = ж V ft2 Легко убедиться, что при подстановке в исходное уравнение найденных значений у и г оно обращается в тождество. Пример 2. Найдем решение уравнения xi-yVz = x2(1-51) относительно у: у = (ii V г) ф ж2 V fti • гф ж2. Легко убедиться, что ip(v,z) ф 0, поэтому решаем уравнение ip(v, z) = [(х\ V г) ф ж2](г ф ж2) = 0 ),0), {1,0}; L,0}; относительно г: г = («1 ф ж2)ж2 V h2 1 ф ж2 = xix2 V ft2 • х2. Так как VM = 0, то решение исходного уравнения существует. Подставив найденное значение z в выражение для у, получим: у = х{х2 V fti • (xi V й2), г = x"ia;2 V h2 х2.(1.52) Если решить исходное уравнение относительно неизвестных в другом порядке, то функции у и г будут иметь вид: у = х{х2 V h2, z = х\х2 V (hi V h2)x2.(1.53) Сравнив решения (1.52) и (1.53), легко заметить, что полностью определенные части у них одинаковые. Решения для у и г зависимые, так как полностью неопределенная функция h2(x2,xi) входит в оба решения. Поэтому решением уравнения (1.51) будет зависимая пара функций {y(x2,xi),z(x2,xi)}. По выражениям (1.52) или (1.53) (результат получается один и тот же) легко вычислить значения этой пары в точках ь>,- = (e2,ei): х2 = 0, xi - 0, » = 0 => 0, х2 = 0, xi = 1, i = 1 => 11, х2 - 1, х\ - 0, i = 2=> {0,1}, {1,1}; x2 = l, Х1 = 1, г- = 3=>{0,0}, {0,1}, {1,1}. Из полученных значений можно составить класс из 2 • 1 • 2 • 3 = 12 полностью определенных пар функций {х, у}. В качестве конкретного решения можно взять любую из этих пар. Пример 3. Найдем решение уравнения х\ V у ф z = х2 относительно у: у = (xi V z) ф х2 V fti • (zi V z) © x2. Далее решаем уравнение rl>(v, z) = [(*! V г) © x2] [(Xl V z) © x2] = 0 относительно г: z = (xi® x2)x2 V Й2 • x2(xi ф ж2). Так как ф(у) = (xi ф ж2)ж"2 = х{х2 ф 0, то логическое уравнение решений не имеет. Приложения систем логических уравнений. Разработанный метод решения систем логических уравнений является мощным инструментом для анализа (см. гл. 2) и синтеза (см. гл. 3) логических схем, широко используемых на практике при проектировании цифровых устройств. Так, он был применен при разработке общего метода структурного синтеза цифровых автоматов на триггерах типов Т, J-K, R-S, D-L и др. [10, 11]. Перечисленные триггеры описываются функциями переходов Q+ = Q®T,(1.54) УQ+ = QJ VQ К,(1.55) Q+ = SvQ-R, R-S = 0,(1.56) Q+ = D-LvQ-L,(1.57) где T,JhK,RhS,DhL - входные сигналы триггеров, Q - исходное состояние триггера, Q+ - следующее состояние триггера (после воздействия входных сигналов). Триггеры типов Т и J-K могут быть только синхронными, а типов R-S и D-L - как синхронными, так и асинхронными потенциальными. При проектировании автоматов в виде таблицы задается функциональная связь между исходным состоянием триггера Q и следующим его состоянием Q+ (переменные в алгебре логики не зависят от времени, поэтому Q и Q+ - разные переменные). Основная задача проектирования заключается в отыскании функций возбуждения триггеров Т, J и К, S и R, D и L, реализующих эту функциональную связь. Для этого следует найти решения функций переходов (1.54) - (1-57) относительно неизвестных функций возбуждения, выразив их через переменные Q и Q+. Триггер типа Т. Решение уравнения (1-54) относительно Т: Т = Q+ 8 Q v h Q+ 8 Q 8 1 = Q+ 8 Q. Для отыскания данной функции возбуждения можно воспользоваться и более простым методом - применить операцию © к левой и правой частям уравнения относительно переменной Q: Q+@Q = Q®T®Q=>T = Q+®Q. Триггер типа J-K. Решение уравнения (1.55) относительно «7: J = g+8Q-vftiQ+8(Q vf), фхф2 = (Q+®QK)[Q+®(ZSvK)]. Приравняв последнее уравнение нулю, находим: К = (Q+ 8 Q) (Q+ 8 1) V h2 Q+ (Q+ © Q) = Q+ Q v h2 Q. Подставив найденное значение К в функцию для J, получим: J = Q+®Q- Q+Q V h2Q VhfQ+®(Qv Q+Q v h2Q) = = Q+®Q-Q+Vh1-Q+@(QVQ+) = Q+ -Qvhx-Q. Триггер типа R-S. Решение системы уравнений (1.56) относительно S: S = Q+ @Q R VP© О V fti • Q+ ф 1 V Д® 0 = = Q+ © Q R V hx Q+ V R, фхф2 = (Q+ © Q R)(Q+ V R). Приравняв последнее уравнение нулю, находим: R = (Q+ 8 Q) Q+ v h2 Q+ = Q+ Q v h2 Q+. Подставив найденное значение R в функцию для 5, получим: S = Q+ ®Q -Q+ -Qvh2-Q+vhx-Q+ vQ+ -Qvh2-Q+ = = Q+ 8 Q Q+ v hx Q+ = Q+ Q v hi Q+. Триггер типа D-L. Решение уравнения (1-57) сначала относительно L, а затем относительно D дает: D = Q+ Qvh2(Q+ VQ), L = Q+®QVhl -Q+®h2. (1.58) Наиболее часто для проектирования цифровых автоматов формальными методами используются триггеры типов Т, J-K и R-S, функции возбуждения которых т = д+®д,(1.59) J = Q+-Qvhx-Q, K = Q+Qvh2Q,(1.60) S = Q+ QVh1Q+, R = Q+ Qvh2 Q+.(1.61) Функции возбуждения D-L-триггера (1.58) использовать значительно сложнее, чем функции (1.59) - (1.61), так как они взаимозависимы (полностью неопределенная функция h2 входит и в D, и в L). Методика синтеза автоматов на D-L-триггерах изложена в [10]. Триггер типа D-T-L. Рассмотрим пример решения уравнения Q+ = D L V (Q ф Т) L с тремя неизвестными D, L, и Т, которое представляет собой функцию переходов D-T-L-триггера. Решение относительно Г дает Т = Q+ Ф (D L VQ I) V fii • Q+ ®(D-L VQ-I). Решив уравнение [Q+ Ф (D L V Q • Г)] [Q+ Ф (D L V Q • I)] = 0 относительно D, получим: D = (Q+ ф Q-I)-(Q+ eO-I) V h2[Q+ ф (L V Q)]-[Q+ Ф (L V Q)]. Из этого следует уравнение (Q+ Ф Q I) • (Q+ Ф Q • I) • [Q+ Ф (L V О)] • [Q+ ф (L V Q)] = 0, решением которого является L = h3. Подставив найденное значение L в функцию D, а затем L и D в функцию Т, окончательно получим: L = h3, D = П3 Q+ V Мз, Т = Й3 • (<Э+ Ф <Э) V Мз- Решение L = Й3 означгшт, что триггер может быть использован для синтеза автоматов и при исключении входа L подачей на него значений 0 или 1. При значении L = 0 функции возбуждения D = h2 3 Пухальсквй Г. И., Новосельцева Т. Я 0 1 2 3 4 5 6 7 ... 119
|
