Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 64
Текст из файла (страница 64)
Контактным Ха-деревом называется контактный (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. Доказать,что схема Еэ, реализующая систему функций Ф и построенная по методу каскадов, является разделительной тогда и только тогда, когда система. Ф состоит нз попарно ортогональных функций. 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 у содержит четыре контакта. Контактная схема называется бесповторной, если каждая переменная встречается в качестве пометки контакта один раз. 2.26. Доказать, что сильно связная бесповторная схема Е: 1) реализует функцию, существенно зависящую от каждой переменной, встрочающейся в схеме; 2) является минимальной. 2.27.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
