Семантика формул логики предикатов

 

Формула имеет семантику, т.е. определенный смысл, и обозначает определенное высказывание, если существует ее некоторая интерпретация.

Интерпретировать формулу– значит связать с ней определенное непустое множество, т.е. конкретизировать предметную область (область интерпретации), а также указать соответствие [25]:

1) каждой предметной константе в формуле – конкретный элемент из множества М;

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

3) каждой n-местной предикатной букве – конкретное отношение между n элементами на М.

Пример [25].

G²(f(a,b)), g²(a,b)

Пусть М – множество натуральных чисел a=2, b=3, f – сложение (a+b), g – умножение (a×b), G – отношение «не меньше» (³).

Тогда: 2+3³2×3 – ложное высказывание

Если a=1, b=2 – высказывание истинное.

Не существует ни одной интерпретации G, при которой эта формула и истинна и ложна одновременно.

Для формулы G²(f(g(x,x),g(y,y),g(a,g(x,y))) при a=2: «x²+y²³2xy» – истинное высказывание.

Общезначимость, выполнимость, невыполнимость.

Формула без свободных переменных называется замкнутой.

Для данной интерпретации всякая замкнутая формула представляет собой высказывание, которое истинно или ложно. А всякая формула со свободными переменными выражает некоторое отношение на области интерпретации, которое может быть истинно для одних значений переменных и ложно для других значений.

Если формула истинна при всех интерпретациях, то она общезначима,

например: .

Если формула ложна при любых интерпретациях, то она невыполнима, например: .

Формула выполнима, если существует интерпретация, в которой она выполнима.

Логика предикатов второго порядка – логика, использующая кванторы по предикатным буквам и (или) по функциям.

Предикаты в информатике могут задаваться и в «неакадемической» форме – с использованием слов естественного языка, например: находиться <Иван, работа> – двухместный предикат «Находиться <Х,У>» – Х находится в У.

 

ТОЖДЕСТВЕННЫЕ ПРЕОБРАЗОВАНИЯ ФОРМУЛ ЛОГИКИ ПРЕДИКАТОВ

 

Операции над предикатами

 

Над предикатами можно производить обычные логические операции [24]. В результате получают новые предикаты.

Инверсией предиката называется предикат, у которого значения истинности проинверсированы.

Конъюнкцией предикатов называется предикат, у которого множество истинностей является пересечением множеств истинности исходных предикатов.

Пусть Р(х) означает предикат «х делится на 2», Q(x) означает предикат «х делится на 3», P(x)∙Q(x) означает предикат «х делится на 2 и х делится на 3», т.е. определяет предикат делимости на 6.

Дизъюнкцией предикатов называется предикат, у которого множество истинности является объединением множеств истинности исходных предикатов.

Аналогично могут быть определены эквиваленция и импликация.

Очевидно, что переменные должны принимать значения из одного общего множества.

Пусть предикаты P₁(x,y) и P₂(x,y) (X={c,d,e},Y={a,b,c,d}) определяются соответствующими таблицами (табл. 85-86) [24]:

Таблица 85

Для P₁(x,y)

Y X	a	b	c	d
c
d
e

 

Таблица 86

Для P₂(x,y)

Y X	a	b	c	d
c
d
e

 

Тогда импликацией P₁(x,y)→P₂(x,y) будет предикат Р_и(х,у) (табл. 87), ложный в соответствующих клетках (табл. 85-86), где первый предикат P₁(x,y) истинный, а P₂(x,y) – ложный. Эквиваленцией P₁(x,y)↔P₂(x,y) будет предикат P_э(x,y) (табл. 88), истинный в соответствующих клетках (табл. 85-86), где оба предиката принимают одинаковые значения.

Таблица 87

Для P_и(x,y)

Y X	a	b	c	d
c
d
e

 

 

Таблица 88

Для P_э(x,y)

 

Y X	a	b	с	d
c
d
e

 

Также, как в логике высказываний определяется равносильность предикатов – она выполняется, когда на всяком наборе значений входящих в них переменных предикаты принимают одинаковые значения: P₁(x,y)«P₂(x,y).

Таким же образом можно определить следование P₁(x,y)→P₂(x,y) предиката P₂ из предиката P₁. Это выполняется тогда, когда P₁(x,y)→P₂(x,y) истинно на всех наборах переменных, т.е. множество истинности P₁ является подмножеством множества истинности предиката P₂ (множество предиката P₁ включается во множество истинности предиката P₂).

Очевидно, что свойства – одноместные отношения – являются одноместными предикатами, а многоместные отношения – это многоместные предикаты.