Атомарните формули и техните отрицания ще наричаме с общото име литерали. Индуктивно дефинираме клас от безкванторни формули, за които ще казваме, че са с ограничено използване на отрицание. Дефиницията се състои от следните две точки:
      1. Всеки литерал е безкванторна формула с ограничено използване на отрицание.
      2. Ако φ и ψ са безкванторни формули с ограничено използване на отрицание, то (φ&ψ) и (φ∨ψ) също са безкванторни формули с ограничено използване на отрицание.

    За една формула ще казваме, че е елементарна дизюнкция, ако тя е дизюнкция на някоя непразна крайна редица от литерали (аналогично се дефинира и понятието елементарна конюнкция, но то няма да ни потрябва в по-нататъшното изложение). Лесно е да се види, че дизюнкцията на две елементарни дизюнкции е винаги еквивалентна на някоя елементарна дизюнкция. И наистина, лесно се вижда, че при произволен избор на положителни цели числа m и n и на формули φ₁, …, φ_m, ψ₁, …, ψ_n е в сила еквивалентността

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

    Теорема. Всяка безкванторна формула е еквивалентна на някоя формула в конюнктивен нормален вид.

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

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

    Забележка. Проверката на еквивалентността (1) можем да извършим например по следния начин. Нека са дадени произволна структура S и оценка v в нея. Очевидно е, че ако лявата страна на (1) е вярна в S при оценката v, то и дясната е вярна. Да предположим сега, че дясната страна на (1) е вярна в S при оценката v. Тогава за всяко i от множеството {1,…,m} и всяко j от множеството {1,…,n} можем да намерим формула χ_ij, вярна в S при оценката v и съвпадаща с някоя от формулите φ_i и ψ_j. Ако има такова j от второто множество, че χ_ij = φ_i за всяко i от първото, то в S при оценката v ще бъде верен първият член на дизюнкцията от лявата страна на (1), а в противен случай за всяко j от второто множество ще има такова i от първото, че да е в сила равенството χ_ij = ψ_j, и следователно в S при оценката v ще бъде верен вторият член на споменатата дизюнкция.

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