Гаврилов Г.П., Сапоженко А.А. - Задачи и упражнения по дискретной математике (1048833), страница 21
Текст из файла (страница 21)
... + атХт, где коэффициенты аь принадлежат множеству Еь и Хь либо некоторая переменная из (хь, хг, ..., хч), либо произведение переменных из этого множества Ц = 1, ..., сп). Говорят, что некоторая функция из Рь предспьавимд (или реализуется) полиномом по модулю й, если суьцествует полинам по модулю й, равный этой функции. Множество всех функций из Рь, представимых полиномами по модулю й (или, короче, множество всех полиномов по модулю й), является замкнутым классом в Рь.. Т е о р е м а (критерий полноты класса полиномов в Рь). Представление каждой, функции иэ Рь полиномом по модулю й возможно в том и только том случае, когда й ьь1ьоспьое число (иными словами, система полиномов сьо модулю й полна в Рь.
тогда и только тогда, когда й — простое число). Если й составное число, то в Рь имеются функции, представимые полиномами, и функции, не представимые полиномами (например, константные функции О, 1, ..., й — 1 и «полиномиальные» х, х, 2 х . у, х + у представимы полиномами, а функции уо(х), псах (х,. у), пап (х, у), х — ' у не представимы).
94 Гж П1. 'к-званные иоппии П р и м е р 1. Представить полиномом по модулю 5 функцию 1 (х) = = хг — ' х из Рз. Решение. Сначала представим функцию 1(х) во второй форме: 1" (х) = ~~ 1'(а) г' (х) = 1" (О) уо(х) + 1'(1) гг(х) + + 1(2) уг(х) + 1(3) '.1з(х) + 1(4) уя(х) = = 0 . 1о(х) + 0 . 1г(х) + 2 уг(х) + 1 гз(х) + 0 .
14(х) = 2 . 1г(х) + уз(х). Далес воспользуемся тем, что уо(х) = 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 (дз(х) + дл(х)), й = б; 4) 1 = (х — 'У) — 'У, й = 4; 5) 7" = (п1ах (х, у) — шш (х, у))г., й = 4. 2. Исследование систем функций й-значной логики на полноту. В й-значных логиках исследование произвольной системы функций на полноту сопряжено с большими техническими труднос- тями: использование критерия полноты, основанного на рассмотре- нии совокупности всех предполных классов в Ры даже при й = 3, 4 требует проверки весьма значительного числа условий (так как в Рз существует ровно 18, а в Рл ровно 82 предполных класса).
До- казательства полноты конкретных систем в Ря проводятся обычно методом сведения к заведомо полным системам (таким, например, как система Россера Туркетта (О, 1, ..., й — 1,,7о(х), дз(х), ..., дь з(х), гйп(х, у), шах(х, у)) или система Поста (х, шах(х, у))). Существует, кроме того, ряд признаков полноты, в которых рассматриваются множества функций, содержащие некоторые совокупности функций от одной переменной и еще только одну функцию., существенно зависящуке не менее чем от двух переменных. Сформулируем наиболее важные из таких призна- ков.
Напомним, что: Ея — это множество всех разнозначных функций из Ры зависящих от одной переменной; СКь — Р 1оь Р множество всех одноместных функций из Рь. П1 Функция 7" (х) к Рь называется суизественной, если она зависит существенно не менее чем от двух переменных и принимает все й значений из множества Еы Теорема 1 (критерий К. Слупецкого). Систпглеа Р~ ~ 'ел(г"(х)) полна в Рь (при й > 3) ттгда и только тогда, когда Дх) су- ьцеотвенная функция. Теорема 2 (критерий С.В.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
