13.4. Эрбрановский универсум множества дизъюнктов

По определению, множество дизъюнктов невыполнимо тогда и только тогда, когда оно ложно при всех интерпретациях па всех облас­тях. Так как невозможно рассматривать все интерпретации на всех областях, было бы удобно, если бы мы могли фиксировать одну такую специальную область H, что S невыполнимо тогда и только тогда, когда S ложно при всех интерпретациях на этой области. Эрбран показал, что такая область существует. Ее называют эрбрановским универсумом множества дизъюнктов S и определяют следующим образом.

Определение 13.4. Пусть H₀ — множество констант, встреча­ющихся в S. Если никакая константа не встречается в S, то H₀ состоит из одной произвольной константы, например, H₀={а}. Для i = 1, 2, ... пусть H_i+1 есть объединение H_i и множества всех термов вида fⁿ(t₁, …, t_n) (при всех n) для всех функций fⁿ, встречающихся в S, где t_j (j = 1, ..., n) принадлежит Н_i. Тогда каждое H_i называется множеством констант i-го уровня для S и Н_ называется эрбрановским универсумом для S.

Примеры.

1. Пусть S₁={Р(а), P(x)Р(f(х))}. Тогда

H₀={a};

H₁={a, f(a)};

H₂={a, f(a), f(f(a))};

……………………………………………..

H_={a, f(a), f(f(a)), f(f(f(a))), …}.

2. Пусть S₂ = {Р(x)(Q(х), R(z), R(у)(Q(y)). Так как не суще­ствует никаких констант в S, положим H₀ = {а}. Поскольку не существует никаких функциональных символов в S, то H=H₀=H₁=…={a}.

Определение 13.5. Пусть S есть множество дизъюнктов. Тогда множество атомов вида Рⁿ(t₁, ..., t_n) для всех n-местных предикатов Рⁿ, встречающихся в S, где t₁, ..., t_n – элементы эрбра-новского универсума S, называется множеством атомов множе­ства S, или эрбрановским базисом S.

Пример. Эрбрапонский базис множества дизъюнктов S={Р(а), P(х)Р(f(х))}:

A={P(a), P(f(a)), P(f(f(f(a)))), …}.

Эрбрановский базис множества дизъюнктов S₂ = {Р(х)Q(х), R(z)Q(x)}:

А={P(a), Q(a), R(a)}.

Определение 13.6. Основной пример дизъюнкта С множества дизъюнктов S есть дизъюнкт, полученный заменой переменных в С на элементы эрбрановского универсума S.

Пример. Пусть S={Р(х), Q(f(у))R(y)}, С=Р(х) - дизъюнкт в S и H={а, f(a), f(f(a)), ...} - эрбрановский универсум S. Тогда P(a), P(f(a)), P(f(f(a))) есть основные примеры С.

Определение 13.7. Пусть S — множество дизъюнктов, H - эрбрановский универсум S и I интерпретация S над H. Говорят, что I есть H-интерпретация множества S, если она удовлетво­ряет следующим условиям:

1. I отображает все константы из S в самих себя;

2. пусть f есть n-местный функциональный символ и h₁, …, h_n – элементы H. В I через f обозначается функция, которая отобра­жает (h₁, …, h_n) (элемент из Hⁿ) в f(h₁, ...., h_n) ( элемент из H). При этом не возникает никаких ограничений при придании значения любому n-местному предикатному символу в S. Пусть А={А₁, А₂, ..., А_n, ...} - эрбрановский базис множества S. H-интерпретацию I удобно представлять в виде: I={m­₁, m₂, ..., m_n, ...}, где m­_j есть А_j или А_j для j=1, 2, ... Смысл этого множества в том, что если m_j есть А_j, то атому А_j {присвоено значение «истинно», в противном случае - значение «ложно».

Пример. Рассмотрим множество S={Р(х)Q(х), R(f(y))}. Эр­брановский универсум H для S есть Н={а, f(а), f(f(а)), ...}. В S входят три предикатных символа: Р, Q, и R. Следовательно, эрбра­новский базис S есть А={P(a), Q(а), R(a), Р(f(а)), Q(f(а)), R(f(a)), …}.

Некоторые H интерпретации множества S:

I₁={Р(а), Q(a), R(а), Р(f(а)), Q(f(a)), R(f(a)), ...},

I₂={Р(а), Q(a), R(а), Р(f(а)), Q(f(a)), R(f(a)), ...},

I₃={Р(а), Q(a), R(а), Р(f(а)), Q(f(a)), R(f(a)), ...}, и т.д.

Можно показать, что для любой интерпретации найдется соот­ветствующая ей H-интерпретация.

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

Доказательство. Первая половина теоремы очевидна, так как по определению S невыполнимо тогда и только тогда, когда S ложно при всех интерпретациях на этой области. Чтобы доказать вторую половину теоремы, предположим, что S ложно при всех H-интерпре­тациях в S. Положим, что S выполнимо. Тогда существует такая интерпретация I на некоторой области D, что S истинно при I. Пусть I* есть H-интерпретация, соответствующая I. Тогда S истинно при I*. Это противоречит предположению, что S ложно при всех H-интерпретациях в S. Следовательно, S должно быть невыполнимо, что и требовалось доказать.

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

H-интерпретации можно представлять в виде семантических деревьев. Как будет видно впоследствии, нахождение доказательства невыполнимости множества дизъюнктов эквивалентно построению семантического дерева. Без потери общности можно рассматривать только бинарные семантические деревья.

Определение 13.8. Если А – атом, то говорят, что две литеры А и А контрарны друг другу, и множество {А, А} называют контрарной парой.

Отметим, что дизъюнкт есть тавтология, если он содержит контрарную пару, так как ААТ. и множество дизъюнктов невыполнимо, если оно содержит два единичных контрарных дизъюнкта, так как А&АF.

Определение 13.9. Пусть S – множество дизъюнктов и A - его эрбрановский базис. Семантическое (бинарное) дерево для S есть растущее вниз дерево T, в котором каждому ребру приписан атом из А или его отрицание таким образом, что из каждого узла N выходит дна ребра, помеченные контрарными литерами, и каждая ветвь дерева не содержит контрарных литер.

Обозначим через I(N) объединение всех литер, приписанных ребрам ветви, ведущей к узлу N. Тогда для каждого узла N I(N) не содержит контрарных пар.

Определение 13.10. Пусть А={А₁, А₂, ..., А_n, ...) - эрбрановский базис множества S. Говорят, что семантическое дерево для S будет полным тогда и только тогда, когда для каждого i(i = 1, 2, ...) и каждого конечного узла N семантического дерева (т. е. для узла, из которого не выходит никаких ребер) I(N) содержит либо A_i либо A_i. Таким образом, в полном семантическом дереве каждая ветвь соответствует одной H-интерпретации.

Когда эрбрановский базис множества S бесконечен, всякое полное семантическое дерево для S будет тоже бесконечно. Полное семантическое дерево для S соответствует исчерпывающему пере­бору всех возможных интерпретаций для S. Если S невыполнимо, то S не сможет быть истинным в каждой из этих интерпретаций. Таким образом, мы можем остановить рост дерева из узла N, если I(N) опровергает S. Это порождает следующие определения.

Определение 13.11. Узел N называется опровергающим, если I(N) опровергает некоторый основной пример дизъюнкта в S, но для любого предшествующего узла NI(N) не опровергает никакого основного примера дизъюнкта в S.

Определение 13.12. Говорят, что семантическое дерево Т замк­нуто тогда и только тогда, когда каждая ветвь T оканчивается опровергающим узлом.

Примеры.

1. Пусть S={Р, QR, РQ, PR}

Эрбрановский базис множе­ства S есть A={Р, Q, R}, невыполнимое множество основных примеров: {Р, QR, РQ, PR}. Семантическое дерево для S показано на рис. 13.1, замкнутое поддерево выделе­но более жирными линиями.

2. Пусть S={Р(х), Р(x)Q(f(x)), Q(f(x))}. Эрбра­новский базис A={Р(a), Q(a), Р(f(а)), Q(f(a))}. Невыполнимое множество основных примеров: {Р(a), Р(а)Q(f(a)), Q(f(a))}.

Семантическое дерево для 5 будет бесконечным (см. рис. 13.2); замкнутое поддерево выделено более жирными линиями.