Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 16
Текст из файла (страница 16)
П р и м е р 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);.
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Сь (Сь способами можно выбрать и переменных из хт,. хг, ..., хп и двумя способами можно выбрать свободный член).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
