Декомпозиция системы булевых функций

 

Из таблицы истинности и карт Карно видно, что функции S и q принимают различные значения на всех наборах аргументов, кроме двух (000) и (111). Причем, на нулевом наборе ониравны нулю, а на единичном наборе – единице.

Таким образом, для шести наборов аргументов справедливо:  

то есть можно выразить более сложную по схемной реализации функцию S через более простую по реализации функцию q.

Для того, чтобы учесть равенство нулю значений функций на нулевом наборе аргументов, необходимо сделать конъюнктивное дополнение функции S конституентой нуля для нулевого набора:

За счет такого дополнения на нулевом наборе аргументов конституена нуля aÚ bÚ p принимает значение, равное нулю, и значение функции S также будет равно нулю. Для остальных наборов аргументов конституена aÚ bÚ p будет равна единице и, следовательно, что справедливо для всех оставшихся наборов аргументов, кроме (111).

Для исправления значения функции S на единичном наборе необходимо в выражении (5) сделать дизъюнктивное дополнение функции конституентой единицы abp для единичного набора.

Таким образом применение декомпозиции позволяет представить систему функций (S, q) в следующем виде:

 

.

 

 

Выполним  совместную факторизацию функций системы:

 

Цена схемы по сравнению с выражением (4) уменьшилась на единицу.

Построим схему одноразрядного сумматора на элементах булева базиса с однофазными входами (рис. 3.25).

Рис. 3.25. Схема одноразрядного комбинационного сумматора

 

Сформулируем общие принципы декомпозиции применительно к двум функциям y ₁  и y ₂, входящим в некоторую систему функций.

1. Применение декомпозиции, которая сводится к выражению одной функции через другую, может оказаться целесообразным только в том случае, если функции y ₁  и y ₂ оказываются либо очень похожими (принимают одинаковые значения почти на всех наборах аргументов), либо практически противоположными (принимают одинаковые значения на небольшом множестве наборов аргументов).

2. За исходную функцию из двух следует выбирать ту, которая обладает меньшей ценой схемной реализации (в дальнейшем будем считать, что такой функцией является y ₂).

3. Для похожих функций исходным является равенство y ₁ = y ₂, а для почти противоположных – равенство

4. Для исправления исходного равенства на значение y ₁ = 0 для наборов аргументов Х₀производится конъюнктивное дополнение правой части исходного равенства конституентами нуля для этих наборов.

5. Для исправления исходного равенства на значение y ₁ = 1 для наборов аргументов Х₁производится дизъюнктивное дополнение правой части исходного равенства конституентами единицы для этих наборов.

 

Пример 3.13. Функции y ₁  и y ₂ от четырех переменных принимают одинаковые значения на всех наборах аргументов, кроме (0011), (0101) и (1110), причем функция y ₁ на первом из них равна единице, на двух других равна нулю. Выразить функцию y ₁  через y ₂ и функцию y ₂ через y ₁.

1. Дополним правую часть исходного равенства y ₁ = y ₂ конституентами нуля для наборов (0101) и (1110) и конституентой единицы для набора (0011). Получим:

2. Дополним правую часть исходного равенства y ₂ = y ₁ конституентами нуля для набора (0011) и конституентами единицы для наборов (0101) и (1110).  Получим:

 

 

Контрольные вопросы и задачи

1. В чем состоит отличие между комбинационной и последовательностной логическими схемами? (2 балла)

2. В чем состоит отличие между позитивным и негативным кодированием двоичного сигнала? (2 балла)

3. Дать оценку нижней и верхней границы цены по Квайну для схемы с однофазными входами, построенной на элементах базиса (ИЛИ, НЕ) по минимальной КНФ. (Примечание: оценка должна содержать цены минимального покрытия – S^a и S^b.) (5 баллов)

4. В отношении минимального нулевого покрытия сформулировать условия, при которых цена схемы с однофазными входами, построенная на элементах булева базиса по минимальной КНФ, будет совпадать с ценой покрытия S^b. (4 балла)

5. Применительно к минимальной ДНФ сформулировать условия, при которых схема с однофазными входами, построенная на элементах базиса (И, НЕ) по этой форме, будет иметь задержку T = 3t, где t – задержка на одном логическом элементе. (4 балла)

6. В отношении минимальной КНФ сформулировать условия, при которых схема с однофазными входами, построенная на элементах булева базиса по этой форме будет иметь задержку T = 3t, где t – задержка на одном логическом элементе. (4 балла)

7. Сформулировать условия, при которых вынесение одной буквы за скобки из термов минимальной КНФ приводит к уменьшению цены схемы, (5 баллов) и проиллюстрировать их примерами. (2 балла за каждый пример)

8. В любом ли случае вынесение за скобки двух букв из двух термов минимальной ДНФ приводит к уменьшению цены схемы? Ответ обосновать и сопроводить поясняющими примерами. (6 баллов)

9. Построить схему, реализующую функцию равнозначности на элементах ИЛИ-НЕ и обладающую минимальной ценой. (3 балла)

10. Построить схему с однофазными входами, реализующую функцию  на элементах базиса (ИЛИ, НЕ) и обладающую минимальной ценой. (5 баллов) Определить цену и задержку схемы. (1 балл)

11. Построить схему с парафазными входами, реализующую функцию из вопроса 10 на элементах базиса (И, НЕ) и обладающую минимальной задержкой. (4 балла) Определить цену и задержку схемы. (1 балл)

12. Построить схему с однофазными входами, реализующую функцию  на двухвходовых элементах И-НЕ и содержащую минимальное количество элементов. (5 баллов)

13. Построить схему, реализующую конъюнкцию шести переменных на двухвходовых элементах ИЛИ-НЕ. (5 баллов)

14. Применительно к схеме с парафазными входами, построенной на элементах булева базиса, сформулировать условия, при которых эквивалентное преобразование в базис И-НЕ приводит к изменению цены схемы. (3 балла)

15. Построить схему с парафазными входами, реализующую систему булевых функций от трех переменных:

 на элементах булева базиса и обладающую минимальной ценой по Квайну. (15 баллов) Определить цену и задержку схемы (2 балла)

16. Булевы функции  и  принимают противоположные значения на всех наборах аргументов, кроме (1110) и (1100), на которых значения функций совпадают и равны единице и нулю соответственно. Решить задачу декомпозиции применительно к системе функций (y₁, y₂), выразив функцию y₁ через y₂, (2 балла) а также y₂ через y₁. (2 балла)

17. Определить функцию, реализуемую схемой. (4 балла)

Определить реакцию схемы на входной набор (10101). (2 балла) Преобразовать схему к двухвходовому базису (ИЛИ-НЕ) с минимальной ценой. (6 баллов)

18. Булева функция y = f ⁴ ( x ) принимает значение, равное нулю, на наборах (3, 5, 8, 10, 13) и безразличное значение – на наборах (1, 4, 7, 14). Построить схему с парафазными входами, реализующую данную функцию на элементах базиса И-НЕ и обладающую минимальной ценой. (20 баллов) Определить реакцию схемы на одном из безразличных наборов и пояснить ее. (3 балла)

В опросы к рубежному контролю

1. Что понимается под свойством симметричности отношения? Привести пример антисимметричного отношения, на котором показать наличие этого свойства.

2. Является ли отношение равенства двух треугольников транзитивным? Утверждение доказать.

3. Записать законы поглощения. В чем состоит свойство их дуальности? Доказать один из них.

4. Записать законы склеивания. В чем состоит свойство их дуальности? Доказать один из них.

5. Для множества В ={0, 1} найти В ³ – третью декартову степень.

6. Записать дистрибутивные законы для операции прямого произведения множеств.

7. Что понимается под конституентой единицы? (2). Записать все конституенты единицы для функции .

8. Действуют ли дистрибутивные законы в алгебре Жегалкина (для операций конъюнкции и сложения по модулю два)? Ответ обосновать.

9. Что понимается под сокращенной ДНФ (СДНФ) булевой функции? Найти СДНФ функции y = f ³ ( x )=& (0, 2, 5). Является ли найденная СДНФ и минимальной ДНФ? Ответ обосновать.

10. Что понимается под самодвойственной булевой функцией? Перечислить все несамодвойственные базовые булевы функции.

11. В чем состоит отличие между комбинационной и последовательностной схемами?

12. Действует ли сочетательный закон в отношении операции сумма по модулю два, стрелка Пирса?

13. Действует ли распределительный закон в алгебре Жегалкина?

14. Как выглядят законы тавтологии и законы с константами в различных базисах?

15. Можно ли построить двоичную алгебру на основе единственной операции импликации?

16. Является ли выражение Х₁Ú ₂Ú ₃ нормальной формой и, если является, то какай (ДНФ или КНФ)? Можно ли рассматривать это выражение в качестве канонической формы и, если можно, то какой (КДНФ или ККНФ) и при каких условиях?

17. Сформулировать условия (в отношении покрытия), а также соответствующей ему нормальной формы, при которых:

a) S _Q = S ^a;

b) S _Q = S ^b;

c) S ^a < S _Q < S ^b.

18. Может ли СДНФ совпадать с КДНФ и, если может, то, при каких условиях?

19. Можно ли считать, что СДНФ является МДНФ и, если можно, то, при каких условиях?

20. Может ли КДНФ являться МДНФ и, если может, то при каких условиях?

21. Привести примеры булевой функции от трех или четырех переменных для которых:

a) МДНФ совпадает с КДНФ, а МКНФ не совпадает с ККНФ;

b) МКНФ совпадает с ККНФ, а МДНФ не совпадает с КДНФ;

c) Обе формы совпадают с каноническими.

22. Сформулировать условия, при которых схема вырождается в одноуровневую.

23. Оценить нижнюю и верхнюю границу цены схемы с однофазными входами, построенную по МНФ.

24. Сформулировать условия, приводящие к вырожденным случаям T=1t и T=2t.

25. Может ли задержка схемы после применения однократной факторизации быть такой же, как и до факторизации (условия и пример)?

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

27. Сформулировать условия целесообразности вынесения за скобки одной или двух букв из произвольного числа термов.

 

Литература

 

О с н о в н а я

 

1. Глушков В.М. Синтез цифровых автоматов. – М.: Физматгиз, 1962.–476 с.

2. Миллер Р. Теория переключательных схем. Т.1. Комбинационные схемы: Пер. с англ. – М. Мир, 1970. – 416 с.

3. Савельев А.Я. Прикладная теория цифровых автоматов. – М.: Высш. шк., 1987. – 272 с.

4. Поспелов Д.А. Логические методы анализа и синтеза схем. – М.: “Энергия”, 1974. – 368 с.

5. Скорубский В.И. Арифметические и логические основы цифровых машин: учебн. пособие. – Л.: Лен. ин-т точной механики и оптики, 1980. – 60 с.

6. Гладков Л.А., Курейчик В.В., Курейчик В.М. Дискретная математика. Учебник/ Под ред. В.М.Курейчика. – Таганрог: Изд. ТТИ ЮФУ, 2011. –494 с.

7. Кузнецов О.П. Дискретная математика для инженера. Изд.6, стереотипное Учебное пособие. 6-е изд., стер. — СПб.: Изд. «Лань», 2009. – 400 с.

 

 

Д о п о л н и т е л ь н а я

 

1. Проектирование цифровых вычислительных машин / С.А. Майоров, Г.И.Новиков, О.Ф. Немолочнов и др.: Под ред. С.А. Майорова. – М.: Высш.шк., 1972. – 344 с.

2. Лысиков Б.Г. Арифметические и логические основы цифровых автоматов. – Минск: Вышэйшая школа, 1980. – 386 с.

3. Майоров С.А., Новиков Г.И. Структура цифровых вычислительных машин. – Л.: Машиностроение, 1970. – 375 с.

4. Баранов С.И. Синтез микропрограммных автоматов. – Л.: “Энергия”, 1974. – 216 с.

5. Новиков Ф.А. Дискретная математика для программистов. 3-е изд. СПб.: Питер, 2009.–383 с.

6. Мальцев И.А. Дискретная математика. СПб.: Изд. " Лань", 2011. – 304 с.

7. Шевелев Ю.П. Дискретная математика. СПб.: Изд. " Лань", 2008. – 592 c.

 

 

 

В 2009 году Университет стал победителем многоэтапного конкурса, в результате которого определены 12 ведущих университетов России, которым присвоена категория « Национальный исследовательский университет ». Министерством образования и науки Российской Федерации была утверждена программа его развития   на 2009–2018 годы. В 2011 году Университет получил наименование «Санкт-Петербургский национальный исследовательский университет информационных технологий, механики и оптики»

⇐ Предыдущая891011121314151617

Поделиться: