bulevy-funktsii-i-postr.-log.-skhem (Методические документы), страница 4

Никакие два выхода логических элементов нельзя соединять вместе.Логические схемы целесообразно строить и изображать поярусам (каскадам). На рис. 7.1 показан пример ЛС для функциидвух переменных f ( x, y)  xy  xy .Ярусное строение произвольной ЛС сводится к следующему:- 1-й ярус содержит ЛЭ, входы которых являются входамивсей схемы;28- 2-й ярус образуют ЛЭ, к входам которых подключаются вобщем случае входы схемы и выходы элементов 1-го яруса;- i-й ярус образуют ЛЭ, к входам которых подключаются выходы элементов предыдущих ярусов i  1, ..., 1, а также входысхемы.ху11&1&1 ярус2 ярус3 ярусРис. 7.1. Трёхъярусная логическая схема.Основными параметрами логических схем являются быстродействие и стоимость.Быстродействие схемы оценивается задержкой распространения сигналов от входов схемы к её выходу.

Эту задержку принято считать в виде:T  k ,где  - задержка на одном логическом элементе, k - максимальное количество логических элементов, через которые проходитсигнал от входов к выходу.Чтобы найти значение числа k все элементы логическойсхемы распределяются по ярусам, так как максимальное количество логических элементов, через которые проходит сигнал отвходов к выходу, совпадает с числом ярусов схемы. Номер ярусаэлемента, на выходе которого формируется выходной сигналсхемы, равен k .29Цена логической схемы определяется в смысле Квайна (SQ).При этом подсчитывается общее число входов логических элементов.Для схемы на рис.7.1. задержка - T  3 , цена по Квайну SQ=8.Пример 7.1.1.

Построить логическую схему, реализующую функциюh  x, y   f 2  y, y, f1  x, y, x   при помощи логических элементовфункций f1 и f 2 . Для схемы найти задержку и цену по Квайну.2. Написать таблицу функции h  x, y  , являющейся суперпо-f1 и f 2 , если h  x, y   f 2  y, y, f1  x, y, x   ,f1  x, y, z   1001 0111 и f2  x, y, z    0110 1010  .3. Выразить h  x, y  формулой.Решение.1. Логическая схема, реализующая функцию h  x, y  , показана на рис.7.2.зицией функцийу x««1 ярус»»2 ярус.Рис.

7.2. Логическая схема, реализующая функциюпомощи логических элементов функцийипри.Для схемы на рис.7.2 задержка - T  2 , цена по Квайну SQ=6.302. Запишем таблицу функций f1  x, y, z  и f2  x, y, z  :хyzf1f20001000101010010111010001101101101111110Составим таблицу функций f1  x, y, x  и f 2  y, y, f1  x, y, x   .f1  x, y, x x y0 0 f1  0,0,0   10 1 f1  0,1,0   01 01 1f1 1,0,1  1f1 1,1,1  1f 2  y, y, f1 f 2  0,0,1  1f 2 1,1,0   1f 2  0,0,1  1f 2 1,1,1  0Выпишем таблицу функции h  x, y   f 2  y, y, f1  x, y, x   .x0 0 1 1y0 1 0 1h  x, y  1 1 1 0h  x, y Вектор значений функции h  x, y  имеет вид: h  x, y   1110  .3. Используя таблицу 3.6, выразим формулой искомую функцию: h  x, y   x  y  x y .Пример 7.2.

Для булевой функцииf  x, y, z   xy  yz  xyz  yz  x  y  z :1. Построить логическую схему, реализующую функциюf  x, y, z  при помощи логических вентилей «И», «ИЛИ», «НЕ».Для схемы найти задержку и цену по Квайну.2. Написать таблицу данной функции.313. Найти фиктивные переменные функции f  x, y, z  .4. Используя основные эквивалентности, преобразовать данную формулу в эквивалентную ей, но не содержащую фиктивныхпеременных. Построить логическую схему, найти её задержку ицену по Квайну.zу x111&&1&&11 ярус2 ярус13 ярус4 ярусРис. 7.3.

Логическая схема, реализующая функцию.32Решение.1. Логическая схема представлена на рис. 7.3.Для схемы на рис.7.3 задержка - T  4 , цена по Квайну SQ=21.2. Построим таблицу. Установим порядок выполнения операций в соответствии с их приоритетностью:f1  x ; f 2  y ; f3  z ; f 4  x  f 2  z ; f5  f 4 ; f 6  xy ;f7  f 2  z ; f8  f1  y  f3 ; f9  yz ; f  f5  f6  f7  f8  f9 .Таким образом, количество операций, необходимых для получения векторного значения функции, равно десяти.Таблица имеет вид:x00001111y00110011z01010101f111110000f211001100f310101010f411011111f500100000f600000011f701000100f800100000f900010001f011101113.

Рассмотрим пары наборов, соседних по переменной x , изначения функции на этих наборах:f  0,0,0   f 1,0,0   0 ; f  0,0,1  f 1,0,1  1;f  0,1,0   f 1,1,0   1; f  0,1,1  f 1,1,1  1 .Значит, x - фиктивная переменная.Рассмотрим пары наборов по переменной y . Так какf  0,0,0   f  0,1,0  , то y - существенная переменная.Рассматривая пары наборов по переменной z , находим, чтоf  0,0,0   f  0,0,1 , поэтому z - существенная переменная.Получили, что f  x, y, z   g  y, z  . Таблица функции g  y, z имеет вид:33yz0 0 1 10 1 0 1g  y, z 0 1 1 1h  x, y 3.6 определяем формулу g  y, z   y  z , т.е.f  x, y, z   y  z .4. Применяя основные эквивалентности, преобразуем формулу к виду, не содержащему фиктивной переменной:f  x, y, z   xy  yz  xyz  yz  x  y  z  xy  yz  xyz  yz  xyz Потаблице xy  yz  xyz  yz  xy  z  y  y   xyz  xy  z  1  xyz  xy  z  xyz  xy   z  z  z  xy   xy  1   z  xy   xy  z  xy  y  x  x   z  y 1  z  y  z .Итак, f  x, y, z   y  z , её логическая схема показана нарис.

7.4. Задержка схемы - T   , цена по Квайну - SQ=2.z у11 ярусРис. 7.4. Логическая схема, реализующаяфункцию.8. Теорема о дизъюнктивном разложении булевойфункции по переменнымОбозначим x,   1,x   x ,   0.34Построим таблицу значений функции x .xσ00011011x 00  0  1 01  0 10  1  0 11  1Из таблицы следует, что x  1 тогда и только тогда, когда x   .Теорема 8.1 (о дизъюнктивном разложении булевойфункции по переменным). Для любой функции алгебры логикиf  x1,..., xn  и для любого k 1  k  n  справедливо следующееравенство:f  x1,..., xn  Vx11  ...  xk k  f 1,..., k , xk 1,..., xn  .1,..., k BkЭто равенство называют формулой дизъюнктивного разложения по совокупности переменных x1,..., xk .Доказательство. Зафиксируем произвольный набор  1, 2 ,..., n  .

Вычислим значение правой части равенства наэтом наборе. Как только хотя бы один из сомножителей будет равен нулю, вся конъюнкция обратится в нуль. Таким образом, изненулевых конъюнкций останется лишь одна - та, в которой i   i , поэтому правая часть равенства примет вид:V1, 2 ,..., k Bk11   2 2  ...   k k  f 1, 2 ,..., k , k 1,..., n   0  ...  0  11   2 2  ...   k k  f 1, 2 ,..., k , k 1,..., n .В силу того, что x x  1 ,f 1, 2 ,..., k , k 1,..., n  .Так как равенствоf 1,..., n  Vуказанноевыражениеравно11  ...   k k  f 1,..., k , k 1,..., n 1, 2 ,..., k Bkвыполняется для произвольного набора  , то справедлива формулаf  x1,..., xn  Vx11  ...

 xk k  f 1,..., k , xk 1,..., xn  .1,..., k Bk35Теорема доказана.□Следствие 8.1. Разложение произвольной функции алгебрылогики по одной переменной имеет вид:f  x1,..., xi 1, xi , xi 1,..., xn   xi  f  x1,..., xi 1,0, xi 1,..., xn   xi  f  x1,..., xi 1,1, xi 1,..., xn .Доказательство. По теореме 8.1 напишем разложение по переменной xi :f  x1,..., xi 1, xi , xi 1,..., xn   xi0  f  x1,..., xi 1,0, xi 1,..., xn   x1i  f  x1,..., xi 1,1, xi 1,..., xn   xi  f  x1,..., xi 1,0, xi 1,..., xn   xi  f  x1,..., xi 1,1, xi 1,..., xn .

□Пример 8.1. Преобразовать функциюf  x1, x2 , x3 , x4    0100 0111 1000 1011 ,используя формулу дизъюнктивного разложения по совокупности переменных x2 , x4 , представляя получаемые функции отдвух переменных формулами над множеством элементарных связок: отрицание, конъюнкция, дизъюнкция, импликация, сумма помодулю два, эквивалентность, штрих Шеффера, стрелка Пирса.Решение. Для данного случая формула дизъюнктивного разложения имеет вид:f  x1, x2 , x3 , x4   V x2a2  x4a4  f  x1, a2 , x3 , a4   a2 ,a4 a2a4xxV 2 4  f  x1, a2 , x3 , a4   0,0  0,11,0 1,1 x20  x40  f  x1,0, x3 ,0   x20  x14  f  x1,0, x3 ,1  x12  x40  f  x1,1, x3 ,0   x12  x14  f  x1,1, x3 ,1  x2  x4  f  x1,0, x3 ,0   x2  x4  f  x1,0, x3 ,1  x2  x4  f  x1,1, x3 ,0  x2  x4  f  x1,1, x3 ,1 .Запишем таблицу функции f  x1, x2 , x3 , x4  :36x1x2x3x4f00000001001000110100010101100111100010011010101111001101111011110 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1С помощью построенной таблицы составим таблицы для четырёх функций, зависящих от переменных x1 , x3 : f  x1,0, x3 ,0  ,f  x1,0, x3 ,1 , f  x1,1, x3 ,0  , f  x1,1, x3 ,1 .x1 x30 00 11 01 1f  x1,0, x3 ,0 0010x1  x3f  x1,0, x3 ,11000x1  x3f  x1,1, x3 ,0 0111x1  x3f  x1,1, x3 ,11101x1  x3Для функции f  x1, x2 , x3 , x4  формула дизъюнктивного разложения по совокупности переменных x2 , x4 имеет вид:f  x1, x2 , x3 , x4   x2  x4  x1  x3  x2  x4   x1  x3   x2  x4   x1  x3   x2  x4   x1  x3  .8.1.

Применение формулы дизъюнктивного разложения приреализации булевой функции на мультиплексореТермином «мультиплексирование» называют процесс передачи данных от нескольких источников по одному общему каналу.Мультиплексор (MS) – это логическое устройство с однимвыходом и двумя типами входов: информационными и адресными.Обозначение MS можно расшифровать как multiplexor.37В мультиплексоре число информационных входов зависит отчисла адресных входов. Если число адресных входов равно m , томаксимальное число информационных входов не превышает 2m .На рис.8.1 приведён пример условно графического обозначения мультиплексора с четырьмя информационными входамиMS (41). Этот мультиплексор имеет два (т=2) адресных входаА0 , А1 и четыре ( 2m  22  4 ) информационных входа D0 , D1 ,D2 , D3 .Ин т2ф.вх.Адр.