Пример 1. Нека α и β са две атомарни формули. Понеже

    Пример 2. Всяка тъждествено вярна формула (в частност формулата от горния пример при α=β) се представя чрез празно множество от дизюнкти, а всяка неизпълнима формула  –  чрез множеството, имащо за единствен елемент празния дизюнкт.

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

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

    За всяка безкванторна формула θ дефинираме безкванторна формула  −θ  (противоположна формула на θ) по следния начин: приемаме, че  −θ = ¬θ  за всяка атомарна формула θ, и полагаме

    Ще наричаме квазидизюнкт всяко крайно множество от безкванторни формули (очевидно дизюнктите са специален вид квазидизюнкти). Обобщаваме семантиката на дизюнктите, като приемаме, че един квазидизюнкт D е верен в дадена конфигурация точно тогава, когато в тази конфигурация е вярна поне една от формулите, принадлежащи на D. Разширяваме и дефиницията за представяне на формула чрез множество от дизюнкти, а именно приемаме, че една формула θ се представя чрез дадено множество Γ от квазидизюнкти, ако θ е вярна точно в онези конфигурации, в които са верни всички квазидизюнкти от Γ. За произволен квазидизюнкт D дефинираме какво ще разбираме под заменящо множество за D, като всяко заменящо множество за D ще бъде някое крайно множество Γ от квазидизюнкти и лесно ще може да се провери, че D е верен точно в онези конфигурации, в които е верен всеки квазидизюнкт от Γ. Дефиницията се състои от следните три точки.
      1. Ако D е дизюнкт, то единственото непразно заменящо множество за D е множеството с единствен елемент D.
      2. Ако D е квазидизюнкт, който не е дизюнкт, то едно непразно крайно множество D′ е заменящо множество за D точно тогава, когато имаме някой от случаите
        (a) за някоя неатомарна формула φ формулата  ¬φ  принадлежи на D, а D′ е множеството с единствен елемент  (D \ {¬φ}) ∪{−φ};
        (b) за някои формули φ и ψ формулата  φ & ψ  принадлежи на D, а D′ е множеството с елементи  (D \ { φ & ψ }) ∪ {φ}  и  (D \ { φ & ψ }) ∪ {ψ};
        (c) за някои формули φ и ψ формулата  φ ∨ ψ  принадлежи на D, а D′ е множеството с единствен елемент  (D \ { φ ∨ ψ }) ∪ {φ,ψ}.
      3. Празното множество е заменящо за квазидизюнкта D точно тогава, когато съществува формула от D, отрицанието на която също принадлежи на  D.

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

      Пример 3. Ако α, β, γ и δ са четири литерала, то квазидизюнктът  {α & β, γ ∨ δ}  има две различни заменящи множества  –  едното е  { {α, γ ∨ δ}}, {β, γ ∨ δ} },  а другото е  { {α & β, γ, δ} }.

      След като дефинирахме какво е заменящо множество за даден квазидизюнкт, дефинираме такова понятие и за произволно крайно множество от квазидизюнкти, а именно под заменящо множество за едно такова множество Γ ще разбираме множество, получено по следния начин: избираме по едно заменящо множество за всеки квазидизюнкт от Γ и образуваме обединението на така избраните заменящи множества (очевидно то е пак едно крайно множество от квазидизюнкти).

      Пример 4. При условията на пример 3 множеството  { {α, γ, δ}}, {β, γ, δ} },  е заменящо множество за всяко от двете посочени там заменящи множества за квазидизюнкта  {α & β, γ ∨ δ}.

      От казаното преди малко във връзка с понятието заменящо множество за квазидизюнкт е ясно, че и за всяко крайно множество от квазидизюнкти съществува поне едно заменящо множество, но може да се случи заменящото множество да не е единствено. Лесно е да се убедим също в това, че винаги, когато Γ′ е заменящо множество за дадено крайно множество от дизюнкти Γ, конфигурациите, в които са верни всички квазидизюнкти от Γ, и конфигурациите, в които са верни всички квазидизюнкти от Γ′, са едни и същи.

      Сега сме готови да опишем един метод, с помощта на който за всяка безкванторна формула можем да намерим крайно множество от дизюнкти, което я представя. Методът се състои в последователно образуване на някои крайни множества от квазидизюнкти и е следният: ако дадената формула е θ, то образуваме най-напред едноелементното множество, имащо за свой елемент едноелементния квазидизюнкт  {θ},  след това образуваме заменящо множество на това множество, след това заменящо множество на заменящото множество и т.н. дотогава, докато се получи множество от дизюнкти. От казаното дотук се вижда, че след извършване на какъв да е брой такива стъпки винаги ще получаваме крайно множество от квазидизюнкти, представящо формулата θ. Следователно, ако след някакъв брой стъпки се получи множество от дизюнкти, то със сигурност ще представя θ.

      Пример 5. Ще приложим гореописания метод към формулата  ¬(α ↔ β),  където α и β са две различни атомарни формули. При един от възможните варианти на протичане на процеса образуваме последователно деветте крайни множества, съставени съответно от квазидизюнктите на деветте реда по-долу:

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

      Нека Γ е крайно множество от дизюнкти, което има ненулева височина, и нека Γ′ е кое да е заменящо множество за Γ. Ще покажем, че височината на Γ′ е по-малка от височината на Γ. Това е очевидно така, когато височината на Γ′ е 0, затова да разгледаме случая, когато тя е различна от 0. Тогава Γ′ не е празно и можен да означим с D′ такъв измежду квазидизюнктите в Γ′, който е с максимална сложност (тя разбира се е различна от 0). квазидизюнктът D′ принадлежи на заменящо множество за някой квазидизюнкт D от Γ, който не може да е дизюнкт (в противен случай бихме имали равенството D′=D, което е невъзможно поради ненулевата сложност на D′). От обстоятелството, че D не е дизюнкт, лесно следва, че сложността на D′ е по-малка от сложността на D (например в случая (c) от точка 2 на дефиницията за заменящо множество сложността на D′ е по-малка от сложността на D, защото не надминава числото, получено от нея, като се извади сложността на дизюнкцията  φ ∨ ψ  и към разликата се прибави сборът от сложностите на φ и на ψ; по подобен начин се разглеждат и останалите възможни случаи, като във връзка с предвидената в точка (a) възможност за замяна на отрицание с противоположна формула е добре предварително да се провери, че противоположната формула на коя да е неатомарна безкванторна формула има по-малка сложност от отрицанието на тази формула). От друга страна обаче сложността на D пък не надминава височината на Γ.

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

      Забележка 3. Да наречем достатъчно подмножество на едно крайно множество Δ от квазидизюнкти кое да е подмножество Δ° на Δ със свойството, че всеки квазидизюнкт от Δ има подмножество, принадлежащо на Δ° (лесно се доказва, че едно подмножество Δ° на множеството Δ е негово достатъчно подмножество точно тогава. когато сред елементите на Δ° са всички минимални дизюнкти от Δ, т.е. онези, които нямат същински подмножества, принадлежащи на Δ). Обобщени заменящи множества за едно крайно множество Γ от квазидизюнкти ще наричаме достатъчните подмножества на заменящите множество за Γ. Очевидно всяко заменящо множество за Γ е и обобщено заменящо множество за Γ. Описаният по-горе метод може да се прилага и чрез използване на обобщени заменящи множества вместо заменящи множества. Например за формулата  (α→β) & ¬(γ→((γ∨φ)→α)),  където α е атомарна формула, β и γ са литерали, а φ е каква да е безкванторна формула, прилагането на така модифицирания метод би могло да протече чрез последователно образуване на осемте крайни множества, съставени съответно от квазидизюнктите на осемте реда по-долу: