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