Математическая логика. Шапорев С.Д (1019113), страница 41
Текст из файла (страница 41)
2) и = — ху ч лу ч т" ч лу2 и луг и ухи хт и ут =— М ХУ Ч .ЛУ2 7 У -, Ч Лг М «У Ч Уг Хь. 1.1! !9. 27 Множество набороя, значения на которых определяют самодаойственную функцию, содержат 2" ' элементов (полоаина всех иаборое, т к. самодаойстаенная функция принимает на противоположных наборах противополпкныс значения).
Общее число функций равно числу даоичныхнабороаллины 2" ',т с 27 (см задачу).112). 1.!1.20, бгункцил латаются нссамодаойстаенной, если «ущесгаует такой набор (пмпз,...,па), что ~(онпз,...,п„)= Р~пппз,,п„) Разобьем переменные х,, х„..., х„на дае группы. В первую екяючим тс персмениыс х„дяя которых а, = 1, а другую тс, для которых аг — — О. Опждеьтаим между собой асс переменные первой группы, переимсноааа их а у,, а также асс пе!мменньм его!юй группы, псреименоаае их а ) з . Получим функцию пг двух переменных Р(у!, у, ), коюрал может оказаться и функцией ог опной переменной, если (пг,ат,...,п„) — единичный или нулсаой нгебор Очсеилно, что ф(1,0) = 7'(пг,пт,,п„), ~аз гэсг Чаем я. Олмнц решения, юаанья гр(01)=1 (цнпт,...,о„),постону гр(01)=Ф(1,0),т.к.
У иеаамолвой- отвеина цо условию. Может окататься, что дальнейшее отожлесталение переменных с сохранением несамодвойсгвенностн невозможно. 6.3. Ответы и решения практического занятия 2(803 1.18.1. 1) СДНФ 1 = хукч хухчхукчхук. Выполним ватой формуле все операции неполного оклеивания и поглощени» 1 .= х (у г )7 у2(г гк)тку(2 7 2)чхугчхукчхтгч ч хук и хкч ухч;у ч к у 2 ч «ух ч кук ч ху2 и х2(!ч у)ч ук((ч х) чку(1ч кч 2)мякч укчху. Итак, методом Квайца найдена сокрашения» ДНФ. Составим теперь матрицу Квайна (табл.
б.20). Таяллия 6.20 Тупиковав ДНФ равна хучхк, она же будет равна минимыиной дНФ. Ишк, МДНФ 1" = хучхк. Сосшвим теперь каргу Карно дпя исходной функции. На карге выделяются три нары точек (отмечены на рис.6.1), абратуюшне 1-к)бьь простые импликангы иммог вил: х у, 22 и ук . Сокрмцеггггш ДНФ равна х у ч хх ч ук. Ит карты Кар но вилно, что пару точек (0,0,1К!,0,1) и соответствующую ей праагую имппиквнту ук можно отбросим.
Тогда МДНФ = ху ч хк. Глав б.дяеб авм кавмваииб ВВВ Проверим теперь функцию на принадвезкность к казкдому нз пяти классов Поста. г'(О О 0) = 0 л 0 и 0 л 0 = 1» О, /й Рв; Т(111)=1л!ч! г, 1=1, ~н Р,; «~,у 2)= туч хх и хулхх (вчем)л(хч )мхч ухч ух» » Г = хуч 22, «'й 5: ! Я О,т. к. содержит произведение хх; /й М, поскольку (0 01)с (011), а ~(001)=1> ~(011)= 0; Риг. б.! 2! СДНФ ~ = ау яч хуя ч ху -ч хух и х ус Тогда « = ху!2ч 2)" ху!2 7 7) «22(у 7 «т 7 «2(х ох!4 ау ч г«7 и . х ух '. х с2 ч х ст н ху (! и 7 ч 2)', ч ху!1 ч 2 и 2)ч хх(1 и ! )ч «2 = х«ч ау ч ч 22 ч ух — сокращенная ДНФ.
Матрица !2вайив приведена а таба. б.21. Гвбявня ббП Часть й. Ответы, имения, укзщние ТупикавыхДНФздесьдве: хучхучх«и хучхучу«Минимы~ь. ны«ДНФ тоже две, они совпадают с тупиковыми. Карта Карно лля данной функции имеет вил, показанный на рис. 60. Имеется четыре нары точек, образующих 1-кубы. (0,0,1)-(0,1,1), (0,1,0)-(0, 1,1), (1,0,0)- (1 0 1) и (О 0 1)(1 0 1), им соответствуют следующие импликанты: х«, ух, ху и у«. Таким образом, сокрщцениая ДНФ равна щчхучхуч ут, а минимальных дНФ даж МДНФ! — — ««чхучху, МДНФ, = ху ч х» ч у« .
Для проверки принадлежности функции к класаам Поста воспользуемся одной из минимальны«дизъюнктивных форм, например, У = к«чхучху. 2(ООО)=ОлОЧОлйчйл0=0, уб Р„; у(! 11)и1л1ч1л1ч1л1и Ох 1, тй РИ /~ у х) и ххч ху ч ху и х«л ху л ху и (х ч х) л (х ч у)л (х ч у) и и (хчххч.«учул)л «чу)м(хчу«)(«чу)мххч хуач хуч чу«ум«у«ч «у Х у, следовательно у'и $; «хчхучху их«лхулху =((хе!)хе1)((хе1)уе1)(х(уе))В1)В1= =(хге«е!Х~уеуе!Ххуехе))В1и = (ху«В ху«В хуВ «ухе у«В уе х«В «В1)(«у В хВ 1)В1 = = ху В хут В ху«е ху В ху«е ху«е Вхуехуеху«еху В«уел«ех«ехехуе«у«е у«е Рла 6.
Длтеара ыскаэыианид 267 ты 1 Юхттытца1ьн1 =ау'хтахакп ухыахсе у%2,6 Д; 1 6 М, т. к. (100)» (120), но у(1 00)ы1> т(110)и0; 31 СДНФ1 =.туа ч хуачхухчлухч хус. у =ху1 ч )чхт(уч у)ч ух(хч х)чху(сч )чхухч ч хтх ч хули хух ч хух н — = ху(1ч сч 2)чха(1 и 1')ч ух(1 ох)чху(1ч 2)н — = луч х ч ухчху — сокрашеннаа ДНФ. Твааиаи 6,22 Туанкавык ДНФ дее лучххчху, хучухчху 1табаь 622); ьаинимальнык ДНФ также дае: МДНФ| =луч усч ху и МДНФ2 = ху ч хх ч ху Карта Карно для исходной функции трек переменных приведена на рис. 6.3. Рне.
6.2 Чапь й Отлети, лилия, лазания Четыре пары точек образуют четыре 1 — куба: (0,0,0)-(0,0,1), (1,1,0)-(1,1,1), (1,1,1)-(1,0,1) и (0,0,1)-(1,0,1). Сокращенная ДНФ из карты Карно равна кучхгч узчху, МДНФ1=хучкучхг, МДНФг =хучкуч уг. Возьмеи вторую мииимачьную дизьюнктивную форму и проверим, к какому классу Поста принадлежит наша функпия. 1(000)=ОлОчОлОчОл0=1, Рб Р,; 1(1,110)=1л1ч1л!ч1л1=1, 1 б Р,; 1 ~у« 'Ркуч «у ч уг и и ху л ху л ух ((хч у)(х ч у)((у ч г)и (хк ч ху ч ху ч уу)(уч г)м н «у ч кууч луг ч куг и х у(1ч г)ч хуг — «у ч куг и 1, 105; 101, т.к, содержит произведение ху; 10М, поскольку (000)-с(100),а г(000)=!>1(100)=0; 4) СДНФУ'=хугч«угч«угчхуг, г = хг(у ч у ) ч уг б ч х) ч ху г ч г) ч хуг ч ху г ч хух ч хуг и и хг(1ч у ч у)ч уг((ч х)ч ху(1ч г) и хг ч уг ч ху — сокрашеиная ДНФ. Тупиковая ДНФ одна хг ч ху, она же равна минимальной, т.е.
МДНФ=«гч«у (табл.б23). Составим теперь карту Карно. Простые импликанты для этой карпе Карно равны: ху, уг и хг, минимальная ДНФ получаеюя па двум парам точек; (0,1,0)-(0 1,1) и (1,1,1)-(1,0 1) (рис б 4), МДНФ = к!ч тУ 1(00,0)=блОчОл0=0, 1 Е Ре; таблице бгк Глава 6. Алгебра аьмквэмгмний Р с. 6.4 У(1,1,1)=1 1'г!о!=1, !6 Р,; фу»)=х» г»У= — х»л»Уи м~!хо»)!»му)мххмх»мхуоу»и 7, 76$! ГОА, з.к содержит х».
Составим таблицу истищэости длл МДР!Ф 6щбл 6.24! Из пес видно, что для всех сравнимых наборов переменных вмпслняется условие а 4 р — э 2 !а)< 76!) Следовательно, 7 е 67; 7'аалиаэ 6»4 5! СДНФ !'=ху»оху»чту». Г= эх!» г )мху» гхэ» гху»= ух!! и» зг»)м ху = — ут ьг ху» — сокращенная ДИФ. Матрица Квайна для этой функции очень прос~а и приведена низко.
Кари Карно изображена на рис 6»й Одна гочка на этой карте Карно принадлежит 0-кубу. эпэ ~очка (0,1,1). Кщс пара точек (1,0,0»41,0,1! Чаем 7!. Ответи, жени», указания обратует 1 — «уб. Простые имлликанты равны хух, ху. Тупиковая ДНФ равна хугчху, она же равна единственной минимальной днэыонктнвной нормальной форме !табл. б.25!. Теалкце йгу у(000)=ОлОЧОлОлО=О, у н Р,; ((! 11) = ! л! ч! л1 л 1 = О, ~ й Р,; у(х, у,т)= туч хуг и ху л 3 уг — (хо у)л (хч у ч 7)м и хх ч х у ' ху ! у у ч хгч ух — = лу'! х у ч хтч у и Т, !" й Я; «уч хуг ихулууу, =(х(уй!)й!) ((тй1)угй1)й1= = (хг' й х й 1) ' (ху7 й уг й!)й 1 = = хугй хугй ту7 йхг'7 йхут й уг й ху й хй 1й! = =хУгйУгйхУйхй Е; Уй М,та.
(О!!)ч(111),~ У(011)=1>У(111)=О. 1.182. Так как хй у = лье у=(тлу)ч(хлу). то х й у = х хьь у и (х л у) ч (х л у) и ху ч ху — СДНФ; Глава а. Аагебра еьюяммааний хЮ у = (хл у)ч (хлу)м (хч (хе, у))г (уч(хл у))=- = ((х ч х) л (х ч у)) л (~~о х) л (у ч у)) и (х г у)(х ч у) — СККФ, По опредепению даойсгееиной функции (хй у)' = (х Юу))=((хй!)Э(уй1))Э!= хй уй1;тожссамос можно ~юяуяить другим способом, (»йу)' ='(хо у)ч(»л у~м и (»лу)л(хлу)= ((хй1)уй1)(х(уй1)Э1)= = (хуй уй1)(»у Юхй!)= = »уй »уй хуй »уйхуйхйхуйуй1= хйуЮ1, т. к. опера- ция споженив па модулю два обладает сяедующими свойствами: хйх=О, хЮ!=х, хйб=х, хйх=1. 1.18 3.
!) Конъюнкция: ху=х.у, днтыонкция. хоукаЂ = хлу= =(»Э1)(уй1)Э1=»уЮхйу; отрицание »=хЮ1; импаикация х — ь умхч умхлу=ллу=л(уй1)Э1= хуй»Ю1; эквиаеяенция хая у и (т — г т) л (у — Ь х) вам (хч»)л ~ ч .т) и .ъ л у л > л хи и х л у л у л х = (т(у Ю 1) Э 1)(у(х Ю 1) Э 1) = = ( у Ю х Э 1)(.те Ю у Э 1) = = лу Э лу Ю лу Э ху Э з:у Э у Э ху Э л Ю 1 = л Ю у Э 1; 2) хч уч х хоулх=(»Э1)(уй1)(хй!)Э1= = (ху Ю уй хй 1)(яй1)Э1= = хут Ю уг Ю хх Э х Ю ху Э у Э х Ю 1 Э 1 = = хуя Э лу й хх Э ух Э х Э у Ю я; 31 хуч угч ха паулу»лхя= (хуй1)(у»Э!)(хай!)Э!= = (туя Ю ух Ю ту Ю 1)(хя Э 1)Ю 1 = Часы я.
От»ежа шанин зшш» = хуг Ю хуг Ю хуг Ю зг Ю хуг Ю уг Ю Ю ху Ю 1 Ю 1 = ху Ю хг Ю уг; 4) хугч хугч хугч гугш г(кучку)чг(луч ху), х у ч ху и ху л ху = (х(у Ю 1) й 1)((х Ю 1)у Э 1) Ю 1 = (ху Ю х Ю 1) . (хуЮУЮ1)Ю1=хйу; ту ч ху и ху л х у = ((ху Ю 1)((х Ю 1(у Ю1)Ю 1) Ю Ю!)=(»уй!)(»уй уйх)Ю!= =»уй хуйхуй уйхуЮхй1=хй уй!=хйу; хухч хуг ч хугч хуг = г(х Юу1ч гх Юу = г(хйу)л х(хйу) = = (хт.й тай 1)((ай 1)(з Ю у Ю1)Ю1)Ю1 = = (хг Ю уг Ю 1)(хг Ю х Ю уг Ю у Юг) Ю 1 = х Ю у Ю г Ю 1. 1.1Ж4.
Пусть х, — така» переменная. Сгруппируем члены, в которые входит Х, и вынесем х,, полу»им У(хнхг,,х»)= х!ф(хг,...,х»)еф(хг,...,ха). Это разяоженис можно рассматривать как полипом Жеев»кина по переменной д с «озффициентами, зависящими от остальных переменных. В разложении ф и О, т. к в противном случае в силу единственности полинома Жеталкина х не входила бы в полинам для Возьмеи значения переменных х, х, ...х„, на которы» ф = 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
