Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 63
Текст из файла (страница 63)
2.3. Построить контактную схему, реализующую функцию 7: 1 (х ) (61 '> Х2 " 13)(Х1 '> Х2 '> ХЗ) 2) 1(х' ) = х1«2 9 хгхз 9 хзх1! 3) 1(х ) = 21 9 х2 9 «3 9 1~ 4) «н(х ) = (Х> ц ХЗУЗ)(У>''> Уг); 5) ДХУ ) = (Х> ~ Хг) ).
(Хз ~ хг); 6) У(* ) = Х>9хгхз 91; 7) У(Х ) = (Х1>«Угхз)(х>9хз). 2.4. Построить контактнук> схему сложности, не превышающей 1, реализующую функцию 1: Ц >(ХУ )=219«2«3, 1=6: 2) > (х~) = х>хг 9 хгхз 9 хзх> 9 1, 1 = 5; 3) «е(х~) = х>Уз Ч «гхз ~Г х>хгУз, 1 = 5; 4) Дх~) = х>хг >> х> хгхз ц у> хгхз >«х хг, 1 = 5; 5) 1(х ) = У> «4 >у хгхзха >ухгУЗУ4'>«х>хл, 1 = 7; 6) 7(хз) = (21 9 хг 9 хз)(х> Ч хз), 1 = 5; Ц 1(ха) = (0000 00010111111Ц 1 = 7. 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) Ф = Его = хт 'тт хг, Л = хт '1 хг, 22 = х1 'тт хг, 12 = хт ~I хг), 5=6; 4) Ф = 12о = хтхг 22 = хтхг~ 22 = хтхг, гз = хтхг), о = 6; 5) Ф = 112 = (00000001), Ег = (00010111) 12 = (01111111)) 5=9; 6) Ф = ЕЛ = (10010110), Ег = (01101001), Ь = (00111100), У, = (П000011)), Ь = 10 2.7. ЕЕайти функции, реализуемые контактными схемами, изобра женными на рис. 10.5. х„ х х Х1 хг Хн — 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",,„)+1,(П"). 2.12. 1) Построить Узь с числом контактов, не превосходящим 16.
2) Показать индукцией по и существование сГ~ такого, что лг(сеся) ~ 2 22 3) Показать путем выбора подходящего т в равенстве (1), что при достаточно больших и для произвольной булевой функции Дх л) 2' справедливо неравенство В(1'(х")) < 8. —. н Метод каскадов для построения контактных схем состоит в следующем. Пусть требуется реализовать контактной схемой булеву функцию 1(хы ..., х„) (и, ) 2). Обозначим через м, (~, '= 1,..., п — 1) совокупность всех подфункций ~(оы ..., оо хн-» .
х ) (оз ..., т,;,) Е В', функции 1, и пусть Й,* .-- множество, составленное из попарно различных функций из м,. Каждому множеству м," (1 = = 1, ..., и — 1) взаимно однозначно сопоставим множество г', точек плоскости, называемых вершинами 1-го ранга. добавим еще три полюса . входной полюс а и выходные полюса Ь и с. Полюс а является вершиной нулевого ранга, полюса Ь, с — вершинами п-го ранга. Полюсу а сопоставим функцию Дхы ..., х„), полюсам Ь, с функции, тождественно равные соответственно единице и нулю.
Положим И = (а, Ь) О () 1с. Множество И разобьем на классы эквивалентносс=1 ти, отнеся к одному классу вершины разных рангов в том и только том случае, когда они соответствуют равным функциям. Пусть и --. произвольная вершина 1-го ранга, а ср„(х,+ы хььз, ..., хи) -- соответствующая ей функция, и пусть уе(0, х,.ез, ..., х ) ~ уе(1, х,, з,..., хо). Тогда соединим вершину о контактом х,+з с вершиной и ранга 1+ 1, которая соответствует подфункции уе(1, х,+з,... ..., х„), и контактом х,сз с вершиной ю, соответствующей подфункции ~ре(0, х,.~з, ..., х„). Если же ~ре(0, х,.ез, ..., хи) = уе(1, х,+я, ..., х„), то обе подфункции равны тождественно функции ре(х,.ьы х,ег,, хн), и контакты между соответствующими вершинами не проводятся. Все вершины из одного класса эквивалентности отождествляются.
В результате получаем схему Ег такую, что 1л в(х") = Д(хл), )ее(ххт) = 7(хи). В случае, когда нас интересует только реализация функции 2", вершина с может быть удалена вместе с инцидентными сй контактами. Изложенный метод очевидным образом переносится на реализацию систем. В дальнейшем под схемой Е, полученной «стандартным» методом каскадов, будем понимать схему, в которой вершина с отброшена. ПРимеР. РеализУем 1(х~) = хзхз еЗ хз методом каскадов.
Имеем Й1 = (хз, хз ~Эхз), Йз = (хз, хз), мз = (О, 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. Доказать,что схема Еэ, реализующая систему функций Ф и построенная по методу каскадов, является разделительной тогда и только тогда, когда система.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
