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