Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1132709), страница 21
Текст из файла (страница 21)
1.5. Пусть Ьз(х) = х, Ь,, г1(х) = х З Ь,(х) (1 > 1). Локазать, что Ьь- ( ) = ль- (х). 1.6. При каких значениях Ь (Ь > 3) функции хз, хз и х~ попарно различны? 1.7. Пусть Ь = 3, 4, ..., 9, 10. Лля каждого такого Ь выяснить, сколько различных функций из Рэ зависящих только от переменной х, можно представить в форме х~ (1 > 1 и степень рассматривается по модулю Й). 1.8. Локазать, что каждую одноместную функцию Д(х) из Ря можно представить в виде суперпозиции над множеством (1, дь з (х), х+ у). 1.9. Функции (д(х) и гз(х) из Рз удовлетворяют следующим условиям: ~г(х) ф сопз1, гз(Ез) ф Ез и ЯЕз) = Ез, где )'(Е) = Ц(е): е е Е).
Локазать, что функция д(х) = уз(х) + 1з(х), где сумма берется по модулю 3, выпускает хотя бы одно значение из Ез, т.е. д(Ез) ~ Ез. 1.10. ПУсть фУнкциЯ Д(х) из Рз пРедставима в виде аохз + азх+ -~-аз (здесь сумма и произведение берутся по модулю 3 и ао, аы аз принадлежат Ез). Выяснить, какие значения могут принимать коэффициенты ао, ам аз, если известно, что функция г(х) выпускает хотя бы одно значение из Ез., т, е, ДЕз) ф- Ез. 2.
Разложение функций й-значных логик в первую и вторую формы. Любую функцию г'(хы хз, ..., х„) из Рь (и > 1) можно представить в так называемой первой форме, являющейся аналогом совершенной д. н. ф. для функций алгебры логики: Дхыхз, ...,х„) = = шах (пцп(г (оы цз, ...
~ ав)., гв1(хз), гав(хз), ..., гв (хп))) а где максимум берется по всем наборам о = (оы оз, ..., о„) значений переменных хм хз, ..., т.„. Справедливо еще одно представление для функций Ь-значной логики, называемое второй формой: Д(хб") = ~ ~(а)у,(хз)...ф „(ха), где суммирование ведется по всем наборам а = (оы ..., о„) значений переменных хы ..., х„(сумма и произведение берутся по модулю Ь).
Пример. Представить функцию Дх, у) = Таблица 3.1 = шах(~о(х) уо(у), х Цз(у) + 21з(у))) из Рз в первой и второй формах. Р е ш е н и о. Сначала выпишем значения функции 1 в таблицу (табл. 3.1). Затем по этой таблице строим первую и вторую формы функции 1. Первая форма выглядит Гл.
П1. й-званные логики следующим образом: 1(х, у) = шах(пцп(1; 1о(х), 7в(у)), ппп(0, Зо(х); А(у)), шш(0,,1о(х), 12(у))., пауз(0, 12(х),,7о(у)), шш(1, Уг(х), А(у)), ппп (2, 72(х),,12(у)), ппп(0, Эг(х),,1о(у)), ппп (2,,12(х),,72(у)), П21П (1, 12(х),. 72(77))). Выполняя простые преобразования, имеем 1(х, у) = шах (ппп (1,,1о(х),,1о(у)), пз1П (1, Ло(х), 72(77)), Ш122 (71(х), 72(77)), П11П (,12(х), 12(у)), Ш1П (1,,12(х), 72(у))), ,7(х У) = 1 70(х) ' ув(у) + О .,70(х) 'Л (У) + О ув(х) ',72(у) + + О . 72(х) 7о(у) + 1 72(х) .
72(у) + 2 ,72(х) . 12(у) + 0 72 (х) уо(у) + + 2 12(х) 27(У) + 1 22(х) 22(у) = гв(х) зв(у) + 72(х) 22(у) + + 2 72(х) 72(у) + 2 72(х) 22(у) + 22(х) 72(у). 1.11. Для заданного к представить функцию 7' в первой и второй формах (полученные выражения упростить): 1) 1=х, Й=З; 2) 1= х, 1=4; 3) 1= — уо(х), 1=5; 4) «21(.) ь б, «) 2 1(.2+ .) 6) 1= ( х)2+х, й = 4; 7) 1 = 372(х) — 72(х), й = 4; 8) 1 = х+ 2У, к = 3: 9) 1 = шах(х, у), к = 3; 10) 1=х — 'уг, й=З:, 11) 1=хг у,. Й=З; 12) 1 = х . у, .72 = 4. 1.12.
Доказать справедливость следующего соотношения, являющегося аналогом совершенной конъюнктивной нормальной формулы для функций из Ры .7(х ) = пйп««(шах(7(оы ог ..., а ), .7,(хг), —,1 2(хг), ... - у.„( .и) (здесь п ) 1 и минимум берется по всем наборам о = (оы аг,..., аа) значений переменных хы хг, ..., хн). 3 2. Замкнутые классы и полнота в й-значных логиках 1.
Некоторые замкнутые классы к-значных логик. Представление функций из Рь полиномами по модулю 72. Пусть 8 - - подмножество множества Еы Говорят, что функция 1(х") из Рь (и ) 1) сохраняет множество 8, если на любом наборе оа = = (пы ог,..., о„) таком, что и, Е 8 (2' = 1, 2, ..., П), она принимает значение 7(оа), также принадлежащее 8. При и = 0 считают по определению, что функция 1 = а (а Е Ьь) сохранявпг множестлво 8 только в том случае, когда а Е Е.
Множество всех функций из Рю сохранлюи7их множество 8, является замкнутым классом; оно обозначается через Т(8) и называется классом сохранения множества К. у'г. Замкнутые классы и полнота в й-эначных логиках 93 Если К вЂ” собственное подмножество множества Еь. (т. е.
йь С К С Еь ) то Т(К) ф Рь (см, задачу 2.3). Пусть Р = (Кь, Кз, ..., К,) разбиение множества Еь, т.е. и Еь = ( ) К„ К, ~ Я при ь = 1, 2, ..., в и К, ГЬ К, ф Я при ь ~ ьц ~=1 Говорят, что элементы а и Ь из Еь эквивалентны отпносительно разбиения Р (обозначение а - б(ьпос1 Р)), если а и д принадлежат одному и тому же подмножеству К разбиения Р. Лва набора сь" и сЗ" называются эквивалентными относнтельно риэбиения Р (обозначение он - Дч (пюс1 Р)), если сх, Д, (шос1 Р) при ь = 1, 2, ..., и.
Говорят, что функция ь'(хсь) из Рь„. (и > 1) сохраняет разбиение Р, если для любых наборов а" и ьбь из эквивалентности аи ьусь (пьос1 Р) следует эквивалентность ь" (оу ч) ь'(ьЗ") (ьпос1 Р). По определению считают, что всякая константная функция (т. е. нульместная функция вида ь" = а, а й Еь) сохраняет любое разбиение Р. Множгсспво всех функций, из Ры сохраняющих разбиение Р = = (Кь, Кг, ..., К,), является замкнутым классом: оно обозначается через П(Р) или П(Кь, Кг, ..., К,) и называется классом сохринения разбиения Р.
Если в ф 1 и в ~ й, то класс П(Р) отличен от Рь (см, задачу 2.4)2 Функция Дх") из Рь (п > 0) называется линейной, если она представима в виде ао + аьхь +... + а„хи, где а с Еь (~ = О, 1,..., и), а сумма и произведение берутся по модулю й. Множество всех линейнььх функций из Рс. образует замкнутый класс линейных функций, который обозначается через Ьь. (или Е). Класс Еь отличен от Рь при всяком й > 3. Полиномом (или многочленом) по модулю й от переменных х,, хг, ..., хи называется выражение вида ае+аьХь +... ...
+ атХт, где коэффициенты аь принадлежат множеству Еь и Хь либо некоторая переменная из (хь, хг, ..., хч), либо произведение переменных из этого множества Ц = 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 а м е ч а н и е. В рассмотренной задаче достаточно было выписать два соотношения между коэффициентами. Однако иногда бывает необходимо рассматривать более полную совокупность уравноний. В и.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
