Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 57
Текст из файла (страница 57)
Другими словами, выражение '»г'.Х+г' Еэквивалентновыражению(11» Х)+(т 2). Последними тремя парами аксиом даются формальные определения опера««й И(А(ЧО ор«гобоя) и ИЛИ (Ой орегайоп) путем перечисления значений сигнала на выходе каждой из рассмотренных схем для всех возможных комбинаций входных сигналов: И ВОТЕЩЕ ЧТО ...
В старых книжках логическое умножение обозначалось простой записью ряДам Цихгарозйюи, (Ху)1, но мы так делать ие будем. Запись рядом не вносит путаницы лишь в том случае, когда названия сигналов могут состоять только нз одного символа. В противном случае как различить: является Ху логическим произведением или двухбуквенным именем сигнала? В алгебре часто имена переменных состоят из одной буквы, но в задачах реального цифрового проектирования мы предпочитаем давать сигналам названия, состоящие нз нескольких букв, которые несли бы смысловую нагрузку. Таким образом, нам необходим разделительный знак между именами, и роль такого знака как раэ "огла бы играть скорее точка, нежели пробел.
В языках описания схем эквивалентом точки в качестве знака умножения служат символы * илн «г, н такой знак является обязательным при написании логической формулы на любом из этих языков 242 Глава 4. Принципы проектирования комбинационных логических схем (АЗ) 0 0=0, (АЗ') ! ч ! = 1; (А4) 1.1=1, (А4) 0+0=0; (А5) О 1 = 1 0 = О, (А 5') 1 ч 0 = 0.~- ! = 1, Пятью парами аксиом (А1-А5) и (А1' — А5') исчерпывается алгебра переключе ний. Все другие сведения о системе можно вывести их этих аксиом, используя их в качестве отправной точки. 4.1.2. Теоремы о функциях одной переменной [Х = О) 0+ 0 = 0 — утверждение справедливо согласно аксиоме А4'! [Х = !) 1+ 0 = 1 — утверждение справедливо согласно аксиоме А5'.
Все теоремы из табл, 4.1 можно доказать методом полной индукции, что мы и приглашаем вас сделать в упражнениях 4.2 и 4.3. Табл. 4.1. Теоремы алгебры переключений для функций одной переменной (Т1') Х ! =Х (Т2') Х . О = О (ТЗ') Х Х=Х (Т1) Х + 0 = Х (Т2) Х+1=1 (ТЗ) Х+ Х = Х (Т4) (Х')'= Х (Т5) Х+ Х'= 1 (Тождества) (Погашающие элементы) (Идемпотентность) (Инволюция) (Т5') Х Х'= 0 (Дополнения! 4.1.3.
Теоремы о функциях двух и трех переменных Теоремы алгебры переключений, относящиеся к функциям двух и трех переменных, перечислены в табл. 4.2. Каждая из теорем легко доказывается полной ин- Осуществляя анализ или синтез логической схемы, мы часто записываем алгебрах ческие выражения, чтобы охаракгеризовать фактическое или желаемое поведение схемы. Теоремгя (глеогетз) алгебры переключений представляют собой заведомо верные утверждения, которые позволяют нам преобразовывать алгебраические выражения, чтобы упростить анализ или более эффективно осуществить синтез соответствующей схемы. Например, теорема, утверждающая, что Х + 0 = Х, позволяет повсюду, где в выражении встретится Х+ О, заменить эту сумму на Х.
В табл. 4.1 перечислены все теоремы алгебры переключений, касающиеся функций одной переменной Х. Как узнать, что эти теоремы справедливы? Мы можем либо сами доказать их, либо поверить на слово тому, кто сделал это. Ну, ладно: поскольку это учебный курс, давайте поупражняемся в доказательствах. Большинство теорем алгебры переключений доказывается исключительно просто методом, носящим название павкой индукции (регтесг нг!исг!ол). В этом методе ключевой является аксиома А!: так как переменная в алгебре переключений может принимать только два различных значения — 0 и 1, — теорему, касающуюся единственной переменной Х, можно доказать, убедившись в ее справедливости для обоих значений Х, то есть для Х = 0 и для Х = 1.
Например, для доказательства теоремы Т! выполним две подстановки: 4.1. Алгебра переключений 243 (тн] (Тт ) (Т8') (Т9') <т)н) (Коммутвтивность) (Ассоциативность) (Дистрибугивность) (Поглощение) (Объединение) (Согласованность) (Тб) Х+ Уь т+ Х <т)) (х+ т) ъ г= х ъ <т; г) ~тв) х тъх г=х <т»<О о») х -х т=х <тш) х т+х )"=х (пи х т+х' г+т г=х т+х' г (т(<') (х -у) (х'+г) (у+я)=(х+у) (хчл) х т=т х (х т) г=х (т ьз <хпт) <х+г)=х+т г х (х»т)=х <х - т) <х -)") = х Эти рассуждения кажутся тривиальными, и это действительно так, но они очень важны, так как образуют теоретическую базу для использования логических схем с числом входов больше двух.
Мы ввели знаки и + как двущщнные операторы ((ипату орега<огл), то есть операторы, связывающие две переменные. Однако на практике мы используем логические схемы И и ИЛИ стремя, четырьмя и ббльшим числом входов. Из теорем следует, что входы логических схем можно подключать к источникам сигналов в любом порядке; зта возможность используется во многих пРограммах разводки соединений на печатньгх платах и внутри специализированныхх ИС.
Можно воспользоваться, в принципе, одним п-входовым вентилем, либо лвухвходовыми вентилями в количестве (и — 1) штук, хотя задеРжка распространения и стоимость в последнем случае будут, вероятнее всего, больше. Теорема Т8 идентична дистрибутивному закону для целых н действительных чисел, то есть логическое умножение распределяется по компонентам логнческоп) сложения. Следовательно, можно «разнести множитель по слагаемым» («ти(пр<у(пй оиг») и представить выражение в виде суммы произведений, как зто лелается в следующем примере: Ч' Р)у+ Х) '(У+ Е) =Ч уу У+Ч уу 2+ Ч Х У» Ч Х Е.
Однако в алгебре переключений имеется и незнакомое правило, состоящее в том что справедливо и обратное: логическое сложение разносится по компонентам логического умножения, о чем свидетельствует теорема Т8'. Таким абрам можно также «разнести слагаемое по сомножителям» («а<(<(<п8 оио)) и "Редставить выражение в виде произведения сумм: ,укцией, тоесть путем нахождения функции для четырех возможных комбинаций Х н у или для восьми возможных комбинаций Х, У н Е. )т первых двух парах теорем речь идет о коммутативности и ассоциативности л гического сложения и логического умножения; эти утверждения идентичны оммутативному и ассоциативному правилам для сложения и умножения целых и действительных чисел. Эти теоремы утверждают, что наличие скобок и порядок „яснов в логической сумме и в логическом произведении несущественны.
Например, со строго алгебраической точки зрения выражение типауу Х у 2 допускает неоднозначное толкование; его следует записывать в виде (уу. (Х. (у 2))) или (((уу . Х) у) 2) или (уу. Х) . (у 2) (см, задачу 4.34). Но наши теоремы говорят, что неопределенность данного выражения по форме не страшна, поскольку в любом случае мы получаем один и тот же результат. Табл. 4.2. Теоремы алгебры переключений для функций двух и трех перемен- ных 244 Глава 4. Принципы проектирования комбинационных лопзчеоких схевя (Ч ' ЪЧ' Х) + (У ' 2) = (Ч+ У) ' (Ч+ 2) (ЧЧ+ У! .
(9Ч+ 2! (Х ч У) ' (Х+ 2). Теоремы Т9 и Т!0 часто используются при минимизации логических функций, Если, например, в логическом выражении появляется подвыражение Х+ Х. У, то согласно теореме поглощения (сочепп8 гйгогет) Т9 нам нужно оставить в выражении только Х; говорят, что Х поглощает (сонет) У. Теорема обьгдиненин (сотЬ)тп8 йеоггт) Т10 говорит, что в случае, когда в выражении возникает подвыражениеХ У+Х У', мы можем заменить его наХ.
ПосколькуУдолжно быть либо нулем, либо единицей, рассматриваемое подвыражение равняется! в том и только в том случае, если Х равняется 1. Хотя теорему Т9 можно было бы доказать полной индукцией, ее справедли вость проявится с большей очевидностью, если мы выведем ее из других тео рем, принятых нами на вооружение к этому моменту: Х+Х У =Х 1+Х.У (согласнотеоремеТ!') = Х .
(1 + У) (согласно теореме Т8) = Х 1 (согласно теореме Т2) =Х (согласно теореме Т! '). Подобным образом можно доказать теорему Т10, используя при этом другие теоремы, причем ключевую роль играет теорема Т8 при переписывании левой части в виде Х ' (У "'Л. Теорема Т!1 известна как теорема согласованности (соазепзиз гйеогет). ЧленУ. 2 называют консенсусом (сопзепзиз) членов Х У и Х' 2. Идея состоит в том, чтоеслиУ сравняется!,толибоХ.У либоХ' гдолжныравняться1;так какуисоба равны 1 и либо Х, л ибо Х'должно быть единицей. Таким образом, член У 2 является избыточным и может быть опущен в правой части Т! 1. У теоремы согласованности есть два важных приложения.
Ее можно применить для устранения паразнтных импульсов, возникающих в результате гонок в комбинационных логических схемах, как мы увидим это в параграфе 4.5. Кроме того, на этой теореме основан итеративно-консенсусный метод нахождения простых импликант(см. Обзорлитературы). Во всех этих теоремах любую переменную можно заменить произвольным логическим выражением. В простейшем случае на место одной нли большего числа переменных можно поставить дополнение к ним: (Х+У)ей'=Х+(У'+Е) (потеоремеТ7).
Но можно выполнить также и более сложные подстановки: (Ч'+Х) (Чу (т +Е))+(Ч'+Х).(ЧЧ (У'+2))'=Ч'+Х (потеоремеТ!О). 4.1.4. Теоремы о функциях п переменных Несколько важных теорем, приведенных в табл.4.3, справедливы для произвол ьного числа переменных и. Большинство этих теорем можно доказать двухшаговым методом, который называется ограниченной индукиией (ртуе 1пдисйоп): сначала убеждаются в том, что утверждение теоремы справедливо при п = 2 (основной щаг (Ьазгз жгр)], а затем доказывают, что если утверждение теоремы верно при п =- й то оно выполняется также при п = ! + 1 (шаг по индукпик 4.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
