Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 65
Текст из файла (страница 65)
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(хй~). Имеем ф(х~) = хгхгхз Ч хгхзх! Ч хгх!. Рели Вг в заседании не участвует (т.е. если хг = 0), то обязан ли быть на заседании Вз, т.е. будет ли функция ф(х!, О, хз, х!) обре!даться в 1 на каком- нибудь наборе вида (цг, О, О, о!)7 Так как ~(хг, О, хз, х!) = хгхз Ч г:гхе, то 7(х!, .О, О, х!) = хгх4 и, значит, 1(1, О, О, Ц = 1. Следовательно, Вз также может не участвовать в заседании. 7) При условиях, указанных в задаче., проект может быть не принят. 1.8.
Ц .9), 1Ц, 12) Не является. Добавляя скобки, можно превратить в формулы выражения Ц, 2), 4), 8), 1Ц и 12). 1.9. Ц вЂ” 5), 8) — 10) Не является. Набавляя скобки, запятые н переменные в формулы можно превратить только выражения 4) и 5). 326 Ответы, указания, решения 1.10. Ц х, у, у, х, «, (х у), .(чу), (ху«), (((у) в (хц«)), А. Указание. См. замечание, следую(цее за определением 2 (в и. Ц. 4) Ь( г(1, х), 1, д(И(х), д(И(Ц, р(Ю(1, у, д(И(Ц), У(И()г( г(1, х), р(И(1: у, д'И(Ц), д(И(х)).
». 5) д(г((х — з у). 1г(И(«,Ч«у), .4. 1.11. Ц Пятью способами. 3) Семью способами. 5) Тремя способами. б) Девятью способами. 1.12. 3) Индуктивный шаг. Для обозначения произвольной двуместной связки из б используем символы и ю Пусть утверждение верно для формул, сложность которых не превосходит 1 (где 1 ) Ц, и рассмотрим формулу й, имеющую сложность, равную 1 4 1. Тогда либо й = (З З), либо й = (З «), где ц ю'((ч) и сложности подформул З и б небольше 1. Если Й = (з З), то З имеет сложность 1 ) 1 и, значит, З = (ч Зг) или З = (Зг * Зз), где * = ю'((ч), поэтому й = (ч(з ЗгИ или Й = = (з Зг «Зз)). По индуктивному предположению в подформулах (з Зг) и (З««З«) двух связок, стоящих рядом, быть не должно.
Значит, таких связок нет и в формулах (з(з Зг)) и 1(З« * Зз)) (две «внешние» связки ч в формуле (ч(з Зг)) разделены скобкой). Если Й = (З «), то возможны случаи: а) З=х, б=(чб(); б) З=х, б=(б««бз)! в) З=(зЗ(), б = х; г) З = (ч З(), б = (ч б~); д) (ч З(), б = (б««бз); е) З = =(З *Зз), б=х; ж) З=(З *Зз), 4=(чб); 3) З=(З * З), б = (Фз «гбз). Здесь х обозначает произвольную переменную и *, *и «« принаплежат 6'(( з). Сложности подформул З и «не превосходят 1. Следовательно, в силу индуктивного предположения связок, стоящих рядом, в них нет. Остается показать, что «внешняя» связка формулы й = (З 4), соединяющая подформулы З и ц, также не стоит рядом ни с какой другой связкой.
Но это вытекает из того факта, что его подформула З (соответственно (г) отлична от поремонной, то между любой связкой, содержащейся в подформуле З (или б), и «внешней» связкой находится хотя бы одна скобка. 1.13. Ц Доказательство можно провести индукцией по сложности формулы. Через 1п(( (иб й) обозначим индекс связки иг в формуле й.
Индуктивный шаг. Пусть утверждение справедливо для формул, имеющих сложность, не превосходяшукг 1 П ) Ц. Рассмотрим формулу й со сложностью, равной 1+1. Возможны случаи: а) й = (ч З); б) й = (З б). Разберем случай б). Каждая связка иг из подформулы З (если З отлична от поременной) имеет в формуле й индекс, на единицу больший индекса той же связки в формуле З, т.е. (пс((иг, Й) = 1+ (пб(иг, З), а значит, !п(((иг, Й) ) 2. Далее, так как число левых скобок в любой формуле равно числу правых скобок в ней (см. задачу 1.12, 2))., то «внешняя связка» в формуле й имеет индекс 1, а для всякой связки иг из подформулы б (если б не является переменной) выполняется неравенство (п(((иг, Й) ) (пб (, й), так как подформула б начинается с левой скобки.
1.15. 2) См. рис. 0.1.1. 4) См. рис. 0.1.2. 5) См. рис. 0.1.3. 7) См. рис, 0.1.4. 1.16. Ц (((О Ю (х 9 (уМ х)))(гх) Й (уф ИЗ х) — З Ц)). 3) г"(И(д(Ю(1, 1«(И(~, у), Зг~ц(х))., 2, 1г(Ю(~, Зз(И(7«(Ю(~, Зг(И(л(И(2, х)))). б) у(И(((З х) З ц, Л(И((Ч х), ц, (З д(И(1, ((зг((хде у), 1, Л(И(х,. х))))). Гл, й Способы задания и свойства функций алгебры логики 327 х у х г Рис.
0.1.1 Рис. 0.1.2 0> (з> лп у у у х у Рис. 0.1.4 Рис. 0.1.3 1.17. 2) Вектор значений функций имеет вид (11111110). 3) Вектор значений функций таков: (10000100). 6) Вектор значений функции выглядит так; (0111111Ц. 1.18. 2) сеь = (010Ц, 4) Йь = (1001001Ц. 6) оь = (110001101100010Ц. 1.19. 2), 6), 9), 10) Эквивалентны. 3), 7) Не эквивалентны. 1 21.
4) й= (х Ч у Ч (х г)) . (х (у Ч г Ч х Ч уД = (х Ч р Ч хг Ч хр) 3с 3с(х Ц=(хЧуЧУ) х=х; З=х" урлЧх=хргЧх=х. 9) Й = (х Ч ууЧ хЧ уг) . (х Ч (у г)) = (х(у Ч Ц Ч х(у Ч 2)) ~(х Ч угЧ Ч р г) = (ху Ч хе Ч х г) (х Ч уг Ч у г) = х (х. Ч ргЧ ур) = х; Ж = ((х Ч у) (у Ч х Ч г)) Ер хуг = ((ху Ю х со у) Ву хуу) ~р хуг = = ху 61 у 61 х 61 у Ю ху = х. 1.22. Ц При решении задач такого типа (связанных с полным или частичным перебором элементов некоторого множества) бывает удобно (и даже необходимо) упорядочить и просматривать элементы данного множества по возрастанию (или убыванию) какого-либо подходящего параметра.
Перебор можно уменьшить путем выявления дополнительных свойств исслелуемых элементов. В нашей задаче перебор можно вести по сложности суперпозиций (формул) над заданным множеством Р. Под сложностью суперпозиции можно понимать, например, число связок в ней или число «шагов» в ее построении. Булевы функции, зависящие от переменных из множества (х, у) и являющиеся суперпозициями над множеством (и1 — э из, и1 из), исчер- 328 Ответы, указания, решения пываются функциями: ~~(х) = 1, .142(х) — = х 142(у) — = 1 А(у) = у х 1у уэх, х.у, ув(х,у)=1, ~э(х,у)з— в х Ьо(х,у)— = У; ХНУ х-у. 2) Функции такие же, как в задаче Ц. 3) Все функции, кроме одной, порождаются за «два шагал.
Всего 16 функций. «Три шага» требуются для построения функции 1(х., у) = 1. 4) Все функции (их восемь) порождаются за «два шага». 5) Все функдии (их 12) строятся за «два шага». 6) 24(х) = х~ 12(у) = у, 23(х~ у) = х, 24(х, У) = у, зз(х~ У) = х ' У, ув(х, у) = х Н у. «Лва шага» нужно только для порождения функции ув(х, У).
7) 71(х) = х., 12(у) = у, уз(х, у) = х, 14(х, у) = у, рв(хз у) = х у. Все функции порождаются за «один шаг». 1.23. Ц Глубина формулы й равна 3, но формула (х — 1 х) ор (х 6Э у) реализует ту же функцию и имеет глубину 2. 2) Рассмотреть формулу (х Н у) (х у). 3) Рассмотреть формулу (х ~ х) ~ (у ~ У) 4), 5), 7), 8), 10) Глубина минимально возможная. 6) Рассмотреть формулу х (х э у). 9) 1'дубина формулы равна 2. 1.24. Ц Предполагая, что 1"(О, 0) = 0 и беря х = у = х = О, имеем 1(1(О, 7(0, 0)) 1(1(О, 0), Д(0, 0))) = 7Ц(0, 0), ДО, 0)) = ~(0, 0) = 0 Это противоречит условию задачи. Значит, 1(0, 0) = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
