Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 16
Текст из файла (страница 16)
Заменить в векторе а прочерки символами 0 и 1 так, чтобы получился вектор значений некоторой линейной функции 7. Выразить ф полиномом: 1) а = (10 - 1), 2) а = (О -11); 3) а = (100 - 0 - ); 4) а = ( 001--. - 1 -); 5) а = (1-- 101 6) а = ( 0 1 00); 7) а = (11 0 1); 8) а = (1 11 0 ); 9) а = (..- -- 10 .
- -- -- — - О. — - . 1--110); 10) а = (1- 0 110); 11) а = (--11- - 1-- — — -1 — -- -- — — — — 0); 12)а=( 0 00 1 0 )' 13)а=( 100 1 1 14)а=( 1 11 11 1 0 15) а=( 1 00 1 1 ). у"л. 76 Замкнутые классы и нолнотиа 3.4. Подставляя на места переменных нелинейной функции функции из множества 10, 1, и, 9), получить хотя бы одну из функций ту, ту, г:у: 1) У(т ) = тзхг ЗУ тгУз 'Ухзх;; 2) ау = (01100111): 3) ау = (11010101); 4) ау = (11001110): 5) ау = (1101 1111 1100 1111); 6) ау = (0111 1111 1110 1110); 7) ау = (11110101111111011); 8) ау = (0111101111111110); 9) ау = (1001011111111010); 10) ау = (1101100110010111); 11) у = (тз ЧУг Чтз)(У~Чхг ухз Чхл); 12) У = (тз зу тг 'у тз Зу тл)(хз ц тг 'у хз Ч хл)(тг зу тз)~ 13) У изигизиз " иглглзлл улзиглзхл ~ хзхгузтл ~' изхгхл ч Зу хгхзул Н хзхгиз ,' 14) Йу = (1100111111111110); 15) Йу = (1011111010110111).
3.5. Выяснить, можно ли путем подстановки функций О, 1., и, р, х, Р на места переменных функций у получить функцию ту: Ц у" = тз — > тг, 2) ау = (11101000); 3) ау = (10010110); 4) ау = (11011011); 5) ау = (10010111); 6) ау = (11010110); 7) У = тг -+ (иг — ~ тз):, 8) У = (э:зтг'зу тзигтз) % уз огиз,' 9) У = Утдтг Ч хгхз Ч тзиз); 10) ау = (10011010); 11) ау = (1001011001101001); 12) ау = (1110100110010111); 13) ау = (1101 1110 0110 1011); 14) ау = (1100 0011 0011 1100); 15) ау = (0111101111111100). 3 6. 1) ПУсть фУнкциЯ 7(хи) пРедставима в виде У" = хн бг Зо(хо з).
Доказать, что на любых двух наборах, различающихся только в п-й координате, функция у принимает противоположные значения. 2) Локазать обратное утверждение, т.е. что если функция У на любой парс наборов, различающихся только в и-й компоненте, принимает противоположные значения, то функция 7 может быть представлена в виде у = и„ Ю иг, где Згне зависит от ин. 3) Локазатьз что функция Учти), принимающая на любых двух соседних наборах противоположные значения, линейна и существенно зависит от всех своих переменных. 3.7. 1) Показать, что если функцию У~я") можно представить в виде У(х"') = ио чгЗг, где Згне зависит от х„,то ~Ху~ = 2" 2) Показать, что если 7 линейна и отлична от константы, то (У7у! = 2" ' 3.8.
Локазатгч что функция у1ти), существенно зависящая от всех своих переменных, является линейной тогда и только тогда, когда при замещении любого подмножества переменных любым набором констант получается функция, существенно зависящая от всех оставшихся переменных. 3.9. Показать,что линейная функция является самодвойственной тогда и только тогда, когда она существенно зависит от нечетного числа переменных. у 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) ~(хр, н~[х, у,. У))] = То й Т,; 14) [бс'~ у, ап(х, у, з))] = То П Т,; Рб) [)т[х, р., ), х чз у)] = Т . 4.6.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
