Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 18
Текст из файла (страница 18)
Проверить, является ли функция 5" монотонной: Ц 5 = (Х1 65хг)ее (Х1 хг); 2) 5 = Х1 -4 (Хг -4 Х1); 3) 5 — х1 -4 (х1 -4 хг); 4) 1 = х1У2:сз Ч х1У2хз 4ех1х2хз Чхгхгхз'у хгхгхз,' 5) 1 х1Х2хз " х1х2хз " х1Х2хз у х1х2хг " х1х2хз 6) 2 = (Х1 1Э хг)Х1х2'») 5 = х1хг 1Э 2:1хз 64 хзх1; 8) У = Хгхг еу Хгхз 9 Хзхг 1Э Х1. 5.3. Лля немонотонной функции 5" указать два соседних набора И, 55 значений переменных таких, что Й <,3 и 5(со) > 1(55); Ц 5" = 21Х2ХЗ Ч Х1Хг, '2) 1а = Х1 64 Хг Ю ХЗ, '3) У = Х1Хг ~Э ХЗ:, 4) 1а = х1 У хгУз, '5) 12 = хгхз Ю хгх4,' 6) 1 = (х1х2х4 4 х2хз) ч' х4 ° З" о, Класс нонопгоннгаг фуннцнй 77 5.4. Пусть Мп множество тех векторов сг = (оо: ом ..., ссг -г) которые являются векторами значений монотонной функции.
Найти число векторов из о(4п, которые можно получить из вектора у -г" = (уо, ум, 'уг" — г) заменой символа — - на 0 или 1: 1) у'=(О ); 2)7г=( ); З) у4=(- ОО- ); 4) 7'=( 10 ); 5) 7з =( 00 6) у' =( 1 о ); 7)7з=( 1 о 8) 7 =(о ..Ц 5.5. Пусть о(4Я„- множество тех векторов Нг = (ое, оы ... ..., сгг г), которые являются векторами значений функций из класса М П Я. Найти число векторов из . ИЯп, которые можно получить, заменяя в векторе 7 символы на 0 и 1: ц -г ( ). 2) -4 ( О ). 5) -4 ( ц. 4) 7г=( -ОО-- О - - --); 5) 7'=(--01 -- О-- - ); 6) 7 "о = (-- -- — О - О - - --О ------ ------ ); 7)у — ( 1 1 1 8)у=( 1 0 ) 5.6.
Выяснить, при каких и ) 1 функция у(т,") монотонна: 1) Дх") =хг Юхгй...йхп; 2) 7(хп) = (4) х,х,; 1<~<о<о 3) г (х ) = хгхг ° ° хп у (хг 6~ хг ео ° ео хп); 4) Х(х") = 9 хнх„...х,„„, ьч =] — [; 5) г'(хп) = хгхг .. хп со с1) хг...х, гго+г ... хп; 1<г<п 6) Дх") = Я Я) т=1 1<ц<ц« ..г <и 5.7. Привести пример немонотонной функции у'(хп), у которой каждая подфункция вида у'(хп) (г = 1, ..., .и), о Е (О, .1), монотонна. 5.8. Показать, что если функция у" немонотонна, то существуют два соседних набора Н и 43 такие, что Н < 13 и у(Н) >,у()3). 5.9. Показать, что функция, существенно зависящая не менее чем от двух переменных, монотонна тогда и только тогда., когда всякая ее подфункция, зависящая существенно от одной переменной, монотонна.
5.10. Показать, что функция у(х") монотонна тогда и только тогда, когда для любого и = 1, 2, ..., и — 1, любого подмножества (гы ..., ъг) С (1,..., и) и любых двух наборов сг = (оы ..., ая) и т = (ты ..., ть) таких, что сс ( т, выполняется тождество у" """(ху1) Ч ун, "., м(х — ун,", ц(хп) 5.11. Локазатгн что для всякой монотонной функции у(х") справедливы разложения .У(х ) = 'П(х ) УУо(т ) У(х ) = (' чуо(х ИФх ). 78 Рл, Пй Замкнутые. классы и полнота 5.12. Показать, что для каждой отличной от константы монотон- ной функции 1 существуют д. н.
ф. и к. н. ф., не содержащие отрица- ний переменных и реализующие 1. 5.13. Элементарная конъюнкция К называется простым цмпли- кантом, если К Ч 1 = 1 и К'Ч г ф 1 для каждой конъюнкции К', полученной из К вычеркиванием букв. Показать, что никакой простой импликант монотонной функции не содержит отрицаний переменных. 5.14. Найти число нижних единиц е(1) и верхних нулей п(Д монотонной функции 1: 1) 1(х ) = хгхг Ч хгхз Чхзх~', 2) Дх ) = хг Ч хг,' 3) Дх ) = хгхгхзЧ хл(хг Ч хг '~ хз), 4) ~(х ) = (х3 Ч хг)(хз е хл) ... (хгя 1 Ч хгь); 5) ~(хза) = (хг ц хг ц хз)(хл Ч хз Ч хс)...
(хзь г ц хзь г Ч хзь). 5.15. Пусть ~р(х, д) = х Ч у. Лля набора Н = (оы ...., он) из В" а положим К-(х") = ~ гг(х„сс;). Показать, что если Н является ниже=-1 ней единицей функции Дхн), то элементарная конъюнкция К-(хчн) входит в полипом Жегалкина функции Д)х") в качестве слагаемого. 5.16. Показать, что не существует монотонных самодвойственных функций, имеющих ровно две нижние единицы. 5.17.
1) Показать, что в В" существует подмножество, состоящее п из,, ) ) попарно несравнимых наборов. , р/'2 п 2') Показать, что ~М" ~ ) 2()н1г1). 5.18. Возрастающей цепью длнны Й в В" называется последова- тельностьнаборов Но, Ны ..., оя такая,что Н, ь < Н; (г = 1, ..., к). Ц Показать, что в В' существует п'. попарно различных возрас- тающих цопсй длины и. 2) Показать, что число попарно различных цепей длины гь содер- жащих фиксированную вершину сг из В,",, равно к! (и — к)!. 5.19.
1) Показать, что мощность любого подмножества попарно несравнимых наборов куба В" не превосходит,, ) ). ~, уц'2 2) Показать, что осли подмножество А С В" состоит из попарно несравнимых наборов и при этом ~~НИ' < й < п/2 для любого В Е А, то ~А~ < ("). 5.20. 1) Используя пгеорему Дилуорса, утверждающую, что мини- мальное число цепей, содержащих все вершины частично упорядочен- ного множества, равно максимальному числу попарно несравнимых наборов в нем, доказать, что ~М"~ < 2-ь п 2) Доказать, что число монотонных функций 1(хн), у которых каждая нижняя единица имеет вес, но превышающий к (О < и < п/2), си~ не превосходит 1 + (й+ 1) ~ Я ).
у" а, Класс мацащанцмх функ ццй 79 5.21. Подсчитать число функций в каждом из следующих мно- жеств: 1) М"ЦТ1 ОТе); 2) М"ЦТ1 г1Те):, 3) М" г1Ь; 4) М" ОЛПЕ; 5) ха(М О В) 5.22. Показать, что: 1) ~БОМ" ~ ( ~М" ~~ при п > 1; 2) (М"~ ( ~Ма ~~э при и > 1; 3) ~Мп( < )Ма — 2)2 22" 5.23. 1) Перечислить все монотонные функции переменных хы х.. 2) Перечислить все попарно неконгруэнтныс монотонные функ- ции, существенно зависящие от трех переменных. 3) Пусть ф(п) .. число монотонных функций, зависящих от пере- менных хх аз .
Ха Показать что: а) ф(1) = 3; б) ф(2) = 6, :в) др(3) = 20: г") ф(4) = 168. 4) Пусть ф,(н) число монотонных функций, существенно зави- сящих от переменных хы хю ..., х„. Найти фс(п) для п < 4. 5.24. Перечислить все попарно неконгруэнтные самодвойственные монотонные функции, зависящие от четырех переменных. 5.25. Показать, что )М"! < )Я" / при и > 4. 5.26. Пусть А С В,". С множество всех наборов Н 6 В", для которых существует набор () из А, сравнимый с Н. Локазатдч что ~А~(",) <~С~© . 5.27. Пусть 1 6 М", йь(1) = ~агу ОВ,",~ /(„).
Показать, что Чя — х(У) < Чь(У) (к = 1: . - и) 5.28. Функция уд(ха), определенная на Ва и принимающая про- извольные действительные значения, называется обобщенной моно- тонной функцией (сокращенно ОМФ), если из Н < Д вытекает, что р(Н) < рФ. 1) Показать, что ОМФ уд(ха) может быть представлена в виде ли- нейной комбинации монотонных булевых функций следующего вида; ~р(х") = с+ ~~~ ауу(х"), Вх " )ем где с †.
действительное число, а ас -- неотрицательное число. 2) Пусть у(х") ОМФ, а уь(уд) = (") ~ ~р(Н). Доказать, что уь 1(ф < уь(ус) (Й = 1, ..., и). 5.29*. 1) Пусть Дха) и д(ха) монотонные булевы функции. )Хх д д! 2 ~> )Ху! 2 )Хд( 2 2) Пусть уд, ..., ~„— — функции из М". Показать, что 1У 1" д 2 "> П (~~Ул~2 ") ь« 1<с<в 80 Га.
П. Замкнутые классы и полнота 5.30. 1) Верно ли, что если у' Е М", то из условия а, Д Е В", и(?1) > и(а) (О?40 > уДО) вытекает, что ?(Д) < 1(?2)? 2) пусть для всякого й (О < и < п) из условий и(11 и) < 2и — 1— — 2", и(?Зи) = и(аи) + 2~ следует, что 1(а") < 1(?З"). Доказать, что 4" Е М.
и — 1 2" — 2 — 1 5.31. Пусть г'(уз ) = Д~ ~„(у, — 4 у4„24). Доказать, что у=о =о (?у?! = )М"). 5.32. Можно ли из функции у = хуз Ч 1(ху -4 2) получить; 1) функцию Ьх отождествлением переменных, 2) функцию хя отождествлением переменных; 3) функцию хе с помощью суперпозиции; 4) функцию х подстановкой констант О, 1; 5) функцию хз подстановкой константы 0; 6) функцикз 2 отождествлением переменных? 5.33.
Показать, что всякая монотонная функция содержится не менее чем в двух классах из То, Т„Д. 5.34. Показать, что М не содержится ни в одном из классов То, Т1, Я, Е, указав монотонные функции, не содержащиеся в соответствую- щих классах. 5.35. Можно ли с помощью функций ху, Х1?у, 1 получить О? 5.36.
Показать, что множество (О, 1, ху, х Ч у) является базисом в М. 5.37. Из множества (О, 1, ху, х Ч у, хр Ч 2, ху Р уз 1? Хх) выде- лить все подмножества, являющиеся базисами в М. 5.38. Доказать, что всякий базис в М содержит не менов трех и не более четырех функций. 5.39. Показать, что всякий базис в М, состоящий из трех функций, содержит функцию, существенно зависящую не менее чем от трех переменных.
5.40. Привести примеры базисов в следующих классах: 1) То П М; 2)Т,пМ; 3)ЬПМ. 5.41. Показать, что если у Е М, то ?' Е М. 5.42. Можно ли из функции 1" = ху Р уя Ч зх получить с помощью операции суперпозиции функцию д = х Ч у? 5.43. Доказать, что у Е М П Я тогда и только тогда. когда 1" Е Е М: (1о*)* = 11" и ~о(х" 1) = 4" (х1....., х, 1, О) 3с 1"(х1, ..., хи 1, О) = О. 5.44. Пусть т(х~) = хзхз Ч хзхзЧ хзх1 и 1(хи) Е М П Я (и > 3). Доказать справедливость представления 4 (Х ) = гп(1 (Х1, 21, Хз, Х4,...., Хи), 1 (Х1, Х2, т2, т4, .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
