Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 14
Текст из файла (страница 14)
1.3. Выписать все попарно неконгруэнтные функции 7'(х~), принадлежащие замыканию множества А: 1) А=(1,х); 2) А=(ху); 3) А=(х у); 4) А = (ху'1~ уг Ч гх): 5) А = (х Ю у В з й Ц:, 6) А =(хм у Р з); 7) А = (х — > у): 8) А = (ху Р г); 9) А = (ху): 10) А = (х(х'~ у)(у р у)(хМух)). 1.4. Из полной для класса ~А) системы выделить базис; 1) А=(0,1,х); 2) А=(хну,х у., Ц; 3) А=(х, хну, хбубзг); 4) А=(ху, хну, хуЧз); 5) А = (хну, х -э у); 6) А = (ху, ху); 7) А=(хзрувг,хуругргх, х); 8)А=(1,х у,хву~ЭзбзЦ:, 9)А=(ху,хуЧхг); 10) А = (х, х Ч у, х Ч у Ч г, ху 7 г).
1.5. Выяснить, какие из указанных ниже множеств являются замкнутыми множествами: 1) множество всех функций от одной переменной; 2) множество всех функций от двух переменных: 3) множество всех функций Дхы хг, ... х„) таких, что 7'(1, 1, ...
...,1)=1., и>0; 4) множество всех функций Д(хо), и > О, таких, что 7"(1, 1, ... ..., 1) = 0; 5) множество всех симметрических функций, т.е. таких функ- /12... и1 ций 1" (хз, хг, ..., х„), что для любой подстановки ( .. ' ' ' . ~ спра~й 1г... ~..) ведливо равенство Дхы хг, ..., хн) = 1(хи, х„,,х;„); 6) множество всех функций 7(х") таких, что ~1зу ~ = 2" 7) множество всех функций, выражаемых полиномом Жегалкина не выше первой степени; 62 Гл. П. Залкндудпыс классы и полнота 8) множество всех функций, выражаемых полиномом Жегалкина не выше второй степени; 9) множество всех функций., допускающих представление в виде д. н.
ф. и не содержащих отрицаний переменных; 10) множество всех функций, любая д. н. ф. которых содержит хотя бы одно отрицание переменной; 1Ц множество всех функций )'(яи), п > О, полипом Жегалкина которых содержит 2" — 1 слагаемых; 12) множество всех функций Д(ти), и > О, полипом Жегалкина которых содержит 2" — 1 слагаемых и не содержит 1 в качестве слагаемого; 13) множество всех функций д"(яи), и > 1, таких, что [дУу[ = 1; 14) множество всех функций У(х"), и > 1, таких, что [дУу[ = 1 и 1(1, 1, ..., Ц = О. 1.6.
Показать, что: Ц пересечение замкнутых классов является замкнутым классом; 2) объединение двух замкнутых классов, вообще говоря, не является замкнутым классом; 3) разность двух замкнутых классов, вообще говоря, не является замкнутым классом; 4) дополнение непустого и отличного от Рз замкнутого класса К до Рд не является замкнутым. 1.7.
Показать, что класс А, предполный в замкнутом классе К, является замкнутым. 1.8. Обосновать следующие свойства замыкания: Ц [[КД = [К): 2) из Кд С Кз вытекает [Кд) С [К,): 3) [Кд Гд Кз) С [Кд) Гд [Кз); 4) [Кд) 0 [Кз) С [Кд дд Кз); 5) [И) = И. 1.9. Выяснить, является ли множество А замкнутым классом. Предполагается, что вместе с каждой функцией 1 из А множеству А пРинадлежат и все фУнкции из Рдп конгРУэнтные 1: Ц А = (О, 1):, 2) А = (т); 3) А = (и, х); 4) А = (1,У); 5) А=(ид ...
яа, п=1,2,...); б) А=(яд~В...Юяи, п=1,2, ...); 7) А = (О, тд дд... дд т„, п = 1, 2, ... ); 8) А = (яд йд... до иди-д., и = 1, 2, ... ); 9) А = (О, и, В... Е из„д, и = 1, 2, ... ); 10) А = (О, 1, хд 6Э... йд то ев и, и б (О, 1), и = 1, 2,... ). 1.10. Ц Перечислить все замкнутые классы К С Рз такие, что число попарно не равных функций в К конечно. 2) Перечислить все замкнутые классы К С Рз такие, что число попарно нсконгруэнтных функций конечно. 3) Указать множество А С Рз такое, что для каждого п > 1 число функций из [А), существенно зависящих от переменных хд, ..., х„, равно: а) 1; б) 2.
1" с. Класс самодвойственных функций 1.11. Ц Локазатгь что если замкнутый класс в Рг содержит функцию, существенно зависящую от и > 2 переменных, то он содержит бесконечно много попарно неконгрузнтных функций. 2) Верно ли, что если замкнутый класс К содержит функцию, существенно зависящую от и > 2 переменных, то для всякого т > и он содержит функцию, существенно зависящук~ от т, переменных? 1.12. Сведением к заведомо полным системам в Рг показать, что множество А является сюлной системой в Рг. 1) А=(х(у): 2) А=(хууг,(х у)~Зг); 3) А = (х в у, х Ю у Ю г); 4) А = (х -+ у, 7' = [01011110)); 5) А = (О, щ(х') = хгхг М хгхз Ч хзхм х Е у Ю 1); 6) А = (х у, х йз у, хууг); 7) А = (хуанхе, у = (01111110)); 8) А = (хд Ю г1 а 1, 7" = [10110110)); 9) А = (О, 1, х 9 у Ю г, ху В гх 9 гу); 10) А = (х у д г, х Ю у).
1.13. Выяснить, какое из отношений С, З, =, у выполняется для множеств Км Кг из Рг [отношение у означает, что не выполнено ни одно из отношений С, З, =): 1) К1 = [Аг П Аг], Кг = [Аг] П [Аг]; 2) Кг — — [Аз~Аз], Кг = [АД[Аз]; 3) Кг = [Аг 0 (.4 гз Аз)], Кг = [А г 0 Аг] и [Аз 0 Аз]; 4) К1 = [А~ ~Аг], Кг = [Аз]~[Аз гз А ]. 1.14. Привести примеры замкнутых классов Км Кг из Рг таких, что Кг С Кг, и таких, что; 1) К, П К, = О, Кг~К, ф- О, [К, С1 К,] = К, ~д К,; 2) Кг П Кг г- И, Кг~К1 г- И, [К1 0 Кг] = К1 0 Кг,' 3) Кг ~ Кг, [Кг~Кг] = Кг~Кг; 4) Кг Г) Кг ~ И., Кг'~Кг ~ И, [Кг~Кг] = Кг1Кг,' 5) К1 Й Кг ~ Я, Кг ~К1 ~ яг. [К1 Ог Кг] = К1 6в Кг.
1.15. Перечислить все предполные классы замкнутого класса; 1)К=[О,х]; 2)К=[0,1]; 3)К=[ту]; 4)К=[хйу]; 5)К=[О,хну]; 6)К=[1,ху]; 7)К=[хйуйг]; 8) К = [х со 'у, 1]. 1.16. Показать, что для любого замкнутого класса К С Рг выполнено равенство [К 0 (хЦ = К 0 (х). 1.17. Показать, что каждый предполный в Рг класс содержит тождественнукз функцию. 1.18. Показать, что всякий замкнутый класс в Рг, содержащий функцию, отличную от константы, содержит и функцию х. 1.19. Показать, что множество Р всех функций алгебры логики не представимо в виде объединения непустых попарно непересекаюшихся замкнутых классов. 64 1"м П. Замкнутые.
кпассы и поанота 1.20. Доказать, что если замкнутый класс Р2 имеет конечный базис, то всякий базис этого класса конечен. 1.21. Доказать, что если непустой замкнутый класс в Р2 отличен от множеств, состоящих из одних констант, то его нельзя расширить до базиса в Р2. 1.22. Доказать, что в замкнутом классе (х — е уе) содержатся только такие функции из Ря, которые могут быть представлены (с точностью до обозначения переменных) в виде х, 1е' 1(х"), где 1(х") е Рз.
1.23. Пусть функция е'(х") принадлежит множеству (х — > у] и зависит существенно не менее чем от двух переменных. Доказать, что ~?Уе~ > 2" '. 2 2. Класс самодвойственных функций Функция у(х1, хз, ..., хп) называется самодвойственной, если 1(х1, хз, ..., хп) = 1*(х1, хз,, хп), или, что то же самое, если У(Х1 Х2 °; Сп) — 1(Х1; Х2 ° °; Хп) ° Из этого определения вытекает, что функция является самодвойственной тогда и только тогда, когда на любых двух противоположных наборах значений переменных она принимает противоположные значения. Класс самодвойственных функций будет обозначаться через Я. ИЗ ОПрсдЕЛЕНИя Я ВЫтЕКаот, ЧтО ~Яп~ = 22 Справедливо следующее утверждение, называемое обычно леммой о нссамодвойствеаной функции: если функция 1(х") не является самодвойственной, то, подставляя на места ее переменных функции х и х, можно получить константу.
Если А — некоторое множество функций из Р2, то через А' будет обозначаться множество всех функций, двойственных к функциям из множества А. Множество А' 1шзывается двойственным к мнохссству А. Если А' = А, то множество А называется самодвойсптсннь м. Пример 1. Выяснить, является ли самодвойственной функция 1, заданная вектором: а) оу = (10110100); б) Ду = (10110010). Р е ш е н и е. Из определения самодвойственной функции вытекает, что на противоположных наборах она принимает противоположные значения. Поэтому вектор о? самодвойственной функции у (хп) имеет вид сеу = (мв, .'~1, ..., <12 — .
1 ~2" — — 1 ° се1 сев). Таким образом, чтобы выяснить, является ли функция 1"(хп), задаваемая вектором (оо, о1, ..., 122. 1), самодвойственной, следует проверить, получается ли вторая половина вектора из первой путем отражения и последующей расстановки отрицаний над координатами. В рассматриваемом примере вектор Иу задает самодвойственную функцию в случае б) и несамодвойственную в случае а). П р и м е р 2. При каких и, функция Й хе ухе2 у .'~хч ол) 1<в (ев«...11ы М(п является самодвойственной? ~ с.
Класс сажодвойственных функнив Решение. Заметим, что множество Хт, наборов о таких, что Да) = О, состоит из всех наборов веса не выше и — )гг/2[= (и/2). Пусть и четно, тогда В„" С Ху. Пусть сй — произвольный набор из Во~ . Противоположный набор о также принадлежит множеству Вл~ . Таким образом, г"(а) = д"(сх) = О, что противоречит само- двойственности. Следовательно, при четных и функция ((х л) не явля(л/г1 ется самодвойственной. Пусть теперь и нечетно.
Тогда Ж вЂ” = (.) В,", п с=с Асу = (.) В,". Очевидно, что о 6 Ас — тогда и только тогда, когда т=-)о/г~ у а 6 Асу. Это и означает, что ( (х") 6 Я при нечетных и. Пример 3. Какие из переменных несамодвойственной функции Дх~), задаваемой вектором ау = (01101101), следует заменить на х, а какие на х с тем, чтобы получить константу? Решение. Поскольку Д(х~) 6 Я, то существует пара противоположных наборов, на которых функция принимает одно и то же значение.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
