Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 83
Текст из файла (страница 83)
Указание. Ц 7 = хгхз Ч х1хгхз. 2) 7 = х>хг Ч хгхз Ч гзхь 3) ( = х1 Чхгхз. 1.8. Утверждение вытекает из того, что замена в СФЭ Е всех пометок Ч на 8с и 3с на Ч приводит к схеме Е*, реализующей двойственную функцию 1*. 1.13. Ц См. рис. 0.10.1. 2) Индукпия по и. Базис индукции доказан в и. 1.
Пусть П схема уни- г" версального многополюсника сложности 2 — п. Побавим к ней вход х„+~ н инвертор для реализации х„+г. Реализуем все функции вида х„ы вс), где ) = Д(хг, ..., х„) -- функции, отличные от констант и реализованные в сС . авдее с использованием уже построенных функций реализуем функции вида (х„лг ЙЯЧ (х„~.г сед), где 1 = Д(хм ..., хо), д = д(хг, ..., хо), 1' У: д, ) Ч д Ц: О. Лля реализации каждой из упомянутых (кроме х„лг) функций требуется дополни- г тельно ровно один элемент. Таким образом, к 2 — и, эле- г ментам схемы 5с„добавляются один инвертор, 2(2 — 2) Рис.
0.10.1 408 Ответы, указания, решения конъюнкторов и (2 — 1)(2 — 2) дизъюнкторов. Всего в полученной схег" эз ме 2 — (и+ 1) элементов. Нижняя оценка следует из того, что каждая функция, отличная от х„з = 1, ..., и, должна быть реализована на выходе некоторого элемента. 1.15.
2) Утверждение вытекает из представлений озз" (х") = = Яз"(х")3зЯ з"(хв) и Я"*™(х") = 5" н"(х"). 1.16. Заметим, что функции оз*~(хз) ()з = О, 1, 2, 3) монотонны и могут быть реализованы схемами, не содержащими отрицаний. Покажем сначала, что совокупность всех схем вида Яз*з(ха) (к = О, 1, 2, 3) может быть реализована с применением двух отрицаний. Имеем яж (х'з) = яг з(хз), Ян(У ) = Я Л(Х ) 3ЗЯ'з(Х~) ЛаЛЕЕ ПОЛаГая ) (Х ) = Хг ЗО Хг ЧЗ ХЗ гЭ З ПО- лучаем (в(хз) = Якг(хз) ГЗ Яз'з(хУз). )з(х~) = )в(х~), ог'г(хчз) = )з(ха) 3з 3з ог з(хз), $ц (х' ) =(г(гхр ) 3з Ба (хз).
Теперь из функций Я ' (хз) и элементарных монотонных конъюнкций можно без применения отрицаний построить любую конъюнкцию вида х,'тг'гз'. Например, хзхгхз = = Я * (хз) й хз, хзхгхз = Б * (хз) 3гхгтз. Располагая всеми элементарными конъюнкциями ранга 3, функции х, (з = 1, 2., 3) можно строить с применением только элементов дизъюнкции. Например, хз = хзхгхз Ч хзхзУзЧ Ч хзУгхз '' хзУгУз.
1.17. Рис. 10.2, з и задача 1.8 показывают, что Цх ОЗ у) < 4. Неравенство Цх Ю 9) ) 4 вытекает нз следующих соображений. В силу не- монотонности функции у = х ОЗ у она не может быть реализована без отрицаний. В минимальной схеме Ез, реализукзщей 1, элемент отрицания не может стоять на выходе схемы; в противном случае в вершине, предшествующей выходу, реализовалась бы функция 1' = у'*, и в силу утверждений задачи 1.8 схома Ез номинимальная.
Таким образом, выход схемы Ез совпадает с выходом одного из элементов 3з или Ч. Обозначим этот элемент через . Тогда з' = з'з з'г, где функции (з, зг реализованы в вершинах схемы Ез, предшествующих выходу. Ни одна из этих функций не является одноместной, так как з отлична от функций вида х Ч )з, х 3з)з. Кроме того, функция )'з но является отрицанием функции З'г, поскольку З не является константой. Отсюда следует, что схема Ез должна содержать еще по меньшей мере два двухместных элемента.
1.19. Провести индукцию по В 1.20. Указание. Рассмотреть схему ЕЗ, реализующую функцию З" = = хг Ч... Ч хгз з и имеющую глубину В 1.21. Утверждение вытекает из задачи 1.19 и из того, что сложность СФЭ, реализующей функцию, существенно зависящую от н, переменных, не меньше, чем н — 1. 2.1. а) у = хз ЗО хг = злУ, Ч хзхг, б) З = хгхзЧ х~хзхз Ч хгхзхз Ч хгхз. в) ) = (хз Ч хг)(Уз ЧУг) = хз 9 ха. г) з' = хз бзхг Ю ха гр 1. д) зз = хзхг Ч хг(хзУ Ч хзхг) Ч хзх . е) зг = хзхг Ч хгхз Ч хзхз. 2.4. Указание. Представитьфункдию з' формулой в базисе (Ч, Й, — ). Если число букв окажется равным (, то построить схему по формуле.
Если число букв окажется больше, чем ) и формула не упрощается, то реализовать отдельные подформулы схемами и попытаться совместить куски полученных схем так, чтобы не возникало «ложных» цепей. Гл. Х. Реалиэаиия булевых функции схемами и формулами 409 Ц ( = хгхгхз Ч хг(сг Ч хз) 2) ф = хг Ч хгхз Ч хгхз. 3) У = хг(х~ Ч хе) Чх~хз. 4) у' = хг(хг Ч хз) Чхг(хгЧ хз). 5) г = хг(хг Ч хз) Ч х~хе. 2 5 Ц ф = (хг Ч хгхз)(х Ч хл). 2) ф = хг Ч хеЧ хз Ч хл, 3) 1 = хг, 4) г = (хг Ч хг)(хл Ч хв)(хз Ч хг) ° 3) г = хг Ч хеЧ хз Ч хл.
б) ф = хгхг Ч хгхз Ч хгхл Ч хгхг Ч хгхл Ч хзхг ° 2.7. Ц 1" = хгхг... х„Ч хгхг... х . 2) 1" = хгхг... х„ьхй„. 3) ф= хг бгхгй...(Эх„. 4)ф=(хм...,х„,ум...,у„)=Р„, где Р~=хгЧум Рлтг=хеуьЧ Ч Ря(хя Ч гул), Р„реализует перенос в (и Ф Ц-й разряд сумматора. 5) йх'") = 8б (хг г -хг ). 1« 2.9. См. задачу 2.6, Ц. 2.10. 3) Представив каждую из функций системы Ф совершенной д. н. ф., отождествим выходы схемы П„, соответствующие элементарным конъюнкциям, относящимся к одной функции. 2.12. 2) Покажем утверждение индукцией по и.
Нетрудно видеть, что я Ь(Уг ) = 2 < 2 ° 2 . По предположению индукции сугцествует схема — 1 для 11,"; г сложности, не большей чем 2 2г . Все функции ф(ха), не зависящие сущоственно от х„, реализованы в УЯ г. Если функция ф зависит от т,„существенно, то она представнма в виде У = х„д Ч х Ь, где д и л различные функции переменных хг, ..., х„г.
Если одна из этих функций (д или Ь) равна нулю, то отнесем 1 к классу Кг, в противном случае к классу Кг. Набавим к схеме 11„г по одной вершине гу для каждой функции ф из Кг О Лг. Если ф б Кг и имеет вид 1 = х„)г, то соединим вершину ив схемы У„" г контактом х„с новой вершиной ер Если ф В Кг и ( = х„д + х„л, то соединим вершины ив и иь схемы Сг„г с новой вершиной ее соответственно контактами х и х. Таким образом, добавляется всего [Л г [ + 2[Л г[ контактов. Ясно, что такое добавление контактов к схеме (г',", не вносит каких-либо цепей с ненулевой проводимостью в У„г и, следоваг тельно, не изменяет функций, реализуемых схемой ((,, Ясно также, что я в новых воршинах реализуются соответствующие им функции из Кг О Кг, и, значит, построена схема для У„. Оценим сложность построенной схемы.
г Имеем йь(ПЯ) < 1я((У„г) -1- [Кг[-1-2[К [ < 2 2 + 2[Кг[-Ь [Кг[ = 2 2 3) Выбирая щ = [1ояг(п — 21оя гг)[, получаем при достаточно больших и Л,([(х")) < Лг(оя „,)+ Ья(П„'') < 2 2 -""'"-"""'*"'+ г> гг~ -г~ лг ) 2"тг 2" '" г 2" +2 2 +, <4 —. п!одг(п — 21обг и) пг и 2.17. Ц Схема для Угь может быть получена по методу каскадов.
Эта схема имеет сложность, равную 2. Предположим, что схема для с1„. г подул -1 ченная по методу каскадов, содержит не более 2 2г контактов. Построим схему для (~У'. Множество )го ввршин этой схемы соатветствуот мнОжеству всех функций 1(х"). Вершины нз 1'о, соответствующие функциям 1 (х "), не 4)о Отеетьц указания, реюеноя зависящим от переменной х„, содержатся также и в Ъь Пусть Км Кз классы функций, зависящих от и переменных, определенные в решении задачи 2.12, 2).
Правило провеления контактов метода каскадов предписывает провести один контакт для каждой вершины, соответствующей функции 1 из Лы и два контакта для вершины, соответствующей функции ) из Кз. Таким образом, общее количество ребер, соединяющих вершины множеств 1 о и Ъ ц равно )К~ ~ + 2~Кз ~. Дальнейшие рассуждения повторяют решение задачи 2.12, 2). 2.18. Утнерждение вытекает из того, что для реализации всех конъюнкций по методу каскадов ~);~ = 2" ' (з = О, 1, ..., и) и из каждой вершины з-го яруса (О < 1 < л) в следующий ярус выходит ровно одно ребро. 2.19.
Доказательство отличается от предыдущего только том, что количество ребер, исходящих из вершины, отличной от полюса Ь, равно 2 при О < г < и — 2. При 1 = п — 1 из каждой вершины исходит одно ребро. 2.21. Пусть, например, схема Е представляет собой последовательное соединение некоторой двухполюсной схемы А и контакта х. Преобразуем схему Е, отбросив все контакты х и стянув в точку каждый из контактов х в А. 51сно, что функдия проводимости новой схемы Е' совпадает с прежней, а число контактов уменьшилось. 2.22.
Если схема Е не является сильно связной, то в ней имеется отросток. Отбрасывая его, мы не изменяем, очевидно, функцию проводимости. Поэтому Е не может быть минимальной. 2.2б. То, что Лк(л Ю у) < 4, вытекает из того, что существует схома для х 9 у (см. задачу 2.Ц сложности 4. Предположим, что минимальная схема для х чз у солержит менее четырех контактов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
