5. Язык логики предикатов (PrL)

Символы языка PrL

Логические символы:

• Переменные x, y, z, … , x₀, y₀, z₀, …

• Логические связки , , , , 

• , ()

• Кванторы  и 

Специальные символы:

• Предикатные символы P, Q, R, … , P₀, Q₀, R₀, …

• Константы a, b, c, … , a₀, b₀, c₀, …

• Функциональные символы f, g, h, … , f₀, g₀, h₀, …

Основные понятия PrL

Предикат P(x,y,a,b,f(x,y,c))

• Степень предиката – число аргументов

• Аргументы – переменные (могут принимать значения на некотором множестве объектов), константы, функциональные символы (функциональный символ олицетворяет некоторый объект, связанный с аргументами)

• Смысл предиката – выражает свойство некоторого объекта или связь между аргументами

Пример. Пусть S – высказывание: «Если Джордж человек, то Джордж смертен»

• В логике высказываний S: A  B

• В логике предикатов P: Человек(Джордж)  Смертен(Джордж)

Обобщение формулы. Пусть x – переменная, принимающая значение на множестве людей.

• P: Человек(x)  Смертен(x)

Использование кванторов  и  - для обозначения всеобщей или частичной истинности формулы.

• P: (x)(Человек(x)  Смертен(x)) – всеобщая истинность

• P: (x)(Человек(x)  Смертен(x)) – частичная истинность

Двойственность кванторов  и :

   или    | (x)(Q(x))  (x)(Q(x))

Терм – это

• Константа

• Переменная

• Функциональный символ f(t₁, … , t_n), где t_i – терм

Атом (элементарная формула) – это выражение вида

P(t₁, … , t_n), где t_i – терм, P – предикатный символ

Формула – это

• Атом

• Если  и  — формулы, то выражения (), (), (), (), () – также являются формулами

• Если x – переменная,  - формула, то формулами являются выражения вида

((x)), ((x))

• Других формул нет

Связанное и свободное вхождение

Переменная x имеет связанное вхождение в формулу , если существует подформула  формулы  такое что, вхождение имеет вид

((x)) или ((x))

Пример. Пусть имеется формула : (x)(y)[P(x)Q(x,y)  R(x)]

и подформула : (y)[P(x)Q(x,y)  R(x)]

Вопрос: Как x входит в формулу  и в подформулу  ?

Основной терм – это терм, в который не входит ни одна переменная.

Предложение (замкнутая формула) – это формула, не имеющая свободных переменных.

Для преобразования формулы в предложение нужно связать все свободные переменные кванторами.

Подстановка – это множество пар вида

={x₁/t₁, … , x_n/t_n}

где x_i – переменные, t_i – термы, причем равенство x_i= x_j влечет равенство t_i= t_j

Если  - атом, терм или формула, то  - выражение, полученное в результате подстановки в  на места свободных вхождений переменных x_i соответствующих термов t_i.

Пример. Рассмотрим формулу

(x,y,z): (y)R(x,y)  (z)(Q(x,z))

и подстановку ={x/f(a,b)}, где f(a,b) – основной терм. Выполнив подстановку в формулу, получим предложение

(f(a,b),y,z): (y)R(f(a,b),y)  (z)(Q(f(a,b),z))

Множества формул как варианты

Пусть S={ c₁, … , c_n } – множество формул PrL,  - некоторая подстановка, тогда результатом подстановки  в S является множество формул

S={ c₁, … , c_n }

Множества формул S₁ и S₂ называются вариантами, если существуют подстановки  и  такие что

S₁= S₂ и S₂= S₁

Пример. Являются ли следующие множества формул вариантами?

S₁={P(f(x,y)), Q(h(z),b)} и S₂={P(f(y,x)), Q(h(u),b)}

S₁= S₂ ={y/x, x/y, u/z}

S₂= S₁ ={x/y, y/x, z/u}