Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 18
Текст из файла (страница 18)
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.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
