Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 20
Текст из файла (страница 20)
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. Показать справедливость следующих равенств: 1) — (У) = т; 2) т З д = (т — ' д); 3) т — '(т — ' у) = пш~(х, у); 4) (т З д) З у = шах(т, у);.
5) (т З у)+У= пни(т, д); 6) т — у = т — ппп(т, у); 7) т — ' у = шах(т, у) — у; 8) ( т) -' (у †' т) = шах(т, у); 9) ( т) -' ( у) = у †' т; 10) (т + у) = ( т) + ( у); И ) (т . у) = ( т) . у; 12) гпах((т + 2) †' 1, Уь г(т)) = т; 13) ппп( Уь г(х), (й — 2) З т) = У; 14) т †' у = (т †' д) + У дв г(у) + у . ую г (т);. 15) иь(т, у) + У уг , (д) + у .
уь г(т) = шах(т, у); 16) шах(т, у) + Уо(у †' т) +,Ь г(т) у = шак(У, у); 17) ппп(т, у) + Уо(у в т) — Уь г(т) у = ш1п(т, у)' 18) Хо(шах( Уо(т), Уг(т), ..., Уг — г(т))) = Л~ — г(т)' 19) Уг(шах(т, 1, Уг(т), Юг(т), ..., Уг г(тИ) = Уо(т); 20) т уоОг(т)) +ус(т) . гг(т) = т+уо(т) — уг(т); 21) Уо(т — '1) — 'Ло(х — '(г — 1)) =,У;(т), г =1, 2, ..., й — 1; 22) ( (( х) — ' 1)) — '(...
(((Й вЂ” 1) — ' — '(-х))-( т) — '...-'( т)) =У; 23) (... (((й — 1) — ' уо(т)) — уо(т — ' 1)) — ' ... †' уо(т — (к — 3))) -' ((к — 1) уо( т)) = У. 1.2. Показать, что функция 7 из Рь порождается с помощью операции суперпозиции множеством функций А (А с Рь), если: 1) У = Уг(т), 4 = (,Уо(т),,Уг(т), шак(т, у)), 1 = 3; 2) 7 = т, А = (Уо(т),,Уг(т), ппп(т, у), шах(т, у)), а = 3; 3) У = У, А = (1, тг,,7г(т), шах(т, у)), к = 3; 4) У=го(т), А=(т — 1, тг), 1=3,5; 5) 7 = г„(т) А = (т. д+ т — уг + 1) к = 3 5.
6) 7= т, А=(1, т.у), 1=3,5; 7) У=У, А=(3,,уо(х), т — 'у), 1=4; 8) У = т, А = (т+ 2, Уо(т), Уг(х), шах(т, у), т. у), й = 4; 9) У = уе(х), А = (т — '1,,7г(т)), Й = 6; 10) У = уз(х) А = (т+2 тг Лз(т)), 1 = 6; 11) У =уз(т), А = (т, — т,,Уь г(т)), 12) У=Уь „(т), А=( т, т — 'у): 13) У = Лк г(т), А = (о — 1, т+ 2, т — ' у); 14) У =ус(т), А = (1, т, т — '2у); 15) У=У, А=(1, т, т — 'у). 1.3. Показать, что если а принадлежит Рь и взаимно просто с к, то каждую функцию,7,(т) (О < 1 < к — 2) можно представить в виде суперпозиции над множеством (т+ а,,7ь г(т)). у'д Преегегаавление функций Ь-заочных логик формулами 91 1А. Показать, что функция уг из Рь прсдставима формулой над множеством (О., 1, ..., Ь вЂ” 1, х — 2у), если: 1) уг = фь з(х), Ь = 2т (т > 2); 2) уг = го(х), Ь = 2т+ 1 (т > 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
