Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 64
Текст из файла (страница 64)
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ь'(ьь, т,) -- число неприводимых СФЭ в стандартном базисе, реализующих функции переменных хь, ..., хн и имеющих сложность, не превышающую т,. Доказать, что ььь(п, т) < (с(п+ т))"тыь где с константа, не зависящая от и и гп. 2.42. 1) Доказать, что для всякого е > О и достаточно больших и существует булева функция 1(х") такая, что ь(У) > — (1 — е). 2) Доказать, что доля бь тех функций 1(х "ь)ь для которых неравенство из п. 1) не выполняется, стремится к нулю при п -+ со. 2.43.
Доказать, что для всякого е > 0 и достаточно больших п существует самодвойственная функция 1(х"), для которой: 2" 2" 1) Аь()) > — (1 — е); 2) А (() > (1 — е). п 1ойь и 2.44. Доказать, что для всякого е > 0 и достаточно больших и существует функция 1(х"), являющаяся суперпозицней функции уь(х, у, х) = ху ьс х и такая, что Ьф(,ь ) > С11 ь и 1(!ОК2 пГ (1 е) ОТВЕТЫ, у'КАЗАНИЯ, РЕШЕНИЯ Глава 1 1.1. 3) 205. 5) 2тт'+ 1.
7) 22тт'+ 2~т+' — 2'"+' -~-1 1.2. 2) (1110011Ц. 4) Если ги ) 4, то и = 2т '+ 2'" ' — 1. набор имеет внд (10~ ... 1Ц; при пг = 2 имеем (10), а при гл = 3 имеем (10Ц. т — ге 1.3. Ц (00110) 4 (0011Ц, (00110) 4 (10110), (01010) 4 (0101Ц 4 <1101Ц, (01010) 4 (11010) 4 (1101Ц. 1Песть пар соседних наборов, противоположных наборов нет. 4) Если гл = 2 и и = 4, то А = 1(101Ц, (110Ц,. (100Ц,. (011Ц, (0100), (0110)). Четыре пары соседних наборов и две пары противоположных.
Если т = 2 и п = 5, то А = 1(1011Ц,. (1110Ц, (1001Ц, (0111Ц, (0100Ц, (01110)). Две пары соседних наборов, противоположных наборов нет. Если пг = 2 и и ) б, то А = ((101 ... Ц, (1 ... 10Ц, (1001 ... Ц, (01 ... Ц, е — 2 ~ -2 ~ — 2 е — 1 (01001 ... Ц, (01 ... 10)). Две пары соседних наборов, противоположных — 1 — 2 наборов нет. Если гл ) 3 и п = гл -~- 2, то А = 1(10 ... 01Ц, (10 ...010Ц, — 1 — г (10 ...01Ц, 0110 ...01Ц, (010 ...0), (0110 т.,О)). Соседних наборов три — 2 — 1 пары, противоположные наборы будут только при гл = 3 (одна пара).
Если т)3 ил)пг+2,тонмеем (10...01 ...1)4(10...01...1,ивтехслу— 1 чаях, когда п — т = 3 или п — пг = 4, (010... 01 ... 1) ~ (01 ... 10... 01Ц. т 1 — — 2 — — 1 т — 2 Соседние наборы (10...01 ... 1) и (10 ... 01 ... Ц, противоположные — -1 -1 (10 ... 01 ... 1) и(01 ... 10 ... О) при и = 2т — 1 (т ) 4), (10 ... 01 ... 1) — 1 — — 1 — — 1 и (01 ... 10 ... О) при п = 21л (т ) 3). Гв. Й Способы забавил и свойства функций алгебры вовики 325 1.4.
Ц („). 2) 2" . Есди Н"=(ог,ог,...,п ) и и(сс"))2" ', то о!=1. 3) и 2 . Число наборов соседних с (ог! ог, ..., о„) равно п. 4) !! с!2". Любой набор !3", отстоящий от фиксированного набора Н" на уп1 расстоянии Й, получается из Н" подходящей заменой некоторых Й компонент на противоположные. 5) 2~. 6) 2" — 2'. Если,З' и у" отличаются в компонентах с номерами гг, ..., г!, го число различных наборов Н", удовлетворяющих условию, равно числу 2 минуС число всех подмножеств мнОжества (гг, ..., г!). 7) 2ш, Справедливы соотношения 0 ч огг~-! < 1 и огге! + огг+г = 1 О=0,1,'...,т-ц.
Сп — г(Й вЂ” Ц! 8) ( у!. Искомое число Равно числУ набоРов длины и — г(Й вЂ” Ц, имеющих вес Й. 1.5. 3) Рассмотреть множество В;"„7гр 4) В таком подмножестве есть наборы одинакового вежа. 5) Набор )уп не сравним с набором Н" тогда и только тогда, когда Д! = 0 для некоторого 1 6 (гг, ..., г!) и Д = 1 для какого-либо 1 ф (г! ! ... ..., гз), где гг, ..., г! — номера всех единичных компонент набора Н". 6) Найти число наборов у", не сравнимых с наборов Н", но сравнимых с набором Д". Затем вычесть полученное число из общего числа наборов у", не сравнимых с Н".
1.6. Ц 2г '. 2) 2 (!"сг1). 3) 2г . 4) 2. 1с 2" =о 1.7. Ц 1Ч, = ((ООЦ, (100), (1ОЦ, (ПО), (П Ц). 4) Л, = ((ОООЦ! (ООП), (01ОЦ, (ОНО), (ОШН, (1000), (1ООЦ, (1010), (101Ц, (1110)). 5) ун, (х' ) = хгхг(хг Ч х4 Ч хз) Ч хгхз(х4 Ч хз) Ч хгхз(х! Ч хз) Ч Ч хгхз(х! Ч хе ~ хз) Ч к!хгх4. Ситуация, когда будут приняты обе гипотезы, возможна (это соответствует наборам (01100), (1000Ц и (1100Ц). 6) Полагая, что х, = 1 тогда и только тогда, когда В, участвует в заседании комиссии (!' = 1, 2, 3, 4), запишем условия а), б) н в) с помощью булевой функции 1(хй~). Имеем ф(х~) = хгхгхз Ч хгхзх! Ч хгх!. Рели Вг в заседании не участвует (т.е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
