Математическая логика. Шапорев С.Д (1019113), страница 6
Текст из файла (страница 6)
Однако с/шдн многи» ДНФ тишь одна булы удовлетворять всем условинм совершенства. ДНФ формулы алгебры логики, удовлетворяющей всем четырем условиям совершенства, называется совершенной дизьюи«жив«ой нормальной формой Условиями соесрюенстеи называютс» следующие: 1, Все логические слагаемые в ДНФ различны 2. Кюядое логическое слагаемое содержит все переменные. Пива 1. Лиэб лопткэ (алгеб внсаээнвемнй Ни одно логическое слагаемое не содерагит х, н х~ одновременно.
4 Ни одно логическое слагаемое не содерэкит х, двюкды. рекам образом, соеершеююй дюыонюнменой формой (С)Е 1Ф) относительно пере временных «„х„...,х„называетс» такая ДНФ. в которой нег одинаковы» Эдсментариых конъюнкций и все элементарные коньюикции правильны и палны относительно переменных «„«з,...,х„Итак, для всякой функции алгебры логики г (э„, х„...,х„), не равной тождественно нулю, справедлива ее следующее представление в виде СДНФ; (1«1,«,...,Х„)и о Х| ЛХз" Л...
Л х" (1 р 1) Г(жлт,е„).-~ ' где аимвал тг означает, что берутся дизъюнкции по тем набораьг переменимх, которые указаны под ннм. Еали функция ~(хп «т,...,к„) задана нс истннностной таблицей, а формулой, ю ее СДНФ можно получить путем равносильных преобразований. Заметим, что формулы, являющиеся ДНФ, можно охарактеризовать как форнулы, содержащие только дизыонкцию, конъюнкцию и отрицание, в которых отрицания спэят только над аргументами, и вначале выполняются все коныонкции, а потом дизъюнкции.
Итак, алгоритм получении СДНФ таков: 1. Для формулы А получаем любую ДНФ. Е Если в ДНФ есть слагаемое В, не содержащее х,, то заменяем Ви Вл(х ох) и(Вл х) о(ВЛ к ) З. Если в ДНФ встретится два одинаковых слагаемых В, то лишнее можно отброситъ,т. к. Вм В= — В. 4. Если в некоторое слагаемое В в дНФА х, входти дважцы, то лишнюю х, можно отбросить, так как х л х, и к,. Если слагаемое В в ДНФА содержит конъюнкцию х; л х,, то х, лх, иб и В иб, и это слагаемое можноатброоить. Формула вида х ' м х"' ч ...м х„" называетса элемелмор юй дюъюнкащй т или днзьюнктом.
Пустим дизъюяклюм называется константа О. дизъюнкт Невыполним в том и только н том случае. если он пустой. за Чесс !. Мвгемапгчесяеяло ияа Кояьшпклшевай пормгмьпон формой (КНФ) формулы А называется равносильная ец формула, представляющая собой конъюнкнию элементарных дизъюнкций. Если КНФ не содержит ни одного дизъюнкта, т. е. пуста, то она эквивалентна 1.
Элементарная дизъюнкция называется праеилыюй, если в нее каагдая персменнвл входит не более одного раза, включая и вхождения под знаком отрицания. Правильная элементарная дизъюнкци» называетсп полной относительна переменных Х,х,...,х„, если каждая из этих переменных входит в нее олин и толька один раз Пусть х„х„...,х„— набор логических переменных, а а = (а„ас,..,,а„)— произвольный двоичный набор этих переменных. Коясшшлуеншай едгшицы побора а называется коиъюикт хчх'з...х,',".
Ковсшнгнуеггяюйпуля побори а 2 1 называется дизыонкт х," ахаю тг...ах„" . Очевидно, по х,'х,'-"...х'„" =1 ! и х;" а ха э ч,..ч.т„е' = 0 тогда италькотогда, когда х1 =а„ха =аз,..., хь =ая. Соаершгяпой коьыопкппмяон порлкмьпой форэюй (СКНФ) относительна переменных х,х„...,х„называетая конъюиктивная нармальнак форма, в кста- рой иет одинаковых элементарных дизыанкций и все элементарные дизьюнкции правильны и полны относительно переменных Х, х„...,д,.
Всякую функци~о ~(~,хз,...,х„), отличающуюся от топщественно истинной, можно представить в виде СК1!Ф следующим образом: ~(хнхз,...,х„)= П х(' охз' '....чх„', (192) у(ш г " )=с где симвшг П означает, что коньюнкции берутся по тем наборам перемен- ных, которые указаны под ним, Здесь ситуация та же, что н для ДНФ. Для я~абай формулы А существует несколько КНФ, среди ннх еать только одна, удовлетворяющая условиям совершенства. Эта КНФ называется совершен пй копьшвкшнеяон нормагыюй формой. Свойства совершенства дла КНФ: 1.
Все сомножители (дизъюнкции) различны. 2. Каждый сомиомагтель содерясит все переменные. йшш г, Алгебра лонжи )алшб а в шз иа) зг Ф Ни один изсамнпжитеяей несодергкьп х и х, одновременно 4. Ни один из сомножителей не содержиг двух одинаковых псременныь. СКНФ, так же «ак и СДИФ, маме~ быть полу ~сна двумя способами, гн таб лицо истинности для формулы А и путем эквивалентных преобразопаний. действительно, найдем связь между СДПФ и СКНФ. Прн этом надо помн~гть сдедующие факты.
полная правиаышя элементарная дизьювкция х" ох'го...ох,'," равна нушо лишь на наборе а,а„...,о„: аналогично г 1 -. подпав правильная элементарная коныоикция х, лх, л..ля„'" равна ° 1 единице на одном наборе а,,а „, „. Тогда если СДНФ,( =- х," л.тг' л...л.т,",", то СДНФ7= о х," лх,'з л...л:,',. г(~ г „)=с и СДНФ !' = о .э," л.т,г л..
л х,"," = г(~ г ъ)с ,„)-с г(, г „)о Таким образом, СКНФ !'= СДНФ ('. (! 9З) Алгоритм полу илия СКНФ пузом эквивахсгпных преобразовании похож на алгоритм получения СДНФ: !. Для формулы Л пол)маем ягору~о КНФ К Если элементарная дизыонкция В. входящая в КНФ, не саверию. х,. то В Во(х, лх,! м(В т,)л)Во.т,) К Рели а некоторую шемснгариую лизь|анкцию В х вхолгп дважды, то лншнкноперсменну~о х, можно отбросить,з. к.
х; о х. их,. 4 Если КНФ содераит два адннакопьш сомножителя В, ~о лишнюю элементарную пизъюнкци~о иожно отбросить, т к В л В = — В Если в элементарную лизьюнкцию В аколит пара х, о г л то ее можно отбросить, т к. х, '. х, = ), а В, л ! — = В, . Чэсц | Мэгэмэгичэсквя логиээ Совершеннме нормальные формы позволяют дать критерий равносильности двух произвольных формул А и В. В самом деле, каковы бы нн были формулы А и В, в том случае если они содержат одни и те же переменные, нх можно заменить равносильными им формулами, которые необходимо привести к совершенным дилъюиктивнмм или конъюнктивным норыаиьным формам.
Если А и  — равносильные формулы, то в силу единственности совершенных нормальных форм как конъюнктивнме, так н днзъюнкгивные нормвяьные формы этих формул должны полностью совпадать. Таким образом, сравнение совершенных нормгшьных форм формул А и В решает вопрос об ил равносильности. При упрощении ДНФ или КНФ удобно пользоваться следующими равносильностямн: ХЧ ХУн Х, Х(ХЧУ)н Х, хохум хо у, холуи хо у, х(х г у)м ху, х(хч у)м ху. 11.9.41 1.10. Закон двойственности Операция конъюнкции называется дэойсмееииод операции дизьюнкции и наоборот, операция пизъюнкции назьншется деодстэенлод операции конь.
юнкции. Среди элементарных функшгй алгебры логики О, 1, х, х, х,л х„ х ч х, О двойственна 1; 1 двойственна О; х двойственна х, х двойственна х; Д л хз двойственна Ц ч х; Д их двойственна х, л из. -- гт... )=~,*,,П функпии /(ц,х„...,х„). Функция, равносильная своей двойственной, т. е ., - Г(~,ч,:лЬГЦ..:;,1=79;;:-. 1,--- самодеодсюееллаф Очевидно, что самодвойсгвенна» функция нрннимаег на противоположных наборах а„а„...,а„ н а„э,...,а„ противоположные значения. удзвя Г.дятел вло ися ( лгеб вы и эи лшр 33 5Ф опРеделениа леойственности следУег, по /"' = (У )' = У, т. с. фуи Г ведается двойственной к 5 'гсеолстео еэакилосегнй грормулы алгебры логики А и А называются деонсмесяяылаь если А' до.
лучаегся из А путем замены квзкдой олсранин на двойственную ей операцию рассмотрим формулу А — хлуо(х-оу)ох= — хлуо(гоу)лх. деойст. ленная ей формула будет иметь вид А' в хзг ул ((хл у)о х)= «5(хуо х), Пусть теперь 5(х у)= хл угг (х-г у) ох. По опрелслению двойственной функции /'(х,у) = ~~~,Д= х л у о (х -г у)л х — = х л у л ~т ~ у))л т и п худ~ о у)~ хи «у л(хну згх)м «у~ум «).
Теауаиа дй Функция, двойствеииан суперпозиции некоторых фувкннй, равносильна соответствуюпзей суперпозпции двойственных функций, т. е. если 9(хох „,х„)= .Г(ф,(т» х,з,,..,х» ) грз(хз,,хз,,...,х„) ...,ф„,(хо, х„,з,...,х„,з ) р* (х, т,, ... х„) = 5 (ф,(х»,х, з,.,х,г ) фз(хзмхзз,...,х,е ), гу„,(х„, х,„„...,х„г ) ...) где чеуез Х,хг,...,х„обозначены все Различные символы пеРемев ных, встречающиеси в наборах (х|мхьз,...,хьг ) (хг«*хзг - -тзг,) (Х ЫХих,...,Х,„Я ), Докюомсльсмео По определению двойственной функции р'(«„хз,...,хе)= ~~(х„х„...,х„)= = (ф Г', -,,д).,Г,, -'„)-- „,Г;„.,-';„.)-)= и-~Г'..-":.;:,",з)-';',Г.—."„'.—."„') (.—",.—.",.—.",) )= мг 5»((х» х, з,...,х» ), Ю,(х,„хгз,...,.тзз ),,..,ф„,(ха, хез,,хе, ),...)= У бй~ (х~ их~ «,...,.«| г, ),ф (хз»хзз,«,хзг ),,фе(х„, и«, з,...,х,х ) ° ). Часть ! Математическая логика Эе В заключение приведем без доказательства еще две теоремы о двойственнык функциях.
?еорежа !.6. Если дла функции „('1х„ хз,...,х„) лвойственней нвляетс» (" ( . .., ., ! . ° ° ° ° %;5 , , 1т и у ( х (, х з, ..., х, ) . Эта формула доказывается методом м атемати чееко й и ндукции. На основании теореьгы 1.б легко доказывается слелующа». Теорсми !.7. Коли формулы Л и В равносильны, то равносильны н двойственные им формулы, т. е.
А и  — з Л' и В". 1.11. Практическое занятие рйв 2. Функции алгебры логики. Закон двойственности 1.11.1. Показать. что кюкдой формуле А алгебры высказываний можно сопоставить функцию Г(А) алгебры логики так, что если 1 = — А„то .г'(А)=г'1А ) !.112. Сколько имеется различных функций алгебры логики от л переменных? 1.11В. По таблице истинности, приведенной в табл. 1.11.1, найти формулы, определяющие функции „у((тч,хз,хз) згг((х~ Хз хз) Гзузлз хг хз)* ~,(~, х , х. ), и придать им более простой вид. Тяеямча ! (! ! у т дм- а логики ! кадра аискавиаална) Парти асс сущсствснныс переменные сясдующих функний: 1) (хо > ) и )у л х); 2) (х л у) l х ° 3) (х-«() -«з))-«((х -«.у) — «( — «з)) 11\ 5 Выразить с помощью супсрпозиций; Ил и — «чсрсзо и 2)л но через — «н 3) через — «и О. 4) о через — « .
1,11.6, Привссти к днзъюнктнвной и конъюнктивной норыальной форме П ((А — «В) — + (С вЂ” «А))-«( — «С). 2) ((((А -«В) — «А)-ь В) — «С) 3) (А -«( — «С)) — «((А -«С)-«(А-«В)). 1,1!В. По ланному набору значсннй псрсмснны» построить элвис|«гарную конъюнкцию, истинную для данного набора зна ~сннй псрсмснныч. 1.! 1.8. Д«зя слсдующик формул найти СДПФ, при этом для формул 1, 2, 3 и 5 использовать два способа. 1) ((А -+ В)-«((Вл С) — «(А л С))). 2) ((А-«В) — «А) — «(А-«(Ал В)), 3) (Ал В)-«Ал(АлВ) — «В; 4) 1 — «(А — «(...— «(А,, -«А„)..)); 5) (А -+ С) — «В -«А.
1 1!.9. Слсдующнс формулы привссти к совершенной коиъюиктнвной нормальной форме: 1) (С -+ А)-«(ВоС вЂ” «А); 2) (Ал В) — «А г (А, (Во С)); Масть 1. Магемаимесяая лагигл 3) А л (В г С)-+ (А л В)» С; 4) (А»В-+АлС)-ь А — гА»ВлС; 5) А, »Ас»...»А„-ьВ, л Вял... лВи. 1,11.10. Найти СДЫФ для всякой тождественно истинной формулы, аодержащей: 1) Одну переменную.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
