Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 64
Текст из файла (страница 64)
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. Доказать, что для каждого натурального т существует минимальная схема сложности т,. 2.28. Доказать, что если к минимальной схеме присоединить контакт, помеченный новой переменной, так, чтобы получилась сильно связная схема, то построенная схема также будет минимальной. 321 у" е. Кони/внтные схемы и формулы 2.29. Пусть А~~(ф) минимальное число контактов в схеме Ху, составленной из замыкающих контактов и реализующей монотоннукг функцию ф/ и т(хз) = хгхг У хгхз У хзхы 1) Привести примеры двух схем сложности 5 из замыкающих контактов, обладающих неизоморфными сетями и реализующих пг(хг). 2) Показать, что Ц(т(хз)) ) 5.
3) Показать, что во всякой схеме Х из замыкающих контактов, реализующей т(хз)/ найдутся переменные хб х такие, что для каждой из них в Е присутствуют не менее чем по два контакта с пометками хб х,. 4) ПУсть Ьч = хгхз, Ьг = хлхз и ф(хз) = т(хы йы Ьг). Показать, что ц(дхв)) = 8. 5) Показать/ что Ьь(Дхз)) < 7. Пусть двухсвязная двухполюсная контактная схема Е является плоской (т.е. ее сеть Г(а, Ь) является плоской) и ее полюсы а и Ь лежат в одной грани. Проведем в этой грани ребро (а, 6) так, чтобы сеть Г',полученная из Г добавлением ребра (а, 6)/ осталась плоской.
Выберем в каждой грани сети Г' по одной вершине. Построим на выбранных вершинах граф С*, двойственный к графу С сети Г'. Каждое отличное от (а, 6) ребро графа С* пересекает некоторый контакт схемы Е. Наметим это ребро той буквой, которой помечен пересекаемый им контакт. Вершины графа С", расположенные в гранях — /' и Рис. 10.10 сети Г', разделенных ребром (а/ 6), обозначим через а*, Ь" и назовем полюсами. Удалим ребро (а*, 6*) из С'. В результате получится двухсвязная схема Е* с полюсами а' и 6'.
Схема Х* называется схемой, двойственной к Е. На рис. 10.10 проиллюстрирован процесс построения двойственной схемы. 2.30. Для схем, указанных на рис. 10.11, построить двойственные. 2.31*. Показать, что контактная схема Е', двойственная к Е, реализует булеву функцию, двойственную к функции, реализуемой схемой Е. 2.32. Показать, что для всякой булевой функции ф такой, что 11 (г') < 7, выполняются равенства ть(У) = ьь(1 ) = ьь(У).
322 Гл. Х. Реализация булевых функций схемами и формулами а у у ° Ь а у Я. ',ь Рнс. 10.11 2.33. Доказать, что для всякой булевой функции у выполняется равенство Т,„Я = А„(Г). 2.34*. Пусть у функция, реализуемвл схемой, указанной на рис. 10.12. Доказать, что функция, двойственная к уь не может быть реализована бесповторной схемой. 2.35. Верно ли, что для всех булевых функций 1 выполняется равенство Тя(У) = Ть(У)7 и 2.36.
Доказать, что для всякой фор- мулы Ф в базисе (ьс, Й, — ) существуРис. 10.12 от эквивалентная ей формула той же сложности, в которой отрицания стоят лишь над переменными. 2.37. Доказать,что для всякой булевой функции у выполняется равенство Твь()) = 1,„()). При получении нижних оценок сложности реализации различных классов функций схемами и формулами часто используются так называемые «мощностные соображения». Примером может служить следующее утверждение. Пусть Я(п, тд) число схем из некоторого класса К, каждая нз которых реализует булеву функцию, зависящую от переменных хы хз, ..., х„ь и имеет сложность, не большую чем ьп. Пусть со(п) число булевых функций 1"(ха) в некотором множестве 0Л.
Тогда если Я(п, ш) ( ьр(п), то в 0Л найдется функция у(х")ь не реализуемая в классе К схемой сложности, меньшей или равной тп. 2.38. Показать, что число Я(п, пс) связных попарно неизоморфных контактных Х"-схем, имеющих сложность не больше ш, не провосходит (опт)ьо, где с -- константа, не зависящая от и и пь 2.39. Показать, что число Р(п, т) связных попарно неизоморфных я-схем сложности не больше гп, реализующих булевы функции переменных хы хз, ..., х„„не превосходит (сп)™, где с -- константа, не зависящая от и и т.
у" 2. Конпьантные схемы н формулы 323 2.40. Показать, что число 4ь(и, т) попарно различных формул сложности не большей т, над множеством связок ('ьь, 3с., — ) и множеством переменных хь, хз, ..., и, не превосходит (сп), где с —— константа, не зависящая от п и т. СФЭ называется неприводимой, если каждая ее вершина принадлежит некоторой ориентированной цепи, соединяющей один из входов с выходом схемы. 2.41. 1) Показать, что для каждой булевой функции 1 существует неприводимая схема, реализующая 1. 2) Пусть 1ь'(ьь, т,) -- число неприводимых СФЭ в стандартном базисе, реализующих функции переменных хь, ..., хн и имеющих сложность, не превышающую т,. Доказать, что ььь(п, т) < (с(п+ т))"тыь где с константа, не зависящая от и и гп.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
