Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 19
Текст из файла (страница 19)
ху, х):, 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 переменных, можно получить одну из функций х У р или х у. 6.19. Ц Доказать, что Ь С Т1 С То 11 Я. 2) Доказать, что множество А является непустым: а) А = (Ь ЕЗ Т1)ЦТо Сз Я); б) А = (Ь Г~ То)11(Т1 '11 Я); в) А = (Т СЗ8)1(таит,). 6.20. Пусть 1(х") — симметрическая функция, существенно за.- висящая от п, > 3 переменных, и у'(1110...0) = )'(00...0). Доказать, что система (((х"), О, х) полна в Рг. 2) Пусть п четно, 1" (хп) симметрическая функция, существенно зависящая от п переменных, 1(0) ~ 1(1).
Доказать, что система () (хп), х) полна в Рг. 6.21. 1) Пусть А -- множество функций из Рг(Хп) такое, что 1 ~А~ > — 2 . Доказать, что система А полна в Рг, п. > 2. 2 Гл. Рм Замкнутые классы и полнота 2) Пусть А множество функций из Рз(Х"), существенно зави- сящих от п переменных, ~А~ > — 2 (п > 2). Локазать, что систе- 2" 2 ма А полна в Рю 3) Пусть |А~ДТо Ы Тз)~ > — 2, А С Рз(Х") (и > 2). Показать, 2 что систома А полна в Рз.
4) Пусть ~А й Ь~ > 2", ~А Г~ М~ > и+ 2, А С Рз(Х") (и ) 2). Ло- казать, что система А полна. 5) Пусть ~Ай Ь~ > 2", ~А езЯ~ > 2", А С Рз(Х") (и ) 3). Пока- зать, что система А полна. 6) ПУсть ~АЛБ~ > — 2з, ~Ай(Ь'~То)~ > 2" ', А С Рз(Х") (и > 3).
Локазать,что система А полна. 6.22. Локазать,что всякая функция У из множества Я~(То 0 Тз 0 0 М О Х) образует базис в Я. 6.23. Верно ли, что всякая функция 7" й То~,(Тз'еЗМ 0 Б Г1 Я) об- разует базис в То? 6.24.1) Верно ли,чтоесли У й МЗ,Б0?,то (О, 1, 7") базисвМ? 2) Верно ли, что для всякой функции г' й М'1ЯОБ такой, что 7" ф (((х Ч уЯ 0 ((худ), множество (О, 1, Г) является базисом? 6.25. Пусть функция 7(х~) такова, что для всякого г (1 (1 ( 4) каждая из подфункций Д и Д принимает значение 1 ровно на четы- рех наборах значений переменных.
Может ли система (О, 1, г") быть полной в Рз? Пусть функция Дх") существснно зависит от всех своих перемен- ных. Через %®ха)) обозначается множество всех таких функций, которые получаются из Д(х") отождествлением переменных, при- чем сама функция Дх") множеству %(Д(х")) не принадлежит. Если п ( 2, то по определению %(Дха)) = И. Множество%(7") называется наследственной снстемой функции 1'. Функция называется невриео- димой, если [%(Д) ~ (Д. Базис Б замкнутого класса Х называется простым, если после замены произвольной функции 7" из Б ее нас- ледственной системой получается система, неполная в Х.
Функция г", не принадлежащая замкнутому классу Х, называется простой отно- ситпельно Х, если ее наследственная система %(т) содержится в Х. 6.26. По функции ?' найти все попарно неконгрузнтные функции, входящие в ее наследственную систему %О ): 1) г"=ху; 2) (=хуч'уз'ч'зх; 3) 7"=хуЕйе; 4) 1"=худ'е:, 5) (=ху" з1; 6) (=хууе1; 7) (=хйуйе; 8) (=ху~Ззуйх~Зу; 9) ~=(хЧе) — гу, 10) 7"=хузйхуЮхФ1.
6.27. Найти все попарно неконгрузнтныо функции, простые отно- сительно класса Х: 1) Х = (0); 2) Х = То', 3) Х = (О; 1); 4) Х = Ь; З о. Полнота и замкнутые классы 87 5) К = Ь а Я; б) К = Тс Л Тг, .7) К = М; 8) К = Я;. 9) К = ~0, 1, х); 10) К = ~0, 1, х, х); 11) К = ~х, х); 12) К=Т ЛБЛБ. 6.28. Выяснить, является ли функция 1 неприводимой: 1)~=хезу; 2)7'=хедер; 3)~=хбгуегес; 4) ~ = хд ОЗ уг ОЗ гх; ос) ~ = хЧ уЧ у; 6) ~ = хуг Ч1(х Ч у Ч г); 7) ~=хуЧг; 8) хууг1; 9) ~=хдаугОЗг1; 10) ~=хуаг. 6.29. Выяснить, является ли базис Б класса К простым: 1) Б = ~О, 1, х,у, х Ю д ~Э г), К = Рг'; 2) Б=~хдаг, 1), К=Рг, 3) Б=(хуЧг,О, 1), К=М; 4) Б=1хуЧг1,0, 1), К=М; 5) Б=1хуйхчзд, х), К=Рг, 6) Б=1хву, х д), К=А; 7) Б=1хву, х-+у), К=Рг,. 8) Б = ~х Ю у йз г, 1), К = А СЗ Тг', 9) Б = 1сх -з у, ху), К = Рг, 10) Б = )х у, пг(х, у, г)), К = Тг.
6.30. Доказать, что в Рг существует ровно два простых базиса, состоящих из одной функции: (х ) у) и ~х 4 у). 6.31. Доказать, что каждая функция 1 из простого базиса в Рг является простой относительно некоторого предполного класса в Рг, к которому 1 не принадлежит. Глава Ш к-ЗНАЧНЫЕ ЛОГИКИ З 1. Представление функций й-значных логик формулами 1. Элементарные функции к-значных логик и соотношения между ними. Всюду в этой главе число к предполагается натуральным и большим 2. Через Ея обозначается множество 10, 1, ... ..., й — 1). Функция 1"(х") = Дхы хз, ..., х„) называется функцией 'к-значной логики, если на всяком наборе о = (оы ог, ..., а„) значений переменных хы хз, ..., х„, где о, е Еь, значение До) также принадлежит множеству Еь.
Совокупность всех функций к-званной логики обозначается через Ря, Понятия фиктивной и существенной переменных, равенства функций, формулы над множеством функций (и связок), операций суперпозиции и замыкания, замкнутого класса, базиса и другие в йэзначных логиках определяются так же, как соответствующие понятия в алгебре логики. Поэтому в дальнейшем приводятся определения только таких понятий, которые чем-то существенным отличаются от аналогичных понятий в Рз. Следующие функции к-злачной логики считаются элезсенспарными: константы О, 1, ..., в — 1; эти функции будут рассматриваться как функции, зависящие от произвольного конечного числа переменных (включая и нуль переменных), отрицание Поста: х + 1(п1ос1 й); обозначение х; огарицаниг Лукасевича: (в — 1) — х:, обозначение х или Асх,: характеристическая функция (первого рода) числа 1: у,;(х) (с = = О, 1, ...,.
й — 1), /1, если х =1, 10, если х у:1; характеристическая функция второго рода числа О,У;(х) (с = = О, 1, ..., ь — 1), 1'к — 1, если х=1, у'д Представление функции й-значных логик формулами 89 минимум х и у: тш(х, у) (другие обозначения: ху, хй у); максимум х и у: шах(х, у) (другое обозначение: х Ч у); сумма по модулю й: х + у (шоб й), читается «х плюс у по моду,лю й»; произведение по модулю й: х у (шог1 й) читается произведение х на у по модулю й *); усеченная разностю л ~ ~ ~ ~ ~ ~ ~ ~ ! ~ | | | | ~ | ~ ~ ~ ~! О, если 0<х<у<й — 1, х — 'у= х — у, если 0(у(х<й — 1; импликация: й — 1, если 0(х<у<й — 1, хну= ~ ~ ~ ! ~ ~ | х | | ~ | ~ ! | ~ ~ ~ ! (й — Ц вЂ” х+ у, если 0 < у < х < й — 1; функция Всбба: пзах(х, у) + 1 (той й), обозначение иь(х, у): разность по модулю й: х — у, если 0<у<х<й — 1, х — у = й — (у — х), если 0<т<у<й — 1.
Функции (операции) |пш, |пах, + и . обладают свойствами ком- мутативности и ассоциативности. Кроме того, справедливы соотно- шения: (х + у) = ( ) + (у ) дистрибутивность умножения относительно сложения; шах(ппп(х, у), я) = т1п(|пах(х, з), шах(у, к)) дистрибутивность операции п1ах относительно операции ппп; ешп(тах(х, у), з) = шах(ппп(х, з), тш(у, з)) — — дистрибутивность операции п1ш относительно операции шах; тах(х, х) = х, п1ш(х,:с) = х идемпотентность операций злах и ппп; тш( х, у) = п1ах(х, у), |пах( х, у) = пйп(х, у) — аналоги правил де Моргана в Рр. Следующие равенства вводятся по определению: епах(хю хз,...., хн з, х„) = тах(п1ах(хы хг, ..., х„е), х„), п ) 3; т1п(х1, тз, °, хп — 1, хп1 = Хп1п(ш1п(хз, хз, ..., хэ — 1), хэ), 'и ) 3; ~ х ~ ~ ~ ! ~ ~ ~ ! ~ ~ ~ ~ ~ ! О, если х=О, й — х, если х~О.
Принимая во внимание ассоциативность умножения по модулю й, произведение хх... х (1 сомножителей, 1 ) 1) записывают часто в виде степени х'. Всюду в этой главе, если не оговаривается противное, знаки + и . пенимаются как знаки сложения и умножения пе мОдулю й. 90 Ули 171. й-заочные аоеики 1.1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
