16. Синтаксис и семантика языка логики предикатов

16.1. Понятие предиката

Предикат (от лат. «сказуемое») Р(x₁,x₂,...,x_n) – функция, переменные которой принимают значения из некоторого произвольного множества М или множеств, возможно и бесконечных, а сама функция принимает 2 значения: «истина» или «ложь».

Р(x₁,x₂,...,x_n):MⁿB, B:{0,1}.

То есть, предикат – это отображение n-ой степени произвольного множества в бинарное множество В, элементы которого принимают два значения: «истина» или «ложь».

Переменные называются предметными или пропозициональными.

Таким образом, понятие предиката является расширением понятия логическая функция.

Предикат от n переменных называется n-местным предикатом.

Вместо предметных переменных в предикат могут быть подставлены определенные значения из предметной области М, т.е. константы. Также в предикат могут быть подставлены некоторые n-местные функции:

f(x₁,x₂,...,x_n):MⁿM.

Очевидно, что высказывание – нульместный предикат, свойство – одноместный предикат, n-местное отношение – n-местный предикат.

Предикат на конечных множествах может быть задан соответствующей таблицей (табл. 84) [24].

Пример.

P(x,y) «x<y»

М_х={1,2,3}

М_у={2,4}

М_хМ_уВ

Таблица 84

Предикат на конечных множествах

(x,y)	x<y	P(x,y)
1,2	1<2	1
1,4	1<4	1
3,2	3<2	0
2,4	2<4	1
3,4	3<4	1
2,2	2<2	0

Множество истинности данного предиката – множество, в котором предикат принимает значение «1».

16.2. Кванторы и связанные переменные

Все формулы логики высказывания являются частными случаями логики предикатов. Все операции логики высказывания переносятся в логику предикатов для связывания предметных букв. Дополнительно используются обозначения кванторов:

x F(х), т.е. «Все х обладают свойством F»;

x F(х), т.е. «Некоторые х обладают свойством F (но возможно и все)»,

где – квантор общности, – квантор существования.

Квантор общности и квантор существования называются двойственными.

Иногда используют обозначения квантора «Равно один»: !.

Если переменная связана квантором, то она называется связанной, иначе – свободной.

Например: x F(x,y), x F(x,y), здесь x – связанная переменная, y – свободная переменная.

16.3. Синтаксис языка логики предикатов. Формулы логики предикатов и формализация суждений

В качестве алфавита в логике предикатов используется латинский язык, как и в логике высказываний [25].

Вводятся следующие обозначения:

• константы: a,b,c,d,e,... – строчные буквы из начала латинского алфавита;

• логические константы (0 – ложь, 1 – истина);

• предметные переменные: x, y, z, v, w,... – строчные буквы из конца латинского алфавита;

• функции: f,g,h,... –строчные буквы из середины латинского алфавита;

• предикатные символы: F, G, H, P, Q, ... – прописные буквы латинского алфавита;

• символы логических операций и кванторов (, |, ,  ,,,…);

• служебные символы, например, символы скобок ( [, ], {, }, (, )).

Символы функций и предикатов называют сигнатурой.

Функции и предикаты иногда снабжаются верхним индексом местности операции.

При определении формулы используется понятие «терм». Терм – объединяет понятия переменных и функций, к которым применяются предикатные буквы.

Всякая предметная переменная или константа – терм.

Если f – n-местная функция, а t₁,t₂,...,t_n – терм, то f_n(t₁,t₂,...,t_n) – тоже терм.

Никакие другие выражения не являются термами.

Пример. f³(a,x,g²(x,y)) – это терм с трехместной функцией f, двухместной функцией g, a – константа.

Если F – n-местный предикат, t₁,t₂,...,t_n – термы, то Fⁿ(t₁,t₂,...,t_n) – элементарная формула. Никакие другие выражения не являются элементарными формулами.

Элементарную формулу иногда называют атомарной или атомом.

Введем понятие формула:

1. всякая элементарная формула – это формула;

2. если F и Q – формулы, а х – предметная переменная, которая входит в F, то x F(x), x F(x), ,F Q, F Q, F Q, F Q – являются формулами.

Примеры.

P²(a,f¹(x)) – формула;

Q¹(x,g²(x,b)) – не формула, так как предикат Q должен быть одноместным;

P²(y,Q¹(z)) – не формула, так как Q¹(z) – не терм;

f¹(g²(x,y)) – не формула, а терм;

F²(a,y)Q¹(b) – формула.