Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 19
Текст из файла (страница 19)
Показать, что: 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. Пусть ( 6 М", йя(д) = ~Ху О В~",~ /(„). Показать, что Чя — х(У) < Чь(У) (к = 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, . ° °; Хи) ,~(ХЗ; ХЗ~ ХЗ; Х4 ° °; Хи)). 81 у 6. Полногпа и замкнутые классы 5А5. 1) Пусть Р" множество функций у из ЯГ1 М", существенно зависящих от и. переменных.
Для каждого п, < 4 перечислить функции из Р". 2) Доказать, что для всякого п ) 4 из функции у Е .Р" можно получить путем отождествления переменных функцию т(хе) = хгхг Ч Ч хгхз Н хзть 5.46. 1) Доказать, что т(хе) = хгхг 'в' хгтз Ч хзхг образует базис в МСЯ. 2) Доказать, что любая функция из М Г1 Я, существонно зависящая более чем от одной переменной, образует базис в М й Я.
5.47*. Пусть Р множество, состоящее из всех монотонных элементарных дизъюнкций, а Х вЂ” множество, состоящее из всех монотонных элементарных конъюнкций. Показать, что множества Р С (О, 1), Х С (О, 1)., М й Тв, М С Т1 и только они образуют пред- полные классы в М. 8 6. Полнота и замкнутые классы В Рг справедлив следующий критерий полноты. Теорема (Э. Пост). Система А функций иэ Рг полна в Рг тпогда и только тогда, когда она целиком не содерокится ни в одном иэ классов То, Ты Ь, Я и М. Функция 1(хо) называется шефферовой (или функцией Шеффера), если она образует базис в Рг.
При исследовании полноты систем функций удобно пользоваться таблицей, которую мы будем называть криглериальной. Эта таблица имеет пять столбцов, каждый нз которых соответствует одному из пяти предполных классов в Рг, а строки таблицы соответствуют функциям исследуемой системы. На пересечении строки таблицы, соответствующей функции 1, и столбца, соответствующего классу К, ставится знак плюс, если у Е К, и минус, если 1 ф К. Система функций полна тогда и только тогда, когда в каждом столбце содержится хотя бы один знак минус. Пример 1. Исследоватьполноту системы А = (у"г — — хд ег г, = х ез д йэ 1). Критериальная таблица имеет вид табл. 2.1. В каждом Таблица 2.1 столбце имеется не менее одного минуса.
Система полна. Пример 2. Исследовать полноту системы А = ф'1М) С Т1(То С С Т,). Для исследования полноты этой системы можно использовать некоторый аналог критериальной таблицы, в котором строки соот- В Г. П. Гаврилов, А. А. Свпоженко Гь П. Замкнутые классы и полнота ветствуют не отдельным функциям, а подмножествам системы А. Разобьем систему А на подмножества А> = Я> М и Аг = Л>~(То 0 Т>) и исследуем принадлежность функции из этих подмножеств предполным классам. Заметим, что х> Е А> й Аг. Отсюда следует, что А; Я То, А, Я Я Т„А; Я >»' (> = 1, 2).
Очевидно, что А> С Я, Аг С В. Заметим, что п>(х, у, г) = ху й уг 61 гх принадлежит А> и не является линейной. Таким образом, А> Я Ь. Остается выяснить справедливость включения Аг С Я. Всякая функция 1 из А имеет вид у = о>х> Ю Юогхг 6~... С похо Ю ое; поскольку Аг С Ь. Поскольку Аг Я То, то ое — — 1. Поскольку Аг л Т>, то ~(1) = ~ ~ец 6~ 1 = О. Следова- 1<><и тельно, нечетное число коэффициентов о>, ..., он обращается в 1.
Значит, функция ) линейна и зависит существенно от нечетного числа переменных. Такая функция, как нетрудно проверить, является само- двойственной. Аналог критериальной таблицы имеет вид табл. 2.2. Таблица 2.2 Система А не является полной в Рг. Критериальная таблица может быть полезной для нахождения базисов, содержащихся в системе А. Пример 3. Из полной в Рг системы А = (Л = х»> у,,6 = ху Ю г, гз = хЮу 9 г>г>1, ~4 = ху>г>уз бЗ зх) выделить всевозможные базисы. Критериальная таблица имеет вид табл.
2.3. По таблице составим Таблица 2.3 к. н. ф. К, в которой элементарные дизъюнкции соответствуют столбцам таблицы и включают в качестве слагаемых символы тех функций, которые не входят в класс, соответствующий столбцу. В данном случае имеем К = >з®»1г У 1зН1г >>14)>,1> >> 1г)>З> >> уг >>гз). Перемножая скобки и используя для упрощения равенства вида А А = А, А(А >> В) = А, А >АГАВ = А, приведем к.н.ф. Кк д.н.ф. П, ~ 6. Полноеиа и замкнутые классы в которой упрощения АГАВ = А невозможны. В нашем случае имеем 7т = ззУ2 Ч,(4)(Л Ч,(2) = зззз Ч.ЬЫ1 — лл.
По полученной д.н.ф. 77 выпишем подмножества функций, соот- ветствующие слагаемым д.н.ф. 77. Это и будут искомые базисы. В нашем случае имеется два базиса; Бз — — (7з, 7з) и Бз — — Я, 7з, 7л) . Полноту систем функций в Рз можно доказывать путем сведения исследуемой системы к известным полным системам таким, как (ху, хс ду, х), (ху, х~у, Ц, (хну), (ху).
Пример 4. Показать полноту в Рз системы А = (7"1 = ху Н уз У " ях 72 = 0: 73 = 1~,(4 = х 9 д ~Э я). Имеем Ях, у, 0) = ху, (4(х, у, 0) = х 6~ у. Таким образом, из функций системы А получаются функции ху, х ~В у, 1 одной из выше- указанных полных систем. Это и означает, что система А полна в Рз. 6.1. Выяснить, полна ли система функций: Ц А =(ху, хчу, хйу, хуЧуяЧзх); 2) А = (ху, х Чу, хвдвяЕЦ, 3) А=(1, х, х(д е)бх(убя), х у); 4) А = (О, х, х(у бааз) Юуз); 5) А=(т, х(у з) (дЧз), хбЗуая); 6) А=(х, х(у з) уя, хвдйз):, 7) А=(ху(хву)., хувхву, 1, хуйузйзх); 8) А = (хд(х еЭ я), Ц; 9) А = (х + у, х — ~ ух, х й у й з, Ц; 10) А = (х -+ д, х Е у). 6.2. Выяснить, полна ли система А функций, заданных векторами своих значений: Ц А = (7з = (0110), 7з = (1100001Ц, 7з = (10010110)); 2) А = (Л = (011Ц; .(з = (0101 1010), (з = (0111 1110)); 3) А = ((з —— (011Ц, (з = (1001 0110)); 4) А = Я = (010Ц, (з = (1110 1000), Л = (0110 100Ц); 5) А = (Л = (100Ц.
7з = (1110 1000)); 6) А = Я = (1Ц, Л = (011Ц, Ь = (0011011Ц); 7) А = ((з — — (10), 7з = (0011 011Ц); 8) А = ((з —— (1Ц, 7з = (00), 7з = (0011 010Ц); 9) А = (Л = (1000 ОООЦ,,(з = (011Ц, Л = (101Ц); 10) А = Я = (1000 ОООЦ, (з = (0110), (з = (100Ц). 6.3. Выяснить, полна ли система А; Ц А = (о П М) Ол (ЦМ); 2) А = (Т С1 Тз ПТо) 0 Я\(То Э Тз):, 3) А = (Г С1 Тз) О (Я С1 М); 4) А = (Ь П Тз) О (У Т ); 5) А = (М~,То) 0 (А~Я); 6) А = (М~,То) 0 (Я~гЛ); 7) А = (Л ОЗ М) 0 (Я~То); 8) А = ((Т Г1 М)~,Тз) 0 (Я Л Тз); 9) А =(М)б) и(ПЛЯ); 10) А= (МЭЯ) и(то'~М) и(Т,ОЗВ). 84 Гл.
11. Залккртыс классы и полнота 6.4. Проверить, является ли система функций А базисом в Рг.. ЦА=(х-+д, х~Ву, хЧу); 2)А=(х61уоВг, хЧу, О, 1); 3) А=(хЮдйуг, хВЭуй1); 4) А=(хууг, хууг, хд г); 5) А = (х <В у ~З г, х ЕЭ у ЕВ г ЕВ 1, ху ЕВ уг Е гх, х); 6) А=(х~ЭуЕВг, хуагх~Згу, О, 1); 7) А=(хау, х уг); 8) А = (хд йг д ОВ й О, 1, хЧ д). 6.5. Из полной в Рг системы А выделить всевозможные базисы; Ц А=(1, х, ху(х~Ву), хву|ЗхуйЗугйгх); 2) А=(0, хВу, х-+у, ху хг): 3) А=(0, 1, хЮуйг, ху~Эгх6~уг, хууг, хну); 4) А=(хд, х ду, хдЧг.
хбу, х — гу), 5) А = (ху Вз г, х йг у оВ 1. ху, х):, 6) А=(хууг, х, хгу, О, хазу); 7).4=(ху, ху'уг, тйу, т — гд, х); 8) А=(хЮу, х у, хЗуаг,ху, х — >д). 6.6. Используя теоретико-множественные операции, выразить че- рез известные замкнутые классы То, Т„Б, Я, М и Рг замыкание множества А: Ц А = Рг'~(То 0 Тг 0 Л 0 Б 0 М); 2) А = М~ (То Г~ т); 3) А = М'1(То П Тг); 4) А = То й (Ь1Я); 5) А = Я1(То'1Тг); 6) А = (Ь П Я)~(То С1 Тг); 7) А = У1Тг Сг ЬЦТг 0 То); 8) А = Ь'1(Я 'сг' То); 9) А = Р,(То 'сг' Тг); 10) А = (То~Тг) сг' (М1Ь); 1Ц А = (То1Тг) 0 (М' То); 12) А = М~,(Я 'сг Б). 6.7 Ц Пусть Р'(Х ) - множество всех функций из Рг(Хг), су- щественно зависящих от двух переменных.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
