В.Н. Нефедов, В.А. Осипова - Курс дискретной математики, страница 8

а(Л« /В)а(Л«т/В)а... а(Л«ЧВ); " (А,т/Лзт/... 1/Л.)а(В, / В,Ъ ... )/В,) (Л,ав,) Ч 'т/ (А а В ) /... 'ь/ (А~ а Вг) т/(А адг) т/ (Ат а В«) ь/... .)/ (Ага Вг) )/... т/(Льа Вг) т/(А«аВН ~/... т/ (Лза Вд, з также обобщенные законы де Моргана: -1 (Л а...аА«) в -)Аг(/... 'т/ )А»1")(А// т/А«)зз = л,а... а,ль Определим теперь некоторые канонические виды формул.

Формулу называют элелгенторной коныонкцией. сели оиа является конъюнкцией (быть может, одно«ленной) переменных е отрицаний переменных. Например, формулы Х» 1 Х» Хз а йПКь ХзаХ» Х а-)Х«аК«аК» ввлнются элемептарпыми конъюнкциями. Говорят, что формула находится в диэвюнктввной нормалы нав форме (ДНФ), если ова являетсн лизыоикцней (быть иолгсь одиочлеаной) элементарных конъюнкций. Напрггиса, фориуяы Х» 1Х» Х аХ«аХ. (ХгаХ а (Х«) т/(Х а )д*аХ ) паколнтся в ДНФ. Теорема 1.2 (о приведении к ДИФ).

Для любой формулы Л можно найти та ую формулу В, находящуюся е ДНФ, по А =- В. Формула В называется дизыонктиеной нарвал~пай формой фарлгуль а Доказательство теоремы расоааается иа трн этапа: /.й этап. Для формулы Л строим такую формулу Ль что Л вн Л~ и в Аг не содержится символов, ш (см. утверждение 12) 2-й этан. Докажем тепергь что для формулы А, важно найти формулу Аз такую, что А~ А» и в А«отриетвппс находится гальха перед всременнымн. Такая формула называется фариулои с «тесными» отрпцаивяии. Докажем это утверждение нику«цквд по числу а ламшесюш символов формулы Аь Гела и = О, то А, есть какая-то переменная Хь В качестве Л нужна взять Хь Пусть утверждение выполняется дзи всех формул А, с числом символов меньше и.

Пусть в формуле Аг содержится точно в логических символов. Рассмотрны следуюШие случаи: 1) Аг имеет вид В~ т/ Сь Тогда в Вь С, логических символов ченьше, чем и. Поэтому сушссгвуют формулы В» С такие, что 2 а*В„С, Сз и в В» С, отрицание встречается тольна летел псРемеиными. Ясно, чта В,(/ С, Равносильна Аг и ввлиетсн )ормулой с «тесными» отрицаниями; 2) А, имеет вид Вг а Сь Доказательство аналогично предыг гужему случаю: вг 3] А~ имеет внд ППВ» Тогда А,е В~ н в В.

лагнчесюсэ символов меньше, чем л. Поэюму к В, применено андуктевное предположение; 4) А, имеет внд -1 (В,<УС]. Тогда А, =-]В,А-]С, н э -]Вь ) С~ логнческпх символов меяьше, чем л. Поэтому существуют газне формулм Вь Сь что -]В~ В„-]С, Сз н в Вь Сз отрнцанпе встречается только перед персменнымк. Ясно. что А В»6Сз и ВзбСз является формулой с «тсснымн» отрнцанкямн; 6) А~ нмщт внд -) (В~ Ь С~). Тогда А, и -]В,)~ ]С» и палее пс«тулаем, как е лрцпыдущсм случае.

Прн практическом преобразования нстречвющпесэ е форму. ле отрк~ганна просто передвигают к переменным, нспсльзуя законы де Морган» н уничтожая пары стоящих раасн отрпцаннй, если таковые встречаются. Прнмер 1.6. Преобразуем к формуле с «теснынн» отряпаниямп: -1(-1-1 (Х,б-]Хз) Ч (Хзб-]Х)) -]-)-) (Хб-]Хг) б АП (Х,ЛП Х ) П(Х ВПХ ) б (-]Хз]Г П-,Х ) ка < ПХ, <1 'т/ -1-1 Хг) б ( -)Хзт) Х~) з ( ]Х~ т/ Хз) й ( -]Хз ]/Х ). 3-й этшс Получеяную формулу А, можно счнтать построенной кз переменных и нх отрнпаннй с помшцыо мпогочленных кснъюнкцпй п днзъюнкцнй.

Применяя теперь обобщенную днстрнбутпвность Ь относительно ]/, ~юследовзтельно преобразуем формулу (аналогнчно приведению алгебраического еыражсния, состааленмого нз переменных, с помощью сложений н умножений к валу многочлена). Заметны, что прз этом ь) булег аналогнчна сложению, а б — умножению. Полученная в результате преобразований формула В будет удовлетворять требованиям доказываемой теоремы. Пример 1.7.

Прнменнм преобразования 3-го шапа к форчуле с «теснымл» отрицаниями, полученной в примере 1.бь ( )Х ]гХз) й ( ~Ха~~ Х~) ("1 Х> й ]Ха) т1 [ ]Х ВХ ) тl (Хай Ь 1Хз) тг' (ХзЬХ~). В результате мы палучнлк формулу, нахо*' пюдуюсн и ДНФ. ГовоРят, что формула А находется е конъюньгиенол нормальной форме (КИФ), если формула А* определена (т. е. э А нот спмволов — н ю) н находятся е ДНФ. КНФ можно дать н другое равноспльнос опредслеппе. Фор-' муну называют элементарной дизнюлкцией, еслн она является лнзыонкцаей (зозможно, одночленной) переменных н отрлнаннб переменных.

Формула находнтсн в КНФ, если она валяется конъюнкцией (возможно. одночленной] элементарных днзьюнкцнй. Теорема 1.3 (о лриэеденпв к ](ВФ). для любол формулы зз ,А можно найти такую формулу В, что А находится а КПФ и А ьм В. Фора«/ла В называется конъюнктиэной нормальной формой .формулы Л. Первое доказательство. Пусть Я ии Л, н Я~ пе содержит символов, ть Пусть В, — диэъюнктивная нормальная форма для формулы А*ь Тогда В*, находится в КНФ н, кроме того, по принципу двойственности В ~ — (Ац)*им А~ ~ я. Значит, В', довлетворяет требованиям теоремы.

торос доказательство. Применив первые два этапа из доказательства теоремы 1.2 о ДНФ, получим формулу Аь равносильную Л, ие содержащую символов —, ~ н содержащую отрицания только перед переменными. Преобразуем теасрь Аз как алгебраическое выражеинс, счятая на этот раз а аналогом сложения, а т/ — аналогом умножения н применяя днстрнбутнвность т/ относительно а. Приведение формулы Аз к виду многочлспэ дает на этот раз КНФ. Пример 1.8. Приведем к КНФ формулу <х,ах,> - ('->к,ах,> Пх,ак,>а(-гх,ахз»'1/ [/ «-,Хга К> а-1<->Ха Х » = <Х,ЬХа->Х,а Х> 1/ '1/((-Хгт/.)Кз>а(-1->к~!/-> Хз)) = (Х ЬХзаПХ аХз)1/ ту(<-,к,)/->х,> а <х,Н->х)> = (к,)/-,х,(/-> х > а а (К 1/ХК <Кз) Ь (Хз>/ ~кгт,/ 1Хз) а (Хз(/Х1)/ <Х) а .а (-1 х ~/-> х ~/ ->х ) а ( >х~ ~/ х )/ ->х ) а (х )/ -! х ~/ -Ч -Гкз) а (Хз>/Х, Н ->Ха>.

Заметим, что первое преобразование основано на равносиль.ности 1б. Нетрудно видеть, что ДНФ не является однозяачно опреде.ленной. РассмотРим, напРимеР, фоРмУлУ Х,>/ (Хз а Хз). Она уже находится в ДНФ. В то же время преобразование Х, т/ '(/ (Х %Хз) — (Хг ~/Хз) а (К~ 1/Хз) иа (Х| ах~) )/ (Х~акз) (/ 1/(Хзак~) 1/(КзаХз) дает длн этой формулы другую ДНФ. Конечно, все ДПФ данной формулы равносильны. Выделим срслн ДНФ формулы так назмвасмую совершенную днэъюиктиввую нормальную форму. Пусть формула А зависит от списка переменных (Хй,..., Хг, >. Говорят, чго А находится в совершенной диэъюнктианой «арзшльной форме (СДНФ) относительно этого списка, если аыколняются след>чощие условияг 1) А находится в ДНФ; '2) каждый дизъюиктнвный член А является й-членной копьюнкцией, причем на 1-и месте (! ( ! ( й) втой конъюнкции обязательно стоит либо переменяая Хй, либо ее отрицание ~кггг 3) все дизъюнктнвяые члены Л попарно различны. Пример 1.9.

Пусть (Хь Хь Хз> — список переменных. росла формулы Х~Ь !Хаа">Хь (Х ЬХзаХз) 1/( ~К~ах Ь эв ЬХ) тт (Х ЬХтб-(Хз) находятся в СДНФ относительно э«ко сшш«а леремемомх. Теорема 1А. Пусть фарнука А зсеискг от сноска лере гккык (Хп,..., Хг„> и А нг тождественно-ложная формула. Тсадо сугцссткует текел форлуло В, что А В к В сжкадгмсл е СДНФ откоснтелько сноско переле нс» (Хч,, Х, >. Согласно теореме о прявелевнн к ДНФ существ)ег формула й, гахан, что А А, и А, находется в ДНФ.

Прп этом кожно считать, что А, зев«сит от санс«в переменных (Х.. Х,„> (в процессе пряведення формулы к ДНФ эовме пере. менныс не пояаляютсн). Булем исходить нз этой формулы к просматривать ее дпзъюнктавные члены, т. е. элечснтэрныс конъюнкцпо: 1. Пусть в элемс~ггарную «омъгон«цпю одноврсненно вхолят какая-побудь перепекна» ХО н ее отрвцапие. Вслп зто сдннствепиая элементарная «оньюккцк» формулы. то она на всек оценках прнянмаег эваченне Л, а следовательно, в вся форму. ла, что невозможно, та» «ак прелколагается, что формула нс тождественно-ложнан. Значит, пмекгся другие элементарные конъюнкц«к.

н формула (пс.:лс некоторых перестановок) будет «меть впх (Х, В-(ха д С) )у О, тле С вЂ” остальные члены нэгней элементарной конъюнкцнн( Π— остальные двзыонктввные члены всеб формулы. Но (Хь Ш Ь-(Хг,ЬС) тттОпа О, поскольку первый х~гзышгктпввый члег лозой части прп всех опенках прннпмает значение Л. Сзслова тельно, паша формула равнсснчьпа О, а рассматрпваемую эле ментарную ьонъюнкцпю можно шброс~гть. Поскольку А ие тохД дсствепно-лохшая, то после всех таких шагов всегда ссткнут какао-то нсотброшскные элементарные «онъпжкцнн. 2. Пусть в некоторой элементарной коныопкцнп перемеггнау Хь (влн -)Х,) встрсчаепж несколько рач.Тогда в свлу кдемпю тентнсстн (равноснльнсегн 2) можно оставить только одв вхожленпе Хн (плн )Хь ). 3. После провеленной обработкн каждая элементарная «онт~ гонапвя С будет содержать какую.нибудь переменную нс бсл(4 одного раза (включая ес вхожденне под зна«ом отряцвпгя.

прн этом воэможнм только следующие варианты: а) коныоннцпя С содержит в качестве своего «ояъюнктн ного члева один Раз Хп и Яе содеРжит нн РазУ -)Хгд б) конъюнкпна С содеРжкт одын Раз -)Хг, п не салеРжг~ нп разу Х,,; в) конъюнкция С не содержит пн Кг, нн -)Хгт г В последком случае мы заменяем С «а (СВИН) тl (С Ь -)Хг ) па основной равносильности 14 (первой формуле ра яа шеплення). Эту операцию следует проаоднть до тех пор, пока для каждой элементарной ноныонкцпи п каждой переменной Х, не будут еыполненм условна «а» плн «6». 4.

Переупорядочпм в каждой элементарной копъюнкцнп сс ьонъюнктнвныс члены таким образом, чтобм па 1-м месте в ней стояла Кп ялп -!Х, 5. Если е преобразованной формуле несколько раз повторястсэ одна и та же элечснтэрная конъюнкция, то, повьзуясь основной равноспльпсстью 5 [ндемпотентностью), выбрасываем есе се вхождгзшя, кроне одного.

Прнмэр ! 1О. Формула (Хза -!ХзаХз) т/ (Хза ~хзахз) »«l т) Х. заавсвт от сппска переменных <Хз, Хь Хз>. Прпвсдем .ес к СДНФ отпасптельно агота спесьз. Первую эленсзшарпую копъюнкцяю можно атброснть, во второй оставить только одно вкажденне Х . а затем провести преобразования по пп. 3, 4. 5з (Хза-)Хз)УХ» (Ха -(Х«ЬХ«)«У(ХЬ !Хза ) Хз) ~) Х) !х,ах)() (х а-(Х) (Х Ь-!х ах)()(х,а-!ха а -! Кз) ту(Л, а К а Хз) ~т) ( Хз а Хз а -!Хз) (/ (Хз а ) Хз а Кз) ~l ту (Кза ! Хза !Хз) пи (Хзахза !Хз) (/ (Хз а !Хза (хз) тl 'тт (Х дзХ«ЬХ»)') ( )Х ах»ах»)Ч ( !КзаХ«а )Хз). Как уже отмечалось, СДНФ обладает некоторой одяпзначносгью, а яненко справедлива следующая теорема.

Теерема 1.6 (а едиишввикогти С)(НФ). Если В, и Вз — совериюнные диэьюиктивкме кормальлые формы формулы А относительно списка лерсмеикык <Хзп..., Хг >, то В и В» логрт откачаться только порядком своик дивьюкятивиык «лекса. Докажем эту теорему несколько ~азднее (см, замечание 1.2, с. 49) Следует отметнть, что если расшпрнть список неременныт <Хч,..., Хз >, от которого зависят фарыула А, назыма псроцепными (реальна в А ме входяшнмн), то относительно нового опаска А будем иметь другую СДПФ.