Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 21
Текст из файла (страница 21)
Далес воспользуемся тем, что уо(х) = 1 — х~ ~, если и простое число (к' > 3), и что уз(х) = уо(х — г), г = 1, ..., й — 1. (Здесхи как обычно, разность и степень берутся по модулю й.) Имеем '() — 1 ( 2)4 — 4 23+ г+2 уз(х) =1 — (х — 3) =1 — (х+2) = — х +2хз+х — 2х. Следовательно, хг — ' х = 2х4 — 2хз — 2хг + 2х. Это выражение можно записать компактнее: 2х(х — 1)г(х+ 1.
Полипом, реализующий функцию 1(х), можно найти также ме- тодом неопределенных ноэфу(иииентое: пусть 1(х) = ао+ а~ . х+ + аг хг + аз . хз + аз х~ (более высокие показатели степени рассмат- ривать не нужно, ибо хоч' = х~ (шоб 5)). Составим систему: ао = 1(0) = О,. ао+аг+аз+аз+а4 =,((1) =О, аз+ 2аг+4аг+Заз+а4 = 1(2) = 2, ао + Заг -'с 4аг + 2аз + аз = гг(3) = 1, ао+ 4а> + аз + 4аз+ аз = Д(4) = О. Решая ее, например, методом исключения, находим: ао — — О, аг = 2, аз=3, аз=3, а4=2. Пример 2.
Показать, что функция 1(х, у) = хг — 'у из Р4 не представима полиномом по модулкг 4. Решение. Предположим противное, т.е, что 1'(х, у) реализуется полиномом по модулю 4, и запишем этот гипотетический полинам в общем виде (с неопределенными коэффициентами): г(х,У) = (аоо+агох+агох +азох )+(ао1У+аггху+оггх У+азгх У)+ + (иогу + епгху + аггх у + ггзгх' У ) + г,,гг,ге г + (позу + аззхУ + агзх У + аззх У ).
(Показатель степени выше 3 рассматривать не надо, так как при 1 > 1 справедливы соотношения хгььг = хг (шод 4) и хг'"з = хз (шоб 4)). Имеем ,((1, 0) = аоо + аго + аго + азо = 1,. (и) 1'(1, 2) = аоо + аго + аго + азо + 2(аог + аы + агг + азг) = 0 Так как уравнение 1+ 2а = О (шоб 4) решений не имеет (в чем можно убедиться непосредственно, полагая последовательно а = О, 1, 2, 3), то система (и) также не имеет решения. Следовательно, у'г. Замкнутые классы и полнота в И-эначных логиках 95 нельзя подобрать подходящие коэффициенты а,, которые обеспечили бы представимость функции 7" в виде полинома по модулю 4.
Значит, функция 1 не реализуема полиномом по модулю 4. 3 а м е ч а н и е. В рассмотренной задаче достаточно было выписать два соотношения между коэффициентами. Однако иногда бывает необходимо рассматривать более полную совокупность уравноний. В и. 2 мы продемонстрируем другие методы доказательства непредставимости функций из Рь полиномами по модулю Й. 2.1. 1) Выяснить, каким из классов Т((0, 2)) и У((0, 1), (2)) принадлежат следующие функции из Рг. а) и; б) ух(х); в),7э(х): г) х — 'у; д) х+ у; е) шш(х, у).
2) Выяснить, каким из классов Т((1, 3)), 5Г((О, 1), (2), (3)) Г((0. 3). (1, 2)) принадлежат следующие функции из Рл. а) х; б) х; в) д1(х); г) х+ 2у; д) шах(х, у): е) хз . у. 2.2. Для функции 1 из Ря при заданном к подобрать классы типа Т(8) и ЩР), которым она принадлежит. При этом К должно быть собственным подмножеством множества Еь (т.е. 8 ф И и 8 ф Его а  — таким разбиением (Кы Кз, ..., 8,) множества Ею чтобы выполнялись неравенства 1 < в < к; 1) й = 3, У = хг + 1; 2) й = 3, У =,т ( '+ 2,); 3) й = 3, ~ = (х~ †' уа) + 1; 4) й = 3, ~ = х у — у + 1: 5) к = 4, 7" = уз(х — хз); 6) к = 4, 7" = Зз(2х + хг); 7) Й=4, 7'=х.у — у+3; 8) Й=5, ~=ш1п(хз,у),: 9)к=5, 7"=(2хг — 'у) — 1; 10)к=б, 7"=хэ у+2; 11) и произвольное число, не меньшее 3, 7' = 71(2х — ' хз), 12) к — произвольное число, не меньшее 3, т" =,7ь х(х у — 1).
2.3. 1) Пусть 8 С Ея. Доказать, что Т(8) ф Ря тогда и только тогда, когда 8 собственное подмножество множества Еь (т.е. К~он К~Ея). 2) Сколько существует различных замкнутых классов в Ря, являющихся классами сохранения множеств? 3) Пусть 8 С Еь. Подсчитать число функций в Рь, содержащихся в классе Т(8) и зависящих от переменных ха, хз, ..., хп (п > 0). 2.4.
1) Пусть лгу = (Кы Кг, ..., К,) - разбиение множества Еь, Доказатхь что 7ЛР) ф Рь тогда и только тогда, когда 1 < в < к. 2) Для к = 3, 4, 5 подсчитать число различных замкнутых классов в Ря, являющихся классами сохранения разбиений. 3) Пусть 1З = (8ы Кг, ..., 8,) разбиение множества Еь, Подсчитать число функций в Ры содержащихся в классе !У(1г) н зависящих от переменных хы хз, ..., х„(п > 0). 2.5.
Г!усть 8 — непустое подмножество из Еы отличное от всего Ею и Р = (К, Ел~8). Подсчитать число функций в Рво зависящих от переменных хз, хх, ..., х, (и > 0) и содержащихся в множестве: 1) Т(8)1У(В); 2) У(Р)1Т(8), :3) Т(8) С 11(Р). 96 Гж Пй й-званные логики 2.6. Через Яь обозначается множество всех равнозначных функций из Ры зависящих от одной переменной (т.е. д(х) принадлежит Яь тогда и только тогда, когда у(Еь) = Еь). Пусть Р, мно- 00 жество всех функций й-значной логики Рь, зависящих от одной переменной, и СЯь — — Рь ~Як. О) Ц Показать, что множества Яь и СЯь являются замкнутыми классами. 2) Подсчитать число функций, зависящих от переменной х и принадлежащих классу Яь Г1 (7((0, й — 2), (1, ..., й — 3), (й — Ц).
(При й = 3 считаем, что (1....., й — 3) = О.) 2.7. 1'азложить в полинам по модулю й функцию 7' из Рь. Ц ( = 2х — ' х-', й = 5; 2) ( = опщ (х', хз), й = 5; 3) 1 = щах(2х — ' 1, хз), й = 5; 4) г" = Зх — '(х — ' 2х), й = 7; 5) ( = щах Их — ' Цз, хз), й = 7; 6) 1 = ~п1п(тз, у), й = 3; 7) (=тпах(2х — 'у,х у), й=З; 8) 7'=х — у, й=З; 9) У = гь з(х), й — произвольное простое число; 10) У = уз(х — хз), й произвольное простое число. 2.8.
Ц Локазать, что функция 2уе(х) из Ре при любом 1 = О, 1, 2, 3 представима полиномом по модулю 4. 2) Локазать, что если функция из Рг, зависящая от одной переменной, принимает значения либо только из множества (О, 2), либо только из множества (1, 3), то она представима полиномом по модулю 4. 3) ИспользУЯ фУнкцию 1(х, У) = 2. Уо(х) Уо(У) (из Р4), показать, что утверждение 2) не обобщается на функции, зависящие более чем от одной переменной. 2.9. Локазать, что если функция ((х) из Р4 не представима полиномом по модулю 4,то при любом целом т > 2 функция (1(х))'", равная т-й степени функции 1(х), также не представима полиномом по модулю 4.
2.10. Подсчитать число функций в Ре, которые зависят только от переменной х и реализуются полиномами по модулю 4. 2.11. Ц Пусть функция 1" (х) из Ро реализуется полиномом по модулю 6. Показать, что сс можно реализовать полиномом по модулю 6, имеющим вид ао + а,х + азх . 2 2) Локазатзн что в Ре число функций, зависящих от переменной х и представимых полиномами по модулю 6, равно 108. 3) Перечислить все функции Д(х) из Ро, которые представимы в виде и+ 5 зо(х) (а и 5 принадлежат Ео), не реализуемы полиномами по модулю 6 и удовлетворяют следующему условию: функция (1(х))~ реализуема полиномом по модулю 6. 2.12. Выяснить, прсдставима ли полиномом по модулю й функция 1 из Ры если: Ц ( = Зх — ' 2х-'., й = 4; 2) ( = Зуо(х), й = 6; у'г.
Замкнутые классы и полнота в й-званных логиках 97 3) 7" = 2 (дз(х) + дл(х)), й = 6; 4) 1 = (х — 'У) — 'У, й = 4; 5) 7" = (п1ах (х, у) — шш (х, у))г., й = 4. 2. Исследование систем функций й-злачной логики на полноту. В й-значных логиках исследование произвольной системы функций на полноту сопряжено с большими техническими труднос- тями: использование критерия полноты, основанного на рассмотре- нии совокупности всех предполных классов в Ры даже при й = 3, 4 требует проверки весьма значительного числа условий (так как в Рз существует ровно 18, а в Рл ровно 82 предполных класса). До- казательства полноты конкретных систем в Ря проводятся обычно методом сведения к заведомо полным системам (таким, например, как система Россера Туркетта (О, 1, ..., й — 1,,7о(х), дз(х), ..., дь з(х), пйп(х, у), шах(х, у)) или система Поста (х, шах(х, у))).
Существует, кроме того, ряд признаков полноты, в которых рассматриваются множества функций, содержащие некоторые совокупности функций от одной переменной и еще только одну функцию., существенно зависящуке не менее чем от двух переменных. Сформулируем наиболее важные из таких призна- ков. Напомним, что: Ея — это множество всех равнозначных функций из Ры зависящих от одной переменной; СКь — Р 1оь Р множество всех одноместных функций из Рь.
П1 Функция 7" (х) е Рь называется суизественнои, если она зависит существенно не менее чем от двух переменных и принимает все й значений из множества Еы Теорема 1 (критерий К. Слупецкого). Систпвлеа Р~ ~ 'ез(г(х)) полна в Рь (при й > 3) тсвгда и только тогда, когда Дх) су- ьцеотвенная функция. Теорема 2 (критерий С.В. Яблонского). Система СКь 0 (7'(х)) полна в Рь (при й > 3) тогда и только тогда, когда 7(х) су- извственная функция. Теорема 3 (критерий Л. Сш|омаа). Система Еь 0 (Д(х)) полна в Ря (при й > 5) тогда и только тогда, когда функция Д(х) су- щественная. При использовании этих теорем полезными являются утвержде- ния, дающие разнообразные критерии полноты систем функций в множествах Р„, Яь и Сот Приведем один из таких результатов.
(П Пусть функция 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 ~ Еь (и, значит, неполную в Рь).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
