2. Интерпретация формулы, область интерпретации, примеры правильно построенных формул.

Формула имеет определенный смысл, т.е. обозначает определенное высказывание, если существует какая-либо интерпретация. Интерпретировать формулу – значит связать с ней определенное непустое множество М, т.е. конкретизировать предметную область, называемую также областью интерпретации и указать соответствие, относящее:

- каждой предметной константе в формуле конкретный элемент на М;

- каждой функциональной букве в формуле конкретную функцию на М;

- каждой предикатной букве в формуле конкретное отношение между элементами на М.

Рассмотрим элементарную формулу G(f(a,b),g(a,b)) и следующую интерпретацию: М – множество действительных чисел;

a, b – числа 2 и 3 соответственно;

f - функция сложения : f (a, b) = a + b;

g- функция умножения : g (a, b) = a * b;

G – отношение “не меньше”.

При такой интерпретации формула обозначает “сумма 2+3 не меньше произведения 2*3” . Это утверждение не верно и поэтому G = Ложь . Формула А называется выполнимой тогда и только тогда, когда существует интерпретация I, такая, что А принимает значение Истина в I. Если формула А принимает значение Истина в интерпретации I, то говорят что I удовлетворяет формуле А. Если некоторая формула A принимает значение Истина при всех интерпретациях, то её называют общезначимой. Формула называется невыполнимой, если при всех интерпретациях она принимает значение Ложь.

Обычно правила записывают в виде A → B. Левая часть выражения называется антецедент, правая консеквент. Выражение A → B ложно только в одном случае: Если А- истинно, а B – ложно. В остальных случаях A → B истинно. Например выражение {луна_сделана_из_зеленого_сыра → лошади_способны_летать } – истинно, т.к. антецедент ложный.

Рассмотрим несколько примеров на составление предикатных формул.

6. Все слоны серые.

x [Слон(x) → Цвет(x, Серый)]

7. Существует человек, который написал “Войну и Мир”.

x [Писать (x, Война и Мир)]

8. У каждого есть свой родитель.

y x P(x, y),

где предикатный символ P представляет собой отношение между аргументами x и y в предикате P(x,y) - x является родителем y. Если в приведенной формуле поменять кванторы местами, то получим формулу: x y P(x, y), которая интерпретируется как – существует некто, кто является для всех родителем. Таким образом, интерпретация формулы зависит от порядка расположения в ней кванторов существования и общности.

9. Если x является родителем y, а y родителем z, то x является дедушкой или бабушкой для z.

xyz){[P(x,y)  P(y,z)] → G (x,z)} ,

где P – родитель, G – дедушка или бабушка.

10. Если x>0 и y>0, то x*y>0.

x y {[G(x,0)  G(y,0)] → G (times(x,y),0} ,

где times(x,y) =x*y, предикатный символ G устанавливает отношение больше между аргументами x,y в предикате G(x,y).

6. В отделе закупок все кому более 30 женаты.

xy{[Работает_в(Отдел_закупок, x)Возраст(x, y)G (y, 30)] → Женат(х)}

7. На каждом красном цилиндре сверху стоит кубик.

x{[Цилиндр(х)Красный(х)] → ( y) [Кубик(y)На(y,x)]}