Материал: Методичка Дзержинский

– это предикат от n-1 переменных. Говорят, что это (N-1)-местный предикат получен из исходного предиката Р(х1,...,хn) навешиванием квантора всеобщности (или существования) по i- той переменной и обозначают

xi P(x2,…,xn)

Об i переменной говорят, что она связана квантором всеобщности.

Определим индуктивную формулу исчисления предикатов .

Определение Терма : 1) Всякая предметная переменная или предметная константа – терм

2) если f – функция и η1, η2,…, ηn – термы то f(η1,…, ηn) – терм

3)Выражение является термом только в том случае, если это следует из правил 1 и 2

Если Р-предикат, а ηi – термы, то Р(η1,..., ηn) – элементарная формула или

атом.

Определение формулы 1) Всякая элементарная формула является формулой

2)Если А и В – формулы и х-предметная переменная, то каждое из выражений А о В

xА(x); xА(x); ┐А (где о- логическая операция) является формулой.

3) Выражение является формулой в том и только в том случае если это следует из правил 1 и 2

В выражении xА(x) формула А(х) называется областью действия квантора x

Предметная переменная, входящая в формулу называется свободной если она не следует непосредственно за квантором и не входит в область действия квантора по этой переменной. Все другие переменные, входящие в формулу называются связанными.

В пределе всякая формула без свободных переменных (замкнутая формула) является высказыванием, которое истинно или ложно, а всякая формула со свободными переменными задаёт некоторое отношение в предметной области. Это отношение может быть истинно или ложно в зависимости от значений свободных переменных.

Каждая формула F(P,…,Pm,x1,…,xn) в исчислении предикатов задаёт оператор, перерабатывающий систему предикатов Р1,...,Рm в предикат Pa от аргументов x1,…,xn, где все эти перемен в формуле являются свободными. Две

36

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

Основы равносильности содержащие кванторы:

Закон де Моргана для кванторов (двойственность)

¬(xР(x)) ≡ x ¬(Р(x))

¬(xР(x)) ≡ x ¬(Р(x))

Коммутация одноименных кванторов

xуР(х,у) ≡ ухР(х,у)

xуР(х,у) ≡ ухР(х,у)

Дистрибутивные законы для кванторов

x(Р(x)^Q(x)) ≡ xР(x) ^xQ(x)

x(Р(x)vQ(x)) ≡ xР(x) vxQ(x)

Законы ограничения действ для кванторов

x(Р(x) v Q(у)) ≡ xР(x) v Q(у) x(Р(x)^Q(у)) ≡ xР(x) ^Q(у)

*

уxР(х,у)→ хуР(х,у) ≡ И

ПРИМЕР.

D(x1,x2) = “Натуральное число х1 делится (без остатка) на натуральное число х2”

Навесим последовательно на его переменные кванторы

1)x1x2D(x1x2) ≡ Л

2)x2х1D(x1x2) ≡ л

3)x1x2D(x1x2) ≡ И

4)x2x1D(x1x2) ≡ и

5)x1x2D(x1x2) ≡ И

6)x2x1D(x1x2) ≡ и

7)x1x2D(x1x2) ≡ Л

8)x2x1D(x1x2) ≡ и

Разные кванторы вообще говоря не коммутируют

Другой способ позволяющий получать предложения состоит в

37

подстановке констант на место свободных вхождений переменных. В общем случае, мы имеем следующее определение подстановки

Опр. Подстановочное множества или просто подстановка есть множество Θ = {U1/ƍ1, U2/ƍ2,…,Unƍm}

Где Ui и ƍi, 1≤i≤n, являются соответственно переменными и термами, причём равенство Ui=Uj влечёт ƍi=ƍj, 1≤i≤j≤m

Если ƭ есть какое-либо выражение (атом, терм или формула) то ƍΘ обозначает выражение, полученное путём подстановки на места свободных вхождений переменных U1,…,Un соответствующих термов

ƍ1,..., ƍm

Пустая подстановка обозначается символом Е={} Основной операцией на множестве подстанов. Является

композиция. Определение.

Пусть Θ {U1/S1,…,Um/Sn}

ψ = {ϑ1/t1,…, ϑn/tn) композицией Θ и ψ наз. Подстановка Θψ

={U1/S1ψ,…,Un/Snψ, ϑ1/t1,…, ϑn/tn } – ( {Ui/Siψ/Ui=Siψ} υ {ϑi/ti/ ϑi ϵ{U1,…,U,}} )

Другими словами, мы сначала применяем подстановку ψ к термам ƍ1,..., ƍm подстановки Θ, заменяя в этих термах переменную ϑi на терм ti, а затем дополняем полученную подстановку элементам и множества ψ. При этом мы отбрасываем элементы вида Ui/Siψ если терм Siψ совпадает с Ui и элементы вида ϑi/ti если ϑi содержится среди переменных U1,...,Un подстановки Θ.

Пример

Θ = {x/f(y), y/z}

Ψ= {x/a, y/b, z/y)

Θ Ψ = {x/f(y)Ψ, y/zΨ, x/a, y/b, z/y} – ({Ui/ƍi/Ui=ƍiΨ} υ { ϑi/ti/ϑi ϵ {Uj}}) =

{x/f(b), y/y, x/a, y/b, z/y} – ({y/y} υ {x/a, y/b, }) = {x/f(b), z/y}

Для произвольных подстановок Θ, Ψ, ϒ и для произвольных термов выполняется равенство : (св-во ассоциативности)

Нормальные формы

В логике предикатов существуют две важные нормальные формы (т е формулы специального вида)

Предваренная нормальная форма(ПНФ) , Сколемовская нормальная

38

форма (СНФ), каждая отличается типами кванторов входящих в предложение.

Преобразуя каждое из двух заданных предложений в одну из этих форм, мы можем легко их сравнивать и определять эквиваленты ли они, является ли одно из них отрицанием другого или просто обладают ли они какими-либо особенностями.

Сколемовская нормальная форма играет важную роль в логическом программировании.

ПНФ: Формула ƍ находится в Предваренной нормальной форме если она имеет вид

(Q1x1)(Q2x2),…,(Qnxn)Ϭ где Qi i=1…,n обозначает один из кванторов им а Ϭ – формула без кванторов.

Выражение (Q1x1),…,(Qnxn) называется префиксом формулы а Ϭ называется матрицей формулы

Пример

Следующие предложения находятся в ПНФ

(х)(у)[Q(x,y)vP(x,y)]

Чтобы привести формулу к ПНФ надо использовать эквивалентность логики высказываний и логики предикатов. Но надо ещё добавить два часто встречающихся случая

Что делать если:

(х)Р(х) ^ (х)G(х) это ≠↔ (х) (Р(х) ^ G(х))

для преобразования этого выражения надо сначала переименовать все вхождения переменной х в формулах (х)G(х). Это сделать важно так как х связанная переменная в этой формуле и её можно заменить на новую переменную которая не будет встречаться и в основной формуле и в формуле Р (например z) тогда

(х)Р(х) ^ (z)G(z) =↔ ((x)(z)[P(x)^G(z)]

Аналогично если

(х)Р(х) v (x)G(x) =↔ ((x)P(x)v ((z)G(z) =↔ =↔ (x)[P(x)v (z)G(z)] =↔ ((x)(z)[ P(x)vG(z)]

Алгоритм приведения формул к ПНФ

1 шаг избавляемся от символов ↔ и → с помощью формул х ~у ≡( ¬х v y)* (x v ¬y)

39

(A ↔ B) =↔ ((A→B)^( B→A) =↔( ┐А v B)^ (A v ┐B)

(A→B) =↔ ( ┐А v B)

2 шаг проносим отрицание вглубь формулы до элементарных. формул

┐(AvB) =↔ ┐А ^ ┐B

┐(A^B) =↔ ┐А v ┐B

┐(┐А) =↔ A

┐((x) А =↔ (x) ┐А ┐(x)А =↔ (x) ┐A

Шаг 3 Выносим кванторы наружу с помощью формул

(Здесь В не содержит свободных вхождений х)

(x) А(х) ^ (x) B(х) =↔(x) (А(х) ^ B(х))

(x) А(х) v (x) B(х) =↔(x) (А(х) v B(х)) (Qx) A(x) ^B =↔ (Qx)[A(x)^B(x)]

(Qx) A(x) vB =↔ (Qx)[A(x)vB(x)]

(Здесь В не содержит свободных вхождений х , (Qx) – это (x) или (x)

)

(x) А(х) v (x) B(х) =↔ (x) (z) [А(х) v B(z)] (x) А(х) ^ (x) B(х) =↔ (x) (z) [А(х) ^ B(z)]

Здесь В не содержит свободных вхождений х, переменная z не входит в В и не входит в А, и В(z) есть результат замены свободных вхождений х на z

Пример

(x) (у)[ (z) (P(x,z) ^ P(y,z)) → (u) R(x,y,u)] ↔

(x) (у)[ ┐ (z) (P(x,z) ^ P(y,z)) V (u) R(x,y,u)] ↔

(x) (у)[ (z) (┐ P(x,z) v ┐ P(y,z)) V (u) R(x,y,u)] ↔ (второй шаг делать не надо сразу третий)

(x) (у) (z) [ (┐ P(x,z) v ┐ P(y,z)) V (u) R(x,y,u)] ↔

(x) (у) (z) (u) [ (┐ P(x,z) v ┐ P(y,z)) V R(x,y,u)]

Окр: Предложение ƍ* наз универсальным если оно содержит только кванторы всеобщности и находится в ПНФ и выполняется тогда и только тогда

40