Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 16
Текст из файла (страница 16)
Показать, что функция д" = у1у1 9 х(уз 9 ф) самодвойственна, если у1 и уз являются самодвойствснными. 2.14. Используя лемму о несамодвойственной функции, доказать, что Я является прелполным классом в РЗ. 2.15. Верно ли, что число самодвойственных функций, сущест- ВЕННО ЗаВИСЯЩИХ От ПЕРЕМЕННЫХ Х1, ХЗ, ..., Хп, РаВНО ЧИСЛУ ФУНКЦИЙ ИЗ РЗ(Хп 1), СущЕСтВЕННО Заанеящнк От ВСЕХ СВОИХ ПЕРЕМЕННЫХ? 2.16. 1) Пусть функция 7"(хп) суп1ественно зависит от перемен- НОй Х1 И КажДаЯ ИЗ КОМПОНЕНТ Д (Хп) И Д(Хп) ЯВЛЯЕТСЯ СаМОДВОйет- венной функцией. Показать, что Дх") не является самодвойственной функцией. 2) Останется ли верным утверждение 1), если слова «каждая из ком1юнент» заменить на «хотя бы одна из компонент»? 2.17.
Показать тождество 3 (Х1 Х2 ХЗ Х4 . Хп)— = 7(Х1; т(Х1 Х2 хз): хи(Х1, Х2, хз), Х4, . Хп) 1е Ч1 ЯИ(Х1, Х2, УЗ), Х2, И1(Х1, Х2,ХЗ) Х4; ° ° ° Сп) Ю ЧЗ.~(т(Х1 Х2 ХЗ), И1(Х1 Х2, ХЗ) ХЗ Х4 -. Хп). 2.18. Используя предыдущую задачу, доказать, что: 1) 8 = Г(Х1 йзха йз хз, т(Х1, ХЗ, хз), ХН; 2) ~ = [(т(Х1, ХЗ, хз)Н 3) Я = '((т(х„хз, хз))). 2.19. Выяснить, является ли множество А самодвойственным: 1) А = (О, 1, х); 2) А = (О, х); 3) А = (х Ю р, х р, х Ю р ес 2); 4) А = (х 4 р, х Ч р): 5) А = (х -+ р, ху); 6) А = (х р., х, 'др, т(х, р., х)); 7) А = (х Е р Е 2, х); 68 Га. П. Замкадганс. кпассм а аопнотиа 8) А = Нх — э д)]; 9) А = [(ка(х, д, з))]; 10) А = [(1, х Е д)]: 11) А = Н1, х Е д, хд)]; 12) А = [(1, хдН; 13) А = [(х'уд, хЕдЯ; 14) А = НхЕдН; 15) А = [(хд ЕзЕ1)]. 2.20. Показать, что: 1) если [А] = 1'з, то и [А*] = Рз, 2) (А*)* = А; 3) если А = [А], то и А* = [А*]; 4) если А, С Аз, то А* С А', 5) если А базис [А], то А' базис [А*] .
3 3. Класс линейных функций Функция 1(х") называется линейной, если она представима полиномом Жегалкина не выше первой степени, т.е. если существуют такие константы еи Е (О, 1), 1 = О, н, что У(х ) = оа Е о1х1 Е, .. Е <~пхп. Множество всех линейных функций обозначается через Ь, а множество всех линейных функций, зависящих от переменнык хы хз, ... ..., хп, — через Г". Из представления (1) вытекает, что ]Ь" [ = 2"+~. Множество Ь является замкнутым и предполным в Рз классом. Справедливо утверждение (аемма о нелинейной функции): если у' й Ь, то, подставляя на места ее переменных функции О, 1, х, д., х., д, можно получить хд или хд.
Если 1" ф Ь, то функция 1 называется нелинейной. П р и м е р 1. Выяснить, линейна ли функция 1, заданная вектором значений о у = (1001 0110 1001 0110). Решение. Найдем вектор Ду коэффициентов полинома Жегалкина для функции )'. Имеем (11 = (1110100000000000). По вектору(11 опРеДелЯетсЯ пРеДставление полиномом 1" = 1 Е х4 Е хз Е хз. Отметим, что в 131 отличны от нуля лишь координаты 1зе, Д, 1зз, Д с номерами., равными 0 либо степеням 2. Это является критерием принадлежности 1 классу линейных функций. Пример 2.
Заменить в векторе Н = ( .110 — -0) прочерки символами 0 и 1 так, чтобы получился вектор значений некоторой линейной функции 1. Выразить ) полиномом. Решение. Сравнивая значения координат ссз и ссз, оз и оз в векторе Н = (ссоссзозозоаозоасст), назсодим, что функпия 1 существенно зависит от переменных хз и хз (так как Д(001) = 1(011) и Д010) д': 1(011)). Тогда в силу линейности функции 1 имеем не = О, оз = сза = 1. Значение ста необходимо положить равным О, так как если бы сза = 1, то, поскольку оа = О, функция сугцественно зависела бы от х1 (ибо у(000) ф 1(100)).
Но тогда в силу линейности функции ( имели бы ((011) ~ ('(111), что противоречит условию, ибо нз = от = О. Таким образом, Нт = (01100110), а ( = хз Е хз. З'3. Класс линейных функций 69 Пример 3. Подставляя на места переменных нелинейной функции ф с вектором зна зелий аат = (1000000000001010) функции из множества (О, 1, х, у, х, д), получить дизък>нкцию х с у. Решение.
Функция х му обращается в 1 на трех наборах. Заметим, что и 7" обращается в 1 на трех наборах: (0000), (1100), (1110), и что все три эти набора имеют 0 в четвертой координате, а вторая координата равна первой в каждом из наборов. Положим хл = О, х1 — — хг = х, хз — — у. Тотда ф = (х, х, у, О) = х~7д. Пля получения дизъюнкции остается лишь подставить у вместо у. Таким образом, ф(х, х, у, О) = х д у. 3.1. Представив функцию 7" полиномом, выяснить, является ли она линейной; 1) ф = х — ~ д; 2) ( = х -+ у Ю ху; 3) ф = ху(х д); 4) У =..су Чхудг; 5) 7" = (труху)г'рг(ху ухд); 6) ф = ((х — > у)(у з х)) — г; 7) ф = хуг Ч ху: 8) з' = хуг 61 туг Юху; 9) ф = т(х, у, г) ОЗ хугее хуг: 10) ф = (х у уг) Ю туг; 11) ф = (х м уг) йз хуг; 12) ф = (хуго ху г) Оз т(у Ю г); 13) ф = хдг ье х(у г) Ф х(уч г); 14) ф = (хрг Югхд) у (хуг бахус); 15) 7' = (х у г хуг) (хдг хуг).
3.2. Выяснить, является ли линейной функция 7', заданная векторно: 1) ау = (1001); 2) ау = (1101); 3) ау = (10010110): 4) ау = (11000011); 5) ау = (10100101); 6) ау = (10100110); 7) ау = (1100100101101001); 8) ау = (01101001); 9) ау = (1001011001101001); 10) ау = (0110100101101001); 11) ау = (1010010110011100); 12) ау = (1010010101011010),. 13) ау = (1010011001100101): 14) ау = (0011110011000011); 15) ау = (1001100101100110).
3.3. Заменить в векторе а прочерки символами 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., и, р, х, Р на места переменных функций у получить функцию ту: Ц у" = т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хз91, хд хг); 8) А = (хд 9 хг 9 хз 9 х4, х 9 1); О) А = (хд 9 хг 9 хз 9 1, 0);.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
