Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 22
Текст из файла (страница 22)
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)... х[в), составленная из букв алфавита А (здесь в > Ц. Кратко эта последовательность обозначается так: х'. Множество всех слов длины в в алфавите А (в > 1) обозначается через А'. Часто рассматривают и слово длины 0 [пустое слово), его обозначают символом Л. Через А* обозначается множество 1Л) 0 ] ) А'. Симз>1 вол вида [а1 ... а„]', где в > 2, п > 1 и аы .,., а, буквы из алфавита А, используется для краткой записи «периодического» слова оа ...он оп ...
ан ... аз ... о, (длины и в). Если и = 1, то вместо [аз]в применяют также символ а'. Бесконечные последовательности т' = х[1) х(2)... х[1)..., составленные из букв алфавита А, называются бесконечными словами в алфавигае А. Множество всех бесконечных слов в алфавите А обозначается через Ае. Слово ю, получающееся приписыванием слова юз справа к конечному слову им называется соединением слов юз и юз и обозначается через юзюз. Слово юз называют при этом префиксом [или началом), а слово соз - суффиксом (илн окончанием). Слово х" = х(1) х(2)... из А ' называется кваэипсриодическим, если существуют такие целые числа по и Т, что по ) 1, Т ) 1 и х[п + Т) = х[п) при и > по. Префикс х(1) х[2)...
х(по — 1) слова х ' в этом случае называют ирвдпериодом, число пв — 1 длиной пред- периода, слово х[по) х[по + Ц... х[по + Т вЂ” 1) —.- периодом слова х' ', а число Т вЂ” длиной периода Такое кв зипериодическос слово удобно записывать в виде х[1) х(2) ... х[ио — 1) [х(по) х[по + 1)... х[по + Т вЂ” 1)] Символом а" обозначается слово хе Е А~, в котором х[1) = а при любом 1 = 1, 2, ...
(а ч А). у 1. Отобраэеения последовап1ельноетей 103 Пусть А и В конечные непустые алфавиты. Множество отображений вида у: А ' э Во обозначается через Рл,в . Алфавиты А и В называют соответственно входным и выходным алфлвптамн отображения из Рл в, слова (последовательности) из множества А называют входными, а из множества В выходными. Отображение у из Рл н „, называется детерминированным оператором или с)етерминированной функцией (сокращенно: д.
оператором или д. функцией), если оно удовлетворяет следующему условию; для всякого в > 1 и любого входного слова х (из А ) в-й символ выходного слова у = у(х ) является однозначной функцией первых е символов слова х''. Множество всех д. функций из Рл в, обозначается через Рл,в,п. В тех случаях, когда А=Еьх ... хЕя (п>Ц, В=Е~х ... хЕ~ (гп>1), и раз п1 рпз где Еь=(0,1,,к — 1) (1е>2) и Е~=(0,1,,1 — 1) (1>2), множества Рл в и Рл в, будут обозначаться через Р,","„и Р„"', соответственно. Если отображение уэ = у(х'и) принадлежит множеству Р"',™„(или Р","и), то при т 2 вместо ул можно применять запись (у,..., у„'), а при и > 2 вместо Дхм) употреблять запись у(х"'', ..., х„); здесь у "г (~ = 1,..., т) переменная, пробегающая множество Е,", и х,"' (1 = 1, ..., п,) переменная, пробегающая поп 12,пп множество Еь. При и = т = 1 верхние индексы у Р„,' и Р„', „ будем иногда опускать, т.е, будем писать Ря р, и Рву .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
