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