Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 63
Текст из файла (страница 63)
Сложностью булевой функции у" в классе контактных схем (обозначение: Хь(ф)) называется сложность минимальной контактной схемы, реализующей у. Сложноспгью булевой функции у" в классе к-схем называется число контактов в минимальной к-схеме, реализующей ф (обозначение: Ь (ф)). Понятие формулы нэд множеством связок было определено в гл. 1. Сложностью булевой функции ф в классе формул (над множеством связок ('зг., Й, — )) будет называться число вхождений символов переменных. Сложность функции у в этом классе формул обозначается через Ь,ь(Д. 2.1.
Найти функции, реализуемые двухполюсными схемами Е, представленными на рис. 10.3. Один из способов построения контактных схем, реализующих булевы функции, состоит в том, что функция представляется в д. н. ф. 314 Гл. Х. Реализаиин булевых фуикиий схемами и формулами 2.2. Представив функцию 7" в д. н. ф. или к. н. ф., построить к-схему, реализующук> 11 Ц >"(хг) = (110Ц; 2) Д(хг) = х> хг, 3) 7(тз) = (1000111Ц; 4) 7'(тз) (11101000) 5) 7" (*3) (01000010 6) .7(х~) = (х1-+ хг)(х>9хз); 7) Х(х~) =х,хг 9хгхз 9 хзх, 91. 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) Ф = 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).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
