Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132701), страница 23
Текст из файла (страница 23)
(П Пусть функция 6, (х), где 0 < з < у < й — 1, определяется так: если х=у, Ь,.(х) = у, если х = е, х в остальных случаях. Теорема 4 (С. Пикар). Каждая из систем (х, Ьш(х), х+ ус(х)) (501(х), йоз(х); ..., йоф П(х), х+,10(х)) полна в Рь 7 Г. П. Гаврилов, А. А. Сапожеико 98 Га.
Туй И-эиаииме газики 2.13. Подобрав подходящий класс типа Т(К) или (1(11) доказать, что система А не полна в Рл Ц А = ( х, ппп (х, у), х . уг),: 2) А = (1, 2, х — 'уг(х), шах(х, у)); 3) .4 = (2, го(х), х + го(х) +,Уг(х) + 1ь г(х), тш (х., у)); 4) .4 = (1г(х), х + Эо(х), х + уо(х) + уг(х), пгах (х; У)); 5) А = (й — 1,,1о(т), т †' у, х у г); 6) А = (2хз, 2х + у, хг у, х ,1о(у), гг + (- у)); 7) А = (х у, пгах (х, у) — г + Ц; 8) А = ( — хг, шах (х, у) + г); 9) А = (1 — х у хг — 'у) 10) А = (2, шах(х, у), х — 'у); 11) А = (й — 2, 1ь гф, так(х., у), х+у); 12) А = (уг(х), х + 1о(х) + уг(х), х ° У, х — ' У); 13) А = (1 1о(х), х+уь — г(х), тш(х, У), пгах(х, У)); 14) А = (1,.
2, ..., а — 1, х+ ус(х), уг(х) + 1, так(х, у)); 15) А = (1, х, х — ' у, ппп(х, у)); 1б) А = ( х, 1о(х), 1г(х), ..., Ль — ъ(х), шш (х, у) + Оо(х) + т уо(УИ (х + У))' 17) А = (1 — т, .уо(х), уг(х), ..., 1ь-г(х), х у, х †' у), ппп (х, у)). 2.14. Как известно (см. ~ 1), система А = (О, 1, ..., й — 1, го(х), г'г(х), ..., 1ь г(х), х+ У, х. У) полна в Ры Ц Показать, что из системы А можно выделить полную в Рь подсистему, состоящую из двух функций.
2) Показать, что любая подсистема системы А, состоящая из одной функции, не полна в Ря. 2.15. Система Россера- Туркетта Аг = (О, 1,..., к — 1, уо(х),,7г(х),....,,7е г(х),шш (х,. у),гпах(х„ у)), как известно, полна в Рь (см. ~ 1). 1) Проверить, что, удаляя из Аг любую константу, отличную от О и й — 1, получаем подсистему, содержащуюся в некотором классе типа Т(8), где о ~ 8 ~ Еь (и, значит, неполную в Рь). 2) Выделить из системы Аг полную в Ре подсистему, состоящукг из 2Й вЂ” 2 функций. 2.16.
Лля заданных а исследовать на полноту следующие подсис- темы системы Россера — Туркетта: 1) Й = 3, (1,,1о(х),,1г(х), ппп(х, у), шах(х, у)); 2) к = 3, (1, 2, 1г(х), пйп (х, у), тах(х, у)); 3) и = 4, (1, 2, зо(х), 7г(х)., ппп (х, у), пгах(х, у)); 4) к = 4, (1, 2,,1о(х), 7з(х), гпш(х, у), тах(х, у)). 2.17. Локазатзо что каждая из приводимых ниже систем полна в Я»: 1) (601(х), йог(х) ... 60(ь П(х))', у'г. Залекнутые классы и полнота в Ь-гаечных логаках 99 2) Е»ог(х),.
Ьпг(х), ..., Ь.л „,(х), ..., Ья г,и.-г(х)); 3) (х, Ьш (т)). 2.18. Доказать, что система (Ьог(х), Ьог(х),, Ьох — г(х) х-> + уо(хЯ полна в Р,. % 2.19. Используя метод сведения к заведомо полным системам, доказать полноту в Рь следу|ощих систем: 1) Еуе(х), 1г(х), "., 7 ( ), .', .— У); 2) (Ь вЂ” 1, х — 'у, х+у); 3) ( х, х+2, х — 'у); 4) ( — х, 1 — хг, х — ' у), :5) (х+ у, (- х) — ' 2у): 6) (х, шш(х, у)); 7) (ппп(х,.
У) — Ц; 8) (1г х(х), х+у, х.у); 9) (1,, г+ у, *' — ' д); 10) (Уо(х), т+ д, д'); 11) (Ь вЂ” 2, х.у+1, ( х) — у); 12) (Ь вЂ” 1, хг — у, хг — 'у); 13) (1, 2.х+у, х у), 14) (1, хг — у, пцп(х, д)); 15) (1, х+УЧ-2, хг — 'У); 16) (х Уо(У), пцп(х, У)). 2.20. Используя критерий Слупецкого, доказать полноту в Ра нижеприводимых систем: 1) (Ь вЂ” 1, х — у + 2, тг — ' у); 2) (уг(х), т + уг, х д + Ц; 3) (х — 'д, ( х) — д): 4) (зх(х)., х — д, т' — у); 5) (х, уе(х), т.у); 6) Ех — 1, (х+уоФ) '(1 у)+(1 ' х) ' Ь угЬ)))' 7) ((1 — 'х) у+* (1 л— у)) 8) (х .Уо(х — У)+ (х — А(х)) Уо(У)+У Эо(х)Ъ; 9) (1е(х — д) + х Зо(У) + (х А(хИ 'А(УН' 10) (х Зо(У) + Яо(х) (У+ус(у) — А(УИ ч-А(х) .
(У вЂ” уо(УИ)' 11) Еу уо(х)+А(т). (У+уо(УИ+АЬ). (уг(х) -А(хИ) 2.21. Исследовать на полноту в Рг следующие системы: 1) (Ь вЂ” 1, х+ 2, гпак(х, у)); 2) (1, 2, х — ' у); 3) (Ь вЂ” 2, т+ д, шш(х, у)); 4) (О., 1, х — '( д)); 5) (2, 2т+у, тг — 'у); 6) (1, 2., шак(хЬ д)); 7) (2 — х, х.у, шах(х, у)); 8) (Ь вЂ” 2, 2х+у, х — у); 9) ( х, — х у, ппп(х, д)); 10) (2, т+у, х — 'у); 11) ( х, 2уо(х), А(х), х — 'д); 12) (1, — х,,Уо(х) +,Ух(х), шах(х, у)); 13) (О, 1, х, 2 — уо(т) — 2уг(х), ппп(х, у)); ГЙ1 14) (1, Ь вЂ” 1, х — 'Н, пйп(т, у)); 15) (Ь вЂ” 2, х, х — 'у).
2.22. Доказать, что приводимые ниже системы полны в Рг тогда и только тогда, когда й простое число: 1) (1, х + у + х г); 2) (х — у + 1, хг — д, х . Уг); 3) (х — 1, х + у т' . Р) 4) (Ь вЂ” 1 х . д + х — у + г). 5) (Ь вЂ” 2 х + 2У х . Уг) 6) (- х, х — д, хг . У); 7* 1ОО Гл. Пй И-злачные логово 7) (х — 2 х+2у+1 х у — х — у). 8) (1 2х+у х уг — х+у 9) (х+у+1, х у — хг); 10) (х — 2у, х у+х+1); 11) (1 + х1 хг + х1 ' хг '... ' хь). 2.23. Доказать, что при составном к перечисленные ниже функции из Рь но представимы полиномами по модулю Рх Ц 7,(х), О < 1 < к — 1; 2) шах(х, у):, 3) тшп(х, у); 4) х †' р;.
5) х З у; 6) (х — у) †' г; 7) любая функция Шеффера (т.е, функция, образующая в Рь полную систему). 2.24. Подобрав для функции 7(х, у) такие многочлены Цо(х), Яг(х) и 11г(х), гтобы хотя бы одна из функций Щ(7Яг(х), Щ(у))) или 1)о(7Яг(х), Яг(х))) была заведомо не разложима в полипом по модулю й, доказать, что при к = 4, 6 нижеперечисленные функции не представимы полиномами по модулю Й: Ц У (2, з),—. 2) 7 (( — )+ ),( —,Ц. 3) 7' = шш( х, у) — '(1 — ' х); 4) 7 = шах(х, у) — '(х — '2). 2.25. Выделить базис из полной в Рь системы А; 1) А = (й — 1, .1о(х), уг(х), .
, уь 1(х), х у, х †' у); 2) А = (х — 2, 7о(х), шах (х, у), .г †' уг, хг у); 3) А = ( х, ппп (х, у), х у, х -~- у); 4) А = (х — 1, х+ 2, шах(х, у), х — ' у):, 5) А = (2 уо(х), х+уг, хг — 'у х у 2.26. Пусть В произвольный базис, вьшеленный из системы Рессора — Туркетта. Доказать, что в нем: а) содержится хотя бы одна из функций,7,,(х) (О < г < к — 2); б) нет константы О; в) если,Уо(х) Е В, то ь. — 1 т В. 2.27. Доказатзч что если замкнутый класс в Рь имеет конечную полную систему, то множество всех различных базисов у него не более чем счетное.
(Два базиса считаются различными, если один из них нельзя получить из другого путем переименования переменных без отождествления.) 2.28. 1) Пусть А .. непустое множество одноместных функций из Рю отличное от всего множества Р и удовлетворяющее следую- ОО щему условию: существует предполный класс В в Рь такой, что В П Рь ~ = А. Доказатгь что такой класс В единственный. О) 2) Доказать, что число предполных классов в Рго каждый из (О ь' которых не содержит целиком множество Р~, меньше 2ь .
2.29. 1) Показать, что в замкнутом классе Кг = [хг уг] из Рз нет ни констант, ни тождественной функции. 2) Показать, что в замкнутом классе Лг = [уг(х) уг(у)) из Рз нет функций, зависящих существенно от одной переменной. у'2. Замкнутые классы и полнота в й-энинных логиках 101 2.30. Две функции из Рь называются конгруэнптыми, сели они могут быть получены друг из друга путем переименования пере- менных без отождествления.
Показать, что замкнутый класс Кз = = (уз(х) уз(у)) из Рз состоит из конечного числа попарно неконгру- энтных функций, зависящих существенно от всех своих аргументов. 2.31. Рассмотрим в Рь замкнутый класс К4 = (Л(х~), эг(хы хз), гз(хы хз, хз); .: 1п(х~, .хз, ..., хп), ...), где (о(хчп) = уз(х1) .уз(хг) ... 7г(хн) (и = 1, 2, 3, ...). Очевидно, что он содержит бесконечно много попарно неконгруэнтных функций.
Доказать, что в К4 нет предполных классов. 2.32. Подсчитать число существенных функций в Ря, зависящих от переменных ху, ххэ ..., х„(п > 2). 2.33. Как известно, в Рь при к > 3 существуют замкнутые клас- сы, не имеющие базисов, и замкнутые классы со счетно-бесконечными базисами. Рассмотрим класс Аь = (5....., ~т, ...), где Ут(х~,...., х ) = 1 при хз=...— — и; з — — хыы —— ...=х =2, хе=1 (1=1, 0 в остальных случаях, т > 2. Базисом в Аь является множество Я, ..., г", ... ). Используя класс Ая, доказать, что в Рь (й > 3) существует континуальное семейство (Вт) замкнутых классов, образующих по включению цепь, т.
е. для любых двух классов В, и В, из семейства (Вт) справедливо только одно из включений: Вт, С В, или В, й Вэ, . Глава 1Ъ" ОГРАНИЧЕННО-ДЕТЕРМИНИРОВАННЫЕ Фо'НКЦИИ 2 1. Отображения последонательностей 1. Основные понятия н факты, связанные с заданием детерминированных функций. Пусть А непустой конечный а фавипк Его элементы называются буквами (или символами). Словом длины в в алфавите А называется последовательность вида х(1) х(2)...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
