Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 17
Текст из файла (страница 17)
Показать,что линейная функция является самодвойственной тогда и только тогда, когда она существенно зависит от нечетного числа переменных. у 4. Классы функций, сохраняюидих нонстаннды 71 3.10. Найти число линейных функций у(хн), существенно зависящих в точности от й переменных. 3.11. Найти число линейных функций 1(х") таких, что у(0, О, ... ..., 0) = 1(1, 1, ..., Ц = 1. 3.12.
Пусть 7'(хд, хг, О, ..., 0) = хд -э хг. Показать, что у ф В. 3.13. Пусть у" (х, О,, О) ф у(хд, 1, ..., 1), у" (хн) существенно зависит от всех переменных, п печатно. Показать, что у ~ Ь. 3.14. Пусть у"(хн) ~ В, Локазатдн что подстановкой констант вместо некоторых п — 2 переменных можно получить нелинейную функцию от двух переменных. 3.15.
Специальной, назовем четверку наборов а, (1, 7, д из В", которая обладает следующими свойствами: множество координат можно разбить на два подмножества А = (гд, ..., дд) и В = (уд, ., ~~~ — ь); набор а таков, что координаты ап, ..., ад„равны 1; набор В таков, что координаты Д,, ..., )1д, равны 0; набор у таков, что 1 < ь < 2 У,, < и;набоР с таков,что би = У,, (и = 1,..., й);кРоме того, и=д для всякого т е Аг выполнено равенство о = Д = 7 = й . Иными словами, специальная четверка образована верхним и нижним наборами некоторой Ус-мерной грани д куба В" и двумя отличными от них противоположными наборами этой грани.
Доказать, что функция 1(х") является нелинейной тогда и только тогда, когда в В" найдется специальная четверка наборов такая,что функция 1(хй') обращается в 1 либо на,одном, либо на трех наборах из специальной четверки. 3.16. Доказать, что если 1(х ) ф Л, ~ддду~ = 2" д, то с помощью подстановки функций (О, 1, х, у, х, Р) на места переменных функции у можно получить как конъюнкцию, так и дизъюнкцию.
3.17. Показать, что отождествлением переменных из нелинейной функции у(хн) (и > 4) можно получить нелинейную функцию, зависящую не более чем от трех переменных. 3.18. Показать, что система А полна в В. Выяснить, является ли система А базисом в В: 1) А = (1, хд 9 хг); 2) А = (О, тд - хг); 3) А = (О, 1, хд 9 хг 9 хз); 4) А = (х 9 1, тд 9 хг); 5) А = (хд 9 хг, хд хг); 6) А = (хд 9 хг 9 хз, х 9 1, .О); 7) А = (хд 9 хг 9 хз 9 1, хд хг); 8) А = (хд 9 хг 9 хз 9 х4, х 9 1); О) А = (хд 9 хг 9 хз 9 1, 0);. 10) А = Е ГД Рг(Хг); 11) А = (Ь 9 Я) 0 (0); 12) А = 7 Б; 13) А = (хд 9 хг, хд 9 хг 9 хз 9 1, Ц; 14) А = (хдхг дУ хдхг, х 9 1); 15) А = (Аддин) П Р(Хг).
3.10. Доказать, что не существует линейной функции у, образундшей базис в В. 72 Рл, П. Замкнутые классы и полнотаа 3.20. Доказать, что 7 й 3 = ((х 9 у 9 2 9 1К. 3.21. Доказать, что система (х,,(1, Уг, Уз), где Л, Уг, Уз попарно различные функции, существенно зависящие от переменных х1, хг, ~од~а в Р2. 3.22. Доказать, что система (О, х, (1, 2'2, 22), где тт, тг, тз Различные функции, существенно зависящие от переменных хт, х, ...
..., хп, п > 2, полна в Рг. 3.23. Доказаттн что из полинома степени 3, зависящего от трех переменных, с помощью отождествления переменных можно получить функцию вида хд 9 1(х, у), где 1(х, д) — некоторая линейная функция. 3.24. Доказать, что из нелинейной функции 7'(хп) с помощью отождествления переменных можно получить функцию вида хд9 91(х, у) или вида хд 9 ух 9 гх 9 7(х, у, 2), где 1(х, у) и 7(х, у, г) линейные функдии.
3 4. Классы функций, сохраняющих константы Функция т'(хп) сохраняет контианту 0 (констланту 1), если у(0, О....., О) = 0 (соответственно если Г" (1, 1, ..., Ц = 1). Множество всех функций алгебры логики, сохраняющих константу 0 (константу 1), обозначается через То (соответственно через Тт). Множество всех функций из Та (Т1), зависящих от переменных хт, хг,..., хп, будет обозначаться через Тп (соответственно через Тп). Каждое из множеств 7о, Тт является замкнутым и предполным в Рг классом.
п — 2 пример 1. Выяснить, при каких и функция Г(хп) = ((2 т(х„ т=1 хт.ет, х,, 1) принадлежит множеству То й Тт. Рещение. Если и нечетно, то Г(хп) является суперпозицией функций т(хт, хг, хз) и хт 9 хг 9 хз, принадлежащих замкнутому классУ 'То й Т,, и, следовательно, Г(хп) б То й Т,. Если и четно, то Г(1, 1, ..., 1) = О,и ( ф То й Т,. Пример 2. Найти число функций 2" (х и ), принадлежащих множеству А = (Л'1То) Г1 3. Решение.
А = (7 т (То й 1)) й 3 = (Ь й З)ЦХ й То й 3). Следовательно, ~А~ = ~ЬйЗ~ — ~Т,йЗйТо( Линейная функция Г(х") является самодвойственной тогда и только тогда, когда она существенно зависит от нечетного числа переменных, т.е. представима в виде Г = х„9 х;, 9... 9 хе.., 9 ст, и б (О, Ц. Число линейных функций Г(хп), зависящих существенно от й переменных, равно 2Сь (Сь способами можно выбрать и переменных из хт,. хг, ..., хп и двумя способами можно выбрать свободный член). Таким образом, ~7тт й оеп~ 2 ~~, С2т-~-1 2п 0 < т < т тт — 1 т т 2 1 Ясно, что ~7" Г1 Зп Г1ТД = — ~Ь" Г1З" ~, поскольку свободный член 2 определяется однозначно (равен 0). Таким образом, ~А~ = 2п 2 4, класом функций, сохраниюсаих констани«о! 4.1.
Выяснить, принадлежит ли функция /' множеству Т1!!Те! 1) У = (х! -« хг)(хг -« хз)(хэ -« х!): 2) У = пг(хг,хг,хз); 3) !" = х! -« (хг †« (хз †« х!)); 4) У = х, хгхз «/ х!хг ц хг, 5) У = [х! «/хг)хз «/х!хг «/тг, 'б) 1 = х!хг хз !/ У«хг'~ хг'!/хгхгхз,' 7) а/ = [10010110); 8) о/ = [11011001); 9) о/ = (10000111), 10) сг/ = [0001 1011). 4.2. Выяснить, при каких и функция /[х!!) принадлежит множеству То««Т! ! /п — 1 ц у[хи,) х а«х, 49 Ехи 2) Х(х') = ~ '3 х х';! !=1 3) ~[Хи) Я) 2С,Х; 4) у(Х ') = !Э Х «/Х!) 1<4<!<п 1<!<!<и 5) Д[хп) = 1 б«(х1 -«хг)(хг «хз)(хз + х4) , (хи, -«хи)(х, -«х!)' и — 2 б) 1(Хс!) = Я! (Х! -+ [Хг+! -+ Хп«2)) ~ !=1 п — г 7) Яс™) = 9 [(х! — «хг-ы) — «х!4.2); !=1 и — 2 8) у[х ) = «1)(х! Е х; . хс,.
); 9*) 1[х и) = . Ф с=1 1<!<!<Я<п 10) /[х") = ф гл(хс, х! хь)' 1<~<!<Ь<п п 1ц г(г") = Я) !р!(хп), !р, 6 Я ! !Т!'! /и†! -1)4,Х [ Я~,п*ф" !), Гдс у1, =1 1=1 про- ИЗВОЛЬНЫЕ ФУНКЦИИ ИЗ Рги, !Р* ДВОйСтВЕННаи К !Р! ФУНКЦИЯ, =1,...,и — 1; /» — ! и — 1 13) /[Хи) = Хи~ ««/!р!(Х" ")[ !2« ~ а«1(ХП !), ГдЕ !р; — ПРОИЗ=1 1.= ! вольные функции из Ри, !рг двойственная к !р! функция, = 1, ..., п — 1; 14) / [Х п ) ««~ уг! [Х и ) !р! Е (Е П ТО) !«О; =1 п 15) ~(х") = 1~~ !р!(х"), !р; Е Я «Т1. Пример 3. Показать, что [[ху, х !Э у)) = То.
Решение. Заметим, что полипом любой функции /" из То не содержит 1 в качестве слагаемого. Но всякий такой полином может быть, очевидно, получен с помощью суперпознции из функций ху, х 9 у. 74 Гж 11. Замккртыс классы и полнота 4.3. Подсчитать число функций, зависящих от переменных хы хз, ..., ха и принадлежащих множеству А: Ц А=ТойТ~; 2) .4=То0ТП 3) .А=ТойЛ; 4) А=Т1 ПЯ; 5) А = То и Ь; 6) А = Р,Т,; 7) А = (Л и Т,) й Я: 8) А = Ь й Т, й Я; 9) А = 5 и Я и То; Р0) А = [5 О Л)1Т,; 1Ц А = [1Л,То) Г1 Я; 12) А = 5 П То, '13) А = (Я Г1 То) 0 ТГП 14) А = (Я й Л~~,,Тз, 15) А = [То'1Т1) й Я; 16) А = [То~Тз) П Л; 17) А= фи5)ПТ,; 18) А=(Т,иТо)ПЯ; 19) А=Т,ПТ,Г1Л; 20) А = [То П Т1 Г1 Ь)1Я; 2Ц А = (Я Г1 Л)1То' 22) А = [К й Ь)~[Т, й Т,); 23) А = ф й ЙЯТо и Т,); 24) А = (51 То) й ТП 25) А = Я~ДТо 0 Т1); 26) А = [о П То)~ТП 27) А = Я~,[То 0 5); 28) А = Я Г1 То Г1 Ь; 29) А = РЯТо 0 Т1); 30) А=(ЛЦТ,ит,)) ПВ; 3Ц А= ~~5; 32) А=5~В; 33) А = (А'1Я) ПТ1; 34) А = [(Я~А)1То)~Т1,' 35) А = ([К й Ь)~То)~Т1, 36) А = Я й (Тз~Ь); 37) А = (Л й Я)~[То й Т1 ); 38) А = [Ь й ТоЯБ й Т1); 39) А = [К й Т )~Т,; 40) А = (Л й Т й Т,)~К, 4Ц А = [То й Тз П Я) ~7; 42) А = То 0 Т1 С1 Я; 43) А=То0Т10ЯОЬ' 44) А=То0ТзОЬ' 45) А = (о\Я) 0 [То~Тз).
4.4. Показать, что: Ц ЛПВПТо =ЛПКПТз = ЛПТойТ, =ЛПКПТойТ,; 2) КГ1То=КПТз =ЯГ1ТойТм 4.5. Показать, что: Ц [~хН д, т 61 уН = То, .2) [~хЧ у, х - у)] = Т,; 3) Цху, х уН = Т~,. 4) [(ху ~Э з)] = То,. 5) [Сху, х 61 у Ю зн = То Г1 ТГП 6) Нху йз з йз 1)] = То Г1 Т1, 7) Цхйу)]=ЬПТо; 8) [Ех-у)]=ЛПТ1, 9) Цх ГЭ у ~В о)] = Ь П Я й То, 10') []т(х,у,з), хбуйя)]=ТойК, 11') Н (х, у, з))] =Т,ПК; 12) [1хвдГО ГО1)] =ЛПЛ; 13) ~(хр, н~[х, у,.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
