Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 17
Текст из файла (страница 17)
Таким образом, ~7тт й оеп~ 2 ~~, С2т-~-1 2п 0 < т < т тт — 1 т т 2 1 Ясно, что ~7" Г1 Зп Г1ТД = — ~Ь" Г1З" ~, поскольку свободный член 2 определяется однозначно (равен 0). Таким образом, ~А~ = 2п 2 4, класом функций, сохраниюсаих констани«о! 4.1. Выяснить, принадлежит ли функция /' множеству Т1!!Те! 1) У = (х! -« хг)(хг -« хз)(хэ -« х!): 2) У = пг(хг,хг,хз); 3) !" = х! -« (хг †« (хз †« х!)); 4) У = х, хгхз «/ х!хг ц хг, 5) У = [х! «/хг)хз «/х!хг «/тг, 'б) 1 = х!хг хз !/ У«хг'~ хг'!/хгхгхз,' 7) а/ = [10010110); 8) о/ = [11011001); 9) о/ = (10000111), 10) сг/ = [0001 1011).
4.2. Выяснить, при каких и функция /[х!!) принадлежит множеству То««Т! ! /п — 1 ц у[хи,) х а«х, 49 езхи 2) Х(х') = ~ '3 х х';! !=1 3) ~[Хи) Я) 2С,Х; 4) у(Х ') = !Э Х «/Х!) 1<4<!<п 1<!<!<и 5) Д[хп) = 1 б«(х1 -«хг)(хг «хз)(хз + х4) , (хи, -«хи)(х, -«х!)' и — 2 б) 1(Хс!) = Я! (Х! -+ [Хг+! -+ Хп«2)) ~ !=1 п — г 7) Яс™) = 9 [(х! — «хг-ы) — «х!4.2); !=1 и — 2 8) у[х ) = «1)(х! Е х; . хс,. ); 9*) 1[х и) = . Ф с=1 1<!<!<Я<п 10) /[х") = ф гл(хс, х! хь)' 1<~<!<Ь<п п 1ц г(г") = Я) !р!(хп), !р, 6 Я ! !Т!'! /и†! -1)4,Х [ Я~,п*ф" !), Гдс у1, =1 1=1 про- ИЗВОЛЬНЫЕ ФУНКЦИИ ИЗ Рги, !Р* ДВОйСтВЕННаи К !Р! ФУНКЦИЯ, =1,...,и — 1; /» — ! и — 1 13) /[Хи) = Хи~ ««/!р!(Х" ")[ !2« ~ а«1(ХП !), ГдЕ !р; — ПРОИЗ=1 1.= ! вольные функции из Ри, !рг двойственная к !р! функция, = 1, ..., п — 1; 14) /[Хп) ««~у!![Хп) !р! Е (АПТЕК)!«О; =1 п 15) ~(х") = 1~~ !р!(х"), !р; Е Я «Т1.
Пример 3. Показать, что [[ху, х !Э у)) = То. Решение. Заметим, что полипом любой функции /" из То не содержит 1 в качестве слагаемого. Но всякий такой полином может быть, очевидно, получен с помощью суперпознции из функций ху, х 9 у.
74 Гж 11. Замккдтыс классы и полнота 4.3. Подсчитать число функций, зависящих от переменных хы хз, ..., ха и принадлежащих множеству А: Ц А=ТойТ~; 2) .4=То0ТП 3) .А=ТойЛ; 4) А=Т1 ПЯ; 5) А = То и Ь; 6) А = Р,Т,; 7) А = (Л и Т,) й Я: 8) А = Ь й Т, й Я; 9) А = 5 и Я и То; Р0) А = [5 О ~)1Т,; 1Ц А = [1Л,То) Г1 Я; 12) А = 5 П То, '13) А = (Я Г1 То) 0 ТГП 14) А = (Я й й~~,,Тз, 15) А = [То'1Т1) й Я; 16) А = [То~Тз) П Т; 17) А= фиЛ)ПТ,; 18) А=(Т,иТо)ПЯ; 19) А=Т,ПТ,Г1Л; 20) А = [ТойТ1 Г15)1Я; 2Ц А = (ЯГ17)1То' 22) А = [К й Ь)~[Т, й Т,); 23) А = ф й ЙЯТо и Т,); 24) А = (51 То) й ТП 25) А = Я~ДТо 0 Т1); 26) А = [о П То)~ТП 27) А = Я~,[То 0 5); 28) А = Я Г1 То Г1 Ь; 29) А = РЯТо 0 Т1); 30) А = (5ЦТ, и Т,)) П В; 3Ц А = ~ ~5; 32) А = 5~В; 33) А = (А'1Я) ПТ1; 34) А = [(Я~А)1То)~Т1,' 35) А = ([К й Ь)~То)~Т1, 36) А = Я й (Тз~Ь); 37) А = (Л й Я)~[То й Т1 ); 38) А = [Ь й ТоЯБ й Т1); 39) А = [К й Т )~Т,; 40) А = (Т, й Т й Т,)~К, 4Ц А = [То й Тз П Я) ~7; 42) А = То 0 Т1 С1 Я; 43) А=То0Т10ЯОЬ' 44) А=То0ТзОЬ' 45) А = (о\Я) 0 [То~Тз).
4.4. Показать, что: Ц 5ПВПТо =5ПКПТз =5ПТойТ, =5ПКПТойТ,; 2) КГ1То=КПТз =ЯГ1ТойТм 4.5. Показать, что: Ц [~хН д, т 61 уН = То, .2) [~хЧ у, х - у)] = Т,; 3) Цху, х уН = Т~,. 4) [(ху ~Э з)] = То,. 5) [Сху, х 61 у Ю зн = То Г1 ТГП 6) Нху йз з йз 1)] = То Г1 Т1, 7) Цхйу)]=ЬПТо; 8) [Ех-у)]=7 ПТ1, 9) Цх ГЭ у ~В о)] = Ь П Я й То, 10') []т(х,у,з), хбуйя)]=ТойК, 11') Н (х, у, з))] = Т, ПК; 12) [1хвдГО ГО1)] = Т П5; 13) ~(хд, н~[х, у,. Р))] = То й Т,; 14) [бс'~ у, ап(х, у, з))] = То П Т,; Рб) [)т[х, д., ), х чз у)] = Т .
4.6. Выяснить, является ли множоство А базисом в классе К: ЦА=(ху х), К=Т~., 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 Га.
56 Замкнутые. классы и ноанотаа Вершина И куба В" называется нижней единицей (верхним нулем) монотонной функции Д(хн), если 5'(о) = 1 (соответственно 5" (П) = О) и для всякой вершины 55 из 55 < о вытекает,что 5(,3) = 0 (соответственно из П < 53 вытекает, что 5"(53) = Ц. Проверку на монотонность булевой функции 5(ха), заданной своим вектором значений И5 = (оо, е21, ..., ог» 1), можно осуществить следующим образом. Разделим вектор а5 на две равные части соу о = (СОО 111,, Егг--о-1) И СО5 = (422 -Ы Сег--о-1,; Сог" — 1) ЕСЛИ отношение 551 < ЙП не выполнено, то 5 (ха) не является монотонной.
о В противном случае каждый из векторов оП (о 6 (О, 1)) вновь раЗдЕЛИМНадВЕраВНЫЕЧаСтИСО со Ига ~Л. ЕСЛИ НЕ ВЫПОЛНЕНО ХОтябЫ у,о 53 одно из отношений о л < сг со, то 5(хн) ~ М. В противном случае вновь делим векторы пополам и т.д. Если отношение предшествования выполняется для всех пар векторов, то 5(ха) монотонна. П р и м е р 1. И5 = (1001111Ц. Первый шаг не обнаруживает немонотонности, так как 1001 < 1111. Второй шаг дает: 10 ~ 01, 11 < 11.
Монотонность нарушена. Лля доказательства монотонности функции 5, которая задана формулой, можно с помощью эквивалентных преобразований представить функцию с помощью формулы, содержащей лишь связки Й и Ч (или другие монотонные операции) . Пример 2. 5 = х ЧУу ухуж Имеем хууУуг = х(у ууг) = = У(у Ч 2). Палее х Ч х(у Ч 2) = х о'у Ч 2. Функция 5 монотонзш, Установить немонотонность функции 5 можно также, получив из нее немонотонную функцию одной переменной путом замены остальных переменных константами.
5.1. По вектору значений с45 выяснить, является ли функция 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 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. Локазатгн что для всякой монотонной функции у(х") справедливы разложения .У(х ) = 'П(х ) УУо(т ) У(х ) = (' чуо(х ИФх ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
