В.Н. Нефедов, В.А. Осипова - Курс дискретной математики (1127083), страница 9
Текст из файла (страница 9)
Например, СДНФ форыулы Х, относительно списка переменных <Х,> совпадает с самой формулой, а относительно спнска переменных <Хь Хз> ЯвлЯетсЯ фоРмУлой (Хз а Кз) Х) (Хз а ! ХВ. Аналогнчпо определяется совершенная конъюнктнвная нормальная форма. Пусть формула А завнснт от списка переменных <ХН.,.., >. Тогда говорят, что А находится в совершенной комаюяшйвкой норма ькой форме (СКНФ) относительно этога списка, ьтлэ Аюрыула А* находятся в СдНФ относнтельно сниска переменных <Х,,..., Х, > или (эквнвалентное определенне) есле выполняются следующие условия: !) А пакоднтся в КНФ; 2) каждый копъюнктнвный член А является й»членной дизь.
4! юнкцией, причем нв 1-м месте (1<!<А) этой дизъюикцип. обязательно стоит либо переменнзя Хге либо ее отрицание )Х1" й" 3) все конъюнктивные члены А попарно рввличны. Пример 1.П. Формулы Х,Ч-)хчТУ-)хз; (Х,ЧХз1УХз)й(-тХг~УХз~УХь)й(Х,~У 'т/ !Хз т/ !Хз) находятся в СКИФ относительно спяскэ переменнык <Хь Хт, Хз>. Теорема !.й. Пусть формула А зависит от списка переленных <Хь...., Х;„> и А не мгыдественно-истиннцч. Тогда существует такая формула В, что А = В и В накодится в СКНВг относительно спевка переленнык <Хгн..., Х;„>.
Пусть А уже нзкадится в КНФ. По условию А нв некой-то. оценке принимает значение Л. Тогда А вв двойственной оцен. кс принимает значение И и по теореме о СДНФ сугцествует такая формула Вь что А пе В, н В, нвхолится в СДНФ. По прянцг~ву двойственности В*, А н В*, ивкодптся в СКНФ. Можно доказать эту теорему но внзлогни с доквзэтельегвон теоремы о СДНФ.
Прн этом применяются равносильности (ХНЧ -1Х т)С) й0 О, (С~IХ,) й (Ст/-)ХН) = С н законы ндемпотевтности. Теорема 1.7.(о единственности СКНФ). Если В, и В, — совершенные конъюнктивные норяальные форм» формулы А относительна списка переяеннык <Хй,..., Х;, >, то В~ в Вз могут отличаться только порлдкон своих конъюнктизных членов. В самом деле, В', и В'з в условиях теоремы будут СДНбь для формулы А* и могут отличаться (по теореме а сдинствен. ности СДНФ) только поряпком дизъюнктнвных членов. Отсюда следует утверждение теоремы.
СДПФ и СКНФ можно использовать для рзспознввзния рввносяльностн Лвух йюрмул. Критерий рввнчкильностнс две формулы А~ и А» зависящие от списка персленныл <Х~ . , Хг > и не равные тождественд но Л (И). равносильна в тон и только в тон случае, если онв приводятся к СДНФ (СКНФ), отличающимся .чншь порлдкон своик дилъюнктивных (конъюнктивньш) членов. Если А~ и А, приводятся к олнай СДНФ В, то А, ыч В Аз.
С другой стороны, если А, ип Ат н В, — СДНФ для Аь в Вз— СДНФ дчя Аь то В~ызд~ Аз, т. е. Вг будет СДНФ и длн А» и в силу теоремы о единственности СДНФ В, должке отлнчэться от Вз тельно порядком своих днзъюнктивных членов. Поскольиу приведение формул к СДНФ (СКНФ) можно проводить автоматически путем последовательных преобразований, то критерий позволяет устанавливать равносильность, ие обрзнщвясь к определению и к оценкам. 42 бй.й. Разрешиыасть Проблемой разрешимости дл» логиня высказываний называют следующую проблему: существует пи такая процедура, которая позволяла бы лля пронзволыюй формулы в конечное число шагов оореяелить, является ли она тавтологией? Ясно, что эта проблема разрешима, поскольку всегда можно перебрать все оценки сппспа перемензык и вычислить на них зпзчеиия формулы.
Опишем теперь другую, более экономичную ироцепуру расйознавания, связанную с приведеиием формулы к КНФ. Утверждение 1.3. Формула является тавтологией в та.и и только в тоя случае, если в ее ХНФ в любую из элеяентарнмг диззюнкций в качестве дизъюпктивных членов входят кюгаянибудь перелюнная и ее отрицониц Это утверждезне является тривиальным следствием двух пижсследующвк лемм, первзя из которых очевидна.
Лемма 1.4, Кокзюнкция яьлжтся тавтологией в тоя и только в тоя случае, если каждый ее конъюнкююный член являггея тшыологиеп. Лемма 1.б. Элементарная дпзъюнкция является тавтологией в тои и только в тоя случае, если в ней одновременно присутствуют какая-нибудь перелгенная з ее отрицание. Действительно, если в элементарную днзъюнкцию входят какая-либо переменная и ее отрицание, то это — тавтология и силу тавтологичности А тг'-г А. И наоборот, пусть ии олив переменная нс вхгщит в элементарную дизъюнкпию А вместе с отрицанием, Пусть также <Хн,..., Х~э> — список переменных, от которого зависит А.
Опрелелии слелующую оценку этого списка: переменная Хг, врнннмает значение Л, если ана входат в А кзк дизъювктиввый член, и значение И вЂ” в противном случае. На этой оценке все дизъюпктивные члены А примут значение Л. В самом деле, либо такой дизъюнктнвный член есть переменная Хч (и тогда он принимает зваченне Л), либо отРицанне пеРеменной -)ХН В последнем слУчае Х» „о, условию ие мажет быть днзъюнктивиы» членам и, следовательмо, принимает значение И, а ПХг †значен Л. Таким образом, формула А опровержима. Пример 1Ау. !.
Данажем, что (Х~ ю Хт) ю ((Хгю Х|) ю (Хгю Х,)) — тавтология: (Х, Х ) ((Хг Х ) ю (Х, Х )) 1( (Х Ч Х ) )I ( й ~«~ БАХ ) Ч )Х Ч Х ) ь(«~й 1Хг) г/(Хзй 1Х|))/ ~Хгь?Хг зв(Х~)гг«г~l-?Хз)/Хг) б (Х~)/-)Хг~/ )Хз'~Г )?«,) й(ПХ,ТУ«,)У ПХ,«УХ,) й д (-1 «. Т?-1», (à —,«; )? Х,). В первую диэъюнкцию входят Х, н -! Хз. ао вторую — Х, п -!Хь в третью — Х, и -!Хь в четвертую — Хз и -!Хт. 2. Рассиотрим форчулу (Х й Хз й Хз) )/ ( ! Х1 й !Ха й Хз) ~/ (Х~ й ! Лз -! Хз).
При приведении ес к К1!Ф среди элементарных дпчъюнкиий. будет диэъюнкция Х~)/пут'ту-)Хз, которая не удовлетворяет нужным условиям. Поэтому данная формула ие является тавтологией. Двойственное утверждение справедлкво и для тождсственволажной формулы. Утверждение 1.4. Формула являстсл тождественно-ложно> в там и только в том случае. если в ее Д!!Ф каждая элементарная ноньюнкиия одновременно содержит е качеюве коньюнктивныя членов «акую-нибудь переменную и ее отри>линг. Зто доказать несложно, исходя нэ принципа двойственности нлн используя леммы, аналогичные 1.4 н !.5. Зццачи н упражнения 1. Сколькими способами можно расставить скобки в слове.
Х, ~ -)Хз'т( Хз Ь/ Хз йХз, чтобы получилась формула! 2. Составить таблицы истинности для формул (Х~ ю чХз) й й (-!Х, тгдз) и (Х, ю (Х,ОХ,1) с ((Хи юХЯ) з (Х зХз)). 3. Записать составные высказывания в виде формул. употребляя высказывательные переменные для обозначения простых высказываний: а) лля того чтобы к было нечетным, достаточно, чтобы л. было простым; б) если идет дождь, то дует ветер; в) есле дует ветер, то идет дождь; г) ветер дует тогда и только тогдь. когда идет дождь; д) неверно, что ветер дует тогда и тельно тогда, когда нет дождя; е) Таня холит в театр только тогда. когда там покааывэют. пьесу и* современной жизни. 4. Локазать равносильности ! — б, 8 — 1! и !3 — 15.
5. )(оказать следующие равносильности: а) -!(А В) Ай-)В; б) Аю-!дна-!А; в) (А'~ В) й (А''т(С) й (В'~ О) й(С)/О)= — (А 5 О))У )у (В 5 с); г) Ай (АтьГС) й (В тг'С)ыт(А 5 В) т/ (АВС); д) (А В В) ~У (АВС) ',у (ВйО) ~/(СйО)=(А ~ГО! й й (В ттт С); е) А т/(-!А йВ)заА т/В. 44 б Доказать тождественную истинность формул ! — 10 (см. с.
33) и тождественпуго истинность следующих формул: «) ( — )Аю-,В) ю(Вюд)1 б) (-1Вщ-1Я) ~ ((тВ~А) юВ); в) (Я В) ((С)/А) (С'ь/В))1 г) ((Я~В) юА) ~А; д) )А=~ (АюВ). 7. Доиазать, что если АХ/В и -)Я'Ь/С тождественно-истинны, то и В з/ С тождественно-истинна. 3. Проверить правильность следующего рассуждения. Если Джонс ие встречал этой ночью Смита, то либо Смит был убийцей, либо Джонс лжет. Если Смит не был убийцей, то Джонс не встречал Смита этой ночью, и убийство имело место после полуночи.
Если убийство было совершено после полуночи, то либо Смит был убийцей, лабо Джонс лжет. Следовательно, Смит был убийцей. 9. Обосновать метод доказательства «разбором случаев»: (А~~/Лз~/... )/А ) ~В (А|юВ) Ь(Аз~ В\Ь... ...Ь (А ~В). Привестн пример такого доказательства. 1б.
Привести к ДНФ и КНФ следующие формулы: а) (Хз ЬХз) ю ( -1Хз Ь Хз); б) -1(-1 (Хз)/-)Хз) ~ (Хзй-1Х~))1 в) ( -1 х, —,х,) - (Х,-Х ); г) ((Х1 ю Хз) ю (Хз ю -1 Хз) ) ю ( -1Хз ю-)Хз). 11. Привести к СДНФ н СКНФ следующие формулы: а) (Хз%-)ХзЬХз) )/(Х,Ь-1Х,Ь-1Хз) )/ (Х1ЬХзЬХз); б) (Хз Ь Хз) ~ ( -1Хз Ь Хз); а) (-1 Хз'з/Хз) Ь (ХзюХз); (-1Х, -1Х)-(Х,-Х); д),(Х~ь/Хз) Ь (Хз юХз). 12. Пусть формула А не содержит никаких логических симжжов, кроые . Доказать. что А являетсл тождественно-истинной тогда и только тогла, когда наждая переменная входит а А четное число раз.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
