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