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

Лекция 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.

СФЭ Примеры Синтез СФЭ по ДНФ

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 .

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