Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 67
Текст из файла (страница 67)
Пусть А предполный класс замхнутого хласса К. Это означает по определению, что [А] ~ К и [Аст'(1)] = К для всякой функции 1 б К'тА. Предлотюжив, что А не является замкнутым, имели бы [А]ттА ф О. Но тогда, с одной стороны, [А 0 ([А]'1А)] = К., а с другой стороны, А С1 ([А](А) = [А] и [[А]] = [А] в силу замкнутости [А].
Пришли к противоречию. 1.9. Ц, 3), 5), 7), 8), 10) Множество А является замкнутым. 2), 4), 6), 9) Множество А не является замкнутым. 1.10. Ц (0]., (1), (1, О). 2) Кроме классов п. Ц еше [О, х], [1, х], [О, 1, х], [х], [О, х], [х]. 3) а) [ху]; б) х бт у, х у]. 1.12. Ц Система (х, ху, х Ч у) является полной в Рг, поскольку всякая 1 б Рг может быть представлена в виде д.н.ф. или к.н.ф. С другой стороны, х=х4х, ху=(х(х)ф(уфу), гЧУ=(хфу)ф(хфу). 334 Ответы, указания, решения 2) Имеем 0 = хх «9 х, ху = ху 6«0, х = (х х) б«х. Система (х, ху) полна, поскольку х Н у = х у.
3) Имеем к=хи«хВОх, хНу=х — «у, ху=х — «у. 4)Имоем 0=1(х,х,х), х=х — «О,. ху=х — «у. 5) Имеем х =хб«06«1, ху=т(х, у, 0). 1.13. 1) Кг С Кг. 2) Вообще говоря, Л«,7Кг. Рассмотреть Аг = (х, ху), Аг = (х, х О«у). Ф 1.14.
1) Например, К« = (0), Кг = (Ц. 2) Например, Л« = [х, 0], Лг = [х, Ц. 3) Кг = [О, х], Кг = [О, 1, х]. 1.15. Ц Мг = [О, 1, х], Мг = [х] предполные в К. 2) М« = (0), Мг = (Ц. 3) [х]. 4) [х«йу«рг]. 1.17. Пусть К - — предполный класс в Рг. Если х ~ К, то в силу пред- полноты К имеем [К С (х)] = Р . Но в силу 1.7 и 1.1б имеем [К С (хИ = = К С (х). По условию х]у ф [Л], а значит, х ] у ф Л С (х) = Рг. Противоречие.
118. Пусть 1(х") не является константой Если «(х, х, ..., х) С (х, х], то на «, очевидно, можно получить х. В противном случае «(х, х, ..., х) б б (О, Ц, Пусть для определенности ((х, х, ..., х) = О. Поскольку [(х"') х Х О, то существует набор о = (аг, ..., а„) такой, что 1(Н) = 1. Заменим в 1 переменную х, на х, если сп = 1, и на у, если л, = О. Тогда получим функцию д(х, у). Ясно, что д(х, у) б (ху, х Ж у) и что х б [д(х, у)]. 1.19. Предположим, что Рг = Кг С Кг С...
С К,, где К, непустые попарно непересекаюгциеся замкнутые классы. Тогда существует г такое, что х ] у б Л;. Но тогда К, = Рг в противоречии с тем, что в ) 1. 1.21. Утверждение вытекает из 1.18 и из того, что система, содержащая функцию х, не может быть расширена до базиса. 1.22.
Указание. Провести индукцию по числу вхождений связки — « в формулу, реализующую функцию 7" б [т — «у]. 1.23. Указание. Использовать задачу 1.22. 2.1. В задачах Ц, 3), 4), 8), 10) функция 7" самодвойственна. В задачах 2), 5) — 7), 9) функция 1" на является самодвойственной. 2.2. В задачах Ц, 3), 5) 8) 7 б В. В задачах 2), 4), 9), 10) 7" 7 В. 2.3. Ц (1100). 4) (0110100Ц.
8) (1001000011110110). 2.4. Ц 7(х,х,х) = 7(х,х.,х) = 1. 2) ](У,х,х) = 1. 2.6. Куб В" разбивается на 2" ' непересекающихся пар противоположных вершин. В каждой такой паре самодвойственная функция 1'(х") обращается в 1 ровно один ра.з. Контрпримером к обратному утворждению является функция х г Ю хе 2.8. Ц, 3) г (х") б В при нечетных п.
2), 4), 5) ~(х") ф В при всех п ~ 3, Дхз) б В. 6) г(х") «с В при всех п = Зй. 2.10. Необходимость. Пусть 1 = х«7« Н хгув. Тогда 7' = (х«1« Н хгув)* = (хг Н (г«)') вг (хг Н (го)*) = = х«(гв)" Н хг(Л')" Н ((в)" (~г')' = хг(г«в)* Н хг(1г')*. 335 Гл. П. Замкнутпыс классы и полнота В силу того, что т' б Я, имеем ) = ), и, следовательно, хт(уо) ттуйт(Л) = хтут ттутуоЦ Полагая х~ = 1, а затем х~ = О, получаем отсюда, что (уо)* = ут' и (т"')" = ~~. достаточность.
Пусть ()т)* = тоЦ Отсюда вытекает., что = ((Л ) ) = (Уо),и, следовательно, 7 = х1 ус 'т Этус = хт(уо ) р бт ( ут )* = (хт утт тт Эт тот)" — т* 2.11. Верно. Вытекает из задачи 2.10. 2.13. 1 является супорпозицией самодвойственных фунхций ш(х ), ут и ут. 2.14. Пусть у ф Я. Требуется доказать, что [(1) О Я = Рт. Имеем (х, х) С Я. Из леммы о несамодвойственной функции вытекает тогда, что (1, О) С [(х, х, т")). Известно, что [х, ху, х т117) = Рт. Отсюда следует, что [О, 1, х 10 у От э, т(хп у, х)) = Рт, ибо Э = х тЭ 1 <Э О, ху = тп(х, у, О), х тту = т(х, у, Ц. Имеем Рг С [О, 1, т От у Ю э, тп(хук)) С [(х, х, тт) О Я) = [(тт) О Я). 2.15. Верно для п = 1, 3 и не верно для остальных натуральных п.
2.16. Ц Из условий этой задачи и из задачи 2.10 следует, что уо = ут'. Но тогда т не зависит сушественно от хп 2) Утверждение остается верным. 2.18. Ц 11етрудно получить все функции т б Я, зависящие не балов чем от трех переменных (см, задачу 2.9). Если для некоторого и все самодвойственные функции 1(х" ) получены, то с помощью представления из задачи '2.17 получим любую функцию Д(Э") из Я.
2.19. В задачах Ц, 3), 5) 7), 10) множества М являются самодвойственными. В задачах 2), 4), 8), 9) множества М не являются самодвойственными. 3.1. Ц, 4), 7), 10) У' ф Ь. 2), 3), 5), 6), 8), 9) 7' б А. 3.2. Ц, 3) — 5)., 7) — 10) т" б Ь. 2), 6) 1 й Ь. 3.3. Ц Имеем ( = ахт Э бхт ~Э с, )'(00) = с = 1, )'(ОЦ = 6 Ю с = О, т'(1Ц = а От б 8 с = 1. Отсюда т" = хт тЭ хз 9 1, оу = (100Ц. 2) 7 = хо. 3), 4) У = хт Э хз <В хз щ 1. 5) ~ = хз тЭ 1. 6) т = х~ ~Э хт. 9) т = х~ бт хз бт хл От 1.
10) 7 = х~ тЭ хз От хт ОЭ 1. 3.4. Ц ((х, .у, у) = ((х, у., Ц = ху. 2) 7(х, у, у) = ху. 3) ((хб у, 0) = х у. 4) 7(х, 1, у) = ху. б) ~(у, О, 1, х) = ху. 6) 7(у,х,у,у)=ху. 1Ц((х,х,х,у)=ху. 12) 7'(х,1,у, Ц=ху. 3.5. Ц, 4), 7), 9) Нельзя, так как [1ту[ < 2. 2) ху = Дх, у, Ц. 3), 8), 1Ц Нельзя, так как т" б А. 5), 6) Нельзя. Указание. Подстановка констант и любое отождествление переменных приводит к уменьшению числа нулей. 3.6. Ц Пусть от, ..., о„т -- произвольный набор значений переменных хт, ..., х т.
Тогда 1(от, ..., оо т, х ) = х„Ю Зт(от, ..., о„т). Отсюда ясно, что т" (от, ..., о„т, О) ф 1"(от, ..., о„т, Ц. 336 Ответы, указания, решения 2) Представим функцию в виде х„6(х" ) Ф д(х" ). Так как У существенно зависит от х„, то 6 х О. Предположим, что 6 х 1. Тогда существует набор а = (оы ..., а з) такой, что 6(а) = О. Но тогда З" (оы..., а 0) = Длы ..., о„ы Ц = д(Н), что противоречит условию. Таким образом, 6 = 1,что и требовалось доказать. 3) Указание; Значение Д(0) и условия однозначно определяют ее значения на В".
При этом на наборах четного веса значение функции совпадает с Д(0), а на наборах нечетного веса противоположно ему. Такова функция хз ф, .. Ю х„бЗ Д(0). Представление единственно. 3.7. Ц, 2) Вытекает из задачи 3.6), Ц. 3.10. 2('6). 3.11. 2" 3.12. Функция хз -в хг нелинейна. Если 1 6 Ь, то хз — > х = з (хы хз, О....., 0) 6 Ь. Пришли к противоречию. 3.13. Предположим, что у 6 Ь.
Тогда 1" = хз Ж... Озх Ющ л 6 (О, Ц. Из условия ((хы О, ..., 0) ф 1(хы 1,..., Ц следует, что и четно. Пришли к противоречию с условием. 3.14. В силу нелинейности функции 1 существуют такие з и у, что 1 = х,х,узах,рз Ю хзрз|3 рю гце. функции р (т = 1,..., 4) не зависят от з и д и р1 ф. О. Пусть й = (оы ..., о, ы о,.~.ы ..., Оз.-ы азьы ... ..., еы) набор такой, что ззз(а) = 1. тогда ф(х„хз) = з"(оы ..., о, х„а,+ы ..., а, ы хз, азе м ...., а„) нелинейна. 3.15. Пос та т о чн о с т ь, Пусть функция 1(х") такова, что в В" найдется специальная четверка наборов Й, )з, у, д такая, что функция 1' принимает на этих наборах значение 1 нечетное число раз.
Положим х = о если тбАз.Еслиже тбАытопусть хы=х при 7ы=1и х =у при у = О. В результате такой подстановки из 1 получается функция 7з(х, д) такая, что р(1Ц = з"(а), р(00) = з"(Д, р(10) = з" (7), р(ОЦ = з'(6). Ясно, что Зз(х, д) ф Ь. Необходимость. Вытекает из 3.14. 3.16. Указание. Используя 3.14, доказать существование грани размерности 2, на которой функция обращается в 1 нечетное число раз. Из того, что ~6ер~ = 2", вывести существование двух граней таких, что на одной из них функция обращается в 1 один раз, а на другой три раза. 3.18.
Ц С помощью супврпозиции из функции з1 еэ хз можно получать любую функцию вида хн В х„бэ... 9 хею путем подстановки 1 любую функцию вила хн Ю х„й... Ю хм б 1. Система А является базисом. 2) 5), 7) 9) А является базисом. 6), 10) А не является базисом. 3.19. Пусть 1 6 Ь.
Если 1 зависит существенно от нечетного числа переменных, то 1' б В П А. Если З" зависит существенно от чотного числа переменных, то либо з'(О) = 0 и 1 у ((1")), либо ДО) = 1, з" (1) = 1 и 0 ф ((з")). 3.21. Среди функций уы зг, уз хотя бы одна является нелинейной, поскольку сущеСтвуют лишь две линейные функции, существенно зависящие от хг и хз. Кроме того, каждая из этих функций не является самодвойственной. Подстановкой х и х на места переменных несамолвойственной функции 1 получаем константу. С помощью отрицания получаем вторую 337 Гл.
П. Зомкнун~ыс классы и ооляоти константу. Подстановкой О, 1, х, х, у, у из нелинейной функции получаем функцию вида ху 63 а. Имеем [(х, ху 63 о)] = Рз. 3.23. Функция представима в видо 3' = хуя Ваху-~-13хх СО уях Ю1(х, у, л), где а, 13, у принадлежат множеству (О, Ц, а 1(х, у, з) 6 Ь. Если а = (3 = у = 1, то Д(х, у, у) = ху 191з (х, у), где П 6 Т. Если а -'; )3 4- у = 2 и, например, а = О, то 3'(х, х, .у) = ху 6312(х, у), Ь 6 Ь. Если а -1-33-~- у < ( 1 и, например, а = )3 = О, то 3(х, у, у) = ху Ю1з(х., у), 1 6 Ь. 4.1 Ц, 3), 4)., 6), 8), 9) 3 6 Тз~,То 2), 5), 7), 10) 3 Ф Тз(То.
4.2. Ц, 2) При четных п 3 2. 3), 4) При и = 2, 3 (шоб 4). 5), 8) При всех и ) 2. 6), 7) При всех четных и. 9), 10) При всех натуральных и х 3 (шоб 4). Указание. (2) нечетко при и = 3 (зпоб 4). уо1 4.3. Ц 22 з. 2) — 22 . 3) 2'. 4) 22 '. 5) 22 -> 2". 6) 2". 4 7) 22 -~- 2" '. 8) 2" '. 9) 22 ' 3- 22 ' -~- 2" 10) — (22 + 2"). 15) О. 2 4.4. Указание. Если 3' 6 Т Сз Я, о 6 (О, Ц, то 3' 6 Т вЂ” Сз Я; если 3 6 6 1 О Уо СЗ Т,, то 3 6 Я.
4.5. Ц ху = (х Ч у) Ж х Ю у. Палее см. пример 3. 2) Указание. Использовать пример 3 и то, что То — — Ты 3) Указание. Свести к 2). 4) У к а з а н и е. х 63 у = хх Ф у, ху = (ху Ф я) Ф я. Палее см. пример 3. 5) Полинам всякой функции из То О Тз содержит нечетное число слагаемых и не содержит 1 в качестве свободного члена. С помощью функций ху, х Ф у Ю я любой такой полинам можно построить. 6) См. 5). 7) Указание. Всякий многочлен не выше первой степени и не содержащий слагаемых, равных 1, является суперпозицией функции х 63 у. 4.6. Ц Ла.Имеем 1=ах х, х у=их у, хФуФя=(х у) х, ху = ху 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
