Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 17
Текст из файла (страница 17)
10) А = Е ГД Рг(Хг); 11) А = (Ь 9 Я) 0 (0); 12) А = 7 Б; 13) А = (хд 9 хг, хд 9 хг 9 хз 9 1, Ц; 14) А = (хдхг дУ хдхг, х 9 1); 15) А = (Аддин) П Р(Хг). 3.10. Доказать, что не существует линейной функции у, образундшей базис в В. 72 Рл, П. Замкнутые классы и полнотаа 3.20. Доказать, что 7 й 3 = ((х 9 у 9 2 9 1К. 3.21. Доказать, что система (х,,(1, Уг, Уз), где Л, Уг, Уз попарно различные функции, существенно зависящие от переменных х1, хг, ~од~а в Р2. 3.22.
Доказать, что система (О, х, (1, 2'2, 22), где тт, тг, тз Различные функции, существенно зависящие от переменных хт, х, ... ..., хп, п > 2, полна в Рг. 3.23. Доказаттн что из полинома степени 3, зависящего от трех переменных, с помощью отождествления переменных можно получить функцию вида хд 9 1(х, у), где 1(х, д) — некоторая линейная функция. 3.24. Доказать, что из нелинейной функции 7'(хп) с помощью отождествления переменных можно получить функцию вида хд9 91(х, у) или вида хд 9 ух 9 гх 9 7(х, у, 2), где 1(х, у) и 7(х, у, г) линейные функдии.
3 4. Классы функций, сохраняющих константы Функция т'(хп) сохраняет контианту 0 (констланту 1), если у(0, О....., О) = 0 (соответственно если Г" (1, 1, ..., Ц = 1). Множество всех функций алгебры логики, сохраняющих константу 0 (константу 1), обозначается через То (соответственно через Тт).
Множество всех функций из Та (Т1), зависящих от переменных хт, хг,..., хп, будет обозначаться через Тп (соответственно через Тп). Каждое из множеств 7о, Тт является замкнутым и предполным в Рг классом. п — 2 пример 1. Выяснить, при каких и функция Г(хп) = ((2 т(х„ т=1 хт.ет, х,, 1) принадлежит множеству То й Тт. Рещение.
Если и нечетно, то Г(хп) является суперпозицией функций т(хт, хг, хз) и хт 9 хг 9 хз, принадлежащих замкнутому классУ 'То й Т,, и, следовательно, Г(хп) б То й Т,. Если и четно, то Г(1, 1, ..., 1) = О,и ( ф То й Т,. Пример 2. Найти число функций 2" (х и ), принадлежащих множеству А = (Л'1То) Г1 3. Решение. А = (7 т (То й 1)) й 3 = (Ь й З)ЦХ й То й 3).
Следовательно, ~А~ = ~ЬйЗ~ — ~Т,йЗйТо( Линейная функция Г(х") является самодвойственной тогда и только тогда, когда она существенно зависит от нечетного числа переменных, т.е. представима в виде Г = х„9 х;, 9... 9 хе.., 9 ст, и б (О, Ц. Число линейных функций Г(хп), зависящих существенно от й переменных, равно 2Сь (Сь способами можно выбрать и переменных из хт,. хг, ..., хп и двумя способами можно выбрать свободный член).
Таким образом, ~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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
