Попов И.И., Матвеев А.А., Максимов Н.В. Архитектура электронно-вычислительных машин и систем (2004) (1186255), страница 11
Текст из файла (страница 11)
Приведем примеры некоторых из этихсвойств:Коммутативность (перестановочность)A∧ B = B∧ AA∨ B = B ∨ A55Закон идемпотентностиА&А = А, A∨A=A,Двойное отрицаниеA= AСочетательные (ассоциативные) законыA ∨ ( B ∨ C ) = ( A ∨ B) ∨ C = A ∨ B ∨ CA ∧ ( B ∧ C ) = ( A ∧ B) ∧ C = A ∧ B ∧ CРаспределительные (дистрибутивные) законыA ∧ ( B ∨ C ) = ( A ∧ B) ∨ ( A ∧ C )A ∨ ( B ∧ C ) = ( A ∨ B) ∧ ( A ∨ C )ПоглощениеСклеиваниеОперация переменной с ее инверсиейОперация с константамиЗаконы де Моргана1.
A & B = A ∨ B (условно его можно назвать 1-й);2. A ∨ B = A & B (2-й)- описывают результатыпеременных, связанных операциями И, ИЛИ.отрицанияВ следующей таблице приведено доказательство истинностидистрибутивного закона.A00001111B00110011C01010101B∨CA ∧ (B ∨ C)A∧ BA∧C( A ∧ B) ∨ ( A ∧ C )0111011100000111000000110000010100000111Аналогичным образом могут быть доказаны и другие тождества.Высказывания, образованные при помощи нескольких операцийлогического сложения, умножения и отрицания называются сложными.Истинность всякого сложного высказывания устанавливается с56помощью таблиц истинности.
Высказывания , у которых таблицыистинности совпадают называются равносильными высказываниями.Сложные высказывания истины для любых значений истинности,входящих в них простых высказываний, называются тождественноистинными.Тождественноложныминазываютсяформулы,принимающие значение (false) для любых значений истинности,входящих в него простых высказываний.На рис. 8 а - ж приведены иллюстрации к основным логическимоперациям и их композициям (т.н. диаграммы Эйлера-Венна).
Вкачестве высказывания А здесь принято утверждение x=>a, в качестве В- y=>b. На рис. 8.а приведены области истинности каждого извысказываний, здесь же становится понятен смысл дополнения(отрицания), объединения (дизъюнкции), пересечения (конъюнкции) идр. операций.Первый из законов де Моргана иллюстрируется рис. 8 д, ж.Логическое значение NULL. В некоторых ЯП (Visual Basic и пр.)для расширения применимости логических выражений на те случаи,когда значение одного или нескольких логических аргументовнеизвестны или не определены, вводится значение null (в дополнение кfalse и true), как правило, такое значение присваивается компиляторомлогической переменной по умолчанию.а).
Диаграмма Эйлера-Венна,иллюстрирующая расположениеобластей истинности высказываний АиВ57б). Конъюнкция высказыванийА и В (AND)в). Дизъюнкция высказываний А и В(OR)/д). Разность высказываний (А - В)г). Исключающая дизъюнкция(XOR).е). Иллюстрация к законам деМоргана (дополнениепересечению высказываний)ж). Иллюстрация к законам де Моргана (пересечение дополнений)Рис. 8. Некоторые примеры диаграммЭйлера-ВеннаС учетом значения null таблицы истинности основных логическихопераций приобретают следующий вид.58Таблица 6Операция отрицания (одноместная, унарная)АfalsetruenullĀtruefalsenullТаблица 7Некоторые двуместные (бинарные) операцииАfalsefalsetruetruefalsetruenullnullnullВfalsetruefalsetruenullnullfalsetruenullА&ВfalsefalsefalsetruefalsenullfalsenullnullA∨BfalsetruetruetruefalsetruenulltruenullА→ВtruetruefalsetruetruenullnulltruenullА~ВtruefalsefalsetruenullnullnullnullnullA xor BfalsetruetruefalsenullnullnullnullnullПобитовые операции.
В некоторых современных ЯП включеныоперации побитового сравнения содержимого машинных слов (которыемогут содержать числовые, строчные и др. данные) при этом каждыйбит результата образуется в соответствии с Табл. 7 (для бинарныхопераций). Унарная операция отрицания (not) в данном случаереализует очевидную замену 1 на 0 и наоборот.Таблица 8Операнды и результаты некоторых операций побитового сравненияX0011Y0101X and Y X or Y X imp Y X eqv Y X xor Y00110011010100111110Другие схемные элементы ЭВМРегистр или триггер — это электронная схема, широкоприменяемая в регистрах компьютера для запоминания одного разрядадвоичного кода. Триггер имеет два устойчивых состояния, одно изкоторых соответствует двоичной единице, а другое — двоичному нулю.59Термин триггер происходит от английского слова trigger —защёлка, спусковой крючок.
Для обозначения этой схемы в английскомязыке чаще употребляется термин flip-flop, что в переводе означает"хлопанье". Это звукоподражательное название электронной схемыуказывает на её способность мгновенно переходить ("перебрасываться")из одного состояния в другое и обратно.Самый распространённый тип триггера — так называемый RSтриггер (S и R, соответственно, от английских set — установка, и reset— сброс). Условное обозначение триггера — на рис.
9 а.б)а)Рис. 9. Схемный элемент RS-триггерОн имеет два симметричных входа S и R и два симметричныхвыхода Q и, причем выходной сигнал Q является логическимотрицанием сигнала .На каждый из двух входов S и R могут подаваться входныесигналы в виде кратковременных импульсов ().Наличие импульса на входе считается единицей, а его отсутствие— нулем.На рис. 9 б показана реализация триггера с помощью вентилей«ИЛИ—НЕ» и соответствующая таблица истинности.Таблица 9S0011R0101Qзапрещено10хранениебитаQ01Перечислим возможные комбинации значений входов R и Sтриггера, используя его схему и таблицу истинности схемы «ИЛИ—НЕ»(табл.
9).601. Если на входы триггера подать S="1", R="0", то (независимо отсостояния) на выходе Q верхнего вентиля появится "0". После этого навходах нижнего вентиля окажется R="0", Q="0" и выход Q станетравным "1".2. При подаче "0" на вход S и "1" на вход R на выходе Q появится"0", а на Q= "1".3. Если на входы R и S подана логическая "1", то состояние Q и Qне меняется.4. Подача на оба входа R и S логического "0" может привести кнеоднозначному результату, поэтому эта комбинация входных сигналовзапрещена.Поскольку один триггер может запомнить только один разряддвоичного кода, то для запоминания байта нужно 8 триггеров, длязапоминания килобайта, соответственно, 8 ×210 = 8192 триггеров.Современные микросхемы памяти содержат миллионы триггеров.Полусумматор.
Вспомним, что при сложении двоичных чиселобразуется сумма в данном разряде, при этом возможен перенос встарший разряд. Обозначим слагаемые (А, В), перенос (P) и сумму (S).Таблица сложения одноразрядных двоичных чисел с учетом переноса встарший разряд выглядит следующим образом,СлагаемыеAB00011011Перенос СуммаPS00010110Из этой таблицы сразу видно, что перенос может реализовать спомощью операции логического умножения,P=A&B.Получим теперь формулу для вычисления суммы. Значения суммыболее всего совпадают с результатом операции логического сложения(кроме случая, когда на вход подаются две единицы, а на выходе долженполучится нуль).61А(0,0,1,1)В(0,1,0,1)И0,0,0,1P(0,0,0,1)НЕ1,1,1,0ИS(0110)ИЛИРис.
10. Логическая схема полусумматораНужный результат достигается, если результат логическогосложения умножить на инвертированный перенос. Таким образом, дляопределения суммы можно применить выражение:S = A∨ B& A& BТеперь, на основе полученных логических выражений, можнопостроить из базовых логических элементов схему полусумматора.По логической формуле переноса легко определить, что дляполучения переноса необходимо использовать логический элемент «И».Из логической формулы для суммы очевидно, что на выходедолжен стоять элемент логического умножения «И», который имеет двавхода. На один из входов подается результат логического сложенияисходных величин, т.е. на него должен подаваться сигнал с элементалогического сложения «ИЛИ».На второй вход требуется подать результат инвертированногологического умножения исходных сигналов A & BТо есть на второй вход подается сигнал с элемента «НЕ», на входкоторого получает сигнал с элемента логического умножения «И».Данная схема, называется полусумматором, так как реализуетсуммирование одноразрядных двоичных чисел без учета переноса измладшего разряда.Полный одноразрядный сумматор.
Полный одноразрядныйсумматор должен иметь три входа, ai, bi - слагаемые и pi-1 - перенос изпредыдущего разряда и два выхода, сумма ci и перенос pi. Таблицасложения в этом случае будет иметь следующий вид,62ai,00110011bi01010101pi-100001111pi00010111Si01101001Рис. 11. Укрупненная схема одноразрядного сумматораИдея построена полного сумматора точно такая же, как иполусумматора. Перенос реализуется с помощью формулы для егополученияpi = (a i & bi ) ∨ (ai & pi −1 ) ∨ (bi & p i −1 ).Логическое выражение для вычислениясумматоре принимает следующий вид,суммывполномS i = (ai ∨ bi ∨ pi −1 ) & pi −1 ∨ (ai & bi & pi −1 ).Укрупненная схема, соответствующая полному сумматоруприведена на рис.
11. Составить соответствующую схему из вентилеймы рекомендуем читателю самостоятельно.Более сложные комбинации логических элементов (узлы)рассмотрены ниже.Преобразования логических формулРавносильные преобразования логических формул имеют то женазначение, что и преобразования формул в обычной алгебре. Онислужат для упрощения формул или приведения их к определённомувиду путем использования основных законов алгебры логики.Под упрощением формулы, не содержащей операций импликациии эквиваленции, понимают равносильное преобразование, приводящее кформуле, которая либо содержит по сравнению с исходной меньшеечисло операций конъюнкции и дизъюнкции и не содержит отрицаний63неэлементарных формул, либо содержит меньшее число вхожденийпеременных.Некоторые преобразования логических формул похожи напреобразования формул в обычной алгебре (вынесение общегомножителязаскобки,использованиепереместительногоисочетательного законов и т.п.), тогда как другие преобразованияоснованы на свойствах, которыми не обладают операции обычнойалгебры (использование распределительного закона для конъюнкции,законов поглощения, склеивания, де Моргана и др.).Покажем на примерах некоторые приемы и способы, применяемыепри упрощении логических формул:1)(законыалгебрылогикиприменяютсявследующейпоследовательности: правило де Моргана, сочетательный закон, правилоопераций переменной с её инверсией и правило операций сконстантами);2)(применяется правило де Моргана, выносится за скобки общиймножитель, используется правило операций переменной с еёинверсией);3)(повторяется второй сомножитель, что разрешено закономидемпотенции; затем комбинируются два первых и два последнихсомножителя и используется закон склеивания);4)); затем(вводится вспомогательный логический сомножитель (комбинируются два крайних и два средних логических слагаемых ииспользуется закон поглощения);5)(сначала добиваемся, чтобы знак отрицания стоял только передотдельными переменными, а не перед их комбинациями, для этогодважды применяем правило де Моргана; затем используем закондвойного отрицания);646)(выносятся за скобки общие множители; применяется правилоопераций с константами);7)(к отрицаниям неэлементарных формул применяется правило деМоргана; используются законы двойного отрицания и склеивания);8)(общий множитель x выносится за скобки, комбинируютсяслагаемые в скобках — первое с третьим и второе с четвертым, кдизъюнкцииприменяется правило операции переменной с еёинверсией);9)(используются распределительный закон для дизъюнкции,правило операции переменной с ее инверсией, правило операций сконстантами, переместительный закон и распределительный закон дляконъюнкции);10)(используются правило де Моргана, закон двойного отрицания изакон поглощения).Из этих примеров видно, что при упрощении логических формулне всегда очевидно, какой из законов алгебры логики следует применитьна том или ином шаге.Минимизация логического выраженияЦелью минимизации логического выражения, представляющегозаданную логическую функцию, является уменьшение стоимости еереализации (количества используемых логических элементов).
Общаясхема процесса реализации логической функции такова. для неесоставляется сумма произведений - дизъюнктивная совершенная65нормальная форма. Затем полученное выражение минимизируют доэквивалентной минимальной суммы произведений. Чтобы определитькритерий минимизации, нужно ввести понятие стоимости, иливеличины, логического выражения.Обычно при оценке стоимости выражения учитывается общееколичество вентилей и их входных значений (входных линий),необходимых для реализации выражения в форме, показанной нарисунке.Стоимость большей схемы (слева) на этом рисунке равна 21:5 вентилей плюс16 входных значений.Инверсия входных значений при подсчете игнорируется.Стоимость более простого выражения (справа) равна 9:3 вентиля плюс6 входных значений.Теперь можно определить и критерий минимизации: Суммапроизведений считается минимальной, если не существуетэквивалентного ей выражения меньшей стоимости.Стратегия упрощения заданного выражения заключается вследующем.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
