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

твх.z0z2z3D0 MSD1 (41)D2D3x0x1А0А1z1YРис.8.1.1. Условно графическое обозначение мультиплексора с четырьмя информационными входами.Разберём принцип действия MS (41). Мультиплексор, в зависимости от управляющего сигнала, поступающего с адресныхвходов А0 , А1 , подключает поочерёдно каждый из четырёх информационных входов D0 , D1 , D2 , D3 к выходу Y .Если на адресные входы А0 , А1 подать переменные x0 , x1 , ана информационные входы D0 , D1 , D2 , D3 , - переменные z0 , z1 ,z2 , z3 соответственно, то двоичный набор  x0 , x1  на адресныхвходах определяет номер i 1 xi  21 j  x0  21  x1  20j 038информа-ционного входа Di , с которого переменная zi передаётся на вы1ход Y, т.е.

Y  zi , если i   x j  21 j .j 0Например, при  x0 x1    00  номером информационного входа будет число 0  2  0  2  0 , следовательно, на выходе получится сигнал Y  z0 ; при  x0 x1    01 номером информационного10входа будет число 0  2  1  2  1 , следовательно, на выходе получится сигнал Y  z1 ; при  x0 x1   10  номером информацион10ного входа будет число 1  2  0  2  2 , следовательно, на выходеполучится сигнал Y  z2 ; при  x0 x1   11 номером информаци10онного входа будет число 1  2  1  2  3 , следовательно, на выходе получится сигнал Y  z3 .Мультиплексор можно использовать в качестве универсального логического элемента для реализации любой булевой функции от числа аргументов, равных числу адресных входов мультиплексора.

Покажем это на примере булевой функции «сумма помодулю 2».Пример 8.1.1. На мультиплексоре реализовать функцию«сумма по модулю 2», заданную таблицей истинности:10x1 0 0 1 1x2 0 1 0 1f 0 1 1 0Решение. Выбираем мультиплексор MS (41), имеющий 2адресных входа (по числу аргументов функции) и 22  4 информационных входов.Чтобы сформировать значения функции f на выходе мультиплексора в соответствии с таблицей истинности необходимо:39- на адресные входы мультиплексора A0 , A1 подать соответствующие аргументы x1 , x2 функции f, чтобы номер информационного входа соответствовал номеру двоичного набора  x1, x2  ;- к информационным входам подключить константы «0» и«1» в такой последовательности, которая полностью копируетпоследовательность единиц и нулей в таблице истинности функции f.Схема реализации функции «сумма по модулю 2» приведенана рис. 8.1.2.Еслипеременныефункциипринимаютзначения x1, x2    0,0 или  x1, x2   1,1 , то мультиплексор (41) коммутирует на выход сигнал с информационного входа D0 или D3 ,т.

е. нулевые значения. Если  x1, x2    0,1 или  x1, x2   1,0  , тона выход поступает соответствующий сигнал с информационноговхода D1 или D2 .01D0 MSD1 (41)D2D3Y=fА0А1Рис.8.1.2. Реализация функции «сумма помодулю 2» на мультиплексоре (41).В примере реализации функции «сумма по модулю 2» использовался мультиплексор с двумя адресными входами, числокоторых равно числу аргументов функции. Однако возможны ситуации, когда с помощью мультиплексора необходимо реализовать булеву функцию с числом переменных большим, чем число40адресных входов. В этом случае применяют формулу дизъюнктивного разложения булевой функции по переменным.В качестве примера реализуем функцию «сумма по модулю2» на мультиплексоре (21). Этот мультиплексор имеет один адресный вход А0 и два информационных D0 и D1 .

В качестве адресной переменной выберем x1 . Запишем формулу дизъюнктивного разложения функции f  x1, x2  по этой переменной:f  x1, x2   x10  f  0, x2   x11  f 1, x2   x1  f  0, x2   x1  f 1, x2  .Составим таблицы для функций f  0, x2  и f 1, x2  , зависящих от переменной x2 .x201f  0, x2 01x2f 1, x2 10x2Для функции f  x1, x2  формула дизъюнктивного разложенияпо переменной x1 имеет вид: f  x1, x2   x1   x2   x1   x2  .D0 MSD1 (21)Y=fА0Рис.8.1.3. Реализация функции «сумма полю 2» на мультиплексоре (21).Чтобы сформировать значения функции f  x1, x2  на выходеMS (21) в соответствии с полученным разложением, необходимо:- к адресному входу А0 подключить переменную x1 ;- на информационные входы D0 и D1 подать сигналы:41D0  f  0, x2   x2 , D1  f 1, x2   x2 .Схема, реализующая функцию «сумма по модулю 2» наMS (21), показана на рис.

8.1.3.Пример 8.1.2. С помощью MS (41) синтезировать булевуфункцию трёх переменных g  x1, x2 , x3   1101 0010  .Решение. В качестве адресных переменных выберем x1 и x2 .Тогда формула дизъюнктивного разложения имеет вид:g  x1, x2 , x3  x1a1  x2a2  g  a1, a2 , x3   a1,a2 VV x1 1  x22  g  a1, a2 , x3  aa 0,0  0,11,0 1,1 x10  x20  g  0,0, x3   x10  x12  g  0,1, x3   x11  x20  g 1,0, x3   x11  x12  g 1,1, x3   x1  x2  g  0,0, x3   x1  x2  g  0,1, x3   x1  x2  g 1,0, x3   x1  x2  g 1,1, x3  .Запишем таблицу функции g  x1, x2 , x3  :x1 0 0 0x2 0 0 1x3 0 1 0g 1 1 00 1 1 1 11 0 0 1 11 0 1 0 11 0 0 1 0С помощью построенной таблицы составим таблицы для четырёх функций, зависящих от переменной x3 :g  0,0, x3  , g  0,1, x3  , g 1,0, x3  , g 1,1, x3  .x3 g  0,0, x3  g  0,1, x3  g 1,0, x3  g 1,1, x3 010011110010x3x342Для функции g  x1, x2 , x3  формула дизъюнктивного разложения по совокупности переменных x1 , x2 имеет вид:g  x1, x2 , x3   x1  x2  1  x1  x2   x3   x1  x2   0   x1  x2   x3  .Чтобы сформировать значения функции g на выходе мультиплексора в соответствии с полученным разложением, необходимо:- на адресные входы мультиплексора A0 , A1 подключить соответствующие переменные x1 , x2 функции g, по которым проводилось разложение;- в соответствии с разложением функции на информационные входы мультиплексора D0 , D1, D2 , D3 подать сигналы:D0  g  0,0, x3   1, D1  g  0,1, x3   x3 ,D2  g 1,0, x3   0 , D3  g 1,1, x3   x3 .Схема мультиплексора, реализующего функцию g, изображена на рис.

8.1.4.10D0 MSD1 (41)D2D3Y=gА0А1Рис.8.1.4. Реализация функции трёх аргументов наMS (41).Переменная x3 в этом случае «выносится» на информационный вход D1 , а переменная x3 на вход D3 .438.2. Совершенная дизъюнктивная и совершеннаяконъюнктивная нормальные формыТеорема 8.2.1 (теорема о совершенной дизъюнктивнойнормальнойформе).Длялюбойбулевойфункцииf  x1, x2 ,..., xn  , отличной от тождественного нуля, справедливоследующее представлениеVx11  x2 2  ...

 xn n ,1,..., n  | f 1,..., n 1которое является единственным.Этот вид называется совершенной дизъюнктивной нормальной формой функции f  x1, x2 ,..., xn  и записывается СДНФ.Доказательство. Пусть функция f  x1, x2 ,..., xn  отлична оттождественного нуля. Напишем разложение этой функции поk  n переменнымf  x1,..., xn  Vx11  x2 2  ...  xn n  f 1, 2 ,..., n  ,1, 2 ,..., n Bnчто можно переписать в эквивалентном видеf  x1,..., xn  Vx11  ...

 xn n  f 1, ..., n  1,..., n  | f 1,..., n 1f  x1,..., xn  Vx11  ...  xn n  f 1,..., n  .1,..., n  | f 1,..., n 0Учитывая, что в первой дизъюнкции все значения функции равныединице, а вторая обнуляется из-за того, что все значения функции в ней равны нулю, получаем:f  x1,..., xn  Vx11  x2 2  ...  xn n .1,..., n  | f 1,..., n 1Покажем, что эта СДНФ единственная. В самом деле, имеетnся 22  1 n-местных функций, не равных тождественно нулю.Подсчитаем число различных СДНФ от n переменных.n!Пусть Cnk - число сочетаний из n элементов по k.k !(n  k )!Так как булевой функции f  x1, x2 ,..., xn  от n переменных соот-44ветствует двоичный набор значений f   0 ,1,...,2n 1 , имею-щий длину 2n , то множеству функций, имеющих в СДНФ однодизъюнктивное слагаемое, соответствует множество двоичныхнаборов значений функций, содержащих только одну единицу.Количество таких наборов равно C1n , поэтому и одночленных2СДНФбудетC1n .2Аналогично определяется число k-членныхСДНФ, которое равно C kn .

Поэтому число всех различных2nСДНФ буде равно: C1n  C 2n  ...  C kn  ...  C 2n . Применяя свой2222ство сочетаний 1  Cn1  Cn2  ...  Cnn  2n , получим:nnC1n  C 2n  ...  C kn  ...  C 2n  22  1.22222nnИтак, 2  1 функций реализуются посредством 22  1СДНФ, т.е. каждой функции соответствует единственная СДНФ.Теорема доказана.□Определение 8.2.1. Формула вида xi1  xi 2  ...  xi m , где m  1 ,12mik 1,2,..., n ,  k 0,1 и все переменные различны, называетсяэлементарной конъюнкцией ранга m на множестве булевых переменных x1,..., xn . Если ранг элементарной конъюнкции равенn, то конъюнкция x1 1  ...  xn n называется полной.Определение 8.2.2. Представление функции f  x1, x2 ,..., xn  ввиде дизъюнкций элементарных конъюнкций, где существует хотя бы одна неполная конъюнкция, называется дизъюнктивнойнормальной формой (ДНФ).Например, функцию f  x1, x2 , x3  можно представить в видеСДНФ f  x1, x2 , x3   x1x2 x3  x1 x2 x3  x1 x2 x3 , у которой все элементарныеконъюнкцииполные,иввидеДНФf  x1, x2 , x3   x1x2 x3  x2 x3 , у которой элементарная конъюнкцияx2 x3 полной не является.45Теорема 8.2.2 (о совершенной конъюнктивной нормальной форме).