Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 83
Текст из файла (страница 83)
1) После применения правила обобщенного склеивания имеем Вт = = хтхгЧ хтхгхтЧ хгУзхл Ч хгхт Ч хтхзхл Н хтйзхл Ч хзхл. После применения правила поглощения получаем Вг = хтхг Ч хгхл Н хзхл. 2) хтхгхз Ч хтхгхл ЧУтхгУл Ч УтУЗУт НУгйзхл. 3) хт Н хг Ч хзН хл. 4) хзУ4 Ч Угхзхл Н хтйгхл Н хтхгхз Н хт бгхз Ч УтУгУл. 5) лтНУтхз Ч хзхл '' хгхз Н хтхгхл.
406 Ответы, указания, решенов 2.3. Ц хгхзЧхгхгхз. 2) хг Чхгхз 3) хгхгЧ хгхгхз. 4) хгУг Чхгхг Ч хгхз Ч хгхз Ч хгхз Ч хгхз. 5) хгхгхз Чхгхгхз. 6) хгхгхз ЧхгхгУ4 Ч хгхзхг. 2.4. Ц хгхз Ч хгхг Чхгхз Ч хгУз. 2) хгхз Ч хгхз Ч х~хг ЧхгУз'Ч хгхг Ч хгхз. 3) хг Ч хгхз. 4) хгхг Ч хгхзЧ хгхз. 5) хгхг Ч хгхз Ч хзхг Ч хгхзхз Чхгхгхз Ч х~хгхз. 6) хг:сг Ч Угхг Ч хгУзхг Ч хгУзх4 Ч хгхзУз Ч хгхзУ4 2.5.
Ц хг Ч хгхз. 2) Угхз Ч хгхз Ч хгхг. 3) тгхг Ч хгхз Ч х хз Ч хгхг. 4) хгхг Ч хгхз Ч хгхз Ч х~ хз Ч хгхз Ч хгхз. 5) хгхг Чхгхзхз Ч хгхзхг Ч хгхгхз Ч х~хзхг Ч Угхзхз. 6) хгхг Ч хгхз Ч хгхз Ч х~Уг Ч хгхз Ч вгтрк Ч хгхзхз. 2.6. Ц хзЧ хгхг. 2) УгУг Ч хгхз Ч УгУз Ч хейз Ч хгхг Ч хгхз.
3) хгхз Ч хгхг. 4) хг Ч хг ЧУз. 5) хгУ4 'Ч хгхз Ч хзхз Ч хгхз Ч хгхз Ч хгхг. 6) Угхз Ч хгхз Ч хзхг Ч хгхг Ч хгхз Ч хгхг. 2.7. Ц хг Ч хз. 2) хг Ч хгхз Ч хгхз. 3) хг Ч хгхз. 4) хг Ч хгхз. 5) хзхз г хгхг Ч хгхз Ч хгхзЧ хгхз Чхгхз Ч хзх4. 2.8. Ц хз, хгхг. 2) Ядреных импликант нот.
3) хгУз, Угхг. 4) хг, хг, хз. 5) хгхгЧ хгУз, хзхо 6) хгУз, хгхз. 2.9. Ц 2" '. 2) 2" '. 3) 6 2" ~. 4) к(гг — к). 5) 2" 6) й + (и — й)(п — 1 — Ц. 7) 2. 8) п(п — Ц, 9) 2". 2.10. Ц ( ). 2)(„) ( + ~). 3) Вытекает из задачи Ц. 4) Вытекает из того,что шш (й!)(и — Й вЂ” т)(т! = (Н!) (и — [ — ))!. 2.11.
Каждый интервал функции 1 однозначно определяется заданием любой пары противоположных в этом интервале точек. Эти точки, очевидно, принадлежат множеству 1Ч7. Поэтому число максимальных интервалов не превосходит числа неупорядоченных пар вершин (быть может, совпадающих) из множества йсу. 2.12. Ц 2" '. 2) 2" 'з. 3) О. 4) 1е(п — й). Указание. В любом максимальном интервале монотонной функции нижняя единица является собственной точкой того интервала, которому она принадлежит. 5) 2" г. Указание. Использовать задачу 1.9, 5) и то, что все интервалы имеют размерность О. 6) й. 7) 2. Заметить, что 7' = хг...хв Ч хг...х„. 9) 2в. 2.13.
Выберем для каждого ядрового импликанта функции Д(х") в точности по одной собственной точке. Рассмотрим все ребра куба В некоторого направления. Никакое ребро не может содержать двух выделенных собственных точек. Отсюда и вытекает утверждение. Гл. Х. Реализация булевых функций схемами и формулами 407 83 3.1. Ц а) Нет. 6) Па. в) Нет. 2) а) Нет. 6) Нет. в) Нет. 3.3. Ц Оьт = туЧ хе. 2) Лвт = В. 3.7. Ц т(Д = р(1) = 1.
2) т(1) = осг, рЩ = 2г 4) т(7) = 58, р(7) = б. 3.8. Указание. Оценка следует из того, что число элементарных конъюнкций над переменными хг, ..., х„равно 3", длина тупиковой д, н, ф. не превосходит 2" и ни одна из конъюнкций в тупиковой д, н, ф. не поглощает другую. 3.9. Указание. Верхняя оценка устанавливается по индукции.
3.11. Ц 2. 2) 2". 3.12. 3) Указание. См. задачу 5.17 гл. Ч1П. 3.13. 2",/и. Глава Х 1.2. Ц а) ((хг ~ хг) ~ (хг ) хг)) ~ (хг ~ хг). 6) (хг — э хг) э (хг -э хг). 2) а) ((хг 4 хг) 4 хг) 4 ((хг 4 хг) 4 хг). 6) хг 8сх . 3) а) (хг ~ хг)(хг ~ хг). 6) ((хму) х) у. 1.3. Ц а) хг Чхг. 6) хг ) (хг ~ хг). 2) а) (хг — э хг) й (хг — э хг). 6) ((хг 4 хг) 4 хг) 4 ((хг ~ хг) 3 хг). 3) а) ((хг ~ хг) ~ хз) ~ Нхг ) хг) ~ хз). 6) хгхгхз Ю (х1 ев Ц(хг Ю Ц(хз бг Ц. 1.4. Ц 7~ = хгхг., ггг = хг хг. 2) 7г = хгхг 9 хгхз Юхзхг, гтг = хг Ю хе 9 хз. 3) 1г = хг Чхе Ч хз, уг =хгхгхз. 1.6. Указание. Ц 7 = х Ч хгхз.
2) з' = хгхгЧ хгхз Ч ггхг. 3) 7 = хз(хг Ч хг) Чхг(хг Ч хз). 4) 1 = (гг Ч хе)(хг Чйз). 1.7. Указание. Ц 7 = хгхз Ч х1хгхз. 2) 7 = х>хг Ч хгхз Ч гзхь 3) ( = х1 Чхгхз. 1.8. Утверждение вытекает из того, что замена в СФЭ Е всех пометок Ч на 8с и 3с на Ч приводит к схеме Е*, реализующей двойственную функцию 7*. 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.8 схома Ез номинимальная. Таким образом, выход схемы Ез совпадает с выходом одного из элементов 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) г = (хг Ч хг)(хл Ч хв)(хз Ч хг) ° б) г = хг Ч хеЧ хз Ч хл. б) ф = хгхг Ч хгхз Ч хгхл Ч хгхг Ч хгхл Ч хзхг ° 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 = х„)г, то соединим вершину ив схемы У„" г контактом х„с новой вершиной ер Если ф В Кг и ( = х„д + х„л, то соединим вершины ив и иь схемы Сг„г с новой вершиной иг соответственно контактами х и х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
