Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 15
Текст из файла (страница 15)
Такими наборами являются в данном случае (010) и (101), причем Д(010) = ((101) = 1. Если заменить хг и хз на х, а хг на х (или хг и хз на х., а хг на х), то получим Дх, х, г:) = г'(х, х, х) = 1. 2.1. Выяснить, является ли функция 1 самодвойственной: 1) У = хгхг Н хгхз Ч хзхг, 2) У = хг У хг, '3) У = хг 6З хг Ю хз Ю 1: 4) ) = (хЧ рЧх)гЧхуз; 5) 1 = хЧуЧз)гЧ хуг; 6) ~ = (хг — > хг); 7) )(хг ог хг); 8) ) = хгхг 66 хати 6З хзхг ог хг ог хз! 9) г = хгхгЧ хз,' 10) У = хг Ю хг Ь (хгхг 'дхгхз дхзхг); 11) гс = х~хг 6г ха(хг 'к' хг),' 12) гс = хгхгхз Ю хгхг Ю хгхз Ю хат~,' 13) ~ = х,хгхз Юхгхгхз Юхгхз Юхгхз,' 14) У = (х1 -+ хг) 69 (хг -~ хз) 61 (хз -а х1) 61 ха; 1->) г = (хг с ха) ~В (:гг « хз) ~В (хг е гч).
2.2. Выяснить, является ли самодвойственной функция д', заданная векторно: 1) ау = (1010); 2) ад = (1001); 3) ае = (10010110); 4) сге = (01100110); 5) оу = (01110001); б) оу = (01001101); 7) ау = (1100100101101100); 8) ае = (1110011100011000); 9) ае = (1000001110001100): 10) ау = (1001101110111001); 11) ау = (1100001110100101): 12) ау = (1100001100111100)! 13) его = (1001011010010110); 14) Йу = (1101010010110010); 15) ау = (1010010101011010). 2.3. Заменить прочерки в векторе а символами 0 или 1 так, чтобы получился вектор значений самодвойственной функции: 1)а=(1 0 ); 2)се=( 01 ); 3)а=(01 ); 4)а=(01 0 О, ); 5)о=( 01 11); 5 Г.
П. Гаврилов, А. А. Сапожонка 66 Гл. 11. Замкнутые. классы и полнотпа 6)а=1 1 1 0 Ц: 7)а=1 10 0 Ц; 8) а = (1001 — — — 1111 — —— 9) ег = (11 — — 00 — — -01 — — 10 — — ); 10) а = (- - - -- -- -. - 01 - — — 101100).
2.4. Определить, какие из переменных функций Дхп) следует заменить на х, а какие на х с тем, чтобы получить константу; Ц а1 = (10110110); 2) а1 = 111011000); 3) а1 = 110100100); 4) а1 = (10101000); 5) а1 = 111001110); 6) а1 = (1000110100101100); 7) а1 = (1001011010011010); 8) а1 = (011100010011000Ц; 9) а1 = 1011010001110101Ц; 10) а1 = (10100101010100110); 1Ц а1 = 11010111011001010); 12) а1 = (0110000Ц; 13) а1 = (1011010011110010); 14) ау = (00001111 0010111Ц; 15) ау = 11110100001101000). 2.5. Пусть тп1х, у, г) = ху о' дя Ч гх. Показать тождества; Ц тп1тп1х, у, г), тп1х, у, г), тлях, у, у)) = = пте1тп(х, у, г), тетях, у, г), тпе,х, р,д)); 2) х 61 р й г = тп1тп1х, у, г), тп(х, у, г), у); 3) тп1тп1х, р, з), тп(х, у, г), пМ,х, у, У)) = = тп(х, тп(х, у, у), тп(х, у, г)): 4) х 6З д 61 г = т1тп1х, у, г), тп1х, р, г), тп1х, у, г)): 5) тп1х, у, У) = птах, у, я); 6) тп1',х, у, г) = ху Ю уя В гх; 7) тп(х, у, г) = тптх, т 1х, у, я), г); 8) хуг Ч 11х Ч у р г) = тп(х, тп(у, г, 1), 1); 9) хуя 1<' ст1х Ч у 'Р г) = тп1тп1,х, у, 1), т1,х, г, 1), тп1,у, г, 1)); 10) хуя 1тттх Ч у Ч г) = тлях Ю у 61 г), 111Ех, у, г), 1).
2.6. Показать, что если 1(хп) 6 Я, то ~Х1~ = 2" 1. Привести пример, показывающий, что обратное утверждение неверно. 2.7. Показать, что не существует самодвойственных функций, существенно зависящих в точности от двух переменных. 2.8. Выяснить, при каких и > 2 функция Дх") является само- двойственной: Ц 16т,") = хт 6З хг 6З... 6т хп3 2) 11х') = 1/ хтхт, 1« 1< 3)Дх )= 1/ 1<1<1«!ди< 4) )'(хп) = Я х х,,", 1(1(1(п 5) 1 тхп) = тхт Ч хг) 6з 1х р хз) у бз 1х,, р п) бз тхп „ 6) Дх") = (х1 ч хг ч хз ) 61 ах< и хз ч хз) ер,, .6г'тХ вЂ” гдХп — 1ЧХп), П=ЗК; 7) 11х ) = тп1х1: хг, хз) 63 тп1хпп хз, хо) Е пт тП~ 1'и — г; тп — 1, Хп), 'П = ЗК; З" х. Класс самодвойствеяпых узуикиий 67 8) 1 (хп) = (х1 — 4 ХЗ)(хз -4 хз) ..
(Хп — 1 -4 хп)(хп 4 Х1); 9) 1 (Х") = (Х1 -4 ХЗ) Ю (ХЗ -4 хз) ~Э... Ю (Хп 1 — 4 хп) 4В 03 (хп ~~) Е х~ 61 Ер... 04 10) 7(хп) = ~/ хпх„...хьо 1 < й ( п. 1< 1< а«. 3< 2.9. Показать, что каждая самодвойственная функция, сущест- венно зависящая только от переменных х1, ХЗ, хз, представима в виде х1 хз ч тп1 хз~ ч ХЗ хз~ либо в виде х1 Ю хг 01 хз б~ и, где сп (3 у, сс б (О, 1). 2.10. Локазатьз что функция Дхп) самодвойственна тогда и толь- КО тОГДа, КОГДа ЕЕ Х1-КОМПОНЕНта Л (Хп) ДВОйСтВЕННа К ЕЕ Х1-КОМПО- пента ув(хп), 2.11. Пусть Дх") такова, что 7'(О, хз, ...., Хп) = Д(1, ХЗ, ..., хп). ВЕРНО ЛИ, ЧтО 2'(Х1, ..., Хп 1, 1) = 1(Х1, ..., Хп 1, 0)? 2.12.
Пусть функция Дх") представима в виде Дх") = = х„у1(хй" 1) р ЗЗ*(хз" 1), где уз некоторая функция такая, что Зс*(х' )Н Зс(х" ) = ус(х" ) Показать, что 2 Е Я. 2.13. Показать, что функция д" = у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 полиномом. Решение. Сравнивая значения координат ссз и ссз, оз и оз в векторе Н = (ссоссзозозоаозоасст), назсодим, что функпия 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
