ПРЕДСТАВЯНЕ НА БЕЗКВАНТОРНИ ФОРМУЛИ В КОНЮНКТИВНА НОРМАЛНА ФОРМА
За една безкванторна формула казваме, че е в конюнктивна нормална форма, ако тя е конюнкция на някакъв брой елементарни дизюнкции (допуска се този брой да е 0 или 1). Да припомним, че под празна конюнкция и празна дизюнкция разбираме съответно логическите символи true и false, под конюнкция и дизюнкция с единствен член дадена формула разбираме тази формула, а елементарни дизюнкции са дизюнкциите, на които всеки член е литерал, т.е. атомарна формула или отрицание на атомарна формула.
Теорема. Всяка безкванторна формула е еквивалентна на някоя безкванторна формула, която е в конюнктивна нормална форма.
Доказателство. За всяка безкванторна формула дефинираме положително цяло число, което в рамките на това доказателство ще наричаме нейна сложност. Дефиницията е индуктивна: приемаме, че атомарните формули и логическите символи true и false имат сложност 1, че отрицанието на една безкванторна формула има два пъти по-голяма сложност от нея и че конюнкцията и дизюнкцията на какъв да е брой формули, по-голям от 1, имат сложност, равна на сбора от техните сложности, увеличен с 1. За всяка безкванторна формула G, която не е атомарна, ще дефинираме друга безкванторна формула -G, която ще наричаме преработено отрицание на G. Дефиницията е следната: преработени отрицания на формулите true, false, ШF, F1 & ... & Fn F1 Ъ ... Ъ Fn, където n е по-голямо от 1 и F, F1, ..., Fn са безкванторни формули, наричаме съответно формулите false, true, F, ШF1 Ъ ... Ъ ШFn и ШF1 & ... & ШFn. Преработеното отрицание на всяка неатомарна безкванторна формула е еквивалентно на нейното отрицание, но лесно се проверява, че има по-малка сложност от него.
За всяка безкванторна формула някои крайни множества от безкванторни формули ще наречем заменящи за нея. За коя да е елементарна дизюнкция приемаме, че единственото заменящо множество за нея е едноелементното множество, състоящо се само от нея. Да разгледаме сега произволна безкванторна формула, която не е елементарна дизюнкция. Тя може да се представи във вида F1 Ъ ... Ъ Fn, където n е различно от 0, F1, ..., Fn са безкванторни формули и F1 не е дизюнкция с различен от 1 брой членове в случай, че n=1. Нека Fi е такава измежду формулите F1, ..., Fn, която не е литерал (такава сигурно има). В зависимост от вида на Fi приемаме, че разглежданата безкванторна формула има следното заменящо множество:
1. Празното множество, ако Fi=true.
2. Множеството с единствен елемент F1 Ъ ... Ъ Fi-1 Ъ Fi+1 Ъ ... Ъ Fn, ако Fi=false (в този случай n сигурно е по-голямо от 1).
3. Множеството с единствен елемент F1 Ъ ... Ъ Fi-1 Ъ -G Ъ Fi+1 Ъ ... Ъ Fn, ако Fi=ШG за някоя формула G (тя разбира се не може да бъде атомарна и следователно има смисъл -G).
4. Множеството, състоящо се от формулите F1 Ъ ... Ъ Fi-1 Ъ Gj Ъ Fi+1 Ъ ... Ъ Fn, j=1,...,k, ако Fi=G1 & ... & Gk за някое k, по-голямо от 1, и някои формули G1, ..., Gk.
5. Множеството с единствен елемент F1 Ъ ... Ъ Fi-1 Ъ G1 Ъ ... Ъ Gk Ъ Fi+1 Ъ ... Ъ Fn, ако Fi=G1 Ъ ... Ъ Gk за някое k, по-голямо от 1, и някои формули G1, ..., Gk (и в този случай n сигурно е по-голямо от 1).
Ясно е, че всяка безкванторна формула има поне едно заменящо множество. Не е трудно да се види, че за всяко заменящо множество за една безкванторна формула F конюнкцията на неговите елементи е еквивалентна на F, т.е. формулите от заменящото множество са едновременно верни в дадена структура при дадена оценка на променливите точно тогава, когато в тази структура при същата оценка на променливите е вярна формулата F. Ако една безкванторна формула F не е елементарна дизюнкция, лесно се проверява още, че всяка формула, принадлежаща на заменящо множество за F, има по-малка сложност от F.
Когато е дадено едно крайно множество M от безкванторни формули, заменящо множество за M ще наричаме всяко множество, получено по следния начин: за всяка формула от M си построяваме някое нейно заменящо множество и образуваме обединението на така построените множества (разбира се това обединение винаги ще е крайно). От казаното преди малко следва, че всяко крайно множество от безкванторни формули притежава заменящо множество и винаги, когато M' е заменящо множество за дадено крайно множество от безкванторни формули M, конюнкцията на формулите от M' е еквивалентна на конюнкцията на формулите от M.
Сега вече сме близо до края на доказателството. Да предположим, че е дадена произволна безкванторна формула F. Да означим с
M1 едно заменящо множество за F, с M2 - едно заменящо множество за M1, с M3 - едно заменящо множество за M2 и т.н. За всяко от тези множества конюнкцията на неговите елементи е еквивалентна на F. Ще покажем, че някое от въпросните множества не съдържа формули, които не са елементарни дизюнкции. И наистина, ако формулата F има сложност c, то лесно се проверява индуктивно, че всяка формула от множеството Mi има сложност, ненадминаваща c-i, или е елементарна дизюнкция (използваме твърдението за сложностите на формулите от заменящо множество за формула, която не е елементарна дизюнкция). Оттук, понеже сложностите са положителни, следва, че поне когато i е равно на c или е по-голямо, съответното Mi не може да съдържа формули, които не са елементарни дизюнкции. Ако си образуваме конюнкцията на формулите от някое такова Mi, тя ще бъде еквивалентна на F формула в конюнктивна нормална форма. ї
Току-що изложеното доказателство дава и метод, с помощта на който за всяка безкванторна формула да може наистина да се намира еквивалентна на нея формула в конюнктивна нормална форма. Например нека F има вида (A®B)®(C®D), където A, B, C и D са атомарни формули. По дефиницията за импликация това дава, че F е дизюнкцията
Ш(ШA Ъ B) Ъ (ШC Ъ D).
Никой от двата члена на тази дизюнкция не е литерал и поради това имаме две възможности да построим заменящо множество за F. Ако се възползваме от това, че първият член на дизюнкцията не е литерал, получаваме заменящото множество
M1 = {(ШШA & ШB) Ъ (ШC Ъ D)}.
Единствената формула от M1 отново е двучленна дизюнкция, на която никой от членовете не е литерал. За разнообразие да използваме сега, че вторият от тях не е литерал. Това дава следното заменящо множество за тази формула и значи и за M1:
M2 = {(ШШA & ШB) Ъ ШC Ъ D}.
Понеже единствената формула от M2 е тричленна дизюнкция, на която само един от членовете не е литерал, тя има само едно заменящо множество и то ще е заменящо множество и за M2. Така получаваме
M3 = {ШШA Ъ ШC Ъ D, ШB Ъ ШC Ъ D}.
От двете формули в M3 втората е елементарна дизюнкция, но първата не е. Получаваме
M4 = {A Ъ ШC Ъ D, ШB Ъ ШC Ъ D}.
И двете формули от M4 са елементарни дизюнкции. Тяхната конюнкция
(A Ъ ШC Ъ D) & (ШB Ъ ШC Ъ D)
е еквивалентна на F формула в конюнктивна нормална форма.
Често пъти е подходящо произтичащият от доказателството метод да се прилага с някои изменения, които не нарушават основното - а) замяната на безкванторните формули, които не са елементарни дизюнкции, с безкванторни формули с по-малка сложност и б) еквивалентността между дадената формула F и конюнкциите на формулите от множествата Mi. Да речем нека в горния пример атомарните формули A и D да съвпадат. Тогава формулата A Ъ ШC Ъ D е еквивалентна на формулата ШC Ъ D, имаща по-малка сложност, а пък формулата ШB Ъ ШC Ъ D е вярна винаги, когато е вярна ШC Ъ D, тъй че бихме могли да вземем
M4 = {ШC Ъ D}.
Значи в този случай ШC Ъ D ще е еквивалентна на F формула в конюнктивна нормална форма. В случай пък че съвпадат формулите A и C, формулата A Ъ ШC Ъ D ще бъде тъждествено вярна и бихме могли да вземем
M4 = {ШB Ъ ШC Ъ D},
тъй че в този случай ШB Ъ ШC Ъ D би била еквивалентна на F формула в конюнктивна нормална форма.
Последно изменение: 26.05.2003 г.