Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 18
Текст из файла (страница 18)
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. 4) Пусть ф,(н) число монотонных функций, существенно зави- сящих от переменных хы хю ..., х„. Найти фс(п) для п < 4. 5.24. Перечислить все попарно неконгруэнтные самодвойственные монотонные функции, зависящие от четырех переменных. 5.25. Показать, что )М"! < )Я" / при и > 4. 5.26. Пусть А С В,". С множество всех наборов Н 6 В", для которых существует набор () из А, сравнимый с Н. Локазатдч что ~А~(",) <~С~© . 5.27. Пусть 1 6 М", йь(1) = ~агу ОВ,",~ /(„). Показать, что Чя — х(У) < Чь(У) (к = 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, . ° °; Хи) ,~(ХЗ; Х2~ ХЗ; Х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). Критериальная таблица имеет вид табл. 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 — лл. По полученной д.н.ф. В выпишем подмножества функций, соот- ветствующие слагаемым д.н.ф. В. Это и будут искомые базисы. В нашем случае имеется два базиса; 61 — — (уз, уз) и Бз — — Я, уз, ул) . Полноту систем функций в Рз можно доказывать путем сведения исследуемой системы к известным полным системам таким, как (ху, хс уу, х), (ху, хЕу, Ц, (хну), (ху).
Пример 4. Показать полноту в Рз системы А = (7"1 = ху Н уз У " ях 72 = 0: 73 = 1~,(4 = х Е д Е я). Имеем Ях, у, 0) = ху, (4(х, у, 0) = х Е у. Таким образом, из функций системы А получаются функции ху, х Е у, 1 одной из выше- указанных полных систем. Это и означает, что система А полна в Рз. 6.1. Выяснить, полна ли система функций: Ц А =(ху, хчу, хЕу, хуЧуяЧзх); 2) А=(ху, хЧу, хЕдЕЕяЕ1), 3) А=(1, х, х(д е)ех(уев), х у); 4) А=(0, х, х(уев)еуз); 5) А=(т, х(у з) (дЧз), хЕуЕя); 6) А=(х, х(у з) уя, хЕдЕз):, 7) А=(ху(хЕу)., хуЕхЕу, 1, хуЕузЕзх); 8) А = (хд(х Е я), 1); 9) А = (х + д, х — ~ ух, х Е у Е з, 1); 10) А = (х -+ д, х Е у). 6.2. Выяснить, полна ли система А функций, заданных векторами своих значений: Ц А = (уз = (0110), уз = (1100001Ц, уз = (10010110)); 2) А = (Л = (011Ц; .(з = (0101 1010), (з = (0111 1110)); 3) А = ((з —— (011Ц, (з = (1001 0110)); 4) А = Я = (010Ц, (з = (1110 1000), Л = (0110 100Ц); 5) А = (Л = (100Ц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
