Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 63
Текст из файла (страница 63)
2.5. Построить контактную схему, реализуюшую 7 и имеющую сложность нс выше Ь, упростив предварительно формулу, с помощью которой она задана: Ц 1 = ((х1 >> х2) Уг Ц х4)>«(хз Ч Х4)(х1х2хз 'и хехз))(х1 >«22хз), 1=5; 2) >л = х>'ч'У>хг 'ч'х> Угхз ''х>Угхзтл, 7 = 4; 3) > = (:11 >«Хг)((2122 >' Х2ХЗ):66 ц (Х2 > Хзхз)(«2 ХЗ)~ >>(Х1 62 " «122 " «6)ХЗ " 11«2 >«ХЗХ6) 4) 1 = У>Угхз((У4 >«У>Узфхз >«х>хахг) >«(хвхг Ч хгхлхз) бе 36(У426'Ц УзхвУ>)) '4 (У1'>УУг)(У4 Ч хв) хз >«хг), Л = 6; 5) 1 = 21 9 хг 9 хз 9 х4 9 х>хгхзха 9 х>хг 9 х>хз 9 х>Х4 9 хгхз9 9хгт4 9 хзхл 9 Х>хгхз 9 Х>хгх4 9 Х>хзх4 9 Хгхзхл, 1 = 4; 6) 7 = х>хгхзх4 '4 ( (1> х>х>>~, 1 = 6.
'1<1<1<4 2.6. Построить контактную схему сложности, не превы>лающей А, реализуюшую систему функций Ф: Ц Ф = (Л = Х>хг >у «гхз и хзх>,,>сг = Х1 9 хг 9 хз), 7 = 12; 2) Ф = («1 = (0000000Ц, >г = (0000001Ц уз = (0000011Ц 74 = (0000111Ц, 16 = (0001111Ц, 16 = (0011111Ц, У, = (0ШШЦ), 7, = 11; 315 у" е. Контпантпные схемы и формулы 3) Ф = 12О = Хт 'тт Хг, Л = Хт '~~ Хг, 22 = Хт 'тт Хг, УЗ = Хт ~I Хг), 5=6; 4) Ф = 12о = хтхг 22 = хтхг~ 22 = хтхг, гз = хтхг), о = 6; 5) Ф = (тг = (00000001), Ег = (00010111) тз = (01111111)) 5=9; 6) Ф = ЕЛ = (10010110), Ег = (01101001), Ь = (00111100), У, = (П000011)), Ь = 10 2.7. ЕЕайти функции, реализуемые контактными схемами, изобра женными на рис.
10.5. х„ х х Хт хг хт| — 2 х~ — 1 х„ Хг Хг ° Ь Х2 — 1 Хг Рис. 10.5 316 Гл, Х. Реализация булевых функций схемами и формулами 2.8. Пусть р(а) = ~ ~2а га, номер набора а = (а1, ..., аа). 2=1 Построить контактную схему с не более чем 1 контактами, реализующую функцию ): 4 ~ 1, р(111, а2) ч р(аз, 414), 1= 7, ~ 0 в противном случае, 2) 41=4) 1, р(аг, аг) = ~(аз ал), ~ 0 в противном случае, 3) УГ') =~' "'"-="""' 1 0 в противном случае, 4) 2,~-4 /1, а1+аз=аз+а4(пзоо2), ) 0 в противном случае, -4 1г г-11 ~ г-12 г-13 + ал ) 0 в противном случае, (а1 зг ггз) ы 1а2 ьг '-14)г 1=4; ) 0 в противном случае, 4 1, если наборы (а1, аз) и (аз, а4) несравнимы, ~ 0 в противном случае, 2.9. Построить контактную схему для одноразрядного двоичного сумматора. Контактным Ха-деревом называется контактный (1, 2а)-полюсник Рь„индуктивное определение которого дано на рис.
10.6. Очевид< Рис. 10.6 но, что Р„реализует все конъюнкции ранга л переменных хг, ..., ха ь и что 1 ь(Рь) = 2" ' 1 — 2; (1, ка)-полюсник называется р зделитвльным, если для любых его выходов Ь, с функция проводимости уь,(х") тождественно равна нулкг. 2.10. 1) Построить Р1, 2) Доказать, что Р~ является разделительным (1, 2")-полиюником. 3) Система функций Ф называется ортогональной, если для любых двух функций )' и д из Ф выполняется равенство у Й д = О. Доказать, 317 у" 8.
Контактные схемы и формулы что для всякой ортогональной системы функций Ф = (уз(хп), ... ..., ут(хи) ) существует контактная схема сложности, не превышающей 2пь~ — 2, реализующая Ф. 2.11. Пусть разделительный (1, 6)-полюсник А с полюсами а, Ьы ..., Ьь соединяется с (щ.. 1)-полюсником В с полюсами аы ..., а,н, Ь так, что каждый выход 6; отождествляется ровно с одним из полюсов аз. Доказать, что для полученного таким образом двухполюсника Е выполнЯетсЯ Равенство уп,ь(хп) = 1/уп,ь,(х )уь.,ь(х )~ =1 где 1, ь(х") функция проводимости между полюсами а, Ь схемы Е; 1', ь,(т") функция проводимости между полюсами а, 6, схемы А; 7ь, ь(хп) функция проводимости между полюсом а, отождествленным с полюсом Ь; схемы А, и полюсом 6 схемы В.
Универсальным контакзлным многополюсником называется (1, 2г )- или (2з, 1)-полюсник, реализующий все булавы функции переменных хы хз, ..., х„. На рис. 10.7 представлена схема Р;ь. Метод Шеннона для синтеза контактных схем, реализующих булевы функции 1(хп), состоит в ис- Рис 107 пользовании схем Р„и ср ь ь Пусть ф(х") функция, которую следует реализовать. Для набора а = (оы ..., он т) из В" ~ положим (й(х ) = ф(оы ..., о„т, хп т.ьы ..., х„). По формуле разложения имеем 1" (*") = З/ хГ " *." „;"1а(х") аев" Пусть Р„контактное дерево с полюсами а, 6о, Ьы ..., Ьз.-- ь реализукьщее конъюнкции К, = х,'х '...
х„" „„между полюсами а п — т и Ьь, где Ь = о(сг) = ~ 2п 'и 'оь Пусть Бь, с=1 г'" универсальный контактный (2, Ц-полюсник с Рь полюсами ав, аы ..., азп — , .6, реализующий все функпии 1(хп тары..., х„). Рассмотрим схему ЕР полученную отождествлением для каждого о Е В" выхода Ь,(В) схемы Р„с входом а„схемы Ьу„таким, что ь ь фп.,ь(хп — те-ы . хп ) = фа(хн) (рис.
10.8). Рь ы В силу разделительности схемы Р,„для по- Ег лученной таким образом схемы Ху с полюсами а и Ь справедливо равенство ° Ь У.,ь(х") = '1/ х,'... х„",",*(а(х") = 1(х"). Рис. 10.8 318 Гл, Х. реализация булевых функиий схемами и формулами Заметим, что из построения следует равенство Т(Ву) =1(12", )+А(%"). 2.12. 1) Построить сгзь с числом контактов, не превосходящим 16.
2) Доказать индукцией по и существование сГ„" такого, что ег(весу) ~ 2 22" 3) Доказать путем выбора подходящего т в равенстве (1), что при достаточно больших и для произвольной булевой функции 2" (хи) 2' справедливо неравенство В(1(х")) < 8. —. и Метод каскадов для построения контактных схем состоит в следующем. Пусть требуется реализовать контактной схемой булеву функцию Д(хы ..., х„) (и, ) 2). Обозначим через м, (~,' = 1,..., п — 1) СОВОКуПНОСтЬ ВСЕХ ПОдфуНКцнй 2'(ОЫ ..., Оо Хинт, Хи), (ОЫ ..., те) 6 В', функции 1, и пусть Й,* -- множество, составленное из попарно различных функций из й;. Каждому множеству м," (1 = = 1, ..., гс — 1) взаимно однозначно сопоставим множество г', точек плоскости, называемых вершинами 1-го ранга.
Добавим еще три полюса - входной полюс а и выходные полюса Ь и с. Полюс а является вершиной нулевого ранга, полюса Ь, с — вершинами п-го ранга. Полюсу а сопоставим функцию 1(хы ..., х„), полюсам Ь, с функции, тождественно равные соответственно единице и нулю. Положим И = (а, Ь) О () 'ги Множество И разобьем на классы эквивалентносс=1 ти, отнеся к одному классу вершины разных рангов в том и только том случае, когда они соответствуют равным функциям. Пусть и --. произвольная вершина 1-го ранга, а ср„(хееы хиьз, ..., хи) --.
соответствующая ей функция, и пусть ~ри(0, х,.ез, ..., х„) ~ ~ре(1, х,, з,..., хи). Тогда соединим вершину о контактом хгез с вершиной и ранга 1+ 1, которая соответствует подфункции усе(1, хеез,... ..., х„), и контактом х,сз с вершиной и, соответствующей подфункции ~ре(0, х,.~з, ..., хи). Если же усе(0, х,.ез, ..., х„) = ре(1, х,лз, ..., х„), то обе подфункции равны тождественно функции усе(х, еы хеез,...., ти), и контакты между соответствующими вершинами не проводятся.
Все вершины из одного класса эквивалентности отождествляются. В результате получаем схему Еу такую, что (, е(хи) = у(хи), ~лх(хи) = 7(хи). В случае, когда нас интересует только реализация функции 2", вершина с может быть удалена вместе с инцидентными сй контактами. Изложенный метод очевидным образом переносится на реализацию систем. В дальнейшем под схемой В, полученной «стандартным» методом каскадов, будем понимать схему, в которой вершина с отброшена.
ПРимеР. РеализУем )(хз) = хзхз Ю хз методом каскадов. Имеем ыс = (хз, хз ~Эхз), йз = (хз, хз), мз = (О, 1). Полагаем Ъо = (а), зрй у" 9. Контактные схемы и формулы 1'! = (1, 2): 1г = (3, 4), 1з = (5, 6). Вершины 1 и 4, соответствующие функции хз, эквивалентны. Способ проведения ребер показан на *г Е ~з х Уз Уз 1 = 5 хг 5 0 хз хз хз Рис. 10.9 рис.
10.9, а. На рис. 10.9, б дана схема, полученная отождествлением эквивалентных вершин и удалением вершины О. 2.13. С использованием метода каскадов построить контактную схему для функции 1: 1) Пх ) = хгхгхз 6!хгхз Ю1; 2) 1(х ) = хгхгцхгхзЧ хзхг, 3) Дхз) = х! 9 хг !Э тз б! 1; 4) ~(хз) = х! Ч хг !гхз)(У! !с хг Ч хз); 5) 1'(хз) (0110 1000) 6) 1(хз) (0110 110Ц.
7) Дх~) = (0000000101111111). 2.14. С использованием метода каскадов построить контактную схему для системы функций Ф: 1) Ф = (хУ, х ц У); 2) Ф = (хг й! хз, г! Ю хг Ю хз, Уг): 3) Ф = Ехз, Уз, хг !9 хз, хг хз, х! й! хг й! хз, х! й! хг й!хз); 4) Ф = 1Уг есхз~ хг Ч хз~ хе> х!Уг М хгхз Ч хгх!)! 5) Ф = (1! — — х! Ог хг Оз хз~ уг — — х! Ч хг!хз Ч хгхг); 6) Ф = )Л = хгхгхз !ух хгУз, Л = хгхз !г хг); 7) Ф = (х! Ч хг, х! и хг, У! Ч хг, х! !! хг); 8) Ф = (хгхг, х!хг, х,хг, хгтг). 2.15. Ноказатгч что если функция 7'(х) не равна тождественно константе, то схема ХР построенная по методу каскадов, является сильно связной.
2.16. Доказать,что схема Еэ, реализующая систему функций Ф и построенная по методу каскадов, является разделительной тогда и только тогда, когда система. Ф состоит нз попарно ортогональных функций. 2.17. 1) Доказать,что схема для универсального многополюсника 5!„, построенная по методу каскадов, имеет сложность,не превышающую 2 2г .
2) Доказать, что для всякой функции 1 и любой схемы ХР построенной для 7' по методу каскадов, выполнено неравенство ЦЕ1) < 8 п 2.18. Доказать, что схема Рг, для реализации всех элементарных конъюнкций ранга и переменных хг, ..., хю построенная по методу каскадов, является контактным деревом и имеет сложность 2н" ! — 2. 320 Гл. Х. Реааизаиим булевых фуиииий схемами и формулами 2.19. Доказатгч что схема В„*ь, реализующая все дизъюнкции ранга и переменных хы ..., х„, имеет сложность 2и+~ — 2. 2.20.
Функция уг (х") (О < т < 2а) называется сьчупенчатой, если р (сто) = 1 тогда и только тогда, когда р(сг) > т. Ц Убелиться в следующих свойствах ступенчатых функций: а) Уга(ха) = 1; б) Угг (ха) = О; в) Угг- с(ха) = хзхг...ха; )хзцсгт г.— (хг,...,х~) при 0<т<2" (х, уи(хг, ..., ха) при 2" < т. < 2", д) уггь (ха) не зависит существенно от х„(й = 1, ..., 2" 1); е) ~ра,(х") — монотонная функция.
2) Убедиться в том, что при применении «стандартного» метода каскадов, когда в 1-м ярусе разложение ведется по переменной х, сложность получающейся схемы равна 3 2" — 2п — 3. 3) Убедиться в том., что если в методе каскадов применить обратный порядок разложения, при котором в г-м ярусе разложение ведется по переменной и — г + 1, то сложность получающейся схемы равна 2и+з — и — 2. 2.21.
Пусть схема Е содержит контакт х'*, и пусть Е' (Ео) —— схема, полученная последовательным (параллельным) соединением этой схемы со схемой из одного контакта хо, сц,З Е (О, 1). Доказать, что схемы Х' и Ев не являк~тся минимальными. 2.22. Доказать, что всякая минимальная контактная схема, реализующая функцию, отличную от констант, является сильно связной. 2.23. Доказать, что не существует минимальных контактных Хз-схем с двумя контактами и Хг-схем с тремя контактами. 2.24. Доказатгч что не существует минимальных контактных Хз-схем сложности 4, содержащих только замыкающие контакты. 2.25. Доказать, что минимальная контактная схема для функции г = х 9 у содержит четыре контакта. Контактная схема называется бесповторной, если каждая переменная встречается в качестве пометки контакта один раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
