Основы построения и функционирования интеллектуальных информационных систем. Былкин В.Д - 29 стр.

UptoLike

ВУЗ: 

ПГУ | Пенза

Составители: 

Рубрика: 

29
2) в матрице формулы заменить каждое вхождение каждой Ǝ- квантифицированной переменной
на некоторый терм. Этот терм является функциональной константой, соответствующей данной
переменной и снабженной списком аргументов, также соответствующим той же самой
переменной;
3) устранить из формулы все Ǝ - квантафикации.
Пример. Найти сколемовскую форму формулы
.
Решение.
, где f и g - сколемовские функции.
Клаузальной формой называется такая сколемовская форма, матрица которой приведена к КНФ.
Любая сколемовская форма допускает эквивалентную клаузальную форму.
Эрбранова интерпретация
Результаты, полученные Эрбраном, приводят к упрощенной проверке выполнимости
формул. Основная идея заключается в проверке невыполнимости клаузальной формы,
интерпретируемой на специальной эрбрановой области. Эрбранова область клаузальной формы G
- это минимальное множество H
G
, удовлетворяющее следующим условиям:
1) для любой предметной константы a , входящей в G , область H
G
содержит
соответствующую эрбранову константу, обозначенную как A;
2) если G не содержит предметных констант, то, тем не менее H
G
содержит эрбранову
константу, обозначаемую как С;
3) для каждой n - местной функциональной константы f , имеющей вхождение в G ,
вводится функциональная константа F и принадлежность элементов h
1
, ... , h
n
к H
G
влечет за
собой принадлежность к H
G
терма F(h
1
,..., h
n
).
Эрбрановой интерпретацией для формулы С называется интерпретация I для формулы G ,
удовлетворяющая ниже перечисленным условиям:
1. Область интерпретации является эрбрановой областью Н
2. Функция интерпретации констант I
C
сопоставляет каждой предметной константе о
соответствующую эрбранову константу A .
)υ,,,,(υ uzyxPzyx
)u)z,g(x,,,),(,( uzxfxuPzx
2) в матрице формулы заменить каждое вхождение каждой Ǝ- квантифицированной переменной
на некоторый терм. Этот терм является функциональной константой, соответствующей данной
переменной и снабженной списком аргументов, также соответствующим той же самой
переменной;

3) устранить из формулы все Ǝ - квантафикации.
       Пример. Найти сколемовскую форму формулы
  x y z υP( x, y, z, u, υ) .
       Решение.
  x z uP( x, f ( x), z, u, g(x, z, u)) , где f и g - сколемовские функции.

Клаузальной формой называется такая сколемовская форма, матрица которой приведена к КНФ.
Любая сколемовская форма допускает эквивалентную клаузальную форму.
Эрбранова интерпретация
       Результаты, полученные Эрбраном, приводят к упрощенной проверке выполнимости
формул. Основная идея заключается в проверке невыполнимости клаузальной формы,
интерпретируемой на специальной эрбрановой области. Эрбранова область клаузальной формы G
- это минимальное множество HG , удовлетворяющее следующим условиям:
       1) для любой предметной константы a , входящей в G , область HG содержит
соответствующую эрбранову константу, обозначенную как A;
       2) если G не содержит предметных констант, то, тем не менее HG содержит эрбранову
константу, обозначаемую как С;
       3) для каждой n - местной функциональной константы f , имеющей вхождение в G ,
вводится функциональная константа F и принадлежность элементов h1 , ... , hn к HG влечет за
собой принадлежность к HG терма F(h1 ,..., hn).
       Эрбрановой интерпретацией для формулы С называется интерпретация I для формулы G ,
удовлетворяющая ниже перечисленным условиям:
1. Область интерпретации является эрбрановой областью Н
2. Функция интерпретации констант IC сопоставляет каждой предметной константе о
  соответствующую эрбранову константу A .




                                                     29

Страницы