За една формула F ще казваме, че се представя чрез дадено множество Γ от дизюнкти (или че Γ представя F), ако F е вярна точно в онези конфигурации, в които са верни всички дизюнкти от Γ.

      Пример 1. Нека A и B са две различни атомарни формули. Понеже

      Пример 2. Всяка тъждествено вярна формула се представя чрез празно множество от дизюнкти, а всяка неизпълнима формула  -  чрез множеството, имащо за единствен елемент празния дизюнкт.

      Забележка 1. Когато Γ е някое крайно множество от дизюнкти, можем за всеки от тези дизюнкти да си образуваме елементарна дизюнкция, на която той е множеството на членовете, а след това да образуваме конюнкция на тези елементарни дизюнкции. Ясно е, че ако Γ представя дадена формула F, то получената конюнкция ще бъде еквивалентна на F. Намирането на конюнкция от елементарни дизюнкции, която е еквивалентна на F, се нарича представяне на F в конюнктивна нормална форма.

      Ще докажем, че всяка безкванторна формула се представя чрез някое крайно множество от дизюнкти (следователно всяка безкванторна формула допуска представяне в конюнктивна нормална форма). Тъй като всяка безкванторна формула е еквивалентна на някоя безкванторна формула с ограничено ползване на отрицание, можем да се ограничим с разглеждането само на безкванторни формули с ограничено ползване на отрицание и да извършим доказателството, като посочим метод за преобразуване на всяка такава формула в крайно множество от дизюнкти, чрез което тя се представя. За описанието на метода е уместно да въведем някои спомагателни термини, към което сега пристъпваме.

      Ще наричаме квазидизюнкт всяко крайно множество от формули с ограничено ползване на отрицание (очевидно диюнктите са специален вид квазидизюнкти). Обобщаваме семантиката на дизюнктите, като приемаме, че един квазидизюнкт Δ е верен в дадена конфигурация точно тогава, когато в тази конфигурация е вярна поне една от формулите, принадлежащи на Δ. Разширяваме и дефиницията за представяне на формула чрез множество от дизюнкти, а именно приемаме, че една формула F се представя чрез дадено множество Γ от квазидизюнкти, ако F е вярна точно в онези конфигурации, в които са верни всички квазидизюнкти от Γ. За произволен квазидизюнкт Δ дефинираме какво ще разбираме под заменящо множество за Δ, като всяко заменящо множество за Δ ще бъде някое крайно множество Γ от квазидизюнкти и лесно ще може да се провери, че Δ е верен точно в онези конфигурации, в които е верен всеки квазидизюнкт от Γ. Дефиницията се състои от следните две точки.
        1. Ако Δ е дизюнкт, то единственото заменящо множество за Δ е множеството с единствен елемент Δ;
        2. Ако Δ е квазидизюнкт, който не е дизюнкт, то заменящи множества за Δ са:
          а) празното множество, ако формулата true принадлежи на Δ;
          б) едноелементното множество, имащо за единствен елемент  Δ\{fail},  ако формулата fail принадлежи на Δ;
          в) всяко множество от вида 

      От току-що дадената дефиниция се вижда, че всеки квазидизюнкт има поне едно заменящо множество, но може да се случи някой квазидизюнкт да има повече от едно заменящо множество.

      Пример 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 ) ∨ (B & ¬ A ) , където A и B са две различни атомарни формули (тя е еквивалентна на отрицанието на формулата от пример 1). При един от възможните варианти на протичане на процеса образуваме последователно четирите крайни множества, съставени съответно от квазидизюнктите на четирите реда по-долу:

      Забележка 2. "Прочистване" на резултата, подобно на това, което направихме в края на горния пример, е възможно и желателно винаги, когато се получат дизюнкти, съдържащи противоположни литерали (такива дизюнкти биха могли заедно с взаимно противоположните литерали да съдържат и още някои други). Могат да се премахнат и онези дизюнкти, които съдържат като подмножества други от получените дизюнкти, ако се случи да се появят такива дизюнкти.

      Остава да покажем, че непременно след някакъв брой стъпки ще се получи множество от дизюнкти, към каквато и безкванторна формула с ограничено ползване на отрицание да приложим метода и както и да използваме евентуалната свобода при избирането на заменящи множества. За тази цел на всяка безкванторна формула с ограничено ползване на отрицание ще съпоставим естествено число, което в рамките на настоящото доказателство ще наричаме нейна сложност. Това ще направим чрез уславянето, че литералите имат сложност 0, формулите true и fail имат сложност 1, а конюнкцията и дизюнкцията на две или повече формули с ограничено ползване на отрицание имат сложност, равна на сбора от сложностите на техните членове, увеличен с 1. Под сложност на един квазидизюнкт ще разбираме сбора от сложностите на формулите, които му принадлежат. За всяко крайно множество от квазидизюнкти Γ ще наричаме негова височина най-голямата измежду сложностите на тези квазидизюнкти, ако Γ не е празно, и числото 0, ако Γ е празно. Очевидно едно крайно множество от квазидизюнкти се състои само от дизюнкти точно тогава, когато височината му е равна на 0. При това положение е достатъчно да се убедим, че винаги, когато Γ е крайно множество от дизюнкти, което има ненулева височина, всички заменящи множества за Γ имат по-малка височина отколкото Γ.

      Нека Γ е крайно множество от дизюнкти, което има ненулева височина, и нека Γ′ е кое да е заменящо множество за Γ. Ще покажем, че височината на Γ′ е по-малка от височината на Γ. Това е очевидно така, когато височината на Γ′ е 0, затова да разгледаме случая, когато тя е различна от 0. Тогава Γ′ не е празно и можен да означим с Δ′ такъв измежду квазидизюнктите в Γ′, който е с максимална сложност (тя разбира се е различна от 0). Квазидизюнктът Δ′ принадлежи на заменящо множество за някой квазидизюнкт Δ от Γ, който не може да е дизюнкт. От обстоятелството, че Δ не е дизюнкт, лесно следва, че сложността на Δ′ е по-малка от сложността на Δ (например ако Δ′ има вида от последната подточка на точка 2 в дефиницията за заменящо множество, то сложността на Δ′ е по-малка от сложността на Δ, защото не надминава числото, получено от нея, като се извади сложността на дизюнкцията F и към разликата се прибави сборът от сложностите на членовете на F). От друга страна обаче сложността на Δ пък не надминава височината на Γ.

      Забележка 3. Чрез метода, който бе описан, всяка затворена безкванторна формула се преобразува в представящо я крайно множество от затворени дизюнкти. Това е така, защото заменящите множества за квазидизюнкт, състоящ се от затворени формули, имат за елементи пак такива квазидизюнкти.
 

Последно изменение: 16.06.2005 г.
 

Previous  Next  Contents