За един дизюнкт ще казваме, че е верен в дадена структура при дадена оценка на променливите, ако поне един литерал, принадлежащ на него, е верен в дадената структура при дадената оценка на променливите. Ясно е, че един дизюнкт е валиден в дадена структура точно тогава, когато той е верен в нея при всяка оценка на променливите. Ще казваме, че едно множество от дизюнкти Δ представя дадена формула φ, ако при произволен избор на структура S формулата φ е вярна в S точно при онези оценки на променливите, при които всички дизюнкти от Δ са верни в S. Тази дефиниция осигурява, че ако Δ представя φ, то φ е тъждествено вярна в една структура точно тогава, когато всички дизюнкти от Δ са валидни в тази структура.

    Лесно е да се види, че всяко непразно крайно множество от непразни дизюнкти представя някоя безкванторна формула. Преди всичко нека да отбележим, че конюнкцията и дизюнкцията на всяка непразна крайна редица от безкванторни формули е безкванторна формула (доказва се чрез индукция относно броя на членовете на редицата). Благодарение на това свойство (по-точно на частта му във връзка с дизюнкцията) за всеки непразен дизюнкт δ съществува такава безкванторна формула φ, че при произволен избор на структура S формулата φ е е вярна в S точно при онези оценки на променливите, при които дизюнктът δ е верен в S (за да получим такава формула, достатъчно е да подредим литералите от δ в редица и да образуваме дизюнкцията на тази редица). Да предположим сега, че е дадено едно непразно крайно множество Δ, чиито елементи са непразни дизюнкти. Като изберем за всеки от тях по една безкванторна формула, свързана с него по гореописания начин, подредим така избраните безкванторни формули в редица и образуваме нейната конюнкция, получаваме безкванторна формула, която се представя от множеството Δ. Да отбележим още очевидния факт, че ако сред елементите на едно множество от дизюнкти фигурира празният дизюнкт, то това множество представя точно онези формули, които са неизпълними, а ако самото множество е празно, то представя точно онези формули, които са тъждествено верни.

    Ще покажем, че е вярно и твърдение в обратната посока, а именно, че за всяка безкванторна формула съществува крайно множество от дизюнкти със същите променливи, което я представя. За целта най-напред ще въведем понятието за атомарна компонента на една безкванторна формула. С това наименование ще назоваваме онези атомарни формули, които са използвани при нейното построяване. По-точна дефиниция на понятието може да се даде по следния индуктивен начин:
      1. Единствената атомарна компонента на една атомарна формула е самата тя.
      2. Отрицанието на една формула има същите атомарни компоненти както нея.
      3. Ако χ е конюнкцията или дизюнкцията на две формули φ и ψ, то атомарни компоненти на χ са атомарните компоненти на φ и атомарните компоненти на ψ.

    С просто индуктивно разсъждение се показва, че множеството на атомарните компоненти на всяка безкванторна формула е крайно и непразно и че множеството на нейните променливи е обединение на множествата на променливите на нейните атомарни компоненти.

    Лема. Ако θ₁, …, θ_n са различни помежду си атомарни формули, а φ е безкванторна формула, чиито атомарни компоненти са измежду θ₁, …, θ_n, то съществува такава n-местна двоична функция f, че за всяка структура S и всяка оценка v в нея е в сила равенството

    Забележка 1. Дефиницията за атомарна компонента може по естествен начин да бъде разпространена за произволни формули, като се приеме, че при поставяне на квантор атомарните компоненти остават същите. Доказаната лема обаче престава да е в сила, ако в нея се пропусне думата „безкванторна“. Например, ако  p е едноместен предикатен символ и φ е формулата ∀X p(X), то не съществува такава едноместна двоична функция f, че за всяка структура S и всяка оценка v в нея да е в сила равенството φ^S,v = f(p(X)^S,v). В това се убеждаваме, като забележим, че при  p(X)^S,v = 1 стойността φ^S,v може да бъде както 1, така и 0.

    Като използваме горната лема, сега ще докажем формулираното по-горе твърдение за представиност на безкванторните формули чрез множества от дизюнкти. Нека φ е произволна безкванторна формула. Нека различните помежду си атомарни формули θ₁, …, θ_n са нейните атомарни компоненти, а f е n-местна двоична функция със свойството от доказаната по-горе лема. За всяка формула θ да се условим под ¬⁰θ и ¬¹θ да разбираме съответно θ и ¬θ. Непосредствена проверка показва, че когато t е някое от числата 0 и 1 формулата ¬^tθ е вярна в дадена структура S при дадена оценка v точно тогава, когато е в сила неравенството θ^S,v≠ t (проверката може да се извърши, като се разгледат поотделно случаите  t = 0  и  t = 1). На всяка n-орка (t₁,…,t_n) от нули и единици, за която  f(t₁,…,t_n) = 0,  да съпоставим дизюнкта {¬^t₁θ₁,…,¬^t_nθ_n}. Ясно е, че той има същите променливи както формулата φ. Нека Δ е множеството на всички така получени дизюнкти. Ще покажем, че то представя φ. Нека S е произволна структура, а v е произволна оценка в нея. За да бъде вярна формулата φ в S при оценката v, необходимо и достатъчно е n-орката (θ₁^S,v,…,θ_n^S,v) да бъде различна от всяка n-орка от нули и единици, за която функцията f се анулира, а това по отбелязаното преди малко условие за вярност на формули от вида ¬^tθ е равносилно с изискването във всеки от дизюнктите, принадлежащи на Δ, да има литерал, който е верен в S при оценката v, т.е. с изискването всеки дизюнкт от Δ да бъде верен в S при оценката v.

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

    Забележка 3. Твърдението, което доказахме, може да се разглежда като друг начин на изказване на едно известно твърдение за представимост на безкванторните формули в конюнктивен нормален вид.

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