Основы бортовых вычислительных машин
 Скачать 3.2 Mb.
|
|
Задания для самостоятельной работы 1. А = 0,101011, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 2. А = -0,100001 , ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 3. А = -0,000000, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 4. А = 0,000000, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 5. А = -0,100010, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 6. А = -0,0000100, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 7. А = -0,101001, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 8. А = 0,100001, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 9. А = 0,000001, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 10. А = 0,0010101, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 11. А = -0,101111, ПК ОК ДК A A A ] [ , ] [ , ] [ - ? 12. Выполнить сложение чисел в прямом, обратном и дополни- тельном кодах: А = 0,010111 и В = -0,00101. 13. Выполнить сложение чисел в прямом, обратном и дополни- тельном кодах: А = -0,00111 и В = 0,10001. 14. Выполнить сложение чисел в прямом, обратном и дополни- тельном кодах: А = 0,0101 и В = -0,000101. 15. Выполнить сложение чисел в прямом, обратном и дополни- тельном кодах: А = 0,001111 и В = -0,10010. 16. Выполнить сложение чисел в прямом, обратном и дополни- тельном кодах: А = -0,000010 и В = 0,100001. 17. Определить произведение дополнительных кодов чисел А = -0.1001 и В = 0.01. 18. Определить произведение дополнительных кодов чисел А = 0.0111 и В = -0.1001 19. Определить произведение дополнительных кодов чисел А = -0.11 и В = -0.101 20. Выполнить деление дополнительных кодов до четырех цифр после запятой. Делимое х = - 0.01011 и делитель у = 0.01101. 37 1.4 Общие сведения о функциях алгебры логики Наука рассуждать (т.е. логика) была создана в IV веке до н.э. древнегреческим мыслителем Аристотелем. Он рассмотрел какие за- коны, приемы, формы присущи человеческому мышлению. Отсюда и название логики – формальная логика. Основоположником математической логики считается немецкий математик Лейбниц. Он в XVII веке попытался сформулировать пер- вые логические исчисления. На фундаменте, заложенном Лейбницем, другой математик, Джордж Буль, отец писательницы Войнич, автора романа «Овод», ввел для логического построения особую алгебру. В отличие от обыч- ной, в ней символами обозначают не числа, а высказывания. Все вы- сказывания имеют всего только два значения – ложь или истина. Так как в двоичной системе счисления только две цифры 0 и 1, то правила алгебры логики приемлемы для двоичной СС. 1.4.1 Функции и операции При синтезе и анализе схем цифровых устройств используется аппарат математической логики, объектом исследования которого яв- ляются двоичные функции f двоичных переменных 1 0 ,..., − n x x , назы- ваемые булевыми функциями или функциями алгебры логики: ) ,..., ( 1 0 − = n x x f f Аппарат булевой алгебры имеет дело с переменными, отражаю- щими истинность или ложность высказываний: если высказывание истинно – ему ставится в соответствие значение x = 1, если ложно - x = 0. Функция f , также как и ее аргументы, принимает значение 0 или 1. Совокупность значений 1 0 ,..., − n d d аргументов 1 0 ,..., − n x x назы- вается набором длины n и обозначается через ( 1 0 ,..., − n d d ). Число D , соответствующее набору, называется номером набора (таблица 1.2). Множество наборов )} 1 1 ( ),..., 0 0 {( = W характеризует область определения функции. Значение функции f на наборе с номером D обозначается через D f : ) ,..., ( 1 0 − = n D d d f f 38 Из множества наборов принято выделять нулевой и единичный – это соответственно наборы (0…0) (номер набора равен нулю) и (1…1) (номер набора равен 1 2 − n ). Два набора ( 1 0 ,..., − n d d ) и ( 1 0 ,..., − n d d ) на- зываются противоположными, если значения одноименных перемен- ных в наборах взаимно противоположны ) 1 ( i i d d − = . Два набора ( 1 0 0 − n d d ) и ( 1 0 1 − n d d ), различающиеся значениями только од- ной переменной, называют соседними. Таблица 1.2 Таблица наборов длины 3 Значение аргументов (набор) Номер набора D 2 d 1 d 0 d 0 0 0 0 1 0 0 1 2 0 1 0 3 0 1 1 4 1 0 0 5 1 0 1 6 1 1 0 7 1 1 1 Поскольку область определения и область значений функции конечны, то она может быть задана таблицей, в которой каждому на- бору с номером D сопоставляют значение функции D f . Такие табли- цы называют таблицами истинности (таблица 1.3). Таблица 1.3 Пример задания различных функций таблицей истинно- сти Пример функций Номер набора Набор 0 1 d d Значения функции ) ( 0 1 d d f ) ( * 0 1 d d f ) ( 0 1 d d ϕ 0 0 0 0 f 0 0 1 1 0 1 1 f 1 1 0 2 1 0 2 f 1 * 1 3 1 1 3 f 0 * 0 Значениям функций 1 2 0 − n f f можно сопоставить двоичный код ) 2 ( F , такой что ) 2 ( F 1 2 1 0 − = n f f f 39 Множество W наборов аргументов области определения функ- ции можно разбить на два подмножества 1 W и 0 W : W = 1 W ∪ 0 W , где 1 W и 0 W - подмножества наборов, на которых функция принимает значения 1 и 0 соответственно. В частности, для ) , ( 0 1 d d f из таблицы 1.3 находим: } )}. 11 ( ), 00 {( , ) 10 ( ), 01 {( 0 1 = = W W На части наборов функция может быть не определена, такие функции называют частичными и помечают звездочками. Наборы, на которых функция может принимать одновременно противоположные значения, называют запрещенными, значения функции на таких набо- рах также отмечают звездочками. Например, функция ) , ( * 0 1 d d f не определена на наборах с номерами 2 и 3 (см. таблицу 1.3). На практике частичные функции на запрещенных наборах дооп- ределяют для того, чтобы полученная функция имела более простую формулу, либо допускала бы более простую схемную реализацию. Количество n N различных наборов длины п в точности равно количеству различных n 2 - разрядных двоичных чисел, а количество f N различных функций – количеству различных наборов n N : n N = n 2 , f N = n n N 2 2 2 = Для п = 1 количество различных значений n N = 2, а f N = 2 2 = 4 (таблица 1.4). Как следует из таблицы 1.4, значения функций 0 F , 3 F - постоянны и не зависят от изменения входной переменной, а функ- ция 1 F совпадает с 0 d . Единственной нетривиальной функцией явля- ется функция 2 F ( 0 d ) = 0 d - инверсия переменной 0 d Таблица 1.4 - Функции одной переменной D 0 d 0 F 1 F 2 F 3 F 0 0 0 0 1 1 1 1 0 1 0 1 Для п = 2 количество различных наборов n N = 4, а количество различных функций f N = 2 4 = 16 (таблица 1.5). 40 Таблица 1.5- Логические функции двух переменных На- бор F 0 F 1 F 2 F 3 F 4 F 5 F 6 F 7 F 8 D d 1 d 0 0 1 0 d d ∨ 1 0 d d ⊕ 1 0 & d d 1 0 & d d 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 0 1 1 0 0 1 1 0 2 1 0 0 0 0 0 1 1 1 1 0 3 1 1 0 0 0 0 0 0 0 0 1 Продолжение таблицы 1.5 D Набор F 9 F 10 F 11 F 12 F 13 F 14 F 15 d 1 d 0 1 0 d d ⊕ 1 0 d d → 1 0 d d ∨ 1 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 0 1 1 2 1 0 0 0 0 1 1 1 1 3 1 1 1 1 1 1 1 1 1 Количество различных функций с увеличением числа аргумен- тов растет чрезвычайно быстро, достаточно быстро растет и число различных наборов. Так для п = 2, n N = 4, f N = 16, но для п = 5 уже n N = 32, f N > 4000000000, поэтому табличное задание функций ста- новится громоздким, и функции предпочитают задавать алгебраиче- ски формулами через простейшие (элементарные) функции – опера- ции. В качестве операций обычно выбирают следующие функции од- ного и двух аргументов (см. таблицы 1.4, 1.5): инверсия (операция НЕ: x y = ), конъюнкция (операция И: 0 1 & x x y = ), дизъюнкция (опе- рация ИЛИ: 0 1 x x y ∨ = ), штрих Шеффера (операция И-НЕ: 0 1 & x x y = ), стрелка Пирса (операция ИЛИ-НЕ: 0 1 x x y ∨ = ), сумма по модулю два (операция М2: 0 1 x x y ⊕ = ). 41 Инверсия, отрицание или операция НЕ реализуется инвертором или логическим элементом (ЛЭ) НЕ (рисунок 1.3,а). Рисунок 1.3- Логические элементы Конъюнкция, логическое произведение (умножение) или опера- ция И – это функция y x & , совпадающая с арифметическим произве- дением двоичных переменных. Конъюнкцию обозначают также через y x y x xy ∧ ⋅ , , . Аргументы функции часто называют сомножителями. Элемент, реализующий конъюнкцию, называют конъюнктором или логическим элементом И (см. рисунок 1.3,б). Говорят (см. табли- цу 1.5), что элемент И всегда пропускает нули со входов на выход (действительно, если хоть один из сомножителей равен нулю, то и произведение равно нулю). Дизъюнкция, логическая сумма (сложение) иначе операция ИЛИ – это функция y x ∨ , которая равна нулю тогда и только тогда, когда все ее аргументы равны нулю. Аргументы дизъюнкции часто назы- вают слагаемыми. Элемент, реализующий дизъюнкцию, называют дизъюнктором или логическим элементом ИЛИ (см. рисунок 1.3,в). Говорят, что элемент ИЛИ всегда пропускает единицы со входов на выход. Сумма или операция сложения по модулю два – это функция y x ⊕ , которая равна единице тогда и только тогда, когда сумма зна- чений аргументов есть число нечетное. Элемент, реализующий эту функцию, называют сумматором по модулю два и отмечают симво- лом М2 (см. рисунок 1.3,г). 42 В математической логике широко используют функцию «им- пликация». Импликация – это функция ) ( y x y x y x ∨ = → → , кото- рая равна единице, если выполняется неравенство y x ≤ (см. таблицу 1.5). Элемент, реализующий импликацию, называют импликатором (см. рисунок 1.3,ж). Функцию, противоположную конъюнкции, называют функцией штрих Шеффера или операцией И-НЕ и обозначают через ) & / ( / y x y x y x = . Логический элемент, реализующий эту функцию, называют элементом Шеффера или элементом И-НЕ (см. рисунок 1.3,д). Функцию, противоположную дизъюнкции, называют функцией стрелка Пирса или операцией ИЛИ-НЕ и обозначают через ) ( y x y x y x ∨ = ↑ ↑ . Элемент, реализующий эту функцию, называют элементом Пирса или элементом ИЛИ-НЕ (см. рисунок 1.3,е). Все пе- речисленные функции за исключением функций инверсии и имплика- ции справедливы для любого числа ( > n 2) аргументов. 1.4.2 Основные законы и правила алгебры логики Основные тождества булевой алгебры, используемые для преоб- разования формул функций, получили название законов и правил. После определения операций алгебры эти тождества являются след- ствиями этих определений и могут быть доказаны. Законы коммутативности (переместительные) для дизъюнкции и конъюнкции x y y x x y y x ⋅ = ⋅ ∨ = ∨ ; Законы ассоциативности (сочетательные) для дизъюнкции и конъюнкции z y x z y x z y x z y x ⋅ ⋅ = ⋅ ⋅ ∨ ∨ = ∨ ∨ ) ( ) ( ; ) ( ) ( Первый и второй законы дистрибутивности (распределитель- ные) ) ( ) ( ) ( ; ) ( z х y x z y x z х y x z y x ∨ ⋅ ∨ = ⋅ ∨ ⋅ ∨ ⋅ = ∨ ⋅ Законы идемпотентности (повторения) для дизъюнкции и конъ- юнкции х х х х х х х х = ⋅ ⋅ ⋅ = ∨ ∨ ∨ ; Законы отрицания (инверсии) х х х х х х = = ⋅ = ∨ ; 0 ; 1 43 Законы двойственности или «правило де Моргана» у х у х у х у х ⋅ = ⋅ ⋅ = ∨ ; Правило свертки у х у х х ∨ = ⋅ ∨ Правила поглощения х у х х х у х х = ∨ ⋅ = ⋅ ∨ ) ( ; Правила полного склеивания х у х у х х у х у х = ∨ ⋅ ∨ = ⋅ ∨ ⋅ ) ( ) ( ; Правило неполного склеивания у х у х х у х у х ⋅ ∨ ⋅ ∨ = ⋅ ∨ ⋅ Правило Порецкого z у у х z x z у у х ⋅ ∨ ⋅ = ⋅ ∨ ⋅ ∨ ⋅ Правила операций с константами 0 0 0 0 0 0 0 0 = ⋅ = ∨ = ⋅ x x x = ⋅ = ∨ = ⋅ 1 1 1 0 0 1 0 x x = ∨ = ∨ = ⋅ 0 1 0 1 0 0 1 1 1 1 1 1 1 1 1 = ∨ = ∨ = ⋅ x Доказательство большинства законов и правил алгебры логики очевидны. Например, ) 1 ( 0 ) ( ) ( ; 1 ) ( ; 1 ) 1 ( x y x y x x y x x y y y x y x x x y x y x x x y y x y x y x x x y x y x x = ∨ ⋅ = ⋅ ∨ = = ∨ ⋅ ∨ = ⋅ ∨ ⋅ ∨ ⋅ ∨ ⋅ = ∨ ⋅ ∨ = ⋅ = ∨ ⋅ = ⋅ ∨ ⋅ = ⋅ = ∨ ⋅ = ⋅ ∨ В других случаях доказательство тождества может быть выпол- нено сравнением значений правой и левой части тождества на всех возможных наборах переменных. Например, необходимо доказать справедливость тождества: у х у х ⋅ = ∨ Зададим таблицей (таблица 1.6) значения выражений у х ∨ и у х ⋅ Значения обоих выражений (см. таблицу 1.6) на всех наборах значе- ний аргументов совпадают, следовательно, они задают одну и ту же функцию. Тождество доказано. 44 Таблица 1.6 Номер набора Набор ) (ху у х ∨ у х ⋅ 0 0 0 1 0 0 0 = = ∨ 1 1 1 0 0 = ⋅ = ⋅ 1 0 1 0 1 1 0 = = ∨ 0 0 1 1 0 = ⋅ = ⋅ 2 1 0 0 1 0 1 = = ∨ 0 1 0 0 1 = ⋅ = ⋅ 3 1 1 0 1 1 1 = = ∨ 0 0 0 1 1 = ⋅ = ⋅ Логические выражения могут быть использованы и в обычной жизни. Например. Три девушки – Аня (А), Валя (В), Клава (К) ходили на танцы в военное училище. Одна из них была в красном платье, другая – в синем, третья в белом. Курсант Иванов был в наряде и на танцы не попал, а его друзья (сослуживцы) Новиков, Петров и Сидо- ров после танцев сообщили: Аня надела красное платье (Ак) Валя – не красное ( к В ) Клава – не синее ( с К ) Стало известно, что только одно из сообщений истинно. Как оп- ределить в каком платье была каждая из девушек. Решение: Из трех вариантов ответа порождаемых сообщением кКс В к А ; с К кВк А ; АкВкКс : с К к В Ак только один истинный, а именно 1 с К кВк А = поэтому Аня была в синем, Валя была в крас- ном платье, Клава в белом. 1.4.3 Алгебры Жегалкина, Шеффера и Пирса Помимо булевой алгебры, в теории функций алгебры логики и, особенно, в приложениях этой теории к задачам синтеза и анализа схем ЭВМ используют и другие алгебраические системы, в том числе алгебры Жегалкина, Шеффера и Пирса. Кроме того, при выборе оптимальных схем по сложности, а так- же при переходе от одной системы элементов ЭВМ к другой возника- ет необходимость в использовании систем операций, принадлежащих различным алгебрам. Алгебра Жегалкина – это множество всех функций, рассматри- ваемое совместно с операциями конъюнкция, сумма по модулю 2 и 45 константа единицы. В алгебре Жегалкина любую функцию рассмат- ривают (записывают) только в виде суперпозиции упомянутых выше операций. Для алгебры Жегалкина действуют следующие законы: коммутативности 1 2 2 1 х х х х ⊕ = ⊕ , ассоциативности 3 2 1 3 2 1 ) ( ) ( х х х х х х ⊕ ⊕ = ⊕ ⊕ , дистрибутивности 3 1 2 1 3 2 1 ) ( х х х х х х х ⊕ = ⊕ Действия с константами: 0 ; 1 = ⊕ = ⊕ х х х х Алгебра Шеффера – это множество всех функций, рассматри- ваемое совместно с операцией штрих Шеффера. Функция Шеффера не подчиняется закону ассоциативности (сочетательному) / ) / ( ) / /( & ) & ( ) & ( & 3 2 1 3 2 1 3 2 1 3 2 1 x x x x x x x x x x x х ≠ ≠ Доказательство этого высказывания может быть выполнено сравнением таблиц истинности логических выражений левой и пра- вой части неравенства (таблица 1.7). Функция Шеффера подчиняется переместительному закону (коммутативности): 1 2 2 1 1 2 2 1 / / & & x x x x x x x х = = Таблица 1.7 1 х 2 х 3 х 1 у 2 у 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 0 0 0 1 1 0 1 0 1 0 1 1 46 Функция Шеффера тождественно равна инверсии конъюнкций или дизъюнкции инверсии аргументов n n n x x x x x x х х х ∨ ∨ ∨ = = & & & / / / 2 1 2 1 2 1 Действия с константами & / 1 & 1 / 1 0 & 0 / 1 1 1 1 1 1 1 1 1 1 x x x x x x x x x x = = = = = = Алгебра Пирса – это множество всех функций, рассматриваемое совместно с операцией стрелка Пирса. Функция Пирса тождественно равна инверсии дизъюнкции ар- гументов или конъюнкции инверсий аргументов: n n n x x x x x x х х х & & & 2 1 2 1 2 1 = ∨ ∨ ∨ = ↑ ↑ ↑ Для алгебры Пирса выполняется переместительный закон: 1 2 2 1 1 2 2 1 x x x x x x x x ∨ = ∨ ↑ = ↑ Также как и для алгебры Шеффера, сочетательный закон не вы- полняется. Действия с константами: 0 1 1 0 0 x x x x x x x x x x = ∨ = ↑ = ∨ = ↑ = ∨ = ↑ Алгебры Жегалкина, Шеффера и Пирса позволяют существенно упрощать решение задач проектирования логических схем ЭВМ на интегральных микросхемах, среди которых важное место занимают элементы Шеффера (И-НЕ) и Пирса (ИЛИ-НЕ), а также для реализа- ции контроля по четности используются сумматоры по модулю 2, со- ставляющие базис алгебры Жегалкина. 1.4.4 Элементарные конъюнкции и дизъюнкции Функции в булевой алгебре записываются только в виде супер- позиции операций конъюнкции, дизъюнкции, инверсии, то есть в ви- де формул из символов операций И, ИЛИ, НЕ. При выполнении опе- раций в булевой алгебре следует соблюдать определенную очеред- ность. Сначала выполняют операции инверсии, затем операции конъ- 47 юнкции и в последнюю очередь операции дизъюнкции. При наличии скобок в первую очередь выполняются операции в скобках. Пример. Вычислить значение функции ) ( ) ( ) , , ( 0 2 0 1 0 2 0 1 2 x x x x x x x x x f ∨ ∨ ⋅ ∨ ⋅ = на шестом наборе. Решение. Для шестого набора 2 x = 1, 1 x =1, 0 x = 0. Подставив эти значения в формулу функции и выполнения последовательно опера- ции, получаем: 1 0 1 0 1 1 1 1 ) 0 1 1 ( ) 0 1 ( 0 ) 1 0 1 ( ) 0 , 1 , 1 ( = ∨ = ∨ ⋅ = ∨ ⋅ ∨ ⋅ = ∨ ∨ ⋅ ∨ ⋅ = f Вычисляя значения функции на каждом наборе, можно легко по- строить таблицу истинности и тем самым осуществить переход от за- дания функции формулой к заданию ее таблицей. Важную роль в булевой алгебре играют функции называемые элементарными конъюнкциями и элементарными дизъюнкциями. Элементарная конъюнкция (ЭК) – это логическое произведение попарно различных отрицаемых или неотрицаемых аргументов (со- множителей). Очевидно, ЭК равна единице тогда и только тогда, когда все ее сомножители с учетом признака отрицания равны единице. ЭК назы- вают полной относительно п аргументов или конституентой едини- цы, если в нее входит каждый из этих аргументов. Конституенту еди- ницы обозначают через ) ( j K , где j - номер единственного набора, на котором конституента равна единице. Если в наборе значение цифры двоичного кода набора равно 0, то переменная в записи конституенты инвертируется, если значение цифры – единица, то переменная запи- сывается без инверсии. Пример, 1 1 0 3 ) 3 ( 0 1 2 = ⋅ ⋅ = j x x x K На всех наборах, кроме j -го значение конституенты единицы ) ( j K =0. Элементарная дизъюнкция (ЭД) – это логическая сумма отри- цаемых и неотрицаемых аргументов (слагаемых). Очевидно, ЭД равна нулю тогда и только тогда, когда каждый из ее слагаемых, с учетом признака отрицания, равен нулю. ЭД, полную относительно п аргументов, называют конституен- той нуля и обозначают через ) ( j М , где j - номер единственного на- бора аргументов, на котором конституента равна нулю. Если в j -м 48 наборе значение цифры двоичного кода набора равно 1, то перемен- ная в записи конституенты инвертируется, если значение цифры – 0, то переменная записывается без инверсии. Пример, 2 1 0 (3) 3 0 1 1 М x x x j = ∨ ∨ = На всех остальных наборах ) ( j М = 1. Непосредственно из определения конституент следует справед- ливость следующей системы тождеств ( j i ≠ ): ) ( j K = ) ( j М , ) ( j М = ) ( j K ; & ) (i K ) ( j K =1, ∨ ) (i М ) ( j М =0. 1.5 Переключательные функции и их минимизация 1.5.1 Канонические формы функций Для практической реализации цифровых устройств часто ис- пользуют ключевые схемы с двумя устойчивыми состояниями, по- этому логические функции, описывающие работу цифровых уст- ройств, называют переключательными функциями (ПФ). Одна и та же функция может быть задана бесчисленным множе- ством формул. Неоднозначность представления функций в виде фор- мул существенно усложняет установление различных соотношений между функциями и задающими их таблицами, например, установле- ние тождества между функциями. Поэтому из всех форм представления переключательных функ- ций особый интерес имеют формы однозначного представления. Та- кие формы называют стандартными или каноническими. Как и табли- цы истинности, канонические формы часто используют в качестве исходных форм задания переключательных функций. В булевой алгебре используют две канонические формы – со- вершенную дизъюнктивную нормальную форму (СДНФ) и совер- шенную конъюнктивную нормальную форму (СКНФ). Для получения СДНФ переключательной функции необходимо выполнить дизъюнкцию конституент единиц тех наборов, на которых ПФ равна 1: СДНФ ) ( 1 j K f W j ∈ ∨ = Правило перехода от табличного способа задания цифрового устройства к СДНФ ПФ вытекает из определения. Например, для за- 49 данной случайным образом таблицы истинности (таблица 1.8) СДНФ переключательной функции имеет следующий вид: СДНФ 0 1 2 0 1 2 0 1 2 0 1 2 ) 4 ( ) 3 ( ) 1 ( ) , , ( x x x x x x x x x K K K x x x f ∨ ∨ = ∨ ∨ = Таблица 1.8 Значение аргументов Номер набора 2 х 1 х 0 х Значение функции ) , , ( 0 1 2 x x x f 0 1 2 3 4 5 6 7 0 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 0 0 Рассмотрим несколько примеров получения СДНФ (таблицы 1.9, 1.10). Таблица 1.9 Значение аргументов Номер набора 2 х 1 х 0 х Значение функции ) , , ( 0 1 2 x x x f 0 1 2 3 4 5 6 7 0 0 0 0 1 1 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 0 0 1 СДНФ переключательной функции по данным таблицы 1.9 име- ет вид: 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 ) , , ( х х х х х х х х х х х х x x x f ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ = Пусть на входе приемника действует последовательность из 4-х импульсов. Наличие импульса отметим 1, а отсутствие 0. Заполним таблицу истинности для устройства определяющего наличие не менее 3-х импульсов в пачке ( таблица 1.10). 50 Таблица 1.10 Значение аргументов Номер набора 3 х 2 х 1 х 0 х Значение функции ) , , ( 0 1 2 x x x f 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 0 0 0 0 0 0 1 0 0 0 1 0 1 1 1 Искомая СДНФ переключательной функции имеет вид: 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 0 1 2 3 х х х х х х х х х х х х х х х х х х х х у ∨ ∨ ∨ ∨ = Совершенная конъюнктивная нормальная форма ПФ получается конъюнкцией конституент нуля тех наборов, на которых переключа- тельная функция равна нулю: СКНФ ) ( 0 j М f W j ∈ Λ = СКНФ ПФ таблицы истинности ) , , ( 0 1 2 x x x f (см. таблицу 1.8) в соответствии с определением равна: ). ( & ) ( & & ) ( & ) ( & ) ( ) 7 ( & ) 6 ( & ) 5 ( & ) 2 ( & ) 0 ( ) , , ( 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 0 1 2 x x x x x x x x x x x x x x x M M M M М x x x f ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ = = = 51 Очевидна справедливость следующих тождеств: ) ( ) ( ; ) ( ) ( 1 0 0 1 j M j K f j M j K f W j W j W j W j ∈ ∈ ∈ ∈ Λ = ∨ = Λ = ∨ = Кроме канонических форм, в булевой алгебре большую роль иг- рают более простые в смысле записи, а зачастую и в смысле схемной реализации функций формы, а именно: Дизъюнктивная нормальная форма (ДНФ); Конъюнктивная нормальная форма (КНФ). ДНФ представляет собой дизъюнкцию (сумму) элементарных конъюнкций, необязательно являющихся конституентами единицы. КНФ представляет собой конъюнкцию (произведение) элемен- тарных дизъюнкций, необязательно являющихся конституентами ну- ля. Следует помнить, что ДНФ и КНФ уже не являются формами однозначного представления функций. На множестве ДНФ и КНФ решают задачу поиска наиболее простых по сложности формул пере- ключательной функции, эту задачу принято называть задачей мини- мизации функций. 1.5.2 Общие понятия о минимизации переключательных функ- ций Выражение переключательной функции в СДНФ или CКНФ яв- ляется отправным при технической реализации логических схем циф- ровых устройств. Сложность логических схем (ЛС) определяется сложностью выражения ПФ, по которому ЛС реализуется. Поэтому раньше всего следует упростить ПФ или, как говорят, произвести ми- нимизацию переключательных функций. Сущность задачи минимизации состоит в поиске способа позво- ляющего по некоторой исходной формуле функции, например СДНФ, находить другую формулу, имеющую наименьшую сложность. Сложность ПФ оценивается числом переменных, входящих в ее выражение (с учетом повторения). Задача минимизации является исключительно сложной и воб- щем виде практически неразрешимой (неизбежен перебор вариантов), поэтому от поиска абсолютных минимальных форм функций прихо- дится отказываться и ограничиваться нахождением минимальных форм лишь среди некоторого класса формул. 52 В булевой алгебре, в частности, ограничиваются минимизацией СДНФ и СКНФ, и нахождением минимальных по сложности ДНФ и КНФ, сокращенно обозначаемых через МДНФ и МКНФ соответст- венно. Известны разные процедуры минимизации ПФ, но все они осно- ваны на применении некоторых тождественных преобразований та- ких как: операции полного и неполного склеивания; операции поглощения; операции удаления (или добавления) лишних членов и др. Операция склеивания выражается тождествами: . А ) х А ( ) х А ( ; А х А х А = ∨ ⋅ ∨ = ⋅ ∨ ⋅ (1.6) В этих выражениях члены А ⋅ х и х А ⋅ (так же, как х А ∨ и х А ∨ ) отличаются только одной переменной, такие члены принято называть соседними. В отношении операции (1.6) говорят также, что члены А ⋅ х и х А ⋅ ( х А ∨ и х А ∨ ) склеиваются по переменной х . Рассмотрим две соседние конституанты единицы четырех пере- менных: 0 1 2 3 8 х х х х К ⋅ ⋅ ⋅ = и 0 1 2 3 9 х х х х К ⋅ ⋅ ⋅ = В результате их склеивания по переменной х о получаем . х х х ) х х ( х х х К К 1 2 3 0 0 1 2 3 9 8 ⋅ ⋅ = ∨ ⋅ ⋅ ⋅ = ∨ т.е. получаем новую конъюнкцию, ранг которой на единицу меньше ранга исходных конъюнкций. При этом переменная, по которой про- изведено склеивание, исключается, а результат склеивания содержит только переменные, входящие одинаковым образом (т.е. либо без ин- версии, либо с инверсией) в исходные конституенты К 8 и К 9 . Это правило является универсальным и применимо к любым соседним ло- гическим выражениям. Операция неполного склеивания определяется соотношением . А А х А х А = ∨ ⋅ ∨ ⋅ Операции поглощения выражаются тождественными соотноше- ниями . А ) х А ( А ; А ) х А ( А ; А х А А ; А х А А = ∨ ⋅ = ∨ ⋅ = ⋅ ∨ = ⋅ ∨ Операция удаления или добавления лишних членов (т.е. таких членов, которые принимают значение, равное 1, одновременно с ос- тавшимися членами выражения (ПФ) основана на тождестве: 53 . А А ... А А = ∨ ∨ ∨ Если в СДНФ некоторой ПФ произвести всевозможные опера- ции склеивания и операции поглощения, получается сокращенная ДНФ. В отличие от СДНФ в нее, в общем случае, входят конъюнкции разного ранга: от первого до (п-1) - го ранга. После отбрасывания лишних членов из сокращенной ДНФ по- лучается ДНФ, называемая тупиковой. Ее особенностью является то, что она уже не допускает применения операций склеивание и погло- щения. Тупиковых ДНФ может быть несколько, так как при выполне- нии операций склеивания и поглощения СДНФ могут объединяться по-разному. Та из тупиковых ДНФ, которая имеет наименьшее число вхождений (наименьшее количество логических переменных и опе- раций), называется минимальной ДНФ (МДНФ). Приведем примеры, иллюстрирующие применение тождествен- ных соотношений с целью минимизации ПФ. Требуется минимизировать ПФ вида 2 1 0 2 1 0 2 1 0 2 1 0 2 1 0 ( , , ) у f x x x x x x x x x x x x x x x = = ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ ∨ ⋅ ⋅ Производя склеивание первого и третьего членов по x 2 , а также второго и четвертого членов тоже по x 2 , получим . x x x x ) x x ( x x ) x x ( x x у 0 1 0 1 2 2 0 1 2 2 0 1 ⋅ ∨ ⋅ = ∨ ⋅ ∨ ∨ ⋅ = К найденному выражению также можно применить операцию склеивания, но уже по x 1 : . x ) x x ( x y 0 1 1 0 = ∨ = Пример. Требуется упростить ПФ вида . x x x x x x x x x x x x ) x , x , x ( f у 0 2 1 2 0 1 0 2 1 2 0 1 0 1 2 2 ⋅ ∨ ⋅ ∨ ⋅ ∨ ⋅ ∨ ⋅ ∨ ⋅ = = В данной ПФнет членов, которые могли бы быть подвергнуты операциям склеивания и поглощения. Поэтому остается проверить, не являются ли лишними некоторые члены. Рассмотрим, например, член 0 2 x x ⋅ . Он принимает значение, равное 1, только тогда, когда 0 x = 1 и 2 x = 0. Найдем значение остальной части функции при таких значени- ях переменных 2 x и 0 x : . x x x x x x 1 0 1 1 0 0 1 1 1 1 1 1 1 = ∨ = ⋅ ∨ ⋅ ∨ ⋅ ∨ ⋅ ∨ ⋅ Из этого следует, что член 0 2 x x ⋅ является лишним, так как, отбросив его, мы не изменим значения функции. Аналогичным путем можно показать, что члены 1 2 x x ⋅ и 1 0 x x ⋅ также являются лишними. Следовательно, ПФ можно записать в виде . x x x x x x ) x , x , x ( f у 0 2 1 2 0 1 0 1 2 2 ⋅ ∨ ⋅ ∨ ⋅ = = 54 1.5.3 Минимизация переключательных функций посредством диаграммы Вейча Диаграмма Вейча (ДВ) для ПФ п переменных x n-1 ,..., х 0 пред- ставляет собой прямоугольник, разделенный на клетки, число кото- рых равно числу n x L 2 = всевозможных наборов переменных. При п = 2, 3, 4 разбиение осуществляется так, что для каждой переменной по- ловина площади большого прямоугольника соответствует i x а вторая половина i x − . Способ разбиения показан на рисунке 1.4 ( п = 2 и 3) и на рисунке 1.5 ( п = 4 ). а) Рисунок 1.4 б) В случае п = 5 ДВ образуется путем состыковывания двух диа- грамм, соответствующих п = 4, причем одна из них ставится в соот- ветствие переменной х 4 , а другая 4 х − . Аналогично строится ДВдля п ≥ 6. Однако при п > 5 диаграмма Вейча становится громоздкой и не- удобной для пользования. Каждая клетка ДВ соответствует некоторому набору перемен- ных с номером α . Рассмотрим, например, клетку, которая лежит на пересечении областей диаграммы, соответствующих переменным 0 1 2 3 х , х , х , х Образуем из этих переменных конъюнкцию 0 1 2 3 х х х х ⋅ ⋅ ⋅ . Она представляет собой конституенту единицы от четырех переменных для набора с номером α = 1010 (2) = 10 (10) . Поэтому присвоим данной клетке номер α = 10. Аналогично нумеруются остальные клетки (см. рисунок 1.5). Переменные i x можно располагать по сторонам ДВ не обязательно в порядке, указанном на рисунке 1.5, но при этом полу- чится другая нумерация клеток. 55 2 х 2 х 12 13 9 8 1 х 3 х 14 15 11 10 1 х 6 7 3 2 3 х 4 5 1 0 1 х 0 х 0 х 0 х Рисунок 1.5 С помощью ДВ задаем ПФ. Пусть, например, ПФ 3 2 1 0 ( , , , ) y f х х х х = равна 1на наборах переменных с номерами α = 0, 2, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14 и равна нулю на всех остальных набо- рах. Аналитическое выражение такой ПФ в СДНФ получается весьма громоздким: 0 2 4 5 6 7 8 10 11 12 13 14 y K K K K K K K K K K K K = ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ ∨ = 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 3 2 1 0 x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x x = ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ ∨ ⋅ ⋅ ⋅ (1.7) Ранее было показано, что при склеивании двух соседних консти- туент единицы ранга п образуется конъюнкция ранга п - 1, в которой содержатся только переменные, входящие одинаковым образом в ис- ходные конституенты единицы. Применим это правило к конституен- там К 12 , К 13 и К 4 , К 5 (рисунок 1.6), в результате получим: 1 2 3 5 4 2 1 2 3 13 12 1 x x x K K P ; x x x K K P ⋅ ⋅ = ∨ = ⋅ ⋅ = ∨ = Соседние конъюнкции Р 1 и Р 2 склеиваются по переменной х 3 , при этом получается конъюнкция 1 2 2 1 1 x x P P Z ⋅ = ∨ = 56 Рисунок 1.6 Таким образом, при склеивании четырех соседних конституент единицы ранга п = 4 образуется конъюнкция ранга п - 2 = 4 – 2 = 2, содержащая только переменные, одинаковым образом входящие в выражения четырех соседних конституент единицы, т.е. в К 4 , К 5 , K 12 и K 13 . Данное правило является универсальным. Применим его к группе четырех соседних конституент единицы, включающей К 0 , К 2 , K 8 и K 10 , и к группе четырех соседних конституент единицы, вклю- чающей К 4 , К 6 , К 12 , K 14 Производя склеивание в той или другой группе, получим 0 2 3 0 2 2 x x Z ; x x Z ⋅ = ⋅ = Конъюнкции Z 2 и Z 3 также являются соседними, так как они разли- чаются одной переменной. Поэтому они склеиваются и дают конъ- юнкцию W = 0 х . Таким образом, при склеивании восьми соседних конституент единицы ранга п = 4 образуется конъюнкция ранга п - 3 = 4 - 3 = 1, содержащая только те переменные, которые одинаковым об- разом входят во все восемь соседних конституент единицы. Обобщая полученные результаты, можно сформулировать про- цедуру минимизации ПФ посредством диаграммы Вейча. Определяются всевозможные группы соседних конъюнкций, ох- ватываемые прямоугольными контурами и содержащие по 1,2,4,8,16 и т.д. конституент единицы (см. рисунок 1.6), при этом одна и та же конституента может входить в несколько разных групп. При п ≤ 4 соседними следует считать не только конституенты, находящиеся в |