Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 62
Текст из файла (страница 62)
По схемам Е, изображенным на рис. 10.2, найти функции, реализуемые ими. 1.5. Построить СФЭ в базисе Б, реализующую систему функций Ф: Ц Ф = (дд = хдхг дс тгтз дс Узтд,,дг = хд ид хг ддд хз); а) Б = (Й, ч, — ), б) Б = (Й, дй), в) Б = (4, $); 2) Ф = (Уд =*д, Л = хдхг,,(з = хдхг*з; Ул = 1); а)Б=(й,— ), б)Б=( —,Ц; 3) Ф = ((д = хд чг хг,,(г = хд дс хг дс хз дУхдхгхз, (з = хдхг М хдхг); 309 у'1. Схемы нэ функциональных элементов Рис. 10.2 6) Ф = (,Г1(х ) = Х1ХЗХ4 Ч Х1ХЗХ4 э Х2ХЗХ4 Ч Х2ХЗХ4, Ь = Л(Х1, хг, хз У4)); а) Б = ( ое, Ч., — ), б) Б = ( ое, 9, — ); 7) Ф = (Л(х ) = хзхгхз Н УгхгУз Ъ УЗХЗУ3 Ч У12224 Н х1 тгх4, .~2 = 71 9 Х2 ° 33 = Х2 9 ХЗ),~4 = 21 9 Х4); а) Б = ( ве, 17', — ), б) Б = ( 32, 9, — ); 8) Ф = Уо = х1, 'хю хз Л = з,,хгхз, Ь = х,,хгхз, 73 =х,хгхз, 34 = 21.'е2.'33 13 = Х122ХЗ, 13 = Х1Х2ХЗ, 37 = Х1ХЗХЗ)~ а) Б = ( й, — ), б) Б = ЕЧ, 9, Ц.
1.6. Реализовать функцию 7(хн) СФЭ в стандартном базисе, предварительно упростив выражение для 7(х ): 1) 7 (х ) Х122хз 7 21х2ХЗ 17х1хгхз э х1Х2хз 17х1хгхз~ 2) 7(х ) = Х1хгхз 17 хзхгхз 47'езхгхз 17 х1УЗУЗ 47У1хгхз 17 ххУгхз1 3) У(х ) — хзхз 1ухгхз 17 Х1.'ег'~ Хгхз,'. 4) Дх ) = (Х1 М хг М хз)(х1 М Хг Ч Хз)(хз Ч хг Ч Уз)(У1 Ч хг Ч Уз); 5) 7 (х~) = (х1 Ч х2)(х1 Ч х2 М хз) Ч х1х2хз 7 х2хз; 6) 7(х ) = (У1 Ч хг)(УЗ 47хз)(21 47 хг Ч хз)(х1 Ч Хг 47хз); 7) 3 (х ) = хзх2 7 х1хз 1 х1х2хз 7х1х2 гхзхз ° 310 Гл, Х.
Реализаиил булевых функиий схемами и формулами Метод синтеза СФЭ, основанный на д. н. фп состоит из двух эта- пов: 1) представления функции в д.н.фб 2) реализации д.н.ф. с помощью СФЭ. 1.7. Реализовать функцию 1 по методу, основанному на д. н. фл 1) 1 = 101000110);. 2) 1 = (01111110); 3) 1 = (00011111); 4) ~=(00010111); 5) )'=16>хй>гу; 6) У=х>1>уйг. 1.8.
Показать, что если Г функция, двойственная к Э", и 1" отлична от константы, то Ь11') = Ц~). Одноразрядным двоичным сумматором называется СФЭ (в произ- вольном базисе), реализующая систему из двух функций: т1х, у, р) = = ху > > ур Ч рх и 11х, у, р) = х а у 6> р. 1.9. Построить одноразрядный двоичный сумматор в базисе со сложностью, не превышающей А: ЦБ=1Ч,3с,— ), А=9; 2)Б=1еЭ,1с), А=5;.
3) Б=1ь, ~> — ), 1.10. Построить СФЭ в базисе 1й>, й ), реэлизующую такук> сис- ТЕМУ фУНКЦИй 1>Э'>1Хп), Эг(Х~), фХ )), Чта иЦ>1ап), Л(ап), Ь(ап)) Равно числУ единиц в набоРе йл = 1о>, ог> оз, ол). Таким обРазом, искомая СФЭ дает двоичное разложение числа единиц набора ал. Здесь, как и раньше, о(о» ..., оп) = ~ еп.
2" ><><и Де>аифратпором называется схема 11п, реализующая систему всех конъюнкций ранга и переменных х>, хг, ..., хп. 1.11. 1) Построить Вг в базисе 1 3с, †) с числом элементов, не превосходящим 6. 2) Построить Вп в базисе Б = 1 й, — ) такую, что ЦВ„) ( 2"+' ч- п — 4.
3) Построить Вп в базисе Б = 1 се, — ) такую, что г.сд ) ( 2п, + 2>пп-з)йг 1.12. Мультиплексором от переменных х>, ..., хп, уо, у>, ... ..., уг. > называется схема М„> реализующая функцию гс>>х> .. хп уо, у>;, уг — >) = >> уп>п„....пд>х>' >и>, ...,с > и где о(п>, ..., ссп) = > о> 2" Ц Построить Мг в стандартном базисе с числом элементов, не превосходящим 13. 2) Доказать, что ЦМп) ( 3 2п -'е 20' ' ~»г + и.
3) Доказать, что А(Мп) > 2" 1.13. Универсальным многополюсником для множества переменных Х называется СФЭ 1>(Х), реализующая все булевы функции переменных из Х. Если Хп = 1х>, ..., хп), то полагаем П> Х") = 11„. 311 г'д Схемы иэ фуниииоиальиых элементов 1) Построить СФЭ Нг сложности 3.
2*) Доказать, что сложность минимального многополюсника У„ г равна 2 — и. 1.14. Пусть В„ь произвольный дешифратор для множества переменных хы ..., хо ь, Х = (х„~+~, ..., хо) и У~ произвольный универсальный многополюсник для множества переменных Х. 1) Доказать, что для произвольной булевой функции у'(хо) А(((хч")) < ИГгм ь) + Б(П~) + 2" ьы 2) Опираясь на результаты задач 1.11 и 1.13, доказать, что для достаточно больших и и любой булевой функции у(х") справедливо неравенство А®хо)) ( 2л'г(и.
3) Доказать, что существует СФЭ в базисе (Ч., йг, ег,. — ), реализующая все самодвойственные функции у(х") и имеющая сложность, г" не превосходящую 2. 2г Функция у(х") такая, что гчу = () Вл., называется пояскооой и г=ь обозначается через Я" т(хо). Функция Яь "(х") называется элементарной симметрической функцией. Функция г"(хо), представимая в виде дизъюнкции элементарных симметрических функций, называется симметрической.
1.15. 1) Доказать, что для любой перестановки я = (гм ..., 1„) чисел 1, ..., и и любой симметрической функции г(х") выполнено равенство 2) Доказать, что для любой поисковой функции существует СФЭ, содержащая не более одного элемента отрицания. 3) Доказать, что для любой симметрической функции у(х") существует СФЭ, содержащая не более (и + 1) /2 элементов отрицания. 1.16*. Построить СФЭ, реализующую три одноместные функции хы хг, хз и содержащую ровно два элемента отрицания.
1.17. Доказать, что Л(х ег у) = 4. Глубиной СФЭ в базисе Б называется максимальное число внутренних вершин (функциональных элементов) в ориентированных цепях, соединяющих вход с выходом. Например, глубина схемы изображенной на рис. 10.1, а, равна 3. 1.18. Построить СФЭ глубины 1 для функции г,: 1) Л = хгхгхзтл, Р = 2; 2) Уг = хгхг 'г хгхгхз,. ~ = 2; 3) Уз = хг Юхг йэхз, 1= 6; 4) У4 хг(хз ч хл)(хз Ч хо) ч хг(хзхз ч хлхз ч хлха Ч хзхе), 1 = 3; о) Ь = хг ч хгхг ц хгхгхз Ч хгхгхзхьм ~ = 2; 6) гз = (хгхг Ч хгхз М хзх1) М (хг 9 хг 9 хз), 1 = 2.
1.19. СФЭ Х называется связной, если граф, полученный из нее заменой дуг на ребра, является связным. Пусть СФЭ Х связна и 312 Гл. Х. Реализация булевых функций схемами и формулами существует единственная вершина (выход) с нулевой полустепеныо исхода. 1) Доказать, что ЦЕ) < '2ьы — 1, где 1 глубина схемы Х. 2) Дсжазатьь что всякая минимальная СФЭ с одним выходом связна. 1.20. Доказать, что для любого 1 существует минимальная СФЭ глубины й 1.21. Доказать, что любая СФЭ, реализуюьцая произвольную функцию Дхн), существенно зависящую от всех переменных, имеет глубину не меньшую, чем 1ояз п — 1.
2 2. Контактные схемы и формулы Сеть Г с 6 полюсами, в которой каждое ребро помечено букВой из алфавита Х: (хз хз ... хн хз хз ... ун), называется йполюсной контактной схемой, реализующей булевы функции переменных хы хю ..., х„, или, короче, (Й, в)-схемой. (2, п)-схемы будут называться Хо-схемами. Сеть Г называется сетью контакт; ной схемьь Контактная схема называется связной (сильно связной, параллельно-последовательной), если таковой является ее сеть. Параллельно-последовательная контактная схема называется кратко к-схемой. Ребра схемы, помеченные символами переменных или их отрицаний, называются контакгнами.
Контакт называется замыкающим, если он помечен символом переменной, и размыкаюсцим, если он помечен символом отрицания переменной. Пусть Хз и Гз две Й-полкюные контактные схемы, полюса каждой из которых помечены буквами аы оз,..., аь. Схемы Еь и ух называются изоморфными, если их сети изоморфны и при этом: а) соответствующие ребра помечены одинаково; б) соответствующие полюса помечены одинаково. Пусть а и Ь - два полюса контактной схемы Е, ~а, Ь] -- некоторая цепь, соединяющая а и Ь, и К„ь1 - конъюнкция букв, приписанных ребрам цепи ]а, 6]. Функция у, ь(х"), определяемая формулой в которой дизъюнкция берется по всем простым цепям схемы, соединяющим полюса а и Ь, называется функцией проводимошпи между полюсами а, Ь схемы Е.
Говорят, что схема Е реализует функцию д(хп), если в ней существуют полюса а и Ь такие, что д(хн) = 1, ь(х"). Контактная схема с й+ 1 полюсами называется (1, к)-полюсником, реализунэиЕим функции дз(хи),..., дь(хп),. если существуют полюс а и полюса Ь, (1 < 1 < 6) такие, что у„ь,(хп) = д;(хцп). При изображении (1, й)-полюсников полюс а изображается светлым кружком и называется входом, полюса Ь, изображаются двойными кружками и называются выходами, остальные вершины изображаются у" 2. Контактные схемы и формулы х о а ° Ь х1 хг а хз .Ь 11 Х1 Х1 'г хг Ю Хг хз Ь х хг Х1 х'з а хг ° Ь Хг х Рис.
10.3 (или к.н.ф.), а затем для каждой элементарной конъюнкции К = = х ' 1с ... ос х;' (дизъюнкцин Р = х.' ч... зг х ') строим схему, представляющую собой последовательное (параллельное) соединение контактов х, ', ..., .т.,", и соединяем полученные схемы параллельно ° Ь (последовательно). Пример. Пусть (1101 ПОО) — вектор значений функции Д(х~). Представим у в совершенной д.н.ф., а затем упростим ее: ф(х ) = хгхзхз Ч хгхзхз Ч хгхзхз Ч хгхзхз Ч хгхзхз = хз зу хгхз Схема, соответствующая этой д.
н. ф., показана на рис. 10.4. темными кружками. В тех случаях, когда число полюсов схемы не указывается., речь всегда будет гщти о двухполюсных контактных схемах. Лве контактные схемы называются эквивалентными, если они реализуют одну и ту же булеву функцию или одну и ту же систему функций. Сложноспгью контактной схемы называется число ес контактов. Контактная схема, имеющая наименьшую сложность среди всех эквивалентных ей схем, называется минимальной.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
