 |
Применение аппарата булевских функций к анализу и синтезу комбинационных схем
|
|
|
|
Рассмотрим так называемые схемы из функциональных элементов (комбинационные схемы), вычисляющие (реализующие) булевские функции.
Под функциональным элементом будем понимать некоторое устройство (внутренняя структура которого нас не интересует[7]), обладающее такими свойствами:
1) оно имеет n³1 упорядоченных входов и один выход;
2) на входы этого устройства могут подаваться сигналы, принимающие два значения, которые будем обозначать через 0 и 1;
3) при каждом наборе сигналов на входах устройство выдает один из сигналов (0 или 1) в тот же момент, в который поступили сигналы на входе;
4) набор сигналов на входах однозначно определяет сигнал на выходе, то есть, если в различные моменты времени на входы поступает одна и та же комбинация сигналов, то в эти моменты на выходе будет один и тот же сигнал.
С каждым функциональным элементом с n входами сопоставим булевскую функцию от n переменных f(x1,x2,…,xn), определяемую следующим образом: входу с номером i (i = 1, 2, …, n) ставится в соответствие переменная xi и с каждым набором <a1, a2, …, ai, …, an> этих переменных (aiÎ{0,1}) сопоставляется число f(a1, a2, …, ai, …, an), равное 0 или 1 в зависимости от того, какой сигнал вырабатывается на выходе при подаче этого набора сигналов на входы данного функционального элемента. О функции f(x1,x2,…,xn) будем говорить, что данный функциональный элемент ее реализует.
В дальнейшем мы будем рассматривать функциональные элементы, реализующие полную систему логических операций: конъюнкцию, дизъюнкцию, отрицание. Эти элементы представлены на рис.2.18.
Теперь определим понятие "схема из функциональных элементов в базисе {&, Ú, Ø}" и понятия ее выходов и входов. Определение будет носить индуктивный характер (подобно тому, как выше определялось понятие формулы логики высказываний).
|
|
|
1. Каждый функциональный элемент представляет собой схему из функциональных элементов с теми же входами и выходами, что и у этого элемента.
2. Если S1 - схема из функциональных элементов и два ее входа соединены вместе, то получающаяся конструкция S будет схемой из функциональных элементов. Входами S являются все несоединенные входы S1 и еще один вход, соответствующий двум соединенным входам схемы S1, а выходом схемы S - выход S1.
3. Если S1 и S2 - две схемы из функциональных элементов, то конструкция S, получающаяся соединением какого-либо входа схемы S2 с выходом схемы S1, также будет схемой из функциональных элементов. Входами схемы S будут все входы схемы S1 и все входы схемы S2, за исключением того, который соединен с выходом схемы S1, а выходом S является выход схемы S2.
4. Если в схеме из функциональных элементов S1 ее вход соединить с выходом некоторого функционального элемента из S1 без образования цикла для какого-либо функционального элемента (то есть его выход не должен соединяться, быть может, через другие функциональные элементы из S1 с его входом), то получившаяся конструкция S является схемой из функциональных элементов. Выходом S будет выход S1, а входами S - все входы S1, кроме того, который соединен с выходом функционального элемента. На рис.2.21 приведен пример подобной схемы:
Определение схемы из функциональных элементов завершено.
Теперь определим булевскую функцию, реализуемую данной схемой.
1. Если схема является функциональным элементом, то булевская функция, ею реализуемая, уже определена.
2. Если схема S1 реализует булевскую функцию f(x1,x2,…,xn), то схема S, построенная в п.2 определения схемы из функциональных элементов, реализует булевскую функцию, полученную из f(x1,x2,…,xn) отождествлением переменных, отвечающих объединенным входам схемы S1.
|
|
|
3. Пусть схема S1 реализует булевскую функцию f(x1,x2,…,xn), а схема S2 - булевскую функцию g(y1,y2,…,ym). Считаем, что все переменные x1,x2,…,xn,y1,y2,…,ym попарно различны. Тогда схема S, построенная в п.3 определения схемы из функциональных элементов, реализует булевскую функцию g(y1, y2, …, yi-1, f(x1,x2,…,xn), yi-1, …, ym), то есть функцию, получаемую путем подстановки в функцию g(y1,y2,…,ym) вместо аргумента yi, сопоставленного входу схемы S2, соединенному с выходом S1, функции f(x1,x2,…,xn).
4. Булевская функция, реализуемая схемой S, построенной в п.4 определения схемы из функциональных элементов, получается из булевской функции, реализуемой схемой S1, операцией, типа описанной в п. 3 настоящего определения. Например, приведенная на рис.2.21 схема реализует функцию f(x1,x2,x3,x4) = Ø(x1&Ø x2&(Øx3Úx4)).
Определение булевской функции, реализуемой схемой из функциональных элементов, завершено.
Поскольку, как отмечалось выше, любую булевскую функцию от n переменных можно выразить в виде суперпозиции функций, образующих полную систему булевских функций (в частности, S0 = {φ3(x), f2(x,y), f8(x,y)} - отрицание, конъюнкция, дизъюнкция), то значит, что и любая булевская функция может быть реализована соответствующей схемой из функциональных элементов.
Схемы из функциональных элементов имеют разнообразное техническое применение. Во многих реальных автоматических устройствах есть блоки, представляющие собой соединение схем из функциональных элементов.
В качестве примера опишем в виде схемы из функциональных элементов один из основных узлов ЭВМ - двоичный сумматор - устройство, предназначенное для сложения n-разрядных двоичных чисел.
Пусть имеются два двоичных числа:
X = xn xn-1 xn-2 … x2 x1 и Y = yn yn-1 yn-2 … y2 y1
(Здесь xi, yj - двоичные цифры 0 или 1.)
Требуется получить число Z, равное сумме чисел X и Y.
Рассмотрим вначале одноразрядный двоичный сумматор на два входа.
Здесь: xi - i- тая цифра числа X; yi - i-тая цифра числа Y; zi - i-тая цифра результата сложения - числа Z; pi+1 - перенос в следующий, (i+1)-ый разряд.
Входы сумматора - xi и yi, выходы сумматора - zi и pi+1.
Опишем выходы сумматора как булевские функции его входов в виде следующей таблицы:
| xi | yi | zi | pi+1 |
| 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 |
|
|
|
Легко видеть:
zi = f1(xi,yi) = Øxi&yi Úxi&Øyi; pi+1 = f2(xi,yi) = xi&yi.
Соответствующие схемы из функциональных элементов представлены на рис.2.23.
Рис.2.23. Функциональная схема одноразрядного двоичного сумматора на два входа.
Рассмотрим теперь одноразрядный двоичный сумматор на три входа. Схематическое представление его на рис.2.24.
В отличие от предыдущего случая теперь мы учитываем перенос из младшего разряда. Здесь: xi - i- тая цифра числа X; yi - i-тая цифра числа Y; pi - перенос из предыдущего, i-го разряда; zi - i-тая цифра результата сложения - числа Z; pi+1 - перенос в следующий, (i+1)-ый разряд.
Входы сумматора - xi, yi, pi, выходы сумматора - zi и pi+1.
Опишем выходы сумматора как булевские функции его входов в виде следующей таблицы:
| хi | yi | pi | zi | pi+1 |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 1 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Соответствующие схема из функциональных элементов представлены на рис.2.25.
Рис.2.25. Функциональная схема одноразрядного двоичного сумматора на три входа.
Сложение n-разрядных двоичных чисел можно осуществить, соединив n сумматоров таким образом, как это показано на рис.2.26.
В данной схеме сумматора первый элемент имеет два входа, а все остальные элементы - по три. Появление 1 на выходе yn+1 означает переполнение разрядной сетки, то есть попытка представить число, содержащее больше, чем n двоичных разрядов.
Рис.2.26. Схема n-разрядного двоичного сумматора.
В некоторых схемах сумматоров "замыкают" выход pn+1 последнего элемента на вход p1 первого. Тогда все элементы схемы сумматора будут иметь по три входа. Такое сложение называют циклическим. Оно находит свое применение при выполнении арифметических операций в ЭВМ.
Работа n-разрядного двоичного сумматора напоминает замóк типа "молния". Но есть существенная разность: замóк застегивается "шаг за шагом", последовательно. А сложение на двоичном сумматоре осуществляется "параллельно" за один шаг (такт), и выход полностью определяется текущим состоянием входов, независимо от их количества. То есть, если в момент времени t подать 2n сигналов на входы xn,xn-1, xn-2, …,x2, x1 и yn,yn-1, yn-2,…,y2,y1, то n сигналов на выходах сумматора zn, zn-1, zn-2, …,z2, z1 появятся в тот же момент времени, без задержки. Схемы из функциональных элементов называют поэтому комбинационными схемами, или схемами без памяти. Они не запоминают результатов своей предыдущей работы.
|
|
|
Естественно, вычислительные устройства должны обладать "памятью". Ее наличие даст возможность конструировать счетчики, арифметические регистры и различные "умные" схемы, которые выполнив одну интересную функцию, начинают выполнять другую, не менее интересную.
Такие схемы и способы их анализа и синтеза мы рассмотрим ниже.
Логические операции, выполняемые микропроцессором
Микропроцессор компьютера способен выполнять основные логические операции: конъюнкцию & (обозначение AND), дизъюнкцию 
(обозначение OR), отрицание Ø (обозначение NOT), строгую дизъюнкцию (или сложение по модулю 2) Å (обозначение XOR).
Особенностью выполнения логических операций микропроцессором является то, что они выполняются над двоичными кодами (словами, полусловами, двойными словами) поразрядно.
Булевы алгебры
Со школы читатель привык к слову алгебра. При этом под алгеброй, как правило, понимается раздел математики, посвященный изучению свойств числовых (арифметических) операций (сложение, вычитание, умножение, деление, возведение в степень, извлечение корня и т.д.), выражений, тождеств, уравнений и т.п.
Но, вообще говоря, слово алгебра в математике понимается значительно шире.
А именно: Алгеброй называют множество объектов любой природы с определенными и замкнутыми на этом множестве операциями.
Если какая-либо операция l определена на множестве Q и результат ее также принадлежит этому множеству, то говорят, что операция l замкнута на этом множестве, или множество замкнуто относительно операции l. Например, множество натуральных чисел N замкнуто относительно операций сложения и умножения натуральных чисел, но не замкнуто относительно операций вычитания и деления, которые могут в качестве результата давать значения, не принадлежащие множеству натуральных чисел (вычитание – отрицательные числа, а деление – дробные).
С этой точки зрения, арифметика – это алгебра с операциями сложения и умножения, замкнутыми на множестве натуральных чисел. Если к числу операций добавить вычитание, то, строго говоря, это уже не будет алгебра.
Рассмотренная в § 1 настоящей главы теория множеств также является алгеброй в указанном выше смысле. Это алгебра множеств, объектами которой являются множества, а определенными и замкнутыми на этих объектах являются операции объединения, пересечения, дополнения.
|
|
|
Точно так же, рассмотренная в § 2 настоящей главы логика высказываний является алгеброй. Это алгебра высказываний, объектами которой являются высказывания, а определенными и замкнутыми на этих объектах являются операции дизъюнкции, конъюнкции и отрицания.
Две последние алгебры принадлежат к особому типу алгебр, называемых булевыми.[8])
Булева алгебра представляет собой множество объектов (любой, но одинаковой, природы) с двумя «особыми» объектами («константами») - «единица» (I) и «нуль» (О), и двумя замкнутыми на множестве объектов операциями «сложения» (+) и «умножения» (´), обладающими следующими свойствами:
коммутативность + и ´:
A+B=B+A, A´B=B´A;
ассоциативность + и ´:
A+(B+C)=(A+B)+C, A´(B´C)=(A´B) ´C;
дистрибутивность + относительно ´ и ´ относительно +:
A+(B´C)=(A+B) ´(A+C), A´(B+C)=(A´B)+(A´C);
идемпотентность + и ´:
A+A=A, A´A=A.
Кроме того, «особые» объекты («константы») I и O обладают следующими свойствами:
A+O=A, A+I=I, A´I=A, A´O=O.
С точки зрения этого определения алгебра множеств является булевой алгеброй, в которой роль «сложения» играет операция объединения множеств (
), роль «умножения» – операция пересечения множеств (
), роль константы «нуль» – пустое множество (Æ), роль «единицы» - универсальное множество (U). Легко проверить, что все указанные выше свойства операций и констант булевой алгебры здесь выполняются.
Алгебра высказываний также является булевой алгеброй. В ней роль «сложения» играет операция дизъюнкции (Ú), роль «умножения» – операция конъюнкции (&), роль “нуля” – логическая константа Л, роль “единицы” – логическая константа И. И опять-таки легко проверить, что все указанные выше свойства операций и констант булевой алгебры выполняются.
Аналогично можно убедиться в том, что «алгебра переключательных схем» также является булевой: «сложению» будет соответствовать параллельное соединение контактов, «умножению» – последовательное соединение, константе «нуль» – всегда разомкнутый контакт, «единице» – всегда замкнутый контакт. [9])
В заключение приведем пример еще одной булевой алгебры – «алгебры максимумов и минимумов». Примем в качестве объектов (элементов) нашей алгебры, например, множество всех чисел отрезка [0,1], т.е. 0£х£1. В качестве операции «сложения» будем рассматривать операцию взятия максимального из двух чисел x и y и обозначать ее max (x,y), в качестве операции «умножения» - операцию взятия минимального из двух чисел x и y и обозначать ее min (x,y). В качестве константы «нуль» примем минимальное число из рассматриваемого отрезка, то есть число 0, а в качестве «единицы» – максимальное число из рассматриваемого отрезка – 1.
Легко проверить, что для определенных таким образом констант и операций выполняются все свойства булевой алгебры.
В самом деле:
коммутативность min и max:
min (x,y)=min(y,x), max (x,y)=max(y,x);
ассоциативность min и max:
min (x, min (y,z)) =min (min (x, y),z),
max (x, max (y,z)) =max (max (x, y),z);
дистрибутивность min относительно max:
min (x, max(y,z)) = max(min(x,y),min(x,z)),
max (x, min(y,z)) = min(max(x,y),max(x,z));
идемпотентность min и max:
min(x,x)=x, max(x,x)=x;
свойства констант 0 и 1:
min(x,0)=0, min(x,1)=x, max(x,0)=x, max(x,1)=1.
Рекомендация: Проверьте (хотя бы на примерах) справедливость этих соотношений
[1])Кроме этих значений часто используются обозначения: T (true – истина) и F (false – ложь), а также 1 и 0.
[2]) F и Ф называют в этом случае подформулами формулы логики высказываний.
[3]) Естественно, логикой высказываний не исчерпывается все многообразие логических рассуждений. Кроме логики высказываний, важное значение имеют логика предикатов, модальная логика, нормативная логика, временная логика, многозначная логика, нечеткая логика и т.д.
[4]) Как такое утверждение В найти или построить - это и есть часть доказательства, зачастую носящая эвристический, то есть поисковый, характер и относится к содержанию математической дисциплины, теорема из которой доказывается. Для нас важна форма доказательства, то есть, его структура.
[5]) Как известно, формула А ~В эквивалентна конъюнкции (A É B)&(B É A).
[6]) См. книгу: Яблонский С.В., Гаврилов Г.П., Кудрявцев В.Б. Функции алгебры логики и классы Поста. –М.:Наука, 1966. –120 с.
[7]) Заинтересованному читателю можем порекомендовать, например, книгу: О.А. Маслюков. Вычислительная техника и программирование. -М.:Высшая школа,1993.-208 с.
[8]) Название булевы эти алгебры получили в честь известного английского математика Джорджа Буля (1815-1864).
[9]) Более подробную информацию о булевых алгебрах можно получить в книге: И.М. Яглом. Необыкновенная алгебра. -М.: Наука, 1968. -70с.
|
|
|
