bulevy-funktsii-i-postr.-log.-skhem (1016573), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

4.1.1показаны способы реализации функции g  x, y  на вентиле «2И»(4.1.1 д)) и логическом элементе функции f  x, y, z  , у которойz - фиктивная переменная (рис.4.1.1 а), б), в), г)).5. Основные эквивалентности для элементарныхфункцийДадим индуктивное определение формулы над множеством.Определение 5.1. Пусть имеется некоторое множество булевых функций A   f1 ... , f 2 ... ,..., f n ... ,... .Введём понятие формулы над A :1) любая функция f  x1,..., xn   A называется формулойнад A ;2) если f  x1,..., xn   A и H1, H 2 ,..., H m — либо переменная,либо формула над A , то выражение вида f  H1, H 2 ,..., H n  является также формулой над A ;3) только те объекты называются формулами над A , которыеможно построить с помощью пунктов 1 и 2 данного определения.Примечание.

Среди H1, H 2 ,..., H n вполне могут быть одинаковые переменные или формулы.Определение 5.2. Две формулы H1 и H 2 над A называютсяравными или эквивалентными, если функции, реализуемые ими,равны. Записывают H1  H 2 .Пример 5.1. Доказать эквивалентность формул:x1   x2  x3    x1  x2    x1  x3  .Решение. Составим таблицы истинности функцийf1  x1   x2  x3  и f 2   x1  x2    x1  x3  .20x1 x2 x3000011110011001101010101 x2  x3 00010001f1 x1  x2   x1  x3 000111110011111101011111f200011111Сравнивая полученные двоичные наборы значений функцийf1 и f 2 , видим, что им соответствует один и тот же набор 0001 1111 .

Следовательно, f1  f 2 и формулы эквивалентныx1   x2  x3    x1  x2    x1  x3  .Доказательства основных эквивалентностей, представленныхниже, проводятся так же, как показано в примере 5.1.Основные эквивалентности1. Коммутативность:а) x1  x2  x2  x1;б) x1  x2  x2  x1 ;в) x1  x2  x2  x1 ;г) x1  x2  x2  x1 .2. Ассоциативность:а) x1   x2  x3    x1  x2   x3  x1  x2  x3 ;б) x1   x2  x3    x1  x2   x3  x1  x2  x3 ;в) x1   x2  x3    x1  x2   x3  x1  x2  x3 .3. Дистрибутивность:а) x1   x2  x3   x1  x2  x1  x3 ;б) x1   x2  x3    x1  x2    x1  x3  ;в) x1   x2  x3   x1  x2  x1  x3 .4.

Закон двойного отрицания: x  x .21Теорема двойственности (правила де Моргана):x1  x2  x1  x2 ;x1  x2  x1  x2 .5. Законы поглощения:а) x  x  x  1  x  x  x  0  x  0  x ;б) x  x  x  1  x  x  x  x  1 ;в) x  x  x  0  x  x  0 ;г) x  1  x  0  x  0  x x  x  x  x .Свойства констант 0 и 1: 0  1; 1  0 .6.а) x1 x2  x1  x2  x1  x2 ;б) x1  x2  x1  x2  x1  x2 ;в) x1  x2  x1  x2    x1  x2   x1   1; г) x1  x2  x1  x2  x1  x2   x1  x2   x1  x2 ;д) x1  x2   x1  x2   x1  x2  x1  x2  x1  x2  x1  x2 .Все эти равенства остаются справедливыми при подстановкевместо переменных любых логических функций и, следовательно, любых формул, представляющих эти функции.Например, в формулах, получающихся многократным применением операции дизъюнкция к более простым формулам, посвойству ассоциативности скобки можно опускать, а по свойствукоммутативности переменные можно переставлять, например,x1   x2  ...

  xn1  xn ...  x1  x2  ...  xn .Таким образом, операция дизъюнкция справедлива для произвольного числа переменных и верна запись x1  x2  ...  xn .Аналогично показывается, что для произвольного числа переменных справедливы операции конъюнкция, сумма по модулю2, стрелка Пирса и штрих Шеффера, т.е. верны выражения:x1  x2  ...  xn ;x1  x2  ...  xn ;22x1  x2  ...  xn ;x1 | x2 | ...

| xn .Введём некоторые соглашения для записи формул:nx1  x2  ...  xn  V xi ;i 1nx1  x2  ...  xn   xi ;i 1nx1  x2  ...  xn   xi .i 1Из законов поглощения вытекают следующие очевидныеутверждения:x1  x2  ...  xn  1  i  xi  1 ;x1  x2  ...

 xn  1  i  xi  1 .Для установки порядка выполнения операций в формулахиспользуются скобки. Для упрощения записи формул устанавливают приоритет выполнения операций. Приоритет примененияопераций убывает в следующем порядке:,  , , , , .Приоритетность операций в сочетании с законами ассоциативности дают возможность более компактной записи формул.Например,x1  x2    x2  x3   x1   x1  x2  x2  x3  x1 .Наряду с основными соотношениями для упрощения формулчасто используются следующие правила:7.

Правила поглощения:а) x1  x1  x2  x1 ;б) x1   x1  x2   x1 .8. Правила склеивания:а) x1  x2  x1  x2  x1 ;б)  x1  x2   x1  x2  x1 .9. Правило обобщённого склеивания:23x1  x3  x2  x3  x1  x2  x1  x3  x2  x3 .Пример 5.2. Построить таблицу булевой функции, заданнойформулойf  x1, x2 , x3   x1  x2  x3  x1 .Решение.1. Установим порядок выполнения операций в соответствии сих приоритетностью:f1  x1 ; f 2  x2  x3 ; f3  f 2  f1 ; f  x1  f3 .Таким образом, количество операций, необходимых для получения векторного значения функции, равно четырём.2. Определим количество строк в таблице:количество строк = 2n + строка для заголовка,где n - количество переменных. В нашем случае имеем: 23  1  9 .3.

Определим количество столбцов в таблице:количество столбцов = количество переменных + количествоопераций,т.е. 3  4  7 .4. Выпишем в таблицу, заполнив столбцы результатами выполнения логических операций в обозначенной последовательности с учётом таблиц истинности основных логических операций:x1 x2 x30 0 00 0 10 1 00 1 11 0 01 0 11 1 01 1 1f111110000f200010001f311110001f11110001Итак, исходная формула задаёт булеву функцию, имеющую двоичный набор значений f  x1, x2 , x3   1111 0001 .246. Графическая интерпретация некоторыхэквивалентностейЗаконы поглощенияЗаконы поглощения позволяют использовать логическиеэлементы с большим количеством входов в качестве логическихэлементов с меньшим количеством входов.

Как говорят, уменьшить число входов логического элемента.Применение законов x  1  x  0  x  0  x для уменьшениячисла входов разберём на примере вентиля «3И», т.к. для логических элементов дизъюнкции и суммы по модулю 2 эти операции проводятся аналогично.1 у x&«&«»»а)б)Рис. 6.1. Реализация на вентиле «3И» вентиля «2И» и логического элемента тождественной функции на один вход.Формула x  1  x позволяет из вентиля «3И» получить:- вентиль «2И», подключением неиспользуемого входа вентиля «3И» к единице (источнику питания) (рис.6.1 а));- логический элемент тождественной функции на один вход,подключением двух неиспользуемых входов вентиля «3И» к единице (рис.6.1 б)).Законы x  1  x и x  0  0 могут быть полезны при построении коммутаторов на вентиле «2И» (рис.6.2), так как подавая наодин из входов вентиля «2И» логический ноль или единицу можно либо пропускать сигнал на выход, либо формировать на выходе нулевой потенциал.250 1 x&&«»«»Рис.

6.2. Реализация на вентиле «2И» коммутаторов.Законы x  x  x  x  x и x x  x  x  x позволяют объединять входы логических элементов. Например, применяя формулуx | x | y  x  x  y  x  y  x | y можно реализовать двухвходовуюсхему "2И-НЕ" на логическом элементе "3И-НЕ", как это показано на рис. 6.3 а). Использовать схему "2И-НЕ" в качестве обычного инвертора, как это показано на рис. 6.3 б), позволяет равенство x x  x  x  x .у x&«&«»а)»б)Рис. 6.3. Реализация «2И-НЕ» на вентиле «3И-НЕ» и построение логического элемента «НЕ» на вентиле «2И-НЕ».Обратим внимание на то, что по правилам Кирхгофа объединение нескольких входов увеличивает входные токи логическогоэлемента и его ёмкость, что увеличивает ток потребления предыдущих элементов и отрицательно сказывается на быстродействии26цифровой схемы в целом.

Поэтому при проектировании цифровых схем стараются избегать таких ситуаций, подключая к лишним входам константы 0 или 1, например, применяя формулыx 1  x  0  x  0  x и x 1  x  0  x  1  x .Правила де МорганаЭти законы позволяют реализовать булеву функцию «И» припомощи логических элементов «ИЛИ» и, наоборот, реализоватьбулеву функцию «ИЛИ» при помощи логических элементов «И».Такая реализация особенно полезна в ТТЛ схемотехнике (транзисторно-транзисторная логика), так как там легко произвести логические элементы «И», но при этом достаточно сложно изготовить логические элементы «ИЛИ».На рисунке 6.4 а) показано построение логического элемента«2ИЛИ» на элементе «2И-НЕ» и двух инверторах при помощиформулы x1  x2  x1  x2  x1  x2 .На рис. 6.4 б) дана схема логического элемента "2И", построенного при помощи формулы x1  x2  x1  x2 на логическом элементе «2ИЛИ» и инверторов на входе и выходе этой схемы.&111111б)а)Рис.

6.4. Элемент «2ИЛИ», построенный на вентиле «2ИНЕ» и двух инверторах; элемент«2И», реализованный навентиле «2ИЛИ» и трёх инверторах.Правила де Моргана обобщаются на n переменных:x1  x2 ...  xn  x1  x2  ...  xn ;x1  x2  ...  xn  x1  x2  ...  xn .27Закон двойного отрицанияЗакон двойного отрицания x  x используется как для упрощения логических выражений (и как следствие упрощения иудешевления цифровых комбинационных схем), так и для устранения инверсии сигналов после таких логических элементов как«2И-НЕ» и «2ИЛИ-НЕ».

В этом случае законы булевой алгебрыпозволяют реализовывать заданные цифровые схемы при помощиограниченного набора логических элементов.7. Логические схемыОпределение 7.1. Логическая схема (ЛС) представляет собойсовокупность логических элементов и связей между ними.Соединения логических элементов (ЛЭ) в рамках единой логической схемы должны удовлетворять следующим правилам:1. К любому входу ЛЭ могут быть подключены:a) выход любого другого ЛЭ;б) входной сигнал (входная переменная), принимающий значения«0» или «1»;в) логическая константа (0 или 1).В реальных электронных схемах подача логической константы на вход элемента реализуется либо заземлением, либо подключением этого входа через резистор к шине питания.2. Выход любого ЛЭ схемы может:а) подключаться к любому числу входов других ЛЭ;б) представлять собой выходной сигнал схемы;в) принимать значения только «0» или «1».3.

Характеристики

Список файлов учебной работы