По определению интерпретации ее областью может
быть любое непустое множество М. Было бы удобно иметь одно множество в качестве
области интерпретации. В случае, когда решается вопрос о выполнимости множества
дизъюнктов, таким множеством является так называемый эрбрановский универсум.
Пусть S –
множество дизъюнктов.
Введем следующее обозначение. Через H0
обозначим множество констант, содержащихся в S. Если S не
содержит констант, то H0 состоит из одной константы, скажем а, т.е. H0={a}. Предположим, что введено множество Hi. Тогда Hi+1 есть объединение
множества Hi и термов вида f(t1,…,tn), где t1,…,tnÎHi,
f – символ n-местной
функции, содержащейся хотя бы в одном из дизъюнктов множества S.
Определение.
Множество H¥=H0ÈH1È…ÈHnÈ… называется эрбрановским универсумом множества
дизъюнктов S.
Приведем три примера, которые будем использовать
в дальнейшем.
Пример 1.
Пусть S={P(x), ØP(x)ÚQ(f(y)), ØQ(f(a))}. Тогда
H0={a},
H1={a,f(a)},
. . .
H¥={a,f(a)},
f(f(a)),…}. |
Пример
2. Пусть S={P(x), Q(x)ÚØR(y)}. Множество S не содержит констант, поэтому H0={a},. Так как дизъюнкты из S не содержат функциональных символов, то H0=H1=H2=…=H¥={a}.
Пример 3. Пусть S={P(x), ØP(b)ÚQ(y,f(y,a))}. Тогда H¥={a, b,
f(a,a), f(a,b), f(b,a), f(b,b), f(f(a,a),a),…}.
Эрбрановский универсум, как мы видим.
Определяется не всем множеством дизъюнктов S, а только символами функций и константами,
входящими в дизъюнкты из S.
Определение.
Множество атомарных формул вида P(t1,…,tn), где t1,…,tnÎН¥, а P – символ n-местного предиката, входящий в дизъюнкты из S, называется эрбрановским
базисом множества дизъюнктов S.
Для множества дизъюнктов S из примера 1 эрбрановским базисом будет
множество атомарных формул B1={P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),…}. Эрбрановским базисом множества дизъюнктов
S из примера 2 будет множество B2={P(a), Q(a), R(a)}.
Пусть термин «выражение» означает терм, атомарную
формулу, литерал или дизъюнкт. Тогда основным
выражением будем называть выражения, несодержащие переменных.
Определение.
Пусть D – дизъюнкт из множества дизъюнктов S. Основным
примером дизъюнкта D называется
дизъюнкт, полученный из D заменой
переменных на элементы эрбрановского универсума Н¥.
Пусть S –
дизъюнкт из примера 1. Тогда дизъюнкт ØQ(f(a)) имеет один основной пример – сам дизъюнкт,
множество основных примеров дизъюнкта ØP(x)ÚQ(f(y))
бесконечно {ØP(a)ÚQ(f(a)), ØP(f(a))ÚQ(f(a)), ØP(a)ÚQ(f(f(a))),…}.
Если S – множество дизъюнктов из
примера 2, то каждый из дизъюнктов этого множества S имеет один основной пример.
Как утверждалось в начале параграфа (и будет
доказано в конце), для решения вопроса о выполнимости дизъюнктов в качестве
области интерпретации достаточно рассматривать только эрбрановский универсум.
Оказывается, можно еще ограничить и саму интерпретацию до так называемой H-интерпретации.
Определение.
Пусть H¥ –
эрбрановский универсум множества дизъюнктов S. Интерпретация j с областью H¥ называется
H – интерпретацией
множества S, если она
удовлетворяет следующим условиям:
1) для любой константы с из S выполняется равенство j(с)=с,
2) если f –
символ n-местной функции из S, то jf – функция, определенная на H¥
равенством
(jf)(t1,…,tn)=f(t1,…,tn)
для любых t1,…,tnÎH¥.
Если B={B1,B2,…,Bn,…} – эрбрановский базис множества дизъюнктов S, то H-интерпретацию
j удобно представлять в виде множества литералов
{L1,L2,…,Ln,…},
где Li есть Bi, если j(Bi)=1, и Li=ØBi,
если j(Bi)=0.
Например, если S – множество дизъюнктов из примера 1, то
эрбрановскими интерпретациями будут
j1={P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),…}
j2={P(a), Q(a), ØP(f(a)), ØQ(f(a)),
P(f(f(a))), Q(f(f(a))), ØP(f(f(f(a)))),…}.
j3={P(a), ØQ(a), P(f(a)),
ØQ(f(a)), P(f(f(a))), ØQ(f(f(a))),…}.
Последнее, что нужно сделать, чтобы доказать
основное утверждение этого параграфа (теорему 4.5), ввести понятие H-интерпретации j*, соответствующей (произвольной) интерпретации j множества S.
Предположим, что S содержит
хотя бы одну константу. Если j – интерпретация множества S с областью М, то для любого элемента h эрбрановского универсума значение j(h)
определено (и является элементом множества М.)
Определение.
Пусть j – интерпретация множества S с
областью М. Тогда H-интерпретацией j*, соответствующей
интерпретации j называется H-интерпретация, удовлетворяющая следующему
условию: для любых элементов t1,…,tn эрбрановского универсума выполняется эквиваленция:
(j*P)(t1,…,tn)=1
Û (jP)(j(t1),…,j(tn))=1
для любого символа предиката P.
Приведем пример. Пусть S – множество дизъюнктов из примера 1. Напомним,
что S={P(x), ØP(x)ÚQ(f(y)), ØQ(f(a))} и эрбрановский базис множества S есть B={P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),…}.
Рассмотрим интерпертацию j с областью М={1,2},
определяемую равенством j(а)=1 и таблицей
4.1.
Таблица 4.1
(В столбцах jP и jQ цифры 0 и 1 – истинностные значения.) Тогда
j*={ØP(a), Q(a), P(f(a)), Q(f(a)), ØP(f(f(a))),…}.
Рассмотрим теперь случай, когда S не содержит констант. Пусть j – интерпретация множества S с
областью М и а – константа, образующая эрбрановский универсум H¥. В этом
случае значение j(а) неопределено.
Для получения H-интерпретации
j* расширяем функцию j на а полагая j(а) равным произвольному элементу из М. Далее
поступаем так, как описано выше. Если множество М неодноэлементно, то мы можем
получить не одну H-интерпретацию
j*, соответствующую j. Нетрудно привести пример, когда H-интерпретаций j* столько же, сколько элементов в множестве М.
Следующее утверждение непосредственно следует из
определений.
Лемма. Пусть j – интерпретация с
областью М, при которой все дизъюнкты из S истинны. Тогда все дизъюнкты из S истинны при любой H-интерпретации j*, соответствующей j.
Теорема
4.5. Множество дизъюнктов S невыполнимо тогда и только тогда, когда S ложно при всех H-интерпретациях, т.е. для любой H-интерпретации множества S в S
найдется дизъюнкт, который ложен при этой H-интерпретации.
Доказательство.
Необходимость очевидна.
Действительно, невыполнимость множества S означает, что это множество ложно при любой
интерпретации. В том числе и при любой H-интерпретации. Достаточность следует из леммы,
поскольку если S выполнимо,
то существует хотя бы одна интепретация j, при которой все дизъюнкты из S
истинны. Но тогда все дизъюнкты из S будут
истинны и при H-интерпретации
j*.
Теорема
доказана.
|