Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 19
Текст из файла (страница 19)
° °; Хи) ,~(ХЗ; Х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Ц. 7з = (1110 1000)); 6) А = Я = (1Ц (з = (011Ц (з = (0011011Ц); 7) А = (7з — — (10), 7з = (0011 011Ц); 8) А = ((з —— (1Ц, уз = (00), уз = (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 Ц Пусть Р'(Х ) - множество всех функций из Рг(Хг), су- щественно зависящих от двух переменных. Найти базисы Б С Р'(Хг), содержащие: а) одну функцию; б) две функции; в) три функции.
2) Показать, что нет базисов Б С Рг(Х'), содержащих четыре функции. 6.8. Выяснить, можно ли расширить до базиса в Рг множество А: Ц А=(х у,щ(х,у,г)); 2)А=(х); 3)А=(хну,хуу); 4) А = (х'~у, ху); 5) А = (О, 1); 6) А = (О, 1., х Чу); 7) А=(х — >у, хну); 8) А=(хор, х у). 6.9. Выяснить, полна ли система функций А = ( Хм Хг): Ц Хг б Я'1М, Хг Ф ЬсгБ: Хг > Хо = 1; 2)УгкЬОТо0Тг, УгЕМЛХч Л вЂ” «Уг— = 1; 3) Л ~ То ог Ь, Хг ф Я, Хг — ~,Хг — = 1; 4) .Хг б (БПЕ)~,То, Хг Е М~(Тг ПБ), Хг -з Хг — = 1 6.10. Выяснить, при каких п > 2 функция Х(х") является шеф- феровой: Ц Х(хп) =1ЮхгхгЮ...Юх,хоы Ю...Юхп гхп ~хохм 2) 1(хи) = 1 сз хгхг Ю...
~Э х,х,л-г Ю... Ю хп гхп:, у у. Полнота и замкнутые классы 85 3) ~(х") = ~/ г,,х,; 4*) ~(х") =1Ю ~ х,х,; 1« 14 1<~<1<и ) Й ) у хнхи' 'х8 т1~ 1«,.. <птн< 6) 1(УП") = 1 Ю (Х1 — 1 хг) Ю (хг — 1 хз) Ю . ... Ю(хп, -+ хп) Ю (хп -1 У1): 7) ге(хп) = 1 Ю (Х1 -1 тг) Ю (хг -1 Уз) Ю... Ю (Х„1 -1 хп); 8) 1(Хп) = (Т1 ~ Х2) Ю (Хг ~ Хз) Ю...
Ю (Хп — 1 ~ Хп) Ю (Хп ~ У1); 9) ге(х") = (У1 ~хг) Ю (хг ~хз)Ю ...Ю (х -1 ~ хп); 10) 1(х ) = Х1У2 . Хп Ю (Х1 + Х2) пс (Х2 е ХЗ) 3е ... СЕ (Хп 1 — 1 Хп) ЕЕ(хп -+ Х1). 6.11. Доказать, что, если 1" монотонна и зависит существенно не менее чем от двух переменных, то система (О, 1) полна в Рг. 6.12. Пусть 11, 52, 12 попарно различные функции переменных х1, хг, существенно завися1цие от двух переменных. Доказать, ЧтО СИСтЕМа (Х, )Ы 1<г, Я ПОЛНа В Рг. 6.13.
С помощью суперпозиции из функции 1 можно получить константы 0 и 1. Доказать., что 1 --- шефферова функция. 6.14. Монотонная функция 1" имеет ровно две нижние единицы. Доказать, что 1 шсфферова функция. 6.15. Доказать, что если 1 ф То'11 Т1 11 8, то у' функция. 6.16. Подсчитать число шефферовых функций в Ру(Х"). 6.17. Функция у' зависит существенно ровно от двух переменных и не принадлежит множеству Т, 0 То. Доказать, что функция 1 шефферова. 6.18*). Доказать, что с помощью отождествления переменных из шефферовой функции, зависящей от и > 3 переменных, можно получить одну из функций х У р или х у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
