Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 58
Текст из файла (страница 58)
Алгебра переключений 245 (<п<(исг!ои агар)). Рассмотрим, например, обобщенную теорему идемпотентнос- ти. При и = 2 теорема Т12 эквивалентна теореме ТЗ и поэтому верна. Если она верна для суммы, в которую Х входит ! раз, то утверждение теоремы справедливо акже для суммы из 1+ 1 величин Х согласно следующему рассуждению: Х+ Х+Х+ ... + Х=Х+ (Х+Х+ ... + Х) (слеваисправаХвходит<+! раз) = Х+ (Х) (если теорема Т12 верна при и = <) =Х (согласно теореме ТЗ). Таким образом, утверждение теоремы выполняется при всех конечных значениях п.
табл. 4.3. Теоремы алгебры переключений для и переменных (Обобщенная ндемпотентность) (Теоремы Де Моргана) ХХ+ ". +Х =Х Х Х ". Х=Х По-видимому чаще всего в алгебре переключений применяются теоремы Т1 3 н Т! 3', называемые и<яараманиДе Моргана (ОеМогеап У <(<гоген<з). Теорема Т(3 говорит, что в случае, если берется дополнение к сигналу на выходе и-аходового вентиля И, то результат эквивалентен прохождению через п-входовой вентиль ИЛИ сигналов, являющихся дополнениями к сигналам на входах вентиля И. Другими словами, схемы на рис. 4.3(а) и (Ь) эквивалентны. 2= <х.т>' (а) г=х'+ж 2=х'+ж рис.4.3.
Эквивалентные схемы соглаонотеореме Де МорганаТ13: (а) И-НЕ; (Ь) "Е.ИЛИ; (с) обозначение вентиля И-НЕ; (б) изображение схемы, эквивалентной вентилю И-НЕ В разделе 3.3.4 было объяснено, как устроена КМОП-схема И-НЕ. Прн любом наборе входных сигналов сигнал на выходе вентиля И-НЕ является дополнением к выходному сигналу вентиля И с теми же самыми входными сигналами, и поэтому фитиль И-НЕ можно обозначить так, как показано на рис.4.3(с).
Однако по своей "онструкции КМОП-схема И-НЕ не представляет собой последовательного вклю"ения схемы И и транзисторного инвертора (схемы НЕ); вентиль И-НŠ— это просто <т>2) <тпг) <Т>3) <т>у> <т>ю <т>5) <тну> <х,.х,.... Х„>'=х,'~х,'+" +х ' <Х) '~ Х ~ '' + Хя) Ху Хя ' ''' Хя (Е<ХНХЬ...,Хи Н )1'=Е<Х1',Хэ',...,Х„',ма) (ОбабщЕННая тварЕМаДЕ МОрГаНа) г<хохя...,х,>=х, г«,х,,....хдэх, -г<о.х,,...,х„) (теоремы расщнрення г<х,,х>....х„)=!х„.г<ох„, „х„>1.<х,,е<>,х, х„)! Шеннона) 246 Глава 4.
Принципы проектировании комбинационных логических схем такое удачное объединение транзисторов, которое реализует функцию И-НЕ, Тео рема Т13 говорит нам, что обозначение, приведенное на рис. 4.3(д), выражает ту же самую логическую функцию (кружочки на входах вентиля ИЛИ указывают на логическое инвертирование). Другими словами, можно считать, что схема И-НЕ выполняет функцию НЕ-ИЛИ. Глядя на входы и выход схемы И-НЕ, пел юя решить, как именно эта схема уст роена внутри: состоит ли она из последовательно включенных схемы И и инверго ра, или из инверторов, за которыми следует схема ИЛИ, или непосредственно реа л изует требуемую функцию средствами КМОП-логики.
Происходит это потому, что»юбая ст«иа И-НЕ выполняет в точности одну и ту же»огни«скую функцию Хотя выбор обозначения не имеет никакого отношения к тому, что делает схема, мы покажем в параграфе 5.1, что подходящий выбор значительно облегчает понимание функции, выполняемой данной схемой. Подобную зквивалентность символических изображений можно вывести нз теоремы Т13'. Как показано на рис. 4.4, функцию ИЛИ-НЕ можно реализовать, включая друг за другом вентиль ИЛИ и инаертор, либо пропустив сначала входные сигналы через инверторы и подавая их затем на вентиль И, Π— — 2=1Х+У) х — 7 2=(Хвт) (с) (а) х — < Г) 2=х г т — к 2= х'Г (Ь) Рис.
4.4. ЭквивалентныесхемыоогласнотеоремеДеМорганаТ13" (а) ИЛИ-НЕ, (Ь) НЕ-И; (с) обозначение вентиля ИЛИ-НЕ, (г() изображение схемы, эквивален- тной вентилю ИЛИ-НЕ ЕР/ЧХ,'Д = (Ф. Х) + (Х У) + ()аГ (Х'+ 2')) =((ЬУ)' Х)+(Х У)+(а ((Х)'+(2)')). Во второй строке мы заключили дополнения переменных в скобки, чтобы напомнить, что «штрих» ' является оператором, а не частью имени переменной.
Теоремы Т! 3 н Т13' представляют собой частные случаи обобщенной твор«мы Дв Моргана (явпвгайгвг! 0«Могаап з гпвогвт) Т14, которая применима к произвольному логическому выражению Е. По определению, доно»нвни«и логическогоо выражен и» (сотр)втвпг ог а 1ойгс вхргваа!оп), обоз иачеаемым (е)', является выражение, значение которого противоположно значению Е для любых возможных комбинаций входных сигналов. Теорема Т! 4 очень важна, так как она дает нам способ преобразовывать н упрощать дополнения выражений.
Теорема Т14 утверждает, что дополнение заданного логического выражения с и переменными можно получить, меняя местами знаки + н . и заменяя все пеРеменные нх дополнениями. Пусть, например, имеется выражение: 4.! . Алгебра переключений 247 По теореме Т1 4 получаем: (Г(%',Х т Х)) =((Ф )'+ Х') (Х' + Ъ") . (%~'ч-((Х')' (у')')), Используя теорему Т4, последнее выражение можно упростить: (Е()!гХ,Уг))'=(Ъ +Х) (Х' -У) (Ъ" +(Х Л)).
В самом общем случае теорема Т14 позволяет находить дополнение заключенного в скобки выражения путем замены+ на . и наоборот, взятия дополнений переменных, не помеченных знаком дополнения ('), и опускания этого знака у переменных, дополнения которых фигурируют в исходном выражении. Обобщенную теорему Де Моргана Т!4 можно доказатгн убедившись в том, что все логические функции можно записать либо в виде суммы, либо в виде произведения подфункций, и применяя затем рекурсивно теоремы Т13 и Т!3'. Однако более информативным и более убедительным является доказательство на основе принципа двойственности, который сейчас будет объяснен. 4. 1 .5.
ДВойСТВЕИИОСТ«э Все аксиомы алгебры переключений были сформулированы попарно. Каждая аксиома, помеченная штрихом (например, А5') получается из аксиомы, не помеченной штрихом (например, А5), в результате того, что О и! меняются местами, и то же самое происходит со знаками . и н, если таковые имеются. Таким образом, мы приходим к следующей жетатеореме (тешглеог«т), то есть к теореме о теоремах: Пуни«и» двойств««ногтя; Любая теорема или тождество алгебры переключений остаются справедливыми, если повсюду меняются местами О и 1 и знаки и+. Метатеорема верна, поскольку истинными являются все утверждения, двойственные по отношению к аксиомам; следовательно, все утверждения, двойственные по отношению к теоремам алгебры переключений, можно доказать, используя двойственные аксиомы.
В конце концов, что значат имена и символы, если уж нато пошло? Если бы в программном обеспечении, с помощью которого была набрана эта книга, была ошибка, в результате чего повсюду в этой главе О и! и знаки+ и поменялись бы местами, то вы научились бы той же самой алгебре переключений; разве что терминологияя окажется при этом немного странной, потому что слова типа «произ- веление» будут употребляться для описания операций со знаком «+».
Двойственность важна, потому что она удваивает полезность всего, что вы Узнаете об алгебре переключений и о преобразованиях функций, относящихся к переключениям. Практическая ценность этого, со студенческой точки зрения, состоит в том, что учить надо только половину всею необходимого! Например, выучив однажды, как по выражениям вида «сумма произведений» синтезировать двухуровневые логические схемы И-ИЛИ, вы автоматически осваиваете двойственный метод синтеза схем ИЛИ-И по выражениям вида «произведение сумм». В алгебре переключений существует все же одно принятое условие, когда знаки и+ не считаются равноправными, так что принцип двойственности не обя- 248 Глава 4. Принципы проекпвроаания комбинационных логических схем зательно оказывается верным.
Можете догадаться, о чем идет речь до того, как прочитаете приведенный ниже ответ на этот вопрос? Рассмотрите утверждение теоремы Т9 и вам станет ясной абсурдность «двойственного утверждениягк Х+Х.У =Х (теоремаТ9), Х. Х+ у = Х (в результате применения принципа двойственности), Х+У=Х (согласнотеоремеТЗ'). Очевидно, что последняя строка в этих выкладках не верна. Где мы поступили неправильно? Проблема заключается в старшинстве операторов. Мы могли запи сать левую часть равенства в первой строке без скобок согласно условию, что у оператора более высокий приоритет. Но коль скоро мы применяем принцип двойственности, нам следовало бы вместо этого назначить больший приоритет оператору + или записать вторую строку в виде: Х (Х+ у) = Х.
Лучший способ избегать подобных затруднений состоит в том, чтобы до применения принципа двойственности записывать исходное выражение со скобками. Давайте дадим формальное определение двойственному логическому выраз>сенин> (>>иа( о)'а!орс ехргевв>о ). Если Е(Х>, Хп ..., Х„ч-,, ') логическое выражение, содержащее переменные Х>, Хн ..., Хи и операторы +, ° и ', и такое, что в нем проставлены все необходимые скобки, то выражением, двойственным по отношению к Е, которое мы будем обозначать Еп, является то же самое выражение при условии, что знаки + и поменяны местами: Еп(Х>,Х>, ...,Х„, +,,') = Е(Х>,Х2, ...,Х„,, +,'). Вы уже знаете это, конечно, но мы специально привели данное определение в такой форме, чтобы подчеркнуть близость двойственности и обобщенной теоремы Де Моргана Т!4, утверждение которой мы можем теперь представить в виде: [Е(ХьХх...,Хп))'= Е (Х>',Хз',...,Х.').
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
