Поперечные профили набережных и береговой полосы: На городских территориях берегоукрепление проектируют с учетом технических и экономических требований, но особое значение придают эстетическим...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
Топ:
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Подходы к решению темы фильма: Существует три основных типа исторического фильма, имеющих между собой много общего...
Дисциплины:
2017-12-12 | 935 |
5.00
из
|
Заказать работу |
|
|
Рассмотрим алгоритм построения КС с помощью скобочных преобразований.
1. Преобразуем исходную ДНФ многократно вынося за скобки переменные.
Пример.
2. Выделяем одинаковые подфункции в скобочной форме F и получаем совокупность функций для F.
Пример.
F = XY(Ф Ú W) Ú WФ
Ф = Z Ú PQ
3. Выделяем конъюнкции или их части общие для нескольких мест (одинаковые) и расширяем совокупность функций.
Пример.
F = XY(F Ú W) Ú WF Ú MN K
F = Z Ú MN P
F = XY(F Ú W) Ú WF Ú YK
F = Z Ú YP
Y = MN
При поиске и выделении общих частей конъюнкций учитывается, что выделение k букв из L конъюнкций дает выигрыш W = k(L - 1).
Выделяя общие части с максимумом W при W > 0, мы обеспечиваем упрощение схемы.
Далее по совокупности БФ строится КС, например, моделированием полученных выражений.
Действия по п.2 и 3 ясны. Действия по п.1 рассмотрим подробнее, полагая, что исходное выражение для F - ДНФ.
Исходную ДНФ, рассматриваемой БФ F, обозначим как D 0.
Делая вынесение за скобки переменных, получим
D 0 = K 0 &(D 01) Ú D 02
КонъюнкцияДНФ
Поиск выносимых за скобки переменных (конъюнкции) рассмотрим далее.
«Убираем» на время из рассмотрения внутри - скобочное выражение для D 01 и получаем ДНФ D 1 .
D 1 = K 0 &(F 01) Ú D 02 .
Переменная, заменяющая ДНФ D 01.
D 1 обрабатываем как исходную ДНФ D 0, если возможно вынесение за скобки K 1 и представление ее в виде
D 1 = K 1 &(D 11) Ú D 12 .
Затем аналогично получаем D 2 , D 3 и т.д.
Если в D j уже нельзя выделить К j, то берем
D j = K j-1 &(F j-11) Ú D j-12
и подставляем туда последовательно (D j-11) вместо F j-11, (D j-21) вместо F j-21 и т.д. до (D 01) вместо F 01.
|
При этом мы получаем выражение, в котором в скобки заключены ДНФ D 01, D 11, …D j-11.
Каждую из этих ДНФ будем обрабатывать как исходную, продолжая до тех пор, пока это возможно.
В результате получим искомую форму.
Рассмотрим пример.
К 0 D 01 D 02
К 1 D 11 D 12
Дальнейшее вынесение за скобки невозможно.
Подставляя всюду D q1 вместо F q1, получаем
Преобразуя каждую ДНФ из скобок, получим
Полученные здесь в скобках ДНФ уже не допускают дальнейших скобочных преобразований.
Заменив преобразованные ДНФ на скобочные выражения, получим
На этом скобочные преобразования завершены.
Выделив одинаковые подфункции, мы получим
В результате, получаем схему.
Замечание о многовыходных схемах.
Для системы БФ, каждая функция приводится к скобочной форме отдельно. Затем во всех функциях находятся одинаковые части формул и конъюнкций и формируется общая совокупность функций.
Следует отметить, что при большом числе «похожих» конъюнкций в разных БФ, лучшие результаты может дать другой подход.
1) В совокупности всех БФ выделяются общие части и заменяются новыми переменными;
2) БФ (с новыми переменными, если они введены) раздельно обрабатываются описанным ранее способом;
3) Введенные в 1) переменные реализуются схемами.
При синтезе многовыходных схем удобно строить схемы, используя поочередно оба подхода, и выбирать лучшую.
Выясним теперь, как в днф D j найти конъюнкцию K j, чтобы, вынеся ее за скобки, получить D j = K j &(D j 1) Ú D j2
Обозначим (K i) J совокупность первых j букв в K i.
Весом W(K i) J для (K i) J назовем
W[(K i) J ] = j . (L k- 1),
где L k - число конъюнкций в D i, содержащих (K i) J.
K i строим, последовательно находя (K i) 1, (K i) 2, …так, чтобы вес W для (K i) J всякий раз был наибольшим и больше нуля.
Переходя к (K i) J нужно подобрать к (K i) J-1 такую переменную, чтобы вес (K i) J был наибольшим.
Отбор переменных к (K i) идет до тех пор, пока вес (K i) J не начнет убывать.
|
Рассмотрим пример.
D i = X1X2X3ÚX1X2X4ÚX1X5ÚX2X5
X1 | W=2 - max | (Ki)1 = x1 | |
X2 | W=2 | ||
(Ki)1 = | X3 | W=0 | |
X4 | W=0 | ||
X5 | W=1 | ||
X1X2 | W=2 - max | (Ki)2 = X1X2 | |
(Ki)2 = | X1X3 | W=0 | |
X1X4 | W=0 | ||
X1X5 | W=0 | ||
X1X2X3 | W=0 | ||
(Ki)3 = | X1X2X4 | W=0 | |
X1X2X5 | W=0 |
В итоге получаем
D i = X1X2(X3ÚX4)ÚX1X5ÚX2X5
К i D i1 D i2
Схема, построенная по этому выражению, будет содержать 4 двухвходовых конъюнктора.
Схема для исходной ДНФ содержит 6 двухвходовых конъюнкторов.
Вес W для K i равен числу конъюнкторов, которые могут быть удалены из КС для ДНФ D i после перехода к КС для D i в виде
D i = K i &(D i1) Ú D i2
СИНТЕЗ КС ИЗ ЭЛЕМЕНТОВ
И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.
КС часто используемых БФ.
Наиболее часто используемыми БФ являются конъюнкция, дизъюнкция, сумма «по модулю 2» и инверсия.
F = X1&X2& … &Xn
F = X1ÚX2Ú… ÚXn
F = X1 X2 … Xn
F = X1oX2o…oXn
где o - либо &, либо Ú, либо .
Существует набор стандартных решений для построения БФ.
Для этого используются следующие правила:
Для &, и имеется свойство ассоциативности:
возможность произвольной расстановки скобок в формуле
F = X1oX2o…oXn
Например:
F = X1oX2o…oXn = X1o(X2(o…oXn))= (X1oX2)o(…oXn)
В зависимости от того, как расставляются скобки, можно получить выражение, задающее КС последовательной, пирамидальной или смешанной структуры.
Последовательная структура.
;
N - число переменных; К - число входов ЛЭ;
Г - глубина КС; S - число ЛЭ в КС.
Пирамидальная структура.
,
Смешанная структура.
Мы увидели, как построить КС с n входами из ЛЭ (либо «блоков») с К входами, реализующими такие же функции, что и вся КС. Обратимся теперь к построению «блоков».
Рассмотрим типы используемых ЛЭ и их обозначения.
ЛЭ И - ИЛИ - НЕ таков, что из него путем подстановки констант или отождествления входов можно получать ЛЭ типа И - НЕ либо ИЛИ - НЕ.
Покажем это.
Рассмотрим способы получения инверторов из элементов И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.
Рассмотрим способы получения конъюнкции из элементов И-НЕ, ИЛИ-НЕ, И-ИЛИ-НЕ.
Получение конъюнкции из элементов И-НЕ.
Получение конъюнкции из элементов ИЛИ-НЕ.
Получение конъюнкции из элементов И-НЕ и ИЛИ-НЕ.
|
Получение конъюнкции из элементов И-ИЛИ-НЕ.
Рассмотрим примеры получения конъюнкций.
Получение дизъюнкции из элементов ИЛИ-НЕ.
Получение дизъюнкции из элементов И-НЕ и ИЛИ-НЕ.
Получение дизъюнкции из элементов И-ИЛИ-НЕ.
Рассмотрим примеры получения дизъюнкций.
Теперь рассмотрим схемы для получения суммы по модулю два.
X | Y | ||
В соответствии с таблицей истинности можно получить несколько способов реализации этой функции.
Первый способ – на элементах И-НЕ.
Второй способ – на элементах ИЛИ-НЕ.
Третий способ – на элементе И-ИЛИ-НЕ.
Рассмотрим использование выражений вида И - ИЛИ.
F=(X1&…&XP) (Y1&…&YP) … (W1&…&WP)
Рассмотрим примеры реализации выражений И-ИЛИ.
КС ДЛЯ ПРОИЗВОЛЬНЫХ БФ.
Процедура построения КС состоит из трех этапов:
1. Строится схема из элементов И, ИЛИ, НЕ.
2. Отдельные части схемы вида И - ИЛИ, либо И, либо ИЛИ переводятся в схемы из заданных ЛЭ (см. раздел 2.3.1).
3. Полученная КС корректируется с целью устранения возможной избыточности, например, вида
или нахождения общих частей.
|
|
Механическое удерживание земляных масс: Механическое удерживание земляных масс на склоне обеспечивают контрфорсными сооружениями различных конструкций...
Особенности сооружения опор в сложных условиях: Сооружение ВЛ в районах с суровыми климатическими и тяжелыми геологическими условиями...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!