Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 17
Текст из файла (страница 17)
Выяснить, является ли множоство А базисом в классе Л: ЦА=(ху х), К=Т~., 2) А=]хуЧз), К=То, 3) А = (ху, т д, х р д), К = Т~., 4) А = 1х ез у ~З з, т[х, р, я) ), К = То П Т,; 5) А = 1ху, х со у 9 я, т[х, д, я)), К = То й Т,; 6*) А = Еху, т[т, у, з)) Л = ТойТз' 7) А = ~х Ю у, та(х, д, з)), К = То Г1 Тз, 8) А=~х~lу, хд), Л =То, 9) А=Схйдйз,0), Л =ТойТл «" о, Класс монотонных функций 75 10) А=(х«одах, хсауЮг61«), К=тоГ1Ь; 11) А=(хубту«йх, хйуйЗз), К=Тейт~,' 12) А = (т(х, у, .я), х Ю д «й х), К = То С Я; 13) А = ((х у) ), К = ЬПЯПТо, 14) А = (х т(у, з, «)), К = ТВ 15) А = (ху, х«йу~г, худ), К = Тейт,. 4.7.
В заданном векторе о заменить координаты символами из множества (О, 1) так, чтобы получился вектор о«значений некоторой функции «, образующей базис в К. Локазать единственность решения: 1)о=(" . "..), К=ТоПХ; 2)о=( ), К=ХПЯ: 3)о=( 110 11 ), К=То, 4) Й=( ), К=Т,Г~Х; 5)а=( ), К=ХГ1ЯСТ; 6) о = (-. 11001100110100--), К = То П т«,. 7) а — (--. -- 1 — . — - — --. —.
- — .—. —..----. — —. — .†.), К = Х П Я; 8)о=( 0 — 0 — ), К=ЯПТ;; 9) Й = ( — -0 — — — — 0 — — — -), К = Я Г1 То, 10) о=( 1 0 ), К=ЯСТВ 11) а=(— 10 ), К=Ялте; 12)а=(. ---.1 .О. ), К=ЯПТВ 13) а — (.— --- . 1-- ----------- 14) о — ( 15) а=( 00 ), К = Я. ..-), К=х пт пт; 1 ), К=Х ПКо «зТо, 4.8. Доказать, что класс Тз является предполным в Рю 4.9. Доказать, что множество А является пред|юлным в Хл 1) А = [(О, хЦ: 2) А = Е П т1; 3) А = Ь П То, 4) А = Ь П Я. 4.10. Выяснить, является ли множество А предполным в То.. 1) А=тоПХс, 2) А=то«15; 3) А=ТоГ1ты 4) А=[(О,х)); 5) А = [(ху, х '«уЯ. 9 б. Класс монотонных функций Булева функция «(ха) называется монотонной, если для любых двух наборов о и Х«из В" таких, что о ( (), имеет место неравенство Х(о) ( Щ).
В противном случае Х(х") будет называться немонотонной. Множество всех монотонных булевых функций обозначается через ЛХ, а множество всех монотонных функций, зависящих от переменных ты хз, ..., х„, через М"'. Множество М является замкнутым и предполным в Рз классом. Справедливо утверждение (лалама о нелонотонной функции): если «ф М, то, поде~валяя на места ее переменных функций О, 1, х, можно получить функцию об 76 Га. 55 Замкнутые. классы и ноанотаа Вершина И куба В" называется нижней единицей (верхним нулем) монотонной функции Д(хн), если 5'(о) = 1 (соответственно 5" (П) = О) и для всякой вершины 55 из 55 < о вытекает,что 5(,3) = 0 (соответственно из П < 53 вытекает, что 5"(53) = Ц.
Проверку на монотонность булевой функции 5(ха), заданной своим вектором значений И5 = (оо, 421, ..., ог» 1), можно осуществить следующим образом. Разделим вектор а5 на две равные части соу о = (СОО 111,, Егг--о-1) И СО5 = (422 -Ы Сог--о-1,; Сог" — 1) ЕСЛИ отношение 551 < ЙП не выполнено, то 5 (ха) не является монотонной. о В противном случае каждый из векторов оП (о 6 (О, 1)) вновь раЗдЕЛИМНадВЕраВНЫЕЧаСтИСО со Ига ~Л. ЕСЛИ НЕ ВЫПОЛНЕНО ХОтябЫ 5,4 53 одно из отношений о л < сг со, то 5(ха) ~ М.
В противном случае вновь делим векторы пополам и т.д. Если отношение предшествования выполняется для всех пар векторов, то 5(ха) монотонна. П р и м е р 1. И5 = (1001111Ц. Первый шаг не обнаруживает немонотонности, так как 1001 < 1111. Второй шаг дает: 10 ~ 01, 11 < 11. Монотонность нарушена. Лля доказательства монотонности функции 5, которая задана формулой, можно с помощью эквивалентных преобразований представить функцию с помощью формулы, содержащей лишь связки Й и Ч (или другие монотонные операции) .
Пример 2. 5 = х ЧУу ухуж Имеем ху4еУуг = х(у 4еуг) = = У(у 45 2). Палее х Ч х(у Ч 2) = х о'у 45 2. Функция 5 монотонзш, Установить немонотонность функции 5 можно также, получив из нее немонотонную функцию одной переменной путом замены остальных переменных константами. 5.1. По вектору значений со5 выяснить, является ли функция 5 монотонной: Ц со5 = (0110); 2) П5 = (0011011Ц; 3) оу = (0101011Ц; 4) ау = (01100110): 5) И5 = (0001 011Ц; 6) И5 = (01010011); 7) Иу = (00100011 0111111Ц; 8) 85 = (0001010101П011Ц, 5.2. Проверить, является ли функция 5" монотонной: Ц 5 = (Х1 егхг)ее (Х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); Ц 1а = 21хгхз Ч хгхг, '2) 1е = Х1 64 хг 64 хз; 3) У = хгхг ~Э хз~ 4) 5" = х1 ухгУз:. 5) 1 = хгхз Ю хгх4,' (Х1хгха 4 Х2ХЗ) ч' Х4 ° З" о, Класс нонопгоннгяг фуннянй 77 5А. Пусть Мп множество тех векторов сг = (оо: ом ..., ссг -г), которые являются векторами значений монотонной функции.
Найти число векторов из о(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 ( О ). З)-4 ( ц. 4) 7г=( -ОО-- О - - --); 5) 7'=(--01 -- О-- - ); 6) 7 "о = (-- -- — О - О - - --О ------ ------ ); 7)у — ( 1 1 1 8)у=( 1 0 ) 5.6. Выяснить, при каких и ) 1 функция у(т,") монотонна: 1) Дх") = хг Ю хг Ю... Ю хп; 2) ((хо) = (43 х,х,; 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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
