Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 83
Текст из файла (страница 83)
Лля каждой пары координат произвольного из этих блоков возьмем вектор из Вл г, имеющий нули в этих координатах. Множество Р получаемых таким образом векторов имеет мощность 4+11 т( ) +1! — 1 — г)( ). Покажем, что для каждого В из В,", т существует т3 из Р такой, что В < т3. В самом деле, поскольку число нулей в В равно 1, а число блоков равно ! — 1, то некоторый блок содержит некоторые дво нулевые координаты. В Р содержится вектор тз, имеющий нули в этих координатах. Ясно, что а < Д. 1.19. 1) 2. 2) 2. 3) 4.
4) 3. 5) 3. 6) 3. 1.20. 1) и. 2) п — 1. 3) л — 1. 4) и. 1.21. Указание. Два столбца матрицы М различаются в бнй строке тогда и только тогда, когда ф-я строка матрицы Мт ! покрывает сумму по модулю 2 этих столбцов. 1.22. Ц, 4), 5), 7) Ла. 2), 3), 6), 8), 9) Вообще говоря, нет.
1.23. Если матрица составлена менее чем из !об. л строк, то число попарно различных столбцов меньше и. 1.24. Пусть А и В тупиковые тесты матрицы М с тл строками. Тогда ни одно из включений А с В, В с А не имеет места. Отсюда вытекает, что число тестов не превосходит числа попарно несравнимых наборов в В'", а т значит,не превосходит , , )). ,~ ит!'2 1.25. Число матриц размерности /т х и с попарно различными столбцами равно 2ь12 + 1)...12я — и+ 1). Число матриц размерности тл х п, у которых фиксированные й строк заданы, равно 2"т 1.26.
1) 11, 2), 11, 4), 12, 3), !3, 4). 2) 11, 2, 3), 11, 2, 4), 11, 3, 4). 1.27. !Э.Ш. Коспанов.) Если в матрице М с попарно различными столбцами расстояние между любыми двумя столбцами не меньше т), то в матриде Мтгт каждый столбед содержит не менее т! единиц.
Теперь утверждение вытекает из задач 1.21 и 1.12. 2.1. Ц хт,хгхз. 2)хтхг. 3)хгхз, хтхгхт. 4)хт. 2.2. 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) Покажем утверждение индукцией по и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
