Представлению булевых функций формулами можно придать следующий "инженерно-конструктивный" смысл. Будем рассматривать формулу Ф(x 1 ,..., x n) над каким-то произвольно фиксированным множеством F как "черный ящик", некое устройство, на вход которого подаются всевозможные наборы значений переменных, а на выходе появляются соответствующие этим наборам значения функции f, представляемой формулой Ф (рис. 6.22).
Чтобы понять, как устроен "черный ящик", мы должны разобрать процесс построения формулы из подформул. Добираясь до "базисных" подформул, т.е. элементов множества F, мы приходим к "кирпичикам", структурным элементам, из которых собран "черный ящик", вычисляющий функцию f. Каждая функция "базиса" F вычисляется соответствующим "узлом", который рассматривается как мельчайшая структурная единица нашего "черного ящика", и его внутренняя структура уже не анализируется.
Пример 6.22. Выберем в качестве множества F стандартный базис. Тогда формула над стандартным базисом, представляющая функцию ~ (эквивалентность), строится следующим образом:
Вычисление по этой формуле (и процесс ее построения из элементов стандартного базиса) можно схематически изобразить так, как показано на рис. 6.23.
Переменное х 1 (точнее, значение этого переменного) подается на вход структурного элемента, называемого инвертором (рис. 6.24, а) и вычисляющего отрицание. Снимаемое с выхода инвертора отрицание х 1 , т.е. функция x 1 , подается на один из входов конъюнктора (рис. 6.24, б), на второй вход которого подается переменное х 2 . На выходе конъюнктора появляется функция x 1 х 2 . Аналогично прослеживается вычисление функции х 1 x 2 , Обе эти функции подаются на входы дизъюнктора (рис. 6.24, в), с выхода которого снимается функция х 1 x 2 ∨ х 1 x 2 (это не что иное, как сумма по модулю 2: х 1 ⊕ х 2). И наконец, эта функция подается на вход инвертора, на выходе которого уже получается функция ~ (эквивалентность). #
Таким образом, мы приходим к идее "схемы" - математической модели вычислителя булевой функции, представленной некоторой формулой, собранного из структурных элементов, каждый из которых вычисляет одну из "базисных" булевых функций. В общем случае "схема" вычисляет булев оператор, причем каждая координатная функция этого оператора снимается с одного из выходов схемы.
Математически "схема" определяется как ориентированный граф специального вида, в котором и вершины, и дуги снабжены некоторыми метками.
Введем обозначение: если F - какое-то множество булевых функций, то через F (n) обозначаем подмножество F, состоящее из всех функций от n переменных (n≥0).
Определение 6.14. Пусть фиксированы множества: F (булевых функций) и Х (булевых переменных).
Схемой из фунпциональныж элементов над базисом F ∪ X (С Ф Э), или просто сжемой над базисом F ∪ X, также (F,Х)-схемой, называют бесконтурный ориентированный граф (т.е. сеть), каждая вершина которого помечена одним из элементов множества F U Х так, что выполняются следующие требования:
- каждый вход сети помечен либо некоторым переменным из Х, либо некоторой константой из F (0) ;
- если вершина v сети помечена функцией f от n переменных (т.е. f ∈ F (n)), то ее полустепень захода равна n, причем на множестве дуг, заходящих в вершину v, задана (взаимно однозначная) нумерация, при которой каждая дуга получает номер от 1 до n.
Если базис подразумевается, то мы будем говорить просто "схема". Кроме того, если множество переменных фиксировано "раз и навсегда" и при рассмотрении различных схем мы меняем только множество функций F, то, как это мы делали, вводя понятия формулы и суперпозиции над заданным базисом, будем говорить о СФЭ над базисом F, полагая каждый раз, что подразумевается однажды фиксированное множество переменных Х, которое (если это не вредит точности) не упоминается.
Определим теперь по индукции понятие булевой функции, вычисляемой вершиной схемы .
Определение 6.15. Пусть задана СФЭ S над базисом F ∪ Х, множество вершин которой есть V.
- Принимается, что каждый вход СФЭ вычисляет булеву функцию, которой он помечен (т.е. некоторое переменное или константу).
- Если вершина v ∈ V помечена функцией f ∈ F (n) , заходящая в нее дуга с номером i (1≤i≤n) исходит из вершины u i ∈ V, которая вычисляет функцию g i , то вершина v вычисляет суперпозицию f(g 1 , ... ,g n).
Таким образом, если каждая вершина СФЭ над F вычисляет некоторую функцию, то порядок, в котором перечисляются функции g 1 , ... ,g n , подставляемые на места переменных функции f, в общем случае существен. Естественно назвать булеву функцию f от n переменных коммутативной, если она сохраняет значение при произвольной перестановке ее переменных. В этом случае мы можем не заботиться о нумерации дуг, заходящих в вершину схемы, помеченную такой функцией.
Пример 6.23. Рассмотрим СФЭ на рис. 6.25. Вершины v 1 и v 2 - входы СФЭ. Эти вершины вычисляют соответственно функции х и у. Тогда вершина v 3 , равно как и вершина v 4 , согласно определению 6.15, вычисляет функцию x|y (штрих Шеффера), а вершина v 5 (выход сети) - функцию (x|y)l(x|y), которая, как известно, равна конъюнкции х · у.
СФЭ, изображенная на рис. 6.26, имеет два выхода, вычисляющие функции (x|x)|(y|y) =x ∨ y и (x|y)|(x|y) =х·у.
Определение 6.16. Булева функция, вычисляемая СФЭ над базисом F ∪ Х, - это функция, вычисляемая каким-либо из ее выходов.
Таким образом, СФЭ вычисляет ровно стмько булевых функций, сколько имеет выходов. СФЭ на рис. 6.25 вычисляет одну функцию, а СФЭ на рис. 6.26 - две.
В общем случае, если {x 1 ,..., x n } - множество всех переменных, которые служат метками входов схемы S над базисом F ∪ Х, имеющей m выходов, СФЭ S определяет отображение булева куба B n в булев куб B m , т.е. булев оператор.
Замечание 6.10. В некоторых случаях функцию, вычисляемую данной СФЭ, определяют несколько иначе, полагая, что это функция, вычисляемая любой вершиной из подмножества выделенных вершин СФЭ. В частности, это могут быть и выходы. В любом случае договоримся из выделенных (в только что указанном смысле) вершин схемы проводить "выходную" стрелку. #
Таким образом, каждая схема из функциональных элементов вычисляет некоторый булев оператор, в частности, если число выходов схемы равно 1, то она вычисляет некоторую булеву функцию.
Можно доказать и обратное: по любому булеву оператору может быть построена СФЭ над базисом F, где F - полное множество, вычисляющая данный оператор.
Представим функцию y 1 в базисе Жегалкина. Используя законы де Моргана, получим
(напомним, что сумма по модулю 2 любого четного числа равных слагаемых равна 0).
y 1 = х 1 х 2 ⊕ х 1 х 3 ⊕ х 2 х 3 = х 1 х 2 ⊕ х 3 (х 1 ⊕ х 2).
СФЭ для булева оператора, заданного в табл. 6.9, над базисом Жегалкина приведена на рис. 6.27.
При проектировании СФЭ полезно иметь в виду числовой параметр, называемый ее сложностью.
Сложность СФЭ - это число ее вершин, не являющихся входами.
Приведенная на рис. 6.27 СФЭ над базисом Жегалкина имеет сложность 5.
Рассмотрим теперь СФЭ для того же оператора над стандартным базисом.
По таблице (см. табл. 6.9) строим СДНФ для функции y 2:
y 2 = x 1 x 2 х 3 ∨ x 1 х 2 x 3 ∨ х 1 x 2 x 3 ∨ х 1 х 2 х 3 .
Карта Карно для этой функции, изображенная на рис. 6.28, показывает, что ее нельзя минимизировать (точнее, записанная выше СДНФ и есть минимальная ДНФ для этой функции). Но можно пойти по другому пути. Мы можем рассматривать табл. 6.9 как таблицу, определяющую частичную булеву функцию y 2 = y 2 (х 1 х 2 х 3 y 1). Минимизируя эту функцию по
карте Карно*, изображенной на рис. 6.29, получаем
* На этой карте мы оно обозначили наборы, на которых функция принимает значение 0, проставив нули в соответствующих клетках. Тем самым мы хотим еще раз зафиксировать внимание на том, что не следует путать нули с прочерками: прочерк в клетке карты, задающей частичную функцию, означает, что на данном наборе значение функции не определено, т.е. не равно ни 0, ни 1.
y 2 = х 1 х 2 х 3 ∨ y 1 (х 1 ∨ х 2 ∨ х 3).
СФЭ над стандартным базисом для рассматриваемого булева оператора приведена на рис. 6.30. Сложность этой СФЭ составляет 11. Заметим, что вершина, вычисляющая функцию y 1 , не является выходом.
Булев оператор, рассмотренный в этом примере, вычисляет двухразрядную сумму (по модулю 2) трех одноразрядных слагаемых. Его можно считать также одноразрядным двоичным сумматором - функциональным блоком многоразрядного двоичного сумматора - для двух слагаемых. Тогда функция y 1 интерпретируетея как "сигнал переноса" в старший разряд. На рис. 6.31 изображено "соединение" трех СФЭ (таких, как показано на рис. 6.30), с помощью которого вычисляется сумма двух трехразрядных двоичных чисел. На третий вход сумматора для младшего разряда подается константа 0, а "сигнал переноса" старшего разряда есть старший разряд суммы, которая в общем случае будет четырехразрядным числом.
Замечание 6.11. Если мы проектируем СФЭ над стандартным базисом и хотим минимизировать ее сложность, то нам необходимо прежде всего построить соответствующую минимальную ДНФ. В этом случае мы може м принять во внимание еще один критерий, по которому минимизируется сама ДНФ, - число отрицаний. Среди всех минимальных (в смысле определения 6.6) ДНФ следует отобрать те, в которых число вхождений переменных под знаком отрицания является наименьшим. С точки зрения сложности СФЭ, которая будет построена по минимальной ДНФ, это означает, что в ней минимизируется число "инверторов" - вершин СФЭ, помеченных функцией отрицания.
Например, для функции, заданной картой Карно (рис. 6.32), к ядру, состоящему из простых импликант х 1 х 2 х 4 и x 1 х 3 x 4 , следует добавить простую импликанту х 2 х 3 х 4 , а не x 1 х 2 х 3 , поскольку она не содержит отрицаний.
Функциональные схемы (ФС) предназначены для преобразования логической информации. Исходная информация, закодированная в виде дискретных сигналов, подаётся на входы схемы`х n . Затем данная информация перерабатывается и в дискретной форме считывается с выходов схемы `у m (n, m – числа ее входов и выходов). Рассмотрим ФС, функционирующие в двузначной логике и имеющие один выход (m =1). Преобразование информации в них может быть задано в виде функции алгебры логики у = f (х n ). Вместо релейных элементов в ФС используются функциональные элементы (ФЭ), реализующие, как правило, элементарные логические функции.
Определение. Анализом называется построение формулы алгебры логики (если необходимо - ее таблицы истинности) по заданной ФС.
Для построения формулы по заданной схеме необходимо связи между ФЭ в ФС представить в виде подстановок в соответствующие им элементарные функции. При этом предполагается, что переработка информации производится поэтапно от входов к выходам. В реальных схемах для обеспечения временного согласования работы всех ФС используют дополнительные элементы.
Анализ ФС можно выполнять двумя способами – от входов к выходам и от выходов к входам. Рассмотрим первый способ, применяя дополнительные обозначения для промежуточных соединений схемы.
Пример 1. В качестве ФЭ приняты {& ,Ú ,Ø }.Произвести анализ ФС, физическая структура которой дана на рис.1.19.
Решение. Обозначив промежуточные соединения ФЭ так, как показано на рисунке, по шагам определяем сигналы, соотвествующие им. При этом перемещаемся от входов схемы к ее выходу.
Рис.1.19
ШАГ 1. R =`y , Q = `z.
ШАГ 2. X = x & R = x &`y , P = x & y, W =P &Q = x & y &`z.
ШАГ 3. Y =X & z = x &`y & z , U =P & z = x & y & z.
ШАГ 4. Z = Y ÚU = x &`y & z Ú x & y & z.
ШАГ 5. F = Z Ú W = x &`y & z Ú x & y & z Ú x & y &`z.
Таким образом, рассмотренная ФС реализует следующую формулу алгебры логики:
F (x , y , z ) = x & `y & z Ú x & y & z Ú x & y & `z.
Найденная формула представляет собой СДНФ. Вектор ее значений истинности имеет вид (00000111).
В зависимости от исходных данных, среди задач синтеза (проектирования) ФС можно выделить:
1) синтез схем по заданным формулам,
2) синтез схем по заданным функциям.
Определение. Синтезом ФС по заданной формуле называют построение структуры ФС, соответствующей заданной формуле алгебры логики.
Решение подобных задач производится по алгоритму, обратному методу анализа. Как отмечено в параграфе 1.7, структура формул алгебры логики позволяет изоморфно отобразить только системы с параллельными и последовательными соединениями элементов. Поэтому в ФС, изоморфно соответствующей формуле, должны быть только соединения данного вида.
Определение. Синтезом ФС по заданной функции называют построение структурной схемы, реализующей заданную функцию алгебры логики.
Поскольку представление функций формулами неоднозначно, то данная задача имеет неединственное решение. Как и в случае релейных схем, оптимальными являются ФС, состоящие из минимального количества ФЭ и соединений между ними. Такие ФС можно получить, используя формулы с минимальным числом переменных.
Как и для РС, будем отдельно рассматривать формулы, оптимальные в классе нормальных форм (которые равны соответствующим минимальным формам), а также абсолютно оптимальные формулы, получаемые из минимальных нормальных форм путем их дальнейшего сокращения с применением законов алгебры логики. Способы получения оптимальных формул – те же, что и в релейных схемах. В Примере 1 расcмотрена ФС, реализующая функцию (00000111). Данная ФС не оптимальна, поскольку соответствующая ей формула описывает СДНФ F = x`y z Ú x y z Ú x y`z , которая не является минимальной. Минимизируя её, получим МДНФ следующего вида: F = x y Ú x z. Ей соответствует ФС на рис.1.20
Рис.1.20
Если применить дистрибутивный закон к МДНФ, то получим формулу с ещё меньшим числом переменных: f = x (y Ú z ). Для данной функции она совпала с МКНФ. Ей соответствует абсолютно оптимальная схема
Рис.1.21
Очевидно, данная схема значительно проще исходной (рис.1.19). Поскольку синтез оптимальных ФС сводится к построению минимальных формул, то аналогично строятся оптимальные схемы и в других базисах. Аналоги первого и второго дистрибутивных законов алгебры логики для шефферовых и веббовых форм можно получить, заменяя в данных законах:
&( x , y )= Ø ½ ( x , y ) = ¯ (Øx ,Øy );
Ú ( x , y )= ½ (Ø x , Øy ) =Ø ¯ (x , y ).
Пример 2. Построить ФС, реализующую одноразрядный двоичный сумматор двух чисел при помощи ФЭ, соответствующих базису {Ø ,¯ } , а также в базисе {¯ }.
Решение. Обозначим одноразрядные двоичные числа, подаваемые на вход, через (х ,у ). На выходе должна быть получена их суммав двоичной системе. Если х= 1, у= 1, то S = 2 10 = 10 2 , поэтому для изображения её в общем случае необходимо использовать два двоичных знака, а ФС должна иметь два выхода. Обозначим их f (старший разряд суммы) и g (младший разряд). Таблицы истинности функций f (х ,у ), g (х ,у ):
| x | y | f (x ,y ) | g (x ,y ) |
Строим СВНФ функций в базисе {Ø ,¯}. f имеет в векторе истинности одну единицу, поэтому ее форма состоит из одной конституенты: f =¯ (Ø х,Ø у ). У функции g СВНФ имеет вид: g =د(¯(х ,Ø у ),¯(Ø х ,у )). Данные формы являются минимальными. При объединении входов элементов функциональную схему можно представить в следующем виде:
Рис.1.22
В рассмотренном примере невозможно упрощение веббовых нормальных форм при помощи законов алгебры логики. В однофункциональном базисе {¯} ФС получим, применяя подстановку Ø х = ¯ (х ,х ). Соответствующая схема дана на рис.1.23.
Рис.1.23
ЗАДАЧИ
1. Построить с использованием ФЭ {& ,Ú ,Ø }оптимальные в классе нормальных форм и абсолютно оптимальные ФС, реализующие следующие функции:
а) (x ®y )Å zy ;б)(x Åy )|z ,в) xy ®yz ;г) x |(y Ú z );д) x ®(y ®z ) ;
е) (10011101) ;ж) (01101011) ;з) (1110101111111110).
2. Построить с использованием ФЭ {Ú,Ø }ФС функций 1.а) -ж).
3. Построить с использованием ФЭ {&,Ø }ФС функций 1.а)-ж).
4. Построить ФС, реализующую одноразрядный двоичный сумматор (Пример 2)при помощи ФЭ следующего вида:
а){& ,Ú ,Ø}, б) {Ú ,Ø } , в) {& ,Ø}, г) {x| y }.
5. С помощью ФЭ {& ,Ú ,Ø }построить ФС следующих устройств:
а) преобразователя с двоичными входами (х ,у ),и выходом f , который работает следующим образом: при подаче х= 0на выходе f = у , а при подаче х = 1на входе f =`у;
б) избирательного устройства с двоичными входами (х , у )и выходами f 0 , f 1 , f 2 , f 3 , который воспринимает на входе комбинацию значений (х у ) как двоичное число i , лежащее в интервале от 0 до 3. Значения выходов для каждого i следующие: f i = 1, а все остальные f j = 0, (0 £ j £ 3 , j ¹ i ).
6. Можно ли в качестве базиса при построении ФС принять следующие наборы функций:
а) (1001),(10001110),
б) (0101),(1011),(1101),
в) (1010),(01110001)?
Ответ обосновать.
7. Привести примеры управляющих функций, ФС которых нельзя построить только из одних ФЭ типа {®}.
8. Привести примеры управляющих функций, ФС которых нельзя построить только из одних ФЭ типа{ Å , º }.
9. Дана ФС из ФЭ {& ,Ú ,Ø }.
Рис.1.24
Можно ли из нее исключить путем эквивалентных преобразований:
а) все элементы {Ø}?
б) все элементы {&}?
в) все элементы {Ú}?
10. Оптимизировать ФС из ФЭ {& ,Ú ,Ø },приведеную на рис.1.25.
Рис.1.25
Построить ФС:
а) оптимальную в классе нормальных форм и
б) абсолютно оптимальную.
Представлению булевых функций формулами можно придать следующий "инженерно-конструктивный" смысл. Будем рассматривать формулу над каким-то произвольно фиксированным множеством как "черный ящик", некое устройство, на вход которого подаются всевозможные наборы значений переменных, а на выходе появляются соответствующие этим наборам значения функции , представляемой формулой (рис. 6.22).
Чтобы понять, как устроен "черный ящик", мы должны разобрать процесс построения формулы из подформул. Добираясь до "базисных" подформул, т.е. элементов множества , мы приходим к "кирпичикам", структурным элементам, из которых собран "черный ящик", вычисляющий функцию . Каждая функция "базиса" вычисляется соответствующим "узлом", который рассматривается как мельчайшая структурная единица нашего "черного ящика", и его внутренняя структура уже не анализируется.
Пример 6.22. Выберем в качестве множества стандартный базис. Тогда формула над стандартным базисом, представляющая функцию (эквивалентность), строится следующим образом:
Вычисление по этой формуле (и процесс ее построения из элементов стандартного базиса) можно схематически изобразить так, как показано на рис. 6.23.
Переменное (точнее, значение этого переменного) подается на вход структурного элемента, называемого инвертором (рис. 6.24, а) и вычисляющего отрицание. Снимаемое с выхода инвертора отрицание , т.е. функция , подается на один из входов конъюнктора (рис. 6.24,5), на второй вход которого подается переменное . На выходе конъюнктора появляется функция . Аналогично прослеживается вычисление функции . Обе эти функции подаются на входы дизъюнктора (рис. 6.24, в), с выхода которого снимается функция (это не что иное, как сумма по модулю 2: ). И наконец, эта функция подается на вход инвертора, на выходе которого уже получается функция (эквивалентность).
Таким образом, мы приходим к идее "схемы" - математической модели вычислителя булевой функции, представленной некоторой формулой, собранного из структурных элементов, каждый из которых вычисляет одну из "базисных" булевых функций. В общем случае "схема" вычисляет булев оператор, причем каждая координатная функция этого оператора снимается с одного из выходов схемы.
Математически "схема" определяется как ориентированный граф специального вида, в котором и вершины, и дуги снабжены некоторыми метками.
Введем обозначение: если - какое-то множество булевых функций, то через обозначаем подмножество , состоящее из всех функций от переменных .
Определение 6.14. Пусть фиксированы множества: (булевых функций) и (булевых переменных).
Схемой из функциональных элементов над базисом (СФЭ), или просто схемой над базисом , также (F,X)-схемой, называют бесконтурный ориентированный граф (т.е. сеть), каждая вершина которого помечена одним из элементов множества так, что выполняются следующие требования:
1) каждый вход сети помечен либо некоторым переменным из , либо некоторой константой из ;
2) если вершина v сети помечена функцией от переменных (т.е. ), то ее полустепень захода равна , причем на множестве дуг, заходящих в вершину , задана (взаимно однозначная) нумерация, при которой каждая дуга получает номер от 1 до .
При изображении схем входы обозначаются кружочками, а вершины, не являющиеся входами, - треугольниками, внутри которых записано обозначение функции, помечающей данную вершину. Выходы отмечаются "выходными" стрелками. На рис. 6.25 приведена СФЭ над базисом .
Если базис подразумевается, то мы будем говорить просто "схема". Кроме того, если множество переменных фиксировано "раз и навсегда" и при рассмотрении различных схем мы меняем только множество функций , то, как это мы делали, вводя понятия формулы и суперпозиции над заданным базисом, будем говорить о СФЭ над базисом , полагая каждый раз, что подразумевается однажды фиксированное множество переменных , которое (если это не вредит точности) не упоминается.
Определим теперь по индукции понятие булевой функции, вычисляемой вершиной схемы.
Определение 6.15. Пусть задана СФЭ над базисом , множество вершин которой есть .
1. Принимается, что каждый вход СФЭ вычисляет булеву функцию, которой он помечен (т.е. некоторое переменное или константу).
2. Если вершина помечена функцией заходящая в нее дуга с номером исходит из вершины , которая вычисляет функцию , то вершина v вычисляет суперпозицию .
Таким образом, если каждая вершина СФЭ над вычисляет некоторую функцию, то порядок, в котором перечисляются функции , подставляемые на места переменных функции , в общем случае существен. Естественно назвать булеву функцию от переменных коммутативной, если она сохраняет значение при произвольной перестановке ее переменных. В этом случае мы можем не заботиться о нумерации дуг, заходящих в вершину схемы, помеченную такой функцией.
Пример 6.23. Рассмотрим СФЭ на рис. 6.25. Вершины и - входы СФЭ. Эти вершины вычисляют соответственно функции и . Тогда вершина , равно как и вершина , согласно определению 6.15, вычисляет функцию (штрих Шеффера), а вершина (выход сети) - функцию , которая, как известно, равна конъюнкции .
СФЭ, изображенная на рис. 6.26, имеет два выхода, вычисляющие функции и .
Определение 6.16. Булева функция, вычисляемая СФЭ над базисом , - это функция, вычисляемая каким-либо из ее выходов.
Таким образом, СФЭ вычисляет ровно столько булевых функций, сколько имеет выходов. СФЭ на рис. 6.25 вычисляет одну функцию, а СФЭ на рис. 6.26 - две.
В общем случае, если - множество всех переменных, которые служат метками входов схемы над базисом , имеющей га выходов, СФЭ определяет отображение булева куба в булев куб , т.е. булев оператор.
Замечание 6.10. В некоторых случаях функцию, вычисляемую данной СФЭ, определяют несколько иначе, полагая, что это функция, вычисляемая любой вершиной из подмножества выделенных вершин СФЭ. В частности, это могут быть и выходы. В любом случае договоримся из выделенных (в только что указанном смысле) вершин схемы проводить "выходную" стрелку.
Таким образом, каждая схема из функциональных элементов вычисляет некоторый булев оператор, в частности, если число выходов схемы равно 1, то она вычисляет некоторую булеву функцию.
Можно доказать и обратное: по любому булеву оператору может быть построена СФЭ над базисом , где - полное множество, вычисляющая данный оператор.
Пример 6.24. Зададим таблицей булев оператор, отображающий в (табл. 6.9).
Из таблицы легко увидеть, что (функция есть не что иное, как мажоритарная функция от переменных , и выше написана минимальная ДНФ для нее, см. пример 6.12). Представим функцию в базисе Жегалкина. Используя законы де Моргана, получим
Учитывая, что , будем иметь
(напомним, что сумма по модулю 2 любого четного числа равных слагаемых равна 0). Итак,
СФЭ для булева оператора, заданного в табл. 6.9, над базисом Жегалкина приведена на рис. 6.27.
При проектировании СФЭ полезно иметь в виду числовой параметр, называемый ее сложностью.
Сложность СФЭ - это число ее вершин, не являющихся входами.
Приведенная на рис. 6.27 СФЭ над базисом Жегалкина имеет сложность 5.
Рассмотрим теперь СФЭ для того же оператора над стандартным базисом. По таблице (см. табл. 6.9) строим СДНФ для функции
Карта Карно для этой функции, изображенная на рис. 6.28, показывает, что ее нельзя минимизировать (точнее, записанная выше СДНФ и есть минимальная ДНФ для этой функции).
Но можно пойти по другому пути. Мы можем рассматривать табл. 6.9 как таблицу, определяющую частичную булеву Функцию . Минимизируя эту функцию по карте Карно*, изображенной на рис. 6.29, получаем
*На этой карте мы явно обозначили наборы, на которых функция принимает значение 0, проставив нули в соответствующих клетках. Тем самым мы хотим еще раз зафиксировать внимание на том, что не следует путать нули с прочерками: прочерк в клетке карты, задающей частичную функцию, означает, что на данном наборе значение функции не определено, т.е. не равно ни 0, ни 1.
СФЭ над стандартным базисом для рассматриваемого булева оператора приведена на рис. 6.30. Сложность этой СФЭ составляет 11. Заметим, что вершина, вычисляющая функцию , не является выходом.
Булев оператор, рассмотренный в этом примере, вычисляет двухразрядную сумму (по модулю 2) трех одноразрядных слагаемых. Его можно считать также одноразрядным двоичным сумматором - функциональным блоком многоразрядного двоичного сумматора - для двух слагаемых. Тогда функция г/1 интерпретируется как "сигнал переноса" в старший разряд. На рис. 6.31 изображено "соединение" трех СФЭ (таких, как показано на рис. 6.30), с помощью которого вычисляется сумма двух трехразрядных двоичных чисел. На третий вход сумматора для младшего разряда подается константа 0, а "сигнал переноса" старшего разряда есть старший разряд суммы, которая в общем случае будет четырехразрядным числом.
В современной технике управляющих и вычислительных устройств важное место занимают дискретные преобразователи, т. е. устройства, которые обладают некоторым числом входов и выходов. Наборы сигналов, поступающие на входы и возникающие на выходах, принадлежат известным конечным множествам.
Поделитесь работой в социальных сетях
Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск
аранов Виктор Павлович. Дискретная математика. Раздел 5. ДНФ и схемы из ФЭ.
Лекция 28. Схемы из функциональных элементов. Задачи анализа и синтеза
Лекция 28. СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ.
ЗАДАЧИ АНАЛИЗА И СИНТЕЗА
План лекции:
1. Понятие схемы из функциональных элементов (ФЭ).
2. Задачи анализа и синтеза схем из ФЭ.
- Понятие схемы из ФЭ
В современной технике управляющих и вычислительных устройств важное место занимают дискретные преобразователи , т. е. устройства, которые обладают некоторым числом входов и выходов. Наборы сигналов, поступающие на входы и возникающие на выходах, принадлежат известным конечным множествам. Устройства осуществляют преобразования входных наборов сигналов в выходные. Математической моделью таких устройств являются так называемые схемы из функциональных элементов (СФЭ).
В качестве примера рассмотрим электрическую схему из трех диодов и сопротивления, показанную на рис. 1.
Рис. 1. Электрическая схема и ее условное обозначение
В точках схемы, изображенных кружком, в различные моменты времени возможно появление либо высокого уровня, приблизительно равного 5 В, либо низкого уровня, приблизительно равного нулю. В точке схемы, отмеченной черточкой, поддерживается постоянно низкий уровень напряжения.
Точки, отмеченные, будем интерпретировать как входы, а точку как выход. Работу схемы можно описать следующим образом: если на всех входах низкий уровень напряжения, то на выходе тоже низкий, если хотя бы на одном из входов высокий уровень напряжения, то на выходе высокий. Если обозначить состояние с высоким уровнем напряжения единицей, а с низким нулем, то зависимость выхода от входов можно задать при помощи булевой функции.
На основании этого приведенную схему называют логическим элементом «ИЛИ».
Подобные схемы можно построить из электронных ламп, электромеханических переключателей, пневмоэлементов и др. Зависимость выхода от входов может описываться не только как дизъюнкция, но также при помощи конъюнкции, отрицания и более сложных булевых функций.
Будем рассматривать логические элементы с различной зависимостью выхода от входов. Эти элементы можно соединять друг с другом, подавая выходы некоторых элементов на входы других. В результате получаем СФЭ.
Определение понятия СФЭ можно разбить на два этапа. На первом этапе раскрывается структурная часть этого понятия, на втором функциональная.
I этап. Разобьем этот этап на ряд пунктов.
1 . Имеется конечное множество объектов (), называемых логическими элементами. Каждый элемент имеет входов и один выход. Элемент графически изображается так, как указано на рис. 2.
2 . По индукции определяем понятие логической сети как объекта, в котором имеется некоторое число входов и некоторое число выходов (рис. 3).
а) Базис индукции. Изолированная вершина называется тривиальной логической сетью. По определению, она является одновременно входом и выходом (рис. 4).
… …
…
Рис. 2 Рис. 3 Рис. 4
б) Индуктивный переход. Эта часть основана на использовании трех операций.
I . Операция объединения непересекающихся сетей. Пусть и две непересекающиеся сети (без общих элементов, входов и выходов), имеющие соответственно и входов и и выходов. Теоретико-множественное объединение сетей и есть логическая сеть, которая имеет входов и выходов.
II . Операция присоединения элемента. Пусть сеть и элемент таковы, что и в выбрано различных выходов с номерами. Тогда фигура называется логической сетью, являющейся результатом подключения элемента к сети. Входами являются все входы, выходами все выходы сети, кроме выходов с номерами, а также выход элемента. Сеть имеет входов и выходов (рис. 5).
… …
Рис. 6.
Рис. 5
III . Операция расщепления выхода. Пусть в сети выделен выход с номером. Тогда фигура называется логической сетью, полученной путем расщепления выхода. Входами являются все входы, выходами все выходы сети с номерами 1, …, …, и еще два выхода, возникших из выхода с номером сети (рис. 6). Следовательно, имеет входов и выходов.
3 . Пусть заданы алфавиты и.
Схемой из функциональных элементов называется логическая сеть с входами из алфавита и выходами из алфавита, которая обозначается
. (1)
Приведем примеры схем.
1. Пусть множество состоит из трех элементов И (конъюнктора), ИЛИ (дизъюнктора) и НЕ (инвертора).
Тогда фигура (рис. 6) будет схемой, так как она может быть построена с использованием операций I III .
Рис. 6 Рис. 7
2. Фигура, изображенная на рис. 7, будет также схемой.
II этап. Определение функционирования схемы.
4 . Сопоставим СФЭ (1) систему функций алгебры логики
(2)
называемую также проводимостью данной схемы .
Пример. а) Для схемы имеем систему, состоящую из одного уравнения
Или.
б) Для схемы аналогично получаем
- Реализация булевых функций схемами из ФЭ . Задачи анализа и синтеза
схем из ФЭ
Задача анализа: для данной СФЭ (1) получить систему булевых уравнений (2).
Алгоритм решения задачи: следуя операциям построения сети I III , последовательно вычисляем функции на выходах элементов сети.
Задача синтеза: для данного базиса функциональных элементов и произвольной системы булевых уравнений (2) построить схему (1) из заданных ФЭ, реализующую эту систему уравнений.
Существование решения задачи синтеза определяется теоремой Поста, согласно которой система функций, реализующих базисные ФЭ, должна быть полна. Функции можно представить в виде суперпозиции функций, а каждому шагу суперпозиции соответствует определенное соединение элементов.
Пример. Для функции
(3)
Схема, соответствующая суперпозиции в правой части формулы (3), показана на рис. 8.
Рис. 8
Проблема синтеза заключается в том, что для данной системы булевых уравнений можно построить много схем из ФЭ, которые реализуют эту систему. В связи с этим возникает задача оптимального синтеза: из всевозможных схем, реализующих данную функцию, выбрать наилучшую по тому или иному признаку, например, с наименьшим числом элементов. Такие схемы будем называть минимальными .
Справедливо следующее утверждение.
Теорема. Существует алгоритм, который для каждой системы булевых функций строит минимальную схему.
Данный алгоритм построения минимальных схем относится к классу алгоритмов типа «полного перебора», так как он основан на просмотре всех схем до определенной сложности. Алгоритмы полного перебора, как правило, обладают большой трудоемкостью и непригодны для практических целей. Поэтому рассмотрим далее более простую задачу, для которой исходная система уравнений содержит одно уравнение
и, следовательно, искомая схема имеет один выход.
Сложность минимальной схемы обозначим через. Будем рассматривать задачу синтеза не для отдельной функции, а для всего класса функций от переменных. Качество алгоритмов синтеза сравнивается путем сопоставления так называемых функций Шеннона. Пусть
минимальная сложность схем, реализующих, которые получаются при помощи алгоритма.
Функции, называются функциями Шеннона, причем очевидно, что
Задача синтеза состоит в том, чтобы найти алгоритм, для которого была бы воз можно ближе к, и чтобы трудоемкость алгоритма была бы существенно меньше, чем трудоемкость алгоритма полного перебора. При такой постановке задачи не требуется, чтобы алгоритм для каждой функции находил минимальную схему, необходимо только, чтобы простейшая схема, получаемая при помощи, имела сложность, сильно не превышающую.
Другие похожие работы, которые могут вас заинтересовать.вшм> |
|||
| 9013. | МЕТОДЫ СИНТЕЗА СХЕМ ИЗ ФЭ. СХЕМЫ ДЕШИФРАТОРА И ДВОИЧНОГО СУММАТОРА | 153.07 KB | |
| Общая теория синтеза СФЭ приводит к выводу о том, что большинство булевых функций при больших значениях имеет сложные минимальные схемы. Это означает, что практическую ценность с точки зрения синтеза представляет весьма узкий класс булевых функций. | |||
| 5321. | Виды и значения параметров автоматических защит для различных элементов заданной расчетной схемы | 526.7 KB | |
| Для обеспечения нормальной работы энергетической системы и потребителей электроэнергии необходимо возможно быстрее выявлять и отделять место повреждения от неповрежденной сети, восстанавливая нормальные условия работы энергосистемы и потребителей. | |||
| 5384. | Разработка электрической схемы стенда для анализа работы тактируемого декодера на 4 входа и 16 выходов | 626.63 KB | |
| Для улучшения эксплуатации подвижного состава АТП разработана организационная структура системы обслуживания и ремонта подвижного состава АТП а также предложен комплект оборудования для диагностирования и технического обслуживания. Основной задачей функционирования ремонтного хозяйства предприятия является обеспечение бесперебойной эксплуатации оборудования. В ее состав входят: ремонтновосстановительная база предприятия склады цехи и общезаводские отделы ремонтного хозяйства технологический оборудования диспетчерский. Организация... | |||
| 1886. | Этапы системного анализа, их основные цели, задачи | 27.44 KB | |
| Теория оптимальных систем позволяет оценить тот предел который может быть достигнут в оптимальной системе сравнить ее с показателями действующей не оптимальной системы и выяснить целесообразно ли в рассматриваемом случае заниматься разработкой оптимальной системы. Для автоматически управляемого процесса автоматически управляемой системы различают две стадии оптимизации: статическую и динамическую. Статическая оптимизация решает вопросы создания и реализации оптимальной модели процесса а динамическая... | |||
| 5123. | Разработка функциональных стратегий | 35.44 KB | |
| Стратегия управления персоналом. Функции и структура управления. Функции управления и их роль в формировании структур управления. Иерархический тип структуры управления. | |||
| 20368. | Влияние состава рецептурных компонентов и технологий на потребительские свойства функциональных продуктов | 742.05 KB | |
| Современной медицинской наукой принята концепция оптимального питания. Это означает, что осуществлен переход от концепции адекватного питании, когда в основном регламентировались и нормировались макронутриенты – источники жира, источники энергии, пластического материала (липиды, белки, жиры), к концепции оптимального питания, когда спектр необходимых для жизнедеятельности организма пищевых веществ и других минорных компонентов, на которые раньше не обращали внимании, значительно расширен. | |||
| 4706. | Методы синтеза карбоксилатов Ме | 9.26 MB | |
| Суть метода заключается в растворении оксида, гидроксида или карбоната металла в водном растворе соответствующей кислоты. Продукт выделяют упариванием раствора до начала кристаллизации или фильтрованием осадка, если карбоксилат не растворим или ограниченно растворим в воде. | |||
| 15923. | Основные методы синтеза пиразалодиазепинов | 263.39 KB | |
| Новые методы синтеза производных пиразолодиазепинов. Разработка новых стратегий синтеза представляет значительный интерес. Систематические и обобщающие исследования синтеза производных пиразолодиазепинов не проводились некоторые вопросы остаются незатронутыми спорными или до конца неразрешёнными. | |||
| 11978. | Энерготехнологические установки на основе гидротермального окисления алюминия для производства электроэнергии, тепла, водорода и функциональных наноматериалов | 49.89 KB | |
| В основе разработки лежит реакция гидротермального окисления алюминия в ходе которой выделяется большое количество тепловой энергии и образуются оксиды алюминия и водород: l2H2O→lOOH бемит15H2415. В качестве исходных реагентов используются дистиллированная вода и микронные порошки алюминия. Установка КЭУ10 Установка ЭТК100 Технические характеристики установки ЭТК100: Параметр Значение Расход алюминия кг ч 101 Расход воды на входе в водоподготовительное устройство кг ч 484 Производительность по водороду нм3 110 Тепловая мощность... | |||
| 6605. | Экспертные системы. Проектирование ТП методом синтеза | 11.67 KB | |
| Представление накопление знаний и поддержание их в актуальном состоянии сложная задача исследуемая в разделе информатики которая называется инженерией знаний. Инженер по знаниям участвует в разработке базы знаний ядра систем называемых интеллектуальными. Чаще всего интеллектуальные системы применяются для решения сложных задач где основная сложность решения... | |||
Лекция 2. Схемы из функциональных элементов
(СФЭ) в некотором базисе. Сложность и глубина
схемы. Примеры. Метод синтеза СФЭ по ДНФ.
Лектор - доцент Селезнева Светлана Николаевна
Лекции по “Дискретной математике 2”.
1-й курс, группа 141,
факультет ВМК МГУ имени М.В. Ломоносова
Лекции на сайте http://mk.cs.msu.su
СФЭ Примеры Синтез СФЭ по ДНФ
Схемы из функциональных элементов
Определим схемы из функциональных элементов в некотором базисе.
Пусть нам задано некоторое множество булевых функций B = {g1 (x1,..., xn1),..., gs (x1,..., xns)} P2, где n1,..., ns 0.
Назовем это множество базисом.
Заметим, что это понятие базиса никак не связано с понятием базиса P2, которое рассматривалось в алгебре логики.
Как правило, мы будем рассматривать стандартный базис B0 = {x&y, x y, x }.
СФЭ Примеры Синтез СФЭ по ДНФ Определение схемы из функциональных элементов Схема из функциональных элементов (СФЭ) в базисе B0 = {x&y, x y, x } – это
1) ориентированный ациклический граф G = (V, E), каждая вершина v V которого имеет полустепень захода d (v), не превосходящую двух (d (v) 2);
2) каждая вершина v с полустепенью захода, равной 0 (d (v) = 0), называется входной (или входом схемы) и ей приписывается некоторая булева переменная xi ;
3) все другие вершины (кроме входов) называются внутренними вершинами схемы;
4) каждой вершине v с полустепенью захода, равной 1 (d (v) = 1) приписыается (функциональный) элемент отрицания; все такие вершины называются инверторами;
5) каждой вершине v с полустепенью захода, равной 2 (d (v) = 2) приписыается либо (функциональный) элемент конъюнкции &, либо (функциональный) элемент дизъюнкции; все вершины, которым приписаны элементы конъюнкции, называются конъюнкторами, все вершины, которым приписаны элементы дизъюнкции, называются дизъюнкторами;
СФЭ Примеры Синтез СФЭ по ДНФ Определение схемы из функциональных элементов (продолжение)
6) кроме того, некотрым из вершин приписаны попарно различные выходные переменные y1,..., ym.
Если задана СФЭ S, входам которой приписаны только переменные x1,..., xn, и с выходными переменными y1,..., ym, то будем обозначать эту СФЭ через S(x1,..., xn ; y1,..., ym).
СФЭ Примеры Синтез СФЭ по ДНФ
– – –
Определение глубины вершины СФЭ По индукции определим глубину d(v) вершины v в СФЭ S.
1. Базис индукции. Каждый вход v СФЭ S имеет глубину, равную 0: d(v) = 0.
– – –
СФЭ и их характеристики Схемы из функциональных элементов являются вычислительной моделью.
Введенные нами характеристики СФЭ показывают разные аспекты эффективности вычислений.
Сложность СФЭ соответствует времени последовательного вычисления.
Глубина СФЭ соответствует времени параллельного вычисления.
Максимальное число вершин с одинаковой глубиной в СФЭ соответствует количеству процессоров при параллельном вычислении.
СФЭ Примеры Синтез СФЭ по ДНФ Пример: сумма трех битов Решение. Аналогично примеру 6 запишем таблицу суммы трех битов x, y и z. Эта сумма может быть числом тоже с двумя двоичными разрядами, поэтому введем две булевы переменные
u0, u1, такие, что x + y + z = 2u1 + u0:
– – –
Литература к лекции 4
1. Яблонский С.В. Введение в дискретную математику. М.:
Высшая школа, 2001. Ч. V, гл. 2, с. 336-355.
2. Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, 2004. Гл. X 1.1, 1.5, 1.7, 1.17, 1.18.
СФЭ Примеры Синтез СФЭ по ДНФ