Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 66
Текст из файла (страница 66)
будет ли функция ф(х!, О, хз, х!) обре!даться в 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.
Полагая затем, что 1(0, Ц=О,ибера в=у=2=О,получаем У(.((О, У(О, О) У(У(О, О), У(0 О))) = ХУ(О, Ц, У(1, Ц) = Х(О, П1, Ц) Отсюда, принимая во внимание условие задачи, выводим, что Д(1, Ц долж- но быть равно О. Но взяв х = 0 и у = 2 = 1, имеем .7Ц(0, У(1, Ц), ~(У(0, Ц, ~(0, Ц)) = 7(7(0, 0): ДО, 0)) = У(1, Ц = О. Это противоречит условию задачи. Следовательно, 7(0, Ц = 1. Аналогично доказывается, что и 1(1, Ц = 1. Значит, 1" (х, у) = х э у или 1'(х, у) = 1. Палее соотношения а) д) проверяются непосредственно (например, с использованием основных эквивалентностей).
2) Но вытеказот. Лостаточно рассмотреть функцизо 1"(х, у) = х у. 125.4) 7* =(х — 1У) — 1(уэх) =хЧУ4(уНх) =1=0; д=(хНУ) й 3е (у Ч х) = х — 1 у л О. Значит, д не двойственна к 1. 6) Не является. 8), 9), 1Ц Является. 1.26. 2) Пусть формулы й и 4В (над множеством 8) эквивалентны. Тогда в силу Определвния эквивалентности формул реализуемыЕ ими функции Равны, т.е. 1'Я = 1"х. Значит, 1"я = 1"в. ПРимвнЯЯ УтвеРждение Ц данной задачи, имеем уя = 1я.
и ув = ув*. Следовательно, ря* = ув-, т.е. Я* и 4В - — эквивалентные формулы. 1.27. Ц 1* = (х 1 Ч у (2 Ч 0)Н х у у)* = =(хЧО) ° (УЧХ (хЧУЧх)=х ° ((УЧХ) (УЧУ))=х (9642). 2) 7'" = хуЧ ху Чуя. 5) ~* = (х Фу) .з. 10) ~' = (х 'Н (я Ве)) у. 1.28. Ц Лве фиктивные переменные. 3) Одна фиктивная переменная. 5) Фиктивные переменные Х1 и хз. 1.29. 4) ( гн 1. 8) 7' гн 1. 9) ~ гн О. 10) 7 ов 1. Гв. й Способы забавна и свойшлви функций алгебры логика 329 1.30.
1) Существенных переменных нет. 3) Только хг. 9) ПеРеменные х1 и хг. 10) ПеРеменные хг, хз и х4. 1.31. 2) Достаточно рассмотреть функпию ага хг. 3) Возможно ди фихсированных переменных. 1.33. 1) У функции нечетное число значений, равных 1. Значит, все ее переменные существенные. 2) Все переменные существенные (так как, например, ио ~ о1, оо ф ог, ОЗ г О11 И Сдо д'- Од). 5) Лве существенные переменные - - хг и гз (оц = о,+1 (1 = О, 2, 4, 6, 8,10.,12,14); о»=одру (1=0,1,...,7); ос~од и оо~о4). 9) Три существенные переменные хг, хг и хд (оц = а,, 4 (1 = О, 1, 2, 3, 8, 9, 10, 1Ц). 1.34. 1) При и ) 3. 2) При и ф 3.
3) При и = 2т»- 1 (т в 1). 4). 6) При и ) 3. 1.37. Имеем гддогу — — (груд»(гдд П 1»сд)) С (гдуЦ»з71 П »Уд)). Значит, ) 4 д удод (: ( 1уу (» ) »Уу ( 2 ) »з71 С »Уу ) ° Так как (гудтд! нечетное число (см. условие задачи), то одно из чисел )»У7! и )447д( нечетное. НапРимеР, число )491). Тогда фУнкциЯ 1 обРащаетсЯ в единицу на нечетном числе наборов, и в силу задачи 1.31, 1) каждая переменная у 7" существенная. 1.38. Ц х»хг, хг Ч хо, хг — 1 хг, хг -д хг, х1 -д хг, хг — 1 хг, х1 Ю хг, хг х, хг~хг, хгйхг. 2) ~Р'(Хз)~ = 218.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
