Математическая логика. Шапорев С.Д (1019113), страница 42
Текст из файла (страница 42)
Тогда значение .Г будет зависел от зна»ения х, т. е. х — существенна» переменная. 1.1г.5. Функци» у (х„ х„...,х„) называется линейной, если она представима полиномом Жегаякина не выше первой степени, т.е. сели существу»те такие константы и, и (0,11 ! = О,л, что У(х„х„..., х„) = и, Ю их Ю ... Ю п„»ь . !) У=х-зуйху=хйуй(хЮ1)у= = хйуйхуйу =хуйхи Уи Глввв В. Дл вьюквзьмеинд 293 2) Г=хуч луч н«улхул2=(«уЮ!)((хЮ!(уЮ1)Ю1) (2В!)В!= (хуВ1)(2В1)(хуВуЮх)Ю1= хтЮу»ЮхВуЮ1 Очевидно, что Гй Ь.
Подобный метод представления функции полиномом Жсгаяки»»а пвзываетсл методом, базирующимся иа преобразовании формул нвд множеством связок (л, Восстановим теперь полинам, представляющий данную 4»ункц»»ю, методом неопределенных коэффициентов. » = ху о ху о 2 = а, Ю л х Ю и, у В ах Ю аысуВ а, ххВ а, ух Ю а» хуз. Г(0 О 0) = 1 = ае Ю а, 0 Ю а» 0 Ю а» 0 Ю аз 0 Ю аз 0 Ю аь 0 Ю а» О, Г(001)=!=ос Юа! ОЮа» ОЮа, 1Ваз ОЮаз ОЮаь ОВа» О, „Г(010)= О =ос Юа,.ОВа» 1Юа» ОЮаз.ОЮаз ОЮаь ОЮа, О, Г(01!)=1= ас Юа, ОЮа»'1Ва» !Юа, ° ОЮаз ОЮаь.!Юа, О, Г(100)= О=ас Юа, 1Ва» ОВа» ОЮаз ОЮа» ОЮаз ОЮа„.О, Г(1 01)=1=ос Юа, 1Юа».ОЮа» 1Вач ОЮаз 1Ва„ОВа, О, Г(110)=1=се Юа, 1Ва» 1Юа» ОЮач 1Юаз ОЮос ОЮа» О, Г(! ! 1) ! ас ® а~ '1® с»» '!Во» '10!аз '1Ю а» '1Ю аз '!Во» '1.
Подобная система всадя имеет рещение, причем есс а, и (0,1), » = О,л . Здесь и =а =а =а = а =!. и =а =а, =0; » з ь ' з Э Г'=ху(хт-»у)=х(уЮ1)(хВуВ1)=(хуЮ1)(хЭуЮ1)= = хуЮ ху Эху ВхЮхуЮх = Ое Е! 4) 1' = (х о ук)В хух и х»» ух Ю хух = =((хЮ!)(утЮ!)Ю!)Ю(хЮ1)ус = = (ху2 Ю у2) Ю (ху2 Ю ут Ю х Ю 1 Ю 1) = = хут Ю ут Ю х Ю хут Ю ул = х и Е . 1.18.6. Так как Г(х„х,...,х„)=а Ва,х, Э...Эа„х„, то м»илвес»во всех линсйнык функций равно числу различных наборов вида (аз,а„...,а„). Поскольку»21а, б (0,1), то число наборов равно 2"'. Чаем!Г.
Отвею, кения казаны 1 18УД Выясним, при каком составе существенных переменных » (х,хз, .„т„=1. Рассмотрим в «ачестве приь»ера функцию двух переменных. Она линейна, т.е. У(х,у)=а Юа,хЮа у. Тогда /» =О, Л =1 .гз !ЮГ у» — 1Ю у у» =!Ю хЮ т, „г =хЮу, 7, =х, г =у.Только г и г удовлетворяютусловию задачи.
У»з все переменные фиктивны и ар =1, у ~» число существеннык пеРеменных четно и аз =1. Та же квРтина набл»одаеюв лла функции трех переменных Д(х,у,з): 1» =О, 1 =1, !» =х, Л =!Юх Л» =у, Л =1Юу Л =«Юу* А =!ЮхЮу Аз =з* Хе !Юг А~» — хЮз /о !Ю»Юа* Гз =УЮз, !»» =1ЮУЮх, 7» =хЮуЮя, 7» =1ЮхЮУЮа. Число всек линейных функцмй н переменныж у которых пе — — 1 и все переменные фиктивны или с аз —- 1 и с четным числом существенных переменных, равно 2" 1.18.8. Функция 2'(х, х„...,х„) сохраняет константу 0 !константу !), если Г (О,О,...м) = 0 !соответственно г (1,1,...Д) =! 1.
11.Р=( — )( — х )(1 — й) Р(О,О, „О)=(О- О)(О-»О)(О-»О)=1, »(! 1,...Д) = (1 -ь1)(1 — »1)(1 — з!) =1. Такии образам, 3ц Р ! Р,; 21 г' — функция от трех переменных и может содержать суперпозиции всех логических свнзок. рассмотрим, например, г» = х, ч х -ел„тогда г',(0,0,0)=ОчΠ— «0=1 и г»(111)=! ч1 — »! =1. Однако /' = (х — » х,)лх, дает г',(000)= (Π— »0)лО = 0 и Рз(11,1)= (1 — »1)л1=!. Следовательно, произвольная у й Р,1Р,; 3) Р=хх»хм ххзчх,: Д(000)=0 ° 0 Оч! Оч!=1, г (1,1,1) = 1 1 1 ч 0 1 ч О = 1, т.
е. Р ц Р, ! Р„; 4) Г=(х, чх,)к»ч з;х,ч~ ОООО)=(Оч1).1ч! Оч!=1, /(112)=(!чО) ОЧО!чО=О, ~й Р! Р,. Гп ш 6, Ллгесра еи хээиюиия 818тш !1 Р=хугхгт г=ху~ = бив функция равна нулю на наборах (0,0,0), (0,1.0). (1,0,0). Все оставшиеся цвборы, исключая (0,0,1), содергкат не менее двух слиниц, а зивчнт, либо не сравнимы ° (0,0,0), (0,1,0), (1,0,0), либо могут быть только больше Ди» наборов (0,0,0)и(0,0,1) набор (0,0,1) не сравним с (0,1,0) и с (1,0„0), но зг(0,0,0)=Ос /(0,0.1)=! Следовеылызо, рассматриваемая функция моно~окна; 2) г = х †з(х — з у). Всего четыре набора неремснныл.
Сравниьг (0,0) и (1,0), но Д(0,0) =! > з (1,0) = О. Функция лемонотоннв, 31,г' = х зг у гг хи у . (О 0) и (1 0), Р(0 0) = 1 > Г(10) = О . Функция немонстоннв, 41 .г = хну+-ь х умхут-+ луж! для всех наборов, следовательно, функния монотонна; 5) Р = х1и хи хх и х(ум 1) ч ш и хи хз и хи я, у — фиктивная нереьгеннея: функция хч = моноюннв, з к. она равна 0 лишь нв наборе (0,0), который предшествует всем оствяыгым наберем.
1.18. !О. Вопрос о и~геле монотонных функций ат л переменных оказывается очень трудныьг. Окончательно он не решен до сих пор; зто число сосчитано лишь для конкретных небольших и, монотонная г (.чту) (не константа) ранив 0 на нулевом наборе и 1 ия единичном. 2!ва другил набора (0,1) и (1,0) следуют зв нулевым, предшествуют единичному, э между собой ле сравнимы Поэтому на них мшкмо задевать любью значения функции, нс нарушая монотонности. Всего задеть зти значения моягно четырьмя способами, твк что можно вялить четыре монотонные функции от двух церемонных, не яышющихся «олсгашнми: и, Г, ту и хну 1.18 ! 1. 1) Нельзя, т к. Ге 2гг„а хй 1;; 21 Можно, 1(х 01 0)= х !.1тгО (х 1 — «1)=х; 3) Мохгно, г(х,=,с, )=ххгч с(тг-з з)м г(я=и хо с э =)и Часть д Огввгм, решегм, !.18.12, 1,2) См.разд 1,14; 3) Пуать (6и Л ) = '1, д), )8, ) = Гтч у~.
Тогда х = ха х = х, т. е. 1! =йгггтйг), хну=хну, т е. 12- — йгз1г81) Таким образом, система 1х ч у) полна; 4) См. Рпзд. 1.14; 5) ПУсть )~и)з)м),д) — палнаасистеиа,а (дмдт)м)-+0). Тогда 11 =х=ячО= х — !О=яр(дпдз), 12 = хи у = » — ь у = йг2 (8 1, 82), т е. ) — ь 0) полна. Решим эту же задачу с помощью теоремы Паста. При заполнении таблицы Поста (табл.б.26) следует помнить некоторые свойства фУнкций из классов Ря,р„5,1 н йб. СлУчаи Р и Р, тРивиальны. Среди линейных функций монотонны лишь О, 1 и х; самодвойст- венны функции с нечетным числом переменных; сохраняют нуль функции, у которых свободный член — нуль; сохраняют единицу функции от четного числа перемсгшых, если их свабодньЩ члеи— нуль, и фуикпии от нечетного чиала переменных, если их авобод- ный член единина.
кайши б.яб Глава б,алгеб еискаэиеания 1.18.!3. 1.!8.!4. !.!8.15. 1) Систеьза функций П в классе К называется его бамгсом, если она полна в К, а всякал ее собственная подсистема пе полна. Система функций )хд х) полна в Р,. О!за состоит из двух подсистем; функций .ту и х ху — монотонная функция (см. таблицу Поста прелыдушей задачи), х — линейная и самодвойстшиная функция.
Таким образом, системы (ху) н Тт) неполны, т. к. эти функции и представляемме ими системы целиком содержатся в какомша иэ пяти классов Ре, Р„5, Ь и М. Слеловательно, !ху х ) — базис в Р,; 2, 3) Рассуждения аналогичны п. 1; 4) Система (хЗ у, хм у,!) имеет шесть подсистем: (хЮ у), (хо у), (1), (хЮ у, хо у), (хЮ у,1), (хор,1). Все они исполни (см. таблицу Посте), т. е, целиком содержатся в каком-то из пятм классов; 5) Рассужлоиия агзшогичиы и !.
1) Из всякой полной системы можно выбрать ие более пити функций, уловлетворяющик теореме Посш. Следовательно, базис не может а!держать более пяти функций; 2) зВоэьме» функцию, ис сохраняюшую нуль. Эта функция илн монотонна, и тогда она тоягдественно равна единипе, или иемоиотонна Если Р 1, то это несамодвойственная функция. Итак, 1 б Р, и Рм — 1 =э)"б 5 или Рй Р, и Рй М Таким образом, в полной системе обязательно найдется функция, не принадлежащая сразу двум иредполным классам. Тогда к этой функции можно присоединить не более трех функций из рассматриваемой системы функций так, чтобы удовлетворялись условия теоремы Поста Следовательно, в базисе не можез быть более четырек функций.
1) Составим таблицу Поста для мой системы фуикпий (табл 6.27). Часн я. Огэеьи шен«я, указан е Тияллца б.хг Первые три функции из системы С уже встречались ранее (см. задачу 1.18.12). рассиотрнм 1, = хуо+ хг. I (О О О) = 0 «ь О = 1, т е.
/, и 1ю 1 (1 1 1) = 1, /; ц Р,, Уп ростим /, = ху+ч хгм хч узч уэ. Двойственная к исй г'; =Хо УХЧУГ— М ЯХ т Е. ~ й 5. Даисс Д» =ХЦУГ КУГМ вЂ” = хо узл уз = х(уяЮ1)((УЮ1)(я%1)Ю1)Ф1= ххах ухй1, т. е. г»'й Ь. Функция равна нулю на двух наборах: (1,0,1) н (1,1,0), на всея остальных Р« =1. 1огда (0,0,0) с (1,О,!), но ~'(0,0,0) = 1 > У'(1,0,1) .= О, Таким образом, !'„ц «Н . По заполненной таблице сосшвнм КНФ системы С, в которой элементарные днзъюнкции соотвеютвуют спшбцам таблицы и включают в качестве слагаемых символы тех функций, которые нс входят в класс, соотвеютвующий столбцу. В данном случае КНФС = -(гз чу~И ч~я)(гг« "'г»з '«Л ч»г»«(Л чЛ)(г»з ч~э чу»). Упростим ззу КНФ и преобразуем ее в ДНФ.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
