Представлению булевых функций формулами можно придать следующий "инженерно-конструктивный" смысл. Будем рассматривать формулу над каким-то произвольно фиксированным множеством как "черный ящик", некое устройство, на вход которого подаются всевозможные наборы значений переменных, а на выходе появляются соответствующие этим наборам значения функции , представляемой формулой (рис. 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, а "сигнал переноса" старшего разряда есть старший разряд суммы, которая в общем случае будет четырехразрядным числом.

Представлению булевых функций формулами можно придать следующий "инженерно-конструктивный" смысл. Будем рассматривать формулу Ф(x 1 ,..., x n) над каким-то произвольно фиксированным множеством F как "черный ящик", некое устройство, на вход которого подаются всевозможные наборы значений переменных, а на выходе появляются соответствующие этим наборам значения функции f, представляемой формулой Ф (рис. 6.22).

Чтобы понять, как устроен "черный ящик", мы должны разобрать процесс построения формулы из подформул. Добираясь до "базисных" подформул, т.е. элементов множества F, мы приходим к "кирпичикам", структурным элементам, из которых собран "черный ящик", вычисляющий функцию f. Каждая функция "базиса" F вычисляется соответствующим "узлом", который рассматривается как мельчайшая структурная единица нашего "черного ящика", и его внутренняя структура уже не анализируется.

Пример 6.22. Выберем в качестве множества F стандартный базис. Тогда формула над стандартным базисом, представляющая функцию ~ (эквивалентность), строится следующим образом:

Переменное х 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. В некоторых случаях функцию, вычисляемую данной СФЭ, определяют несколько иначе, полагая, что это функция, вычисляемая любой вершиной из подмножества выделенных вершин СФЭ. В частности, это могут быть и выходы. В любом случае договоримся из выделенных (в только что указанном смысле) вершин схемы проводить "выходную" стрелку. #

Можно доказать и обратное: по любому булеву оператору может быть построена СФЭ над базисом 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 , поскольку она не содержит отрицаний.

Размер: px

Начинать показ со страницы:

Транскрипт

1 Лекция 2. Схемы из функциональных элементов (СФЭ) в некотором базисе. Сложность и глубина схемы. Примеры. Метод синтеза СФЭ по ДНФ. Лектор - доцент Селезнева Светлана Николаевна Лекции по Дискретной математике 2. 1-й курс, группа 141, факультет ВМК МГУ имени М.В. Ломоносова Лекции на сайте

2 Схемы из функциональных элементов Определим схемы из функциональных элементов в некотором базисе. Пусть нам задано некоторое множество булевых функций B = {g 1 (x 1,..., x n1),..., g s (x 1,..., x ns)} P 2, где n 1,..., n s 0. Назовем это множество базисом. Заметим, что это понятие базиса никак не связано с понятием базиса P 2, которое рассматривалось в алгебре логики. Как правило, мы будем рассматривать стандартный базис B 0 = {x&y, x y, x}.

3 Определение схемы из функциональных элементов Схема из функциональных элементов (СФЭ) в базисе B 0 = {x&y, x y, x} это 1) ориентированный ациклический граф G = (V, E), каждая вершина v V которого имеет полустепень захода d (v), не превосходящую двух (d (v) 2); 2) каждая вершина v с полустепенью захода, равной 0 (d (v) = 0), называется входной (или входом схемы) и ей приписывается некоторая булева переменная x i ; 3) все другие вершины (кроме входов) называются внутренними вершинами схемы;

4 Определение схемы из функциональных элементов (продолжение) 4) каждой вершине v с полустепенью захода, равной 1 (d (v) = 1) приписыается (функциональный) элемент отрицания; все такие вершины называются инверторами; 5) каждой вершине v с полустепенью захода, равной 2 (d (v) = 2) приписыается либо (функциональный) элемент конъюнкции &, либо (функциональный) элемент дизъюнкции; все вершины, которым приписаны элементы конъюнкции, называются конъюнкторами, все вершины, которым приписаны элементы дизъюнкции, называются дизъюнкторами;

5 Определение схемы из функциональных элементов (продолжение) 6) кроме того, некотрым из вершин приписаны попарно различные выходные переменные y 1,..., y m. Если задана СФЭ S, входам которой приписаны только переменные x 1,..., x n, и с выходными переменными y 1,..., y m, то будем обозначать эту СФЭ через S(x 1,..., x n ; y 1,..., y m).

6 Пример СФЭ Пример 1. СФЭ S(x 1, x 2, x 3 ; y 1, y 2, y 3):

7 Пример СФЭ Пример 1. Как правило СФЭ изображаются следующим образом S(x 1, x 2, x 3 ; y 1, y 2, y 3):

8 Определение сложности СФЭ Сложностью L(S) СФЭ S называется число внутренних вершин этой СФЭ, т.е. число функциональных элементов в СФЭ S.

9 Сложность СФЭ Пример 2. Сложность СФЭ S:

10 Определение глубины вершины СФЭ По индукции определим глубину d(v) вершины v в СФЭ S. 1. Базис индукции. Каждый вход v СФЭ S имеет глубину, равную 0: d(v) = Индуктивный переход. 1) Если в инвертор v СФЭ S ведет дуга из вершины v 1, то d(v) = d(v 1)) Если в конъюнктор или дизъюнктор v СФЭ S ведут дуги из вершин v 1 и v 2, то d(v) = max(d(v 1), d(v 2)) + 1. Глубиной D(S) СФЭ S называется максимальная из глубин ее вершин.

11 Глубина СФЭ Пример 3. Глубина вершин СФЭ S и глубина СФЭ S:

12 Определение функционирования СФЭ В каждой вершине СФЭ реализуется (или вычисляется) некоторая булева функция. По индукции определим булеву функцию, которая реализуется в вершине v СФЭ S. 1) Если v входная вершина, и ей приписана переменная x i, то в вершине v реализуется функция f v = x i. 2) Если в инвертор v ведет дуга из вершины v 1, и в вершине v 1 реализуется функция f v1, то в вершине v реализуется функция f v = f v1. 3) Если в конъюнктор (или дизъюнктор) v ведут дуги из вершин v 1 и v 2, и в вершинах v 1 и v 2 реализуются функции f v1 и f v2 соответственно, то в вершине v реализуется функция f v = f v1 &f v2 (соответственно f v = f v1 f v2).

13 Функционирование СФЭ Считается, что СФЭ S(x 1,..., x n ; y 1,..., y m) реализует систему булевых функций F S = {f 1,..., f m }, реализующихся в ее выходных вершинах y 1,..., y m.

14 Функционирование СФЭ Пример 4. Булевы функции, реализующиеся в вершинах СФЭ S: F S = {x 3, x 1 x 2, x 1 x 2 x 3 }.

15 Линейная программа Линейной программой с входами x 1,..., x n над базисом B 0 = {x&y, x y, x} называется последовательность z 1, z 2,..., z t, в которой для каждого номера j, j = 1,..., t, выполняется, что 1) либо z j = x i ; 2) либо z j = z k при k < j; 3) либо z j = z k &z l при k, l < j; 4) либо z j = z k z l при k, l < j. Линейная программа последовательно вычисляет значения z 1,..., z t как функции булевых переменных x 1,..., x n.

16 СФЭ и линейные программы Понятно, что вычисление в СФЭ можно переписать в виде линейной программы. И наоборот, каждую линейную программу можно представить в виде некоторой СФЭ.

17 СФЭ и линейные программы Пример 5. СФЭ S соответствует линейная программа z 1 = x 1 &x 2, z 2 = x 3, z 3 = z 1 z 2.

18 СФЭ и их характеристики Схемы из функциональных элементов являются вычислительной моделью. Введенные нами характеристики СФЭ показывают разные аспекты эффективности вычислений. Сложность СФЭ соответствует времени последовательного вычисления. Глубина СФЭ соответствует времени параллельного вычисления. Максимальное число вершин с одинаковой глубиной в СФЭ соответствует количеству процессоров при параллельном вычислении.

19 Пример: сумма двух битов Пример 6. Построить СФЭ в стандартном базисе, реализующую (вычисляющую) сумму двух битов x и y. Решение. Запишем таблицу суммы двух битов x и y. Эта сумма может быть числом с двумя двоичными разрядами, поэтому введем две булевы переменные z 0, z 1, такие, что x + y = 2z 1 + z 0: x y z 1 z

20 Пример: сумма двух битов Решение (продолжение). Тогда z 0 = x y, z 1 = xy. Учитывая, что x y = (x y) (x y), получаем CФЭ: Понятно, что L(S 1) = 3, и D(S 1) = 3.

21 СФЭ в произвольном базисе Аналогично вводится понятие СФЭ в произвольном базисе B P 2.

22 Пример: сумма трех битов Пример 7. Построить СФЭ в базисе P2 2 (т.е. из всех булевых функций, зависящих от двух переменных), реализующую (вычисляющую) сумму трех битов x, y и z.

23 Пример: сумма трех битов Решение. Аналогично примеру 6 запишем таблицу суммы трех битов x, y и z. Эта сумма может быть числом тоже с двумя двоичными разрядами, поэтому введем две булевы переменные u 0, u 1, такие, что x + y + z = 2u 1 + u 0: x y z u 1 u

24 Пример: сумма трех битов Решение (продолжение). Тогда u 0 = x y z, u 1 = xy xz yz. Учитывая, что xy xz yz = xy z(x y), получаем CФЭ: Видим, что L(S) = 5, и D(S) = 3.

25 Реализация булевой функции СФЭ А можно ли произвольную булеву функцию (или систему булевых функций) реализовать СФЭ в базисе B 0 = {x&y, x y, x}? Можно. Как это можно обосновать? Например, так. Т.к. {x&y, x y, x} полная в P 2 система, произвольную булеву функцию f можно представить формулой только через конъюнкцию, дизъюнкцию и отрицание. Например, в виде совершенной ДНФ, если f 0, и в виде x& x, если f = 0. А затем по этой ДНФ (формуле) построить соответствующую СФЭ. Такой метод построения СФЭ для булевых функций называется методом синтеза по ДНФ.

26 Синтез СФЭ по ДНФ А какой сложности получится СФЭ S по ДНФ для булевой функции f (x 1,..., x n), зависящей от n переменных? Совершенная ДНФ для функции f будет содержать не более 2 n элементарных конъюнкций. Каждая элементарная конъюнкция это конъюнкция n переменных или их отрицаний.

27 Синтез СФЭ по ДНФ Поэтому в схеме будут: n инверторов для реализации всех отрицаний переменных x 1,..., x n ; по (n 1) конъюнктору для реализации каждой из не более 2 n элементарных конъюнкций в совершенной ДНФ; не более (2 n 1) дизъюнктора для реализации дизъюнкции элементарных конъюнкций ДНФ. Получаем, что L(S) n + (n 1) 2 n + (2 n 1) n 2 n + n.

28 Сложность булевой функции Сложностью L(f) булевой функции f (x 1,..., x n) в классе СФЭ называется минимальная сложность среди всех СФЭ, реализующих функцию f. Таким образом, доказали теорему: Теорема 1. Для произвольной функции f (x 1,..., x n) P 2 верно L(f) n 2 n + n.

29 Задачи для самостоятельного решения 1. Для булевой функции f (x 1, x 2, x 3) = () построить СФЭ в стандартном базисе сложности Для булевой функции f (x 1, x 2, x 3) = () построить СФЭ в стандартном базисе сложности Для булевой функции f (x 1, x 2, x 3, x 4) = x 1 x 2 x 3 x 4 построить СФЭ в стандартном базисе глубины Доказать, что в стандартном базисе L(x y) = 4.

30 Литература к лекции 4 1. Яблонский С.В. Введение в дискретную математику. М.: Высшая школа, Ч. V, гл. 2, с Гаврилов Г.П., Сапоженко А.А. Задачи и упражнения по дискретной математике. М.: Физматлит, Гл. X 1.1, 1.5, 1.7, 1.17, 1.18.

31 Конец лекции 4

Лекция: Схемы из функциональных элементов с задержками (СФЭЗ), автоматность осуществляемых ими отображений. Представление КАВ СФЭЗ. Упрощения КАВ. Отличимость и неотличимость состояний КАВ. Теорема Мура

Лекция: Теорема Анселя о разбиениии n-мерного куба на цепи. Теорема о числе монотонных функций алгебры логики. Теорема о расшифровке монотонных функций алгебры логики. Лектор - доцент Селезнева Светлана

Лекция: Конечные автоматы с выходом (КАВ). Автоматные функции, способы их задания. Теорема о преобразовании периодических последовательностей автоматными функциями. Лектор - доцент Селезнева Светлана Николаевна

Лекция: Частично упорядоченные множества (ЧУМ). Диаграмма ЧУМ. Максимальные, минимальные, наибольший и наименьший элементы. Цепи и антицепи, длина и ширина конечных ЧУМ. Теорема о разбиении ЧУМ на антицепи.

Лекция 2. Свойства биномиальных коэффициентов. Подсчет сумм и метод производящих функций (конечный случай). Полиномиальные коэффициенты. Оценки биномиальных и полиномиальных коэффициентов. Оценки сумм

Лекция: Алгоритм распознавания полноты в P k. Замкнутые классы. Классы функций, сохраняющих множества и сохраняющих разбиения, их замкнутость. Теорема Кузнецова о функциональной полноте. Предполные классы.

Лекция 2. Комбинаторика. Свойства биномиальных коэффициентов. Подсчет сумм и метод производящих функций. Полиномиальные коэффициенты. Оценки биномиальных и полиномиальных коэффициентов. Асимптотические

Лекция: Конечнозначные функции. Элементарные k-значные функции. Способы задания k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.

Лекция 3. Последовательности, определяемые рекуррентными соотношениями. Однородные и неоднородные линейные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Лектор - доцент Селезнева Светлана

Лекция 15. Функции конечно-значных логик. Элементарные функции k-значной логики. Способы задания функций k-значной логики: таблицы, формулы, I-я и II-я формы, полиномы. Полнота. Лектор - доцент Селезнева

Лекция: Функции конечнозначных логик. Элементарные функции k-значной логики. Способы задания функций k-значной логики: таблицы, формулы, I-я и II-я формы, полиномы. Полнота. Лектор - доцент Селезнева Светлана

Лекция: Функция Мёбиуса на ЧУМ. Функция Мёбиуса на n-мерном кубе. Формула обращения Мёбиуса. Принцип включений-исключений. Задача о подсчете числа перестановок- беспорядков. Лектор - доцент Селезнева Светлана

Лекция 2. Свойства биномиальных коэффициентов. Метод производящих функций, подсчет сумм и доказательство тождеств. Полиномиальные коэффициенты. Принцип включений-исключений. Лектор - доцент Селезнева Светлана

Лекция: Существенные функции. Три леммы о существенных функциях. Критерий полноты Яблонского. Критерий полноты Слупецкого. Шефферовы функции. Лектор доцент Селезнева Светлана Николаевна [email protected]

Лекция: Основные комбинаторные числа. Оценки и асимптотики для комбинаторных чисел. Лектор - доцент Селезнева Светлана Николаевна факультет ВМК МГУ имени М.В. Ломоносова Лекции на сайте http://mk.cs.msu.su

Лекция: Свойства биномиальных коэффициентов. Подсчет сумм и метод производящих функций (конечный случай). Полиномиальные коэффициенты. Оценки биномиальных и полиномиальных коэффициентов. Оценки сумм биномиальных

Лекция: Конечные автоматы с выходом. Преобразование периодических последовательностей конечными автоматами с выходом. Отличимость состояний в конечных автоматах с выходом. Упрощение автоматов. Лектор Селезнева

Лекция: Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Оценки мощности затеняющего множества n-мерного куба. Оценки длины полиномиальных нормальных форм функций

Лекция 5. Покрытие множества и покрытие матрицы. Градиентное покрытие. Лемма о градиентном покрытии. Оценки мощности затеняющего множества булева куба. Оценки длины полиномиальных нормальных форм булевых

Лекция 3. Последовательности, определяемые рекуррентными соотношениями. Однородные и неоднородные линейные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры Лектор - доцент Селезнева

Лекция 3. Отношения на множествах. Свойства. Формула включений-исключений. Отношение эквивалентности. Отношение частичного порядка. Лектор - доцент Селезнева Светлана Николаевна Лекции по Дискретным моделям.

Лекция 4. Особенности многозначных логик. Замкнутый класс, базис замкнутого класса. Теоремы Янова и Мучника о существовании в многозначных логиках замкнутых классов без базиса и замкнутых классов со счетным

Лекция. Функции натурального аргумента (последовательности). Однородные и неоднородные линейные рекуррентные уравнения (ЛОРУ и ЛНРУ). Общие решения ЛОРУ и ЛНРУ. Примеры Лектор - доцент Селезнева Светлана

Лекция: Хроматическое число графа. Критерий двухцветности графа. Теоремы о верхних и нижних оценках хроматического числа графа. Лектор - доцент Селезнева Светлана Николаевна Лекции по Дискретным моделям.

Лекция: Графы и сети. Оценка числа псевдографов с q ребрами. Оценка числа деревьев с q ребрами. Планарные графы. Формула Эйлера для планарных графов. Наибольшее число ребер в планарных графах. Непланарность

Лекция 1. Комбинаторика. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями. Их число. Лектор - доцент Селезнева Светлана Николаевна Кафедра математической кибернернетики

Лекция: Последовательности. Однородные и неоднородные линейные рекуррентные уравнения. Общие решения линейных рекуррентных однородных и неоднородных уравнений. Лектор - доцент Селезнева Светлана Николаевна

Лекция 8. Раскраски. Эквивалентность раскрасок относительно группы. Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема Пойа. Лектор Селезнева Светлана Николаевна

Лекция: Раскраски. Эквивалентность раскрасок относительно группы перестановок. Теорема Пойа (частный случай). Производящие функции. Перечисляющий ряд для фигур и перечисляющий ряд для функций. Теорема

Лекция 2. Конъюнктивные нормальные формы. Имплицента, простая имплицента функции. Сокращенная КНФ функции алгебры логики. Способы построения сокращенной КНФ. Лектор Селезнева Светлана Николаевна [email protected]

Математические модели и методы логического синтеза СБИС Осень 2015 Лекция 4 План лекции Логическая оптимизация комбинационных логических схем Различные способы представления функций алгебры логики (ФАЛ)

Лекция: Недетерминированные конечные автоматы (НКА) без выхода. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и конечными недетерминированными автоматами. Процедура

Лекция 1. Выборки. Размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Примеры. Лектор - доцент Селезнева Светлана Николаевна Лекции по курсу Дискретная

Лекция 1. Комбинаторные объекты: выборки, размещения, перестановки, размещения с повторениями, сочетания, сочетания с повторениями, их число. Комбинаторные числа: факториал, убывающий факториал, биномиальные

ЛЕКЦИЯ 4 СХЕМЫ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 1. Основные определения Прежде всего необходимо рассмотреть композицию. Функцию можно представить в виде «черного ящика», у которого есть вход и выход. Пусть

Лекция 2. Алгоритм распознавания полноты в P k. Теорема Кузнецова. Замкнутые классы. Классы функций, сохраняющих множество. Классы функций, сохраняющих разбиение. Предполные классы. Лектор д.ф.-м.н. Селезнева

Лекция 3. Полином Жегалкина. Способы построения полинома Жегалкина функции. Линейная имплицента функции. Линейная конъюнктивная нормальная форма (ЛКНФ). Нахождение всех линейных имплицент функции. Проверка

Лекция 2. Производящие функции: подсчет комбинаторных сумм и доказательство тождеств, перечисление комбинаторных объектов. Принцип включений-исключений. Подсчет числа перестановок-беспорядков. Лектор -

Лекция 5. Графы. Раскраски графов. Хроматическое число графа. Критерий двуцветности графа. Верхние оценки хроматического числа графа. Лектор д.ф.-м.н. Селезнева Светлана Николаевна [email protected] Лекции

Лекция: Конечные автоматы (КА) без выхода (конечные автоматы-распознаватели). Диаграммы переходов. Автоматные множества (языки). Лемма о свойствах автоматных множеств. Пример неавтоматного множества. Лектор

Лекция 1. Конечнозначные функции. Элементарные k-значные функции. Способы задания k-значных функций: таблицы, формулы, 1-я и 2-я формы, полиномы. Полнота. Теорема о полноте системы Поста. Функция Вебба.

Лекция 7. Задача выбора маршрутов и ее частный случай задача распределения рейсов по дням. Графовая модель для задачи распределения рейсов. Хроматическое число графа. Критерий двураскрашиваемости графа.

Курс «Основы кибернетики» для студентов специализации 01.02.09.01 (математическое и программное обеспечение вычислительных машин) 1. Общая информация (учебная нагрузка, формы контроля и др.). Курс является

Лекция 6. Графы. Наследственные свойства графов. Оценка числа ребер в графах с наследственным свойством. Экстремальные графы. Наибольшее число ребер в планарных графах и графах без треугольников с заданным

Math-Net.Ru Общероссийский математический портал Д. С. Романов, Метод синтеза легкотестируемых схем, допускающих единичные проверяющие тесты константной длины, Дискрет. матем., 2014, том 26, выпуск 2,

Лекция: Конечные автоматы без выхода, детерминированные и недетерминированные. Теорема о совпадении классов множеств слов, допускаемых конечными детерминированными и недетерминированными автоматами. Процедура

Практическая работа 2 Построение нормальных форм логической функции Цель работы: Научиться строить конъюктивные, дизъюнктивные, совершенные нормальные формы логической функции Содержание работы: Основные

Семинар по сложности булевых функций Лекция 1: Введение А. Куликов Computer Science клуб при ПОМИ http://compsciclub.ru 25.09.2011 25.09.2011 1 / 26 План лекции 1 Булевы функции 2 Булевы схемы 3 Почти

Практическая работа 1 Анализ и синтез логических и релейных систем управления ВВЕДЕНИЕ Устройства дискретного действия, выполненные на элементах гидро-, пневмо- и электроавтоматики, и управляющие микропроцессоры

Лекция: Регулярные выражения и регулярные множества. Теорема Клини о совпадении классов автоматных множеств и регулярных множеств. Лектор - доцент Селезнева Светлана Николаевна Лекции по Дискретной математике

Лекция 3 Булевы алгебры и булевы функции Булевы алгебры Понятие об алгебраических системах Алгебраическая система или алгебраическая структура множество символов некоторого алфавита (носитель) с заданным

Лекция 5. Графы. Примеры применений графов. Транспортная задача. Поток в сети, теорема Форда и Фалкерсона о величине максимального потока в сети. Алгоритм построения максимального потока в сети. Лектор

Лекция: Графы. Примеры применений графов. Транспортная задача. Поток в сети, теорема Форда и Фалкерсона о величине максимального потока в сети. Алгоритм построения максимального потока в сети. Лектор -

Занятие 8 Напомним, что для произвольных множеств A и B существуют множества A B = {x x A и x B}; (пересечение A и B) A B = {x x A или x B}; (объединение A и B) A \ B = {x x A и x / B} (разность A и B).

Лекция 7. Числа Рамсея. Верхняя оценка числа Рамсея. Нижняя оценка числа Рамсея. Лектор Селезнева Светлана Николаевна [email protected] факультет ВМК МГУ имени М.В. Ломоносова Лекции на сайте http://mk.cs.msu.ru

Лекция: Графы. Основные понятия. Связные графы. Деревья. Остовное дерево. Число висячих вершин в остовном дереве. Лектор - доцент Селезнева Светлана Николаевна Лекции по Дискретным моделям. Магистратура,

Лекция 11. Булевы схемы. Дискретная математика, ВШЭ, факультет компьютерных наук (Осень 2014 весна 2015) Булевой схемой от переменных x 1,..., x n мы будем называть последовательность булевых функций g

УТВЕРЖДАЮ Проректор по учебной работе Ю. А. Самарский 10 июня 2008 г. ПРОГРАММА И ЗАДАНИЯ по курсу ДИСКРЕТНЫЕ СТРУКТУРЫ по направлению 010600 факультет ФИВТ кафедра анализа данных курс II семестр 4 Два

Московский государственный университет имени М. В. Ломоносова Факультет вычислительной математики и кибернетики С. А. Ложкин ЭЛЕМЕНТЫ ТЕОРИИ СИНТЕЗА ДИСКРЕТНЫХ УПРАВЛЯЮЩИХ СИСТЕМ Москва 2016 Оглавление

Лекция: Наследственные свойства графов. Экстремальные графы. Числа Рамсея. Лектор - доцент Селезнева Светлана Николаевна факультет ВМК МГУ имени М.В. Ломоносова Лекции на сайте http://mk.cs.msu.su Наследственное

Лекция: Операции над конечно-автоматными множествами. Дополнение, объединение, пересечение, произведение и итерация автоматных множеств, их автоматность. Лектор - доцент Селезнева Светлана Николаевна Лекции

Министерство Российской Федерации по связи и информатизации Поволжская государственная академия телекоммуникаций и информатики Кафедра высшей математики Одобрено Методическим советом ПГАТИ 29 марта 2002

Лекция 5. Раскраски ребер графов. Хроматический индекс графа. Хроматический индекс двудольных графов. Верхняя и нижняя оценки хроматического индекса графа. Лектор Селезнева Светлана Николаевна [email protected]

Math-Net.Ru Общероссийский математический портал Н. П. Редькин, О схемах, допускающих короткие единичные диагностические тесты, Дискрет. матем., 1989, том 1, выпуск 3, 71 76 Использование Общероссийского

МАТЕМАТИЧЕСКАЯ ЛОГИКА(1) Задания к практическим занятиям 1. Алгебра высказываний Высказывание - величина, которая может принимать два значения: истина и ложь. Высказывания обозначают большими латинскими

Поделитесь работой в социальных сетях

Если эта работа Вам не подошла внизу страницы есть список похожих работ. Так же Вы можете воспользоваться кнопкой поиск

аранов Виктор Павлович. Дискретная математика. Раздел 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
	Представление накопление знаний и поддержание их в актуальном состоянии сложная задача исследуемая в разделе информатики которая называется инженерией знаний. Инженер по знаниям участвует в разработке базы знаний ядра систем называемых интеллектуальными. Чаще всего интеллектуальные системы применяются для решения сложных задач где основная сложность решения...

5. Обходы графов: эйлеровы цепи и циклы, необходимые и достаточные условия их существования, алгоритм Флери.

6. Обходы графов: гамильтоновы цепи и циклы, достаточные условия их существования.

7. Деревья, их свойства, кодирование деревьев, остовные деревья.

8. Экстремальные задачи теории графов: минимальное остовное дерево, алгоритмы Прима и Краскала.

9. Экстремальные задачи теории графов: задача коммивояжера, «жадный» алгоритм

10. Экстремальные задачи теории графов: задача о кратчайшем пути, алгоритм Дейкстры.

11. Изоморфизм и гомеоморфизм графов, методы доказательства изоморфности и неизоморфности графов.

12. Плоские укладки графов, планарные графы, критерий Понтрягина-Куратовского.

13. Необходимые условия планарности, формула Эйлера для планарных графов.

14. Правильные вершинные раскраски графов, хроматическое число, неравенства для хроматического числа.

15. Теорема о пяти красках, гипотеза четырех красок, «жадный» алгоритм.

16. Хроматический многочлен, его нахождение и свойства.

17. Задача о поиске выхода из лабиринта, реберная раскраска графа.

19. Составление расписания выполнения комплекса работ в кратчайшие сроки методами теории графов.

20. Элементарные булевы функции и способы их задания (табличный, векторный, формульный, графический, карта Карно).

21. Существенные и фиктивные переменные булевых функций, основные тождества, эквивалентные преобразования формул.

22. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом неопределенных коэффициентов.

23. Линейные и нелинейные полиномы Жегалкина, разложение булевых функций в полином Жегалкина методом эквивалентных преобразований.

24. Разложение булевых функций в сднф и скнф.

25. Минимизация днф и кнф методом эквивалентных преобразований.

26. Минимизация днф и кнф с помощью карт Карно.

27. Замкнутые классы булевых функций т0, т1, l, лемма о нелинейной функции.

28. Замкнутые классы булевых функций s и м, леммы о несамодвойственной и немонотонной функции.

29. Полная система функций, теорема о двух системах булевых функций.

30. Теорема Поста о полноте системы булевых функций, алгоритм проверки системы на полноту, базис.

31. Схемы из функциональных элементов, правила построения и функционирования, метод синтеза сфэ, основанный на сднф и скнф.

32. Метод синтеза сфэ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника, сложность получаемых схем.

33. Основные комбинаторные операции, сочетания и размещения (с возвращением и без возвращения элементов).

34. Комбинаторные принципы сложения, умножения, дополнения, включения-исключения.

35. Биномиальные коэффициенты, их свойства, бином Ньютона.

36. Треугольник Паскаля, полиномиальная формула.

37. Алфавитное кодирование: необходимое и достаточные условия однозначности декодирования.

38. Алфавитное кодирование: теорема Маркова, алгоритм Маркова.

39. Коды с минимальной избыточностью (коды Хаффмана), метод построения.

40. Линейные коды, порождающая матрица, двойственный код.

41. Самокорректирующиеся коды (коды Хэмминга), метод построения.

42. Определение, схема и функционирование абстрактного автомата, способы задания автоматов.

43. Типы конечных автоматов, автоматы Мили и Мура, автоматы-генераторы.

44. Слова и языки, операции над ними, их свойства.

45. Регулярные выражения и регулярные языки, теорема Клини.

46. Задача анализа автоматов-распознавателей.

47. Задача синтеза автоматов-распознавателей.

48. Эквивалентные состояния автомата-распознавателя, эквивалентные автоматы-распознаватели, минимизация автоматов-распознавателей, алгоритм Мили.

49. Эквивалентные состояния автомата-преобразователя, эквивалентные автоматы- преобразователи, минимизация автоматов- преобразователей, алгоритм Мили.

50. Детерминированные и недетерминированные функции, примеры, способы задания.

51. Ограниченно-детерминированные (автоматные) функции, способы их задания.

52. Логические автоматы, способы их задания, синтез двоичного сумматора.

53. Операции над логическими автоматами: суперпозиция и введение обратной связи.

31. Схемы из функциональных элементов, правила построения и функционирования, метод синтеза сфэ, основанный на сднф и скнф.

Определение

Определение. Функциональный элемент – это математическая модель элементарного дискретного преобразователя, который по определенному закону осуществляет преобразование поступающих ему на вход сигналов в сигнал на выходе преобразователя. Из функциональных элементов с помощью некоторых правил можно строить более сложные по структуре и функционированию модели – схемы из функциональных элементов. В этих моделях входные и выходные сигналы кодируются символами 0 и 1.

Правила построения. Для получения сложных СФЭ из более простых к ним последовательно применяются операции расщепления входа или выхода схемы, присоединения функционального элемента к схеме и подключения функционального элемента ко входу или выходу схемы. Эти операции напоминают правила получения сложной формулы из более простых с помощью суперпозиции.

Синтез СФЭ. Поскольку дизъюнкция, конъюнкция и отрицание образуют полную систему в классе Р 2 , то любую булеву функцию от n аргументов можно реализовать схемой из функциональных элементов – дизъюнкторов, конъюнкторов и инверторов – с n входами и одним выходом. Для этого можно, например, выразить данную булеву функцию через СДНФ или СКНФ и затем «синтезировать» полученную формулу в виде схемы из функциональных элементов, последовательно применяя перечисленные выше операции расщепления, присоединения и подключения.

32. Метод синтеза сфэ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника, сложность получаемых схем.

Определение . Функцияотnаргументовназывается булевой функцией (или функцией алгебры логики), если каждому наборуона ставит в соответствие число.

Для задания булевых функциймы будем использовать таблицы, векторы, формулы и графики. Примем следующее обозначение:– это множество всех наборов, где.

Метод синтеза СФЭ, основанный на компактной реализации всех конъюнкций с помощью универсального многополюсника. Данный метод также основывается на представлении функции в виде СДНФ, но позволяет строить менее сложные схемы за счет более компактной реализации конъюнкций. Разложение функции в СДНФ может содержать конъюнкции, имеющие общие множители. Если две таких конъюнкции реализовать одной подсхемой в блоке, то для этого потребуется конъюнкторов хотя бы на единицу меньше, чем их требовалось прежде, при независимой реализации всех конъюнкций первым методом синтеза. Компактной реализации всех возможных конъюнкций длиныn можно добиться с помощью индуктивно построенного универсального многополюсника, имеющегоn входов и 2 n выходов, гдеn = 1,2,3,… Преимущества метода особенно заметны, когда одной схемой требуется реализовать систему из нескольких булевых функций. В этом случае можно было бы расщепить и далее пропустить через дизъюнкторы те выходы универсального многополюсника, которые соответствуют конъюнкциям, входящим в СДНФ функций заданной системы. Это позволило бы обойтись меньшим количеством конъюнкторов, чем если бы каждую функцию заданной системы независимо реализовали своей собственной подсхемой.

Сложность такого многополюсника равна L () =.

Если схема из функциональных элементов Σ содержит ровно r функциональных элементов, то говорят, что она имеет сложность r и записывают это в виде равенства L (Σ) = r .