По индукции можно строго доказать, что

H(S) = H_¥ = {а, f(a), f(f(a)), f(f(f(а))),...}.

Из способа построения следует, что мощность H(S) всегда либо конечна либо счётна. Таким образом, его эле-менты всегда можно упорядочить и рассмотреть все по оче-реди. В случае счетной мощности число просмотров будет бесконечным.

Определение. Эрбрановским базисом А множества дизъюнктов S называется множество всех атомов вида P(t₁,...,t_n), где P - предикаты, входящие в S, (t₁ ,...,t_n) – набо-ры термов из эрбрановского универсума H(S).

Смысл эрбрановского базиса в том, что он содержит все возможные подстановки термов из H(S) в предикаты из дизъюнктов S.

Пример 3. Построить эрбрановский базис множества дизъюнктов S = {P(a),ØP(x)}.

Решение. В Примере 1 показано, что H(S) = {а}. Так как в S содержится только один предикат P, то А = {Р(а)}.

Пример 4. Построить эрбрановский базис множества дизъюнктов S = {P(a), P(x) Ú Q(f(x))}.

Решение. В Примере 2 найдено: H(S) = {а, f(a), f(f(a)), f(f(f(а))),...}. В S содержатся предикаты P и Q. Подставляя в них последовательно все термы из H(S), получим следую-щий счетный эрбрановский базис:

А = {P(а), P(f(a)), Q(f (a)), P(f (f (a))), Q(f (f (a))), P(f(f(f(а)))), Q(f (f (f (а)))),...}.

Определение. Рассмотрим дизъюнкт D_iÎS (1£ i£ k). Ос-новным примером дизъюнкта D_i ÎS называется дизъюнкт, полученный из D_i подстановкой в него вместо предметных переменных термов из эрбрановского универсума H(S).

Каждый основной пример дизъюнкта D_i не содержит переменных и является как бы одним из возможных значений D_i при подстановке в него конкретных величин литер, входящих в него. Так как матрица, соответствующая S, является произведением дизъюнктов D_i, то, если ос-новной пример какого-либо дизъюнкта ложен на интерпре-тации I, то ложна и вся матрица. В этом случае интерпре-тация I будет опровергать исходную формулу, порожда-ющую S.

Пример 5. Найти основные примерыдизъюнкта D₂ из множества S = {P(a),ØP(x)}.

Решение. В Примере 1 показано, что H(S) = {а}. Следова-тельно, основной пример один - Ø Р(а).

Пример 6. Найти основные примерыдизъюнкта D₂ из множества S = {P(a), P(x) Ú Q(f(x))}.

Решение. В Примере 2 найдено: H(S) = {а, f(a), f(f(a)), f(f(f(а))),... }. Следовательно, основные примеры будут сле-дующими:

1) P(a) Ú Q(f(a)); 2)P(f(a)) Ú Q(f(f(a))); 3)P(f(f(a)))) Ú Q(f(f(f(a)))); 4)P(f(f(f(a))))) Ú Q(f(f(f(f(a))))) и т.д.

Допустим, доказывается невыполнимость некоторой формулы В в логике предикатов, имеющей сигнатуру {X,A, F,P} (X,A,F,P- множества предметных переменных, конс-тант, функциональных и предикатных переменных в В), и задача уже сведена к определению невыполнимости мно-жества дизъюнктов S, по которомупостроен эрбрановский универсум H(S).

Определение. Эрбрановской интерпретацией (Н – ин-терпретацией) множества дизъюнктов S, построенного по формуле В с сигнатурой {X,A,F,P}, называется любая интер-претация I над H(S) вида I = { H(S), A¢, F¢, P¢}, в которой:

1) A¢ = A, т.е I отображает константы в самих себя,

2) F¢ = F, функции из F ¢ действуют на H(S) так же, как и функции F,

3) предикаты P¢ могут быть равными (по истинности) пре-дикатам из эрбрановского базиса, либо обратными к ним.

В дизъюнктах D_i на данных интерпретациях вместо констант, переменных и функций должны использоваться элементы H(S), а вместо предикатов - либо значения на тер-мах из H(S) (элементы эрбрановского базиса) либо их отрицания.

Пример 7. Привести примеры эрбрановских интерпре-таций множества дизъюнктов S = {P(x)Ú Q(f(x)), P(a) Ú Q(y)}.

Решение. Сигнатура S имеет вид: {X= (x, y); A = (a); F = (f); P = (P¹, Q¹) }.

Эрбрановский универсум множества дизъюнктов H(S) = {a, f (a), f (f (a)), f (f (f (a))),...}.

Эрбрановский базис A = { P(a), Q (a), P(f(a)), Q(f (a)), P(f (f (a))), Q (f (f (a)))),... }.

H-интерпретации получаем, рассматривая в качестве значений предикатов элементы эрбрановского базиса и их отрицания:

I₁ = { H(S), a, f, P(a), Q(a), P (f(a)), Q (f (a)), P(f(f(a))), Q(f(f(a)),...};

I₂ = {H(S), a, f, Ø P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))), Q(f(f(a)),...};

I₃ = {H(S), a, f, P(a), Ø Q(a), P(f(a)), Q(f(a)), P(f(f(a))), Q(f(f(a)),...};

I₄ = {H(S), a, f, Ø P(a), Ø Q(a), P(f(a)), Q(f(a)), P(f(f(a))), Q(f(f(a)),...} и т.д.

Очевидно, все множество Н - интерпретаций как бы описывает не только все возможные значения термов, вхо-дящих в S, но и истинностные значения предикатов из S. Справедлива следующая

Теорема. Множество дизъюнктов S невыполнимо Û когда оно невыполнимо на всех его Н -интерпретациях.