АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Эрбрановская интерпретация.

Определение. Пусть H_¥ – эрбрановский универсум множества дизъюнктов S. Интерпретация j с областью H_¥ называется H – интерпретацией множества S, если она удовлетворяет следующим условиям:

1) для любой константы с из S выполняется равенство j(с)=с,

2) если f – символ n-местной функции из S, то jf – функция, определенная на H_¥ равенством

(jf)(t₁,…,t_n)=f(t₁,…,t_n)

для любых t₁,…,t_nÎH_¥.

Если B={B₁,B₂,…,B_n,…} – эрбрановский базис множества дизъюнктов S, то H-интерпретацию j удобно представлять в виде множества литералов

{L₁,L₂,…,L_n,…},

где L_i есть B_i, если j(B_i)=1, и L_i=ØB_i, если j(B_i)=0.

Например, если S – множество дизъюнктов из примера 1, то эрбрановскими интерпретациями будут

j₁={P(a), Q(a), P(f(a)), Q(f(a)), P(f(f(a))),…}

j₂={P(a), Q(a), ØP(f(a)), ØQ(f(a)), P(f(f(a))), Q(f(f(a))), ØP(f(f(f(a)))),…}.

j₃={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-интерпретация, удовлетворяющая следующему условию: для любых элементов t₁,…,t_n эрбрановского универсума выполняется эквиваленция:

(j*P)(t₁,…,t_n)=1 Û (jP)(j(t₁),…,j(t_n))=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

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*.

Дата добавления: 2015-09-27 | Просмотры: 796 | Нарушение авторских прав