Математическая логика. Шапорев С.Д (1019113), страница 40
Текст из файла (страница 40)
Это число равно числу лвоичных наборов длили 2". Действительно, в нстинностной таблице функции г'(«!,хз,...,«к) фиксируем каким- либо способом порядок строчек, т.е. лорлдок наборов (и!,аз, ,п„) значений аргументов з;,хз, ,х„, Тогда функциа Г(~,«г,...,.т,) однозначно определив«ел своим последним столбцом, т е. набором из 2" нулей и едимиц. Развичнмк функций столько, сколько имеетск различим«наборов ллинм 2" из двух элементов О и 1, т. е. 2з 1113. Т (хохз,хз)=««,«эоххзхз ч«хзх,'г.г,.ь,х, и —= .т «з(«~ ц «~) г«зхз(«1 .' «~)и х «з и х хз, Тз(«о«зсз)=хетт~ э ««з«з г««ге;г«х «з г«««зч ««з«з г«,,«, —= : «заз(«> о «!)о«>«з(«з ч«з)ь«ггзхз о«>«з«з ч г~ «зхз — = «~«з«з о«> «ьз и о«хз«з ч«гтз цхз«з их (хз ч~хз)зг«з(«з ох~«э)ох~«,«з и — «(«з о«э)ох(«! ох )ч««з«з «гтз ч««э зггзк ч П«оггг «, = — = «з(«о«,хг)ч ««, о««г ', «» = ««, ', ««; т« '.
««, ',г «т = — «~ («г ".гг )'г «г («~ г хг)э«газ ,' !з(«м.тг «з)= х,хзхз м«1«.«з =х!хз(хз ц«з)их!«з. Г'„(«пхз,хз) = ххх, оггтх, ч хтг«з ч ххах, и хх(х, г«,)о наср я. Оте ты, июння, укааання 1. ! !.4 1) у(О,у,т)ю(Олу)ч аля)и ут, т (1, у, ) = (1 л у! ч (и л к) а у ч уа а (уч у )л 1(у ч х) ю уч х, у'(О,у,т)ну'(1,у,х); ЯХ,О,т)= (хлО)ч(1 ля)ах, Д(щ1, х) ю (хл 1) ч (О л к) и т, У(ХО, х) и Г(Х1, т); !'(х у О) = (х л у) ч (у л О) и ху, Г(х у1)= (хл у)ч !ул1)а у(хл у)= (хч у)л(уч у)а хч у, ал(х УО) К У(х У!). Все переменные сущеспинны 2! Г(О,у)=(Ол у)чО и О, Я(1,у)=(!л у)ч1ю!, у'(О,у)н !'(1,у), !'(Х,О)=(хлО)чхюОч ха х, а(Х1)ю(ХЛ!)ЧХаХЧХ Х .Г(ХО)ю/(Х!), Х вЂ” СущеотВСН- нея переменная, у — фиктивнае.
3! !'(х, у, к) = (х -к (у е х)) к ((х -е у) — т (х е к)) ю ю Л~чв)ч х ч у 4х ч я)~ а х л у ч хч ((х л у)4» ч х)) ю ахл(улк)ч((хчх)л(хч кача)вхухч (хч уча)а (хчху )ч ч у ч х — х ч (уя ч 3 ) ч х а х ч у ч ко х а хч у ч 1 ю 1. Все три переменные в формуле — фиктивные, формула тоадест- венно истинная. 1.1!.5. 0 хл умхч у, х-к уюхч у; 2! Хлумхлум хчум х — ~ у, хчумхчумх — «у; 3) ха хчО в = х-кО, 4) хо у — (хчу)л (учу)а (ха у)чую(хлу)чую ю хч учу и(х-ау) — ау, Глава б. Лм евра анекаамеаннн ггб 1.11.б.
1) ((А — Ь В) -Е (С вЂ” з А)) — 1 ( — ь С) в А ч В ч (С ч А)ч ~ч С) в в А ч В л С ч А ч В ч С и ((А ч В) л (С л А)) ч В ч С в в ((А ч В) л С л А)ч В ч С =— (((А л А)ч (А л В))л С) ч В ч С = н АСч АВСч О ч С' в АСч В ч С вЂ” ДНФ, получим иперь КНФ АС ч В ч С в ((А и В) л (С ч В))ч С в в ((А ч В ч С) л (С ч В ч С)) в А и В ч С вЂ” КНФ; 27 ((((А — ь О) — ь А) — ь В) -ь С') — ь С в А ч В ч А ч В ч С ч С в в Л ч В ч Ач В л Сч С в (((ГА ч В) л А) ч В) л С) ч С =— — = ((ГА л А)ч (А л В) ч В) л С) ч С в (((А ч О) л (О ч В)) л С) ч С в ((А ч В) л С) ч С = — ((А и С) ч (В л С)) ч С в в АС ч ВС ч С =— ВС ч С ВСч С 1ВлС)ч СвГОч С)л(Сч С) — = 1ВчС)л С вЂ” КНФ, 31 ((А з ( — ь С)) — ь ((А -ь С) — ь (А — ь В))) в — = А ч В ч Сч А ч С ч А ч В в (А л (В л С)) ч (А и С) ч 1А ч В) =— в АВСч АСч Ач  — ДНФ, А В С ч АСч А ч В в АВ С ч А ч С ч В в А ч В ч С вЂ” КНФ.
1.! 1.7 Пусть переменные Ао А,,...,А, принимвот значение 1, а переменные В,, В , ,Вв — значение б. Требуемой заементарной коныонкпией будетвыражение,~ л А л ...л Аь л В, лВ, л...л Вв 1.11.8. 1) Табвинный способ реализован дл» формулы 1. Результаты привалены взабл. 6.17. Час«ь!! Оюетм шелиа, навалил решила а ! т СДНФ =АВСч АВСч АВСч АВСч АВСч АВС ч АВС ч АВС. Способ эквивааентнык преобразований: ((А — «В) — «((ВлС) — «(АлС))) — Ач В»ГВлССч(длС))»ГАлВ)ч ч((В»С)чАС) АВ4Ь ч ГС»А) ~Сч С))АГА»»Счдм пАВ(СчС)ч В(Ач А у чС)чС(Ач А~Вч В)чА(В ! ВА.»С)н н АВСч АВ Сч АВС ч АВС ! АВС ч АВС ч АВС ч АВС ч АВС ч ч АВС ч АВСч А В Сч АВС ч А ВС ч АВС и А ВСч А ВСч АВСч ч АВСч АВСч АВСч АВС»АВС.
Надо заметить, нто способ эквивалентнык преобразований заметно лучше табличного. Прн малом числе переменных это не оюутимо, ио, если, например, рассмотреть функцию !' (х„хз,...,х ) = ц ч х, ч ... ч хз,, то будет видно, лто формула в правой части содержит 39 символов 120снмволое перемеинык и 19 символов дизъюнкции), таблица же для ! (ц,х„...,хм) со держит 2 >10, т.е. более миллиона строк. 2) ((А-«В) — «А) — «(А-ь(ВлА))п А, В»Ач(Ач АВ)п = бдчВ)ад)чГАчАВ)м ГАл А)ч(Ал В)ч (АчАВ)н — АВчАВчАнАВ»А АВчА(В»В)=АВчдйчАВ; Гпеез П. Легебдв енскзеывеннп ггг 1,11В.
3)АлВ-ьАлАл — ьВиАлВчАлАлВчВи и (АВ л А) л (АВ л В) и Л л В; 4 +(Аз ь(-. ь(Ае, -е А„),.))жА, ч (А, ч (,. ч зЛт„, чА„) ))иА чАгч...ч~,,ч =-А (Аз чАз)(Аз чА )..(г~, чЛ )ч гЛ,(Л,чА)(А,чА,).(А, чА,)ч, ... ч А„~(А, ч А~)(Аз ч Аз)..(А„го Ае з). (А„ч 8 )ч А„(тй ч А,)(Аз ч Аз) ..(А„, ч А„, ) Все записанные конъюнкпии раскрываются одинаково. Например А,(А ч Л ). (А„м чА, ДА„ч ~,)н и (~А ч А, Аз)..(А„, ч А„,)(А„чА„)и а (ЛА А,, чА А А„, ч ., ч А А ~,, и Л Л Азы )(А„ч Ае) и и ~АзАемй„чА~АздептУ„ч.,чг~АзА, ~Л„ч ч А А Аеы г~, ч А ЛзА и Л, ч А Лей„, А„ч., ч А,А Ае,йе.ч ~~,А~~,,А„ и т.д. Поппе спинний иденов по закону идемплентности в итоговой СДНйг всей формуяы будут содержаться все логические спвгеемые виде гзи л Ап л..л Ап,кроме одного А, л А г ...л Ае,гя, .
5) (А — + С)-ь В-ь А ай чСч Вч А и (АлС)ч (ВлА)и и АС ч АВ и АС(В ч В) ч АВ(С ч С) и =- АСВ ч АСВ г ЛВСч АВС. 1) Твбп ичный способ дпя фар муяы 1 (тебя. б. 18). Чапа Н Оивнв решенна Кеаэанаа гтв Табаева банг СДНФ 1) = АВС, СКНФ1) = СДНФ1) = АВС и А ч В ч С Метод эквивалентных преобразованнй: (С вЂ” э А) — е ~В ч С -э А) и С ч А ч В ч С ч А и и (С л А)ч (В ч Сч А) и Ач В ч Сч СА и А ч В ч С; 21 А л В е Ач(Ал(Вч С))и Алйч Ач (Айч АС)= и(АВ л А)ч (АВ ч АС)иАВч АС и А(Вч С)и и (А ч (В л В)) л ((В ч С) ч (А л А)) и и (А ч В) л (А ч й) л (В ч С ч А) л (В ч Сч А) и и ((А ч В) ч (С л С)) л ((А ч В) ч (С л С)) л л (А ч В ч С) л (А ч й ч С) =- (А ч В ч С1 л (А ч В ч С) л л (А ч В ч С) л (А ч В ч С )л (А ч В ч С) л (А ч В ч С) и и (АЧВЧС)(Ач ВчС)(Ач ВчС )АчВчС ААч Вч С); 3) Ал~йч С) — э (АлВ)чСиАл(ВчС)ч((АчС)л(ВчС))и и АВ ч АС ч (А ч С) л (В ч С) и Глава 6 ЛлгеВГм высказывания ггя и АВч АСч й(Вч С)чС(В чС)в в АВ ч АС ч АВ ч АС ч ВС ч С вЂ”= в АВ ч АС ч ВС ч С в АВ ч С в в (А ч С) л (В ч С) в в ((А ч С) ч (В л В)) л ((В ч С) ч (А л А)) в = — (А ч В ч С) л (А ч Вч С)л (А ч В ч С) л (А ч В ч С) в м(Ач В .'С)(Ач ВчС ЯАчВ чС); 41 (А ч  — э АлС) — э А е Ач В лС в ЛчВч (А лС)ч ч Ач А ч (В л С) — = А ч В) л ГАл С) ч А ч (В л С) в в (А ч В) л (Л ч С) ч А ч (В л С) ° =(Аь В)лАч(Ач В)лС ч(Ач В)л Ач С)в = — АЯч АВч АСч ВСч (Ач В)л Ач(Ач В)лС в = АВчЛСч ВСч Ач АВч АСч ВСв в А ч АВ ч ВС ч ВС = Ач АВ ч С = А ч В ч С; 5) А(чдт ч, чА, -эВ~ лбз л..лВ„в в ((А, л Ат л ...
л Л) ч В, ) л ((А, л Аз л ... л Я, ) ч Вт) л ... ... л ((А, л Аг л ...Я, ), В„) в (А~ ч В, ) л ГАт ч В, ) л ... ...л (Д„ч В,)л (А, ч В.з)л (Аэ ч Вт)л ... .. л (гй, ч Вг) л ... л (гй . В„) л (Аг и В, ) л .. л (л„ч В„) . 1.!!.1О. Поскольку исходная формула абсолютно истинне, ее СДНФ должна аодержать все различные элементарные коньюнкции, каждая иэ которых обладает свойствами совершенства Число элементарных коньюнкций для функции л переменных должно быль равно числу строк исгиннсстной таблицы, т е.
2". Тогда: !) СДНФУ'(х) = хч х; 2ВО Часа Я. Стевги, аминя, шзвниа 2) СДНФг'(х,у)= куч хуч хуч ху; 3) сднФ у (к у 2)=хуке ку2ч ту« чкусчкжч хукчху«ч «ук. !.1!.1! Исходные сосбражени» аналогичны соображениям предыдущей задачи. Ц СКИФ /(х)= хлх; 2) СКИФ/'(х,у)=(кч у)л(хч у)л(«чу)л(хч у); 31 СКИФ 2(х, у,к)= (хч у ' 2)луч у ~2)л «чу 77)л л(х чу ' 2)лГхч уч 2)л (хч уч 2)л л~чучк)л(хчучк). 1.1 !.12. Так как /(х, у,я) и 1, то формулу удобно представить в виде ДНФ, тогда достаточно, чтобы хотя бы одна конъюнкция была истинной Это можно обеспечить перечислением переменных в конъюнкциях, причем дсстаточно трех конъюнкций, и прн этом одна из переменных должна входить в конъюнкцию сама, а две других в виде отрицаний, Таким обраэоьг, /(х,у, )= (клул 2)ч (хлулк)ч (хлул 2).
!.1!.13. Представим опшь формулу в аид» дНФ. Дл» функции 7(х,у,г) существует только трн пары значений переменных, в которых большинство переменных принимает одно и то же значение: (1,1,0) (1,0,!) и (0,1,1) ил» (0,0,1), (0,1,0) и (1,0,0). Тогла функция, принимающая то же значение, что и бояьшинство переменных, имеет вид 7(ху,к)=ху чхуячхух. Для меньшинства переменных справедливы аналогичные рассуждения и /(х у,з)= лук ч хукч хук.
! 3 !.14. Рассмотрим первое уравнение хл 7' м хл у. Для его смущсствлсниа переменная 2 в Г(х, у, я) должна быть фиктивной, т. е 3: лунку(с«с!мку чкуг. !"ассмотрнм теперь второе условие хч 2 -= — = х ч хх и л„у, х ч хк = (ту ч хх)ч х м (ху(2 ч 2) г «2(у ч 1))ч х, Глава б Алгебра вмск зив н Д гб! т. е. Г(х, у, т) должна содержать следующие сяагаемые: Г (х, у, г) = хут о «у« о «уг и «уг . 1.1115. Заметим,что х ох» »Г.. их, и (х, ох ч ...ох )л л(у''))н (х, лу)тг'г(х» лу)чГ .м(х лу)о (х л у),анщ»огниво «» л х» л ... л х» н (х» л х, л ... л х») г (1 г, у) и (х» г т) л (х о у) л .. л (х, чу)л (х, о у). используя это, мы всегда можем считать.
что у любых формул А и В заданные норманьныс формы содержат одни и те же переменные. СДНФ(Ач В) получится, если взять дизьюнкции всех эвемснтариых конъюнкций СДНФ А и СДНФ В . СКИФ (А о В) находщси цо формуле СКИФ(А ч В) = СДНФ ГА, В). Дяя этого необходимо 1) Вь»писать дизьюнкции эаемснтарных конъюнкций переменных, невходящихвСДНФ(Ао В); 1) О* =1, 1' =0 поскояьку висит существенно, надо функции: х = хм х, « функция ни от каких аргументов пс щпосщвить отрицание вищь на значение и хм х, т.е. х и х саиодвойсщенны; 2) Заменить о иа л, а л на 'г, К на «;, а «; на х,. Подученная формула будет СКНФ (А о В). 1.1! 1б.
В СКНФ А заменить о на л и л на и. Действнтсяьно, перемен. ные у формулы А(ц,х„...,х„) преврвтнвись в хщх»,...,»:„у формулы А', что соогветствуст изменению переменных при переходе от СКНФ к СДНФ. Необходимо теперь только поменять местами двойствснныс операции, тогда окончательно вместо А цояучим А= А', эта же операция необходима при пресбрвзощиии СКНФ в СДНФ. Например, А = х — ! у, А' = у — » х !см. задачу 1.11.17). х-ь ум хм у — СКНФ По описанной процедуре СДНФ(х-+ у) = хл у.
Насамом деве у-с хм«му= — «л у— СДНФ А'. 1.11.17. гвг Ча |ь г. Окяева вюния, я яачяя 1тх л у) а х л у ю х ч у ю х ч у, (х ч у)" ах ч у =— х л у а х л у, 1тх -е у) а х — т у — х и у ю у у-е х, (я .!'-==*еР=УО=О=Ь. !'В а а а чхлхчую у — ьхл х — ьу — = уьех! 2) ревзин задачу двумя способами.
Условии означают, что ! у'11,1,0) = 1, /110!)=1, Двойственная функция получается из исходной Р(0,1,1) =1. при замене значений всех псреиенных на противОположные, т. е. всюду в истинностной таблице !таба.б.!9) нужно заменить О на ! и ! на О. Тайен б.!р Из табл. 6 !9 получаем: / (хух) = «юч хухч хуг, У" т1Х,У,Х)=ЯХ,У,г)ю ЛУХЧ ХУХЧХУХЧХУгЧХУЛ.
Второй способ: ! (х у г) = Ях у г) = хуг ч хуг ч хугоЂ ю хуг л хуг л туг = 1хч у ч 1)!хм у и г)1х ч у ч г)а гав Глава В реглера еиогаеиеалкй мгхчхучхгчтучуучу2члхчу2ч77)(хчуч )и (л ч ухч)'2)(х ч) ч ) лх оку ч Ч ХУ2 '7 Х)' Г У Уг 7 Уг'7 Х7 Ч У22 '7 У2 = И ХУ2 Ч Х У 2 7 ЛУ Ч Ут Ч Хг М «Ут Ч ч х у Гч лух ч ху 2 ч хуг ч хуго лух ч т У2 —= и ХУ2 Ч ХУ 7, Ч ЛУ 2 Ч ХУ2 Ч ХУ2 1.11.!8 По определению самодаойстеенной функции, 7(х!,Хз,...,хл) л = Р*(з:!,хт,...,л;,)= ) Гхыхз,...,лк). В нашем слУчас (лу ч ух ч 22) = ху и у - ч х 2 и =-~ХЧ))Л~ЧХ)Л~Х .)и и (г ч у)(у ч 2 гухг ч 2) — = !Уху ч у ч хг ч у")гух .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
