Г.П. Гаврилов, А.А. Сапоженко - Задачи и упражнения по дискретной математике (1055357), страница 20
Текст из файла (страница 20)
Показать справедливость следующих равенств: 1) — (У) = т; 2) т З д = (т — ' д); 3) т — '(т — ' у) = пш~(х, у); 4) (т З д) З у = шах(т, у);. 5) (т З у)+У= пни(т, д); 6) т — у = т — ппп(т, у); 7) т — ' у = шах(т, у) — у; 8) ( т) -' (у †' т) = шах(т, у); 9) ( т) -' ( у) = у †' т; 10) (т + у) = ( т) + ( у); И ) (т . у) = ( т) . у; 12) гпах((т + 2) †' 1, Уь г(т)) = т; 13) ппп( Уь г(х), (й — 2) З т) = У; 14) т †' у = (т †' д) + У дв г(у) + у . ую г (т);.
15) иь(т, у) + У уг , (д) + у . уь г(т) = шах(т, у); 16) шах(т, у) + Уо(у †' т) +,Ь г(т) у = шак(У, у); 17) ппп(т, у) + Уо(у в т) — Уь г(т) у = ш1п(т, у)' 18) Хо(шах( Уо(т), Уг(т), ..., Уг — г(т))) = Л~ — г(т)' 19) Уг(шах(т, 1, Уг(т), Юг(т), ..., Уг г(тИ) = Уо(т); 20) т уоОг(т)) +ус(т) . гг(т) = т+уо(т) — уг(т); 21) Уо(т — '1) — 'Ло(х — '(г — 1)) =,У;(т), г =1, 2, ..., й — 1; 22) ( (( х) — ' 1)) — '(... (((Й вЂ” 1) — ' — '(-х))-( т) — '...-'( т)) =У; 23) (... (((й — 1) — ' уо(т)) — уо(т — ' 1)) — ' ... †' уо(т — (к — 3))) -' ((к — 1) уо( т)) = У. 1.2. Показать, что функция 7 из Рь порождается с помощью операции суперпозиции множеством функций А (А с Рь), если: 1) У = Уг(т), 4 = (,Уо(т),,Уг(т), шак(т, у)), 1 = 3; 2) 7 = т, А = (Уо(т),,Уг(т), ппп(т, у), шах(т, у)), а = 3; 3) У = У, А = (1, тг,,7г(т), шах(т, у)), к = 3; 4) У=го(т), А=(т — 1, тг), 1=3,5; 5) 7 = г„(т) А = (т. д+ т — уг + 1) к = 3 5.
6) 7= т, А=(1, т.у), 1=3,5; 7) У=У, А=(3,,уо(х), т — 'у), 1=4; 8) У = т, А = (т+ 2, Уо(т), Уг(х), шах(т, у), т. у), й = 4; 9) У = уе(х), А = (т — '1,,7г(т)), Й = 6; 10) У = уз(т) А = (т+2 тг Лз(х)), 1 = 6; 11) У =уз(т), А = (т, — т,,Уь г(т)), 12) У=Уь „(т), А=( т, т — 'у): 13) У = Лк г(т), А = (о — 1, т+ 2, т — ' у); 14) У =ус(т), А = (1, т, т — '2у); 15) У=У, А=(1, т, т — 'у). 1.3.
Показать, что если а принадлежит Рь и взаимно просто с к, то каждую функцию,7,(т) (О < 1 < к — 2) можно представить в виде суперпозиции над множеством (т+ а,,7ь г(т)). у'д Предетаеление функций И;заочных логик формулами 91 1А. Показать, что функция уг из Рь прсдставима формулой над множеством (О., 1, ..., й — 1, х — 2у), если: 1) Уг = дь г (х), к = 2т (т > 2); 2) Уг = Уо(х), и = 2т + 1 (т > 1). 1.5. Пусть Ьг(х) = х, Ь,,лг(х) = х З Ье(х) (г > 1). Показать, что аь -1(х) = оь-г(х). 1.6.
При каких значениях к (к > 3) функции хг, хз и х~ попарно различны? 1.7. Пусть й = 3, 4, ..., 9, 10. Лля каждого такого й выяснить, сколько различных функций из Рь, зависящих только от переменной х, можно представить в форме х~ (1 > 1 и степень рассматривается по модулю й). 1.8. Локазать, что каждую одноместную функцию Д(х) из Ря можно представить в виде суперпозиции над множеством (1, дь г(х), х+ у). 1.9. Функции (д(х) и уг(х) из Рз удовлетворяют следующим условиям: гз(х) ф сопз1, гг(Ез) ~ Ез и Ь(Ез) = Ез, где г(Е) = Ц(е): е е Е). Локазать, что функция д(х) = уг(х) + уг(х), где сумма берется по модулю 3, выпускает хотя бы одно значение из Ез, т.е. 9(Ез) ~ Ез.
1.10. ПУсть фУнкциЯ Д(х) из Рз пРедставима в виде аохг + агх+ -~-аг (здесь сумма и произведение берутся по модулю 3 и ао, аы аг принадлежат Ез). Выяснить, какие значения могут принимать коэффициенты ао, аы аг, если известно, что функция г(х) выпускает хотя бы одно значение из Ез., т, е, ДЕз) ф- Ез. 2. Разложение функций?е-значных логик в первую и вторую формы. Любую функцию г'(хы хг, ..., х„) из Ру (а > 1) можно представить в так называемой первой форме, являющейся аналогом совершенной д.
н. ф. для функций алгебры логики: ф(х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, Ло(х), 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(х) . 72(у) + 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-значных логик. Представление функций из Рь полиномами по модулю 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г(х) + уз(х).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
