|
|
Пример 1. Нека A и B са две различни атомарни формули. Понеже
Пример 2. Всяка тъждествено вярна формула се представя чрез празно множество от дизюнкти, а всяка неизпълнима формула - чрез множеството, имащо за единствен елемент празния дизюнкт.
Забележка 1. Когато Γ е някое крайно множество от дизюнкти, можем за всеки от тези дизюнкти да си образуваме елементарна дизюнкция, на която той е множеството на членовете, а след това да образуваме конюнкция на тези елементарни дизюнкции. Ясно е, че ако Γ представя дадена формула F, то получената конюнкция ще бъде еквивалентна на F. Намирането на конюнкция от елементарни дизюнкции, която е еквивалентна на F, се нарича представяне на F в конюнктивна нормална форма.
Ще докажем, че всяка безкванторна формула се представя чрез някое крайно множество от дизюнкти (следователно всяка безкванторна формула допуска представяне в конюнктивна нормална форма). Доказателството ще извършим, като посочим метод за преобразуване на всяка такава формула в крайно множество от дизюнкти, чрез което тя се представя. За описанието на метода е уместно да въведем някои спомагателни термини, към което сега пристъпваме.
За всяка безкванторна формула F дефинираме безкванторна формула −F (противоположна формула на F) по следния начин: приемаме, че −F = ¬F за всяка атомарна формула F, както и че −true = fail, −fail = true, за всяка безкванторна формула F0 полагаме −(¬F0) = F0 и за всеки n безкванторни формули F1, …, Fn , където n>1, полагаме
Ще наричаме псевдодизюнкт всяко крайно множество от безкванторни формули (очевидно диюнктите са специален вид псевдодизюнкти). Обобщаваме семантиката на дизюнктите, като приемаме, че един псевдодизюнкт D е верен в дадена конфигурация точно тогава, когато в тази конфигурация е вярна поне една от формулите, принадлежащи на D. Разширяваме и дефиницията за представяне на формула
чрез множество от дизюнкти, а именно приемаме, че една формула F се представя чрез дадено множество Γ от псевдодизюнкти, ако F е вярна точно в онези конфигурации, в които са верни всички псевдодизюнкти от Γ. За произволен псевдодизюнкт D дефинираме какво ще разбираме под заменящо множество за D, като всяко заменящо множество за D ще бъде някое крайно множество Γ от псевдодизюнкти и лесно ще може да се провери, че D е верен точно в онези конфигурации, в които е верен всеки псевдодизюнкт от Γ. Дефиницията се състои от следните две точки.
1. Ако D е дизюнкт, то единственото заменящо множество за D е множеството с единствен елемент D;
2. Ако D е псевдодизюнкт, който не е дизюнкт, то заменящи множества за D са:
а) празното множество, ако формулата true принадлежи на D;
б) едноелементното множество, имащо за единствен елемент D\{fail}, ако формулата fail принадлежи на D;
в) всяко множество от вида
От току-що дадената дефиниция се вижда, че всеки псевдодизюнкт има поне едно заменящо множество, но може да се случи някой псевдодизюнкт да има повече от едно заменящо множество.
Пример 3. Ако A, B, C и D са четири литерала, то псевдодизюнктът {A & B, C ∨ D} има две различни заменящи множества - едното е { {A, C ∨ D}}, {B, C ∨ D} }, а другото е { {A & B, C, D} }.
След като дефинирахме какво е заменящо множество за даден псевдодизюнкт, дефинираме такова понятие и за произволно крайно множество от псевдодизюнкти, а именно под заменящо множество за едно такова множество Γ ще разбираме множество, получено по следния начин: избираме по едно заменящо множество за всеки псевдодизюнкт от Γ и образуваме обединението на така избраните заменящи множества (очевидно то е пак едно крайно множество от псевдодизюнкти).
Пример 4. При условията на пример 3 множеството { {A, C, D}}, {B, C, D} }, е заменящо множество за всяко от двете посочени там заменящи множества за псевдодизюнкта {A & B, C ∨ D}.
От казаното преди малко във връзка с понятието заменящо множество за псевдодизюнкт е ясно, че и за всяко крайно множество от псевдодизюнкти съществува поне едно заменящо множество, но може да се случи заменящото множество да не е единствено. Лесно е да се убедим също в това, че винаги, когато Γ′ е заменящо множество за дадено крайно множество от дизюнкти Γ, конфигурациите, в които са верни всички псевдодизюнкти от Γ, и конфигурациите, в които са верни всички псевдодизюнкти от Γ′, са едни и същи.
Сега сме готови да опишем един метод, с помощта на който за всяка безкванторна формула можем да намерим крайно множество от дизюнкти, което я представя. Методът се състои в последователно образуване на някои крайни множества от псевдодизюнкти и е следният: ако дадената формула е F, то образуваме най-напред едноелементното множество, имащо за свой елемент едноелементния псевдодизюнкт {F}, след това образуваме заменящо множество на това множество, след това заменящо множество на заменящото множество и т.н. дотогава, докато се получи множество от дизюнкти. От казаното дотук се вижда, че след извършване на какъв да е брой такива стъпки винаги ще получаваме крайно множество от псевдодизюнкти, представящо формулата F. Следователно, ако след някакъв брой стъпки се получи множество от дизюнкти, то със сигурност ще представя F.
Пример 5. Ще приложим гореописания метод към формулата ¬(A ↔ B), където A и B са две различни атомарни формули. При един от възможните варианти на протичане на процеса образуваме последователно деветте крайни множества, съставени съответно от псевдодизюнктите на деветте реда по-долу:
Забележка 2. "Прочистване" на резултата, подобно на това, което направихме в края на горния пример, е възможно и желателно винаги, когато се получат дизюнкти, съдържащи противоположни литерали (такива дизюнкти биха могли заедно с взаимно противоположните литерали да съдържат и още някои други). Могат да се премахнат и онези дизюнкти, които съдържат като подмножества други от получените дизюнкти, ако се случи да се появят такива дизюнкти. Всъщност такива "прочиствания" биха могли да се правят и в междинните резултати и така да се намалява обемът на работата. В пример 5 при получаването на трите псевдодизюнкта, които са на седмия ред, веднага би могъл да се премахне псевдодизюнктът { ¬ B , ¬ ¬ B } и това би ни избавило от появата на дизюнкта { ¬ B , B } на следващия ред. Също така бихме могли да премахнем дизюнкта { A , ¬ A } оше при появата му на осмия ред.
Остава да покажем, че непременно след някакъв брой стъпки ще се получи множество от дизюнкти, към каквато и безкванторна формула да приложим метода и както и да използваме евентуалната свобода при избирането на заменящи множества. За тази цел на всяка безкванторна формула ще съпоставим естествено число, което в рамките на настоящото доказателство ще наричаме нейна сложност. Това ще направим чрез уславянето, че атомарните формули и формулите true и fail имат сложност 1, конюнкцията и дизюнкцията на две или повече безкванторни формули имат сложност, равна на сбора от сложностите на техните членове, увеличен с 1, а отрицанието на коя да е безкванторна формула има два пъти по-голяма сложност от самата формула. Под сложност на един псевдодизюнкт ще разбираме сбора от сложностите на формулите, които му принадлежат и не са литерали (ако няма такива формули, т.е. ако даденият псевдодизюнкт всъщност е дизюнкт, ще смятаме, че въпросният сбор е 0). За всяко крайно множество от псевдодизюнкти Γ ще наричаме негова височина най-голямата измежду сложностите на тези псевдодизюнкти, ако Γ не е празно, и числото 0, ако Γ е празно. Очевидно едно крайно множество от псевдодизюнкти се състои само от дизюнкти точно тогава, когато височината му е равна на 0. При това положение е достатъчно да се убедим, че винаги, когато Γ е крайно множество от дизюнкти, което има ненулева височина, всички заменящи множества за Γ имат по-малка височина отколкото Γ.
Нека Γ е крайно множество от дизюнкти, което има ненулева височина, и нека Γ′ е кое да е заменящо множество за Γ. Ще покажем, че височината на Γ′ е по-малка от височината на Γ. Това е очевидно така, когато височината на Γ′ е 0, затова да разгледаме случая, когато тя е различна от 0. Тогава Γ′ не е празно и можен да означим с D′ такъв измежду псевдодизюнктите в Γ′, който е с максимална сложност (тя разбира се е различна от 0). Псевдодизюнктът D′ принадлежи на заменящо множество за някой псевдодизюнкт D от Γ, който не може да е дизюнкт. От обстоятелството, че D не е дизюнкт, лесно следва, че сложността на D′ е по-малка от сложността на D (например ако заменящото множество за D, на което принадлежи D′, е получено по предпоследната подточка на точка 2 от дефиницията за заменящо множество, то сложността на D′ е по-малка от сложността на D, защото не надминава числото, получено от нея, като се извади сложността на дизюнкцията F и към разликата се прибави сборът от сложностите на членовете на F; по подобен начин се разглеждат и останалите възможни случаи, като във връзка с последната подточка на точка 2 от дефиницията за заменящо множество е добре предварително да се провери, че противоположната формула на коя да е неатомарна безкванторна формула има по-малка сложност от отрицанието на тази формула). От друга страна обаче сложността на D пък не надминава височината на Γ.
Забележка 3. Чрез метода, който бе описан, всяка затворена безкванторна формула се преобразува в представящо я крайно множество от затворени дизюнкти. Това е така, защото заменящите множества за псевдодизюнкт, състоящ се от затворени формули, имат за елементи пак такива псевдодизюнкти.
Последно изменение: 16.06.2005 г.
|
|