дзержинский и воронцов 2

Пример. Дано выск азывание

(CA ↔ (B→C))^(A↔B)^A(↔┐C))

Докажите что оно не подтверждаемо (или невыполнимо).

Исчисление предикатов

Опр. Пусть x1,x2,….xn – символы переменных произвольной природы. Наборы переменных (x1,…,xn) принадлежат множеству S2, которое будем называть предметной областью, а переменные будем называть предметами. N- местным предикатом, определённым на предметной области S2, называют отображение S2 во множестве высказываний.

То есть это утверждение о предметных переменных обладающее свойством, что при фиксации значений всех переменных об этом утверждении можно сказать, истинно оно или ложно

P(x,y,z) = “ x2 + y2 ≤ z2; x,y,z ϵ R “- трёхместный предикат определённый

на R3

D(x1,x2) = “натуральное число x1 делится без остатка на натуральное число x2” – двухместный предикат определённый на множестве пор натуральных чисел D(6,3)=И D(5,2)=Л

Множеством истинности предиката наз:

P-1({И}) = {(x1,…,xn) ϵ S2/ P(x2,…,xn) = И}

Множеством ложности предиката наз:

P-1({Л}) = {(x1,…,xn) ϵ S2/ P(x2,…,xn) = Л}

Предикат P, определённый на S2 наз тождественно истинным, если P- 1({И}) = S2

Тождественно ложным. если P-1({Л}) = S2

Нетривиально выполнимым если P-1({И}) ≠ ø и P-1({Л}) ≠ ø

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

Утверждение. Множество n- местных предикатов, определённых на S2

33

образует булеву алгебру предикатов, т е для них справедливы все аксиомы булевых алгебр (свойства операций)

Фиксация значений переменных: пусть Р(x1,…,xn) n местный предикат, определённый на S2. Зафиксируем xi=a (1≤i≤n). Получим n-1 местный предикат.

Q(x1,…,xi-1, xi+1…,xn)≡P(x1,…, xi-1,a, xi+1,…,xn)

Определённый на мн S2ia значений переменных x1,…, xi-1, xi+1,…xn

Пример P(x,y,z) = x2 + y2 ≤ z2; x,y,z ϵ R3 зафиксируем z=2 получим “ x2 + y2 ≤ 4” (x,y) ϵ R2

Навешивание кванторов:

Окр. Пусть P(x) – одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое xP(x) (для любого x P(x)), которое истинно тогда и только тогда, когда P(x) тождественно истинный предикат.

О высказывании xP(x) говорят, что оно получено из предиката Р навешиванием квантора всеобщности из переменной х

Опр. Когда Р(х) – одноместный предикат. Поставим ему в соответствие высказывание, обозначаемое xP(x) (существует х Р(х)), которое ложно тогда и только тогда, когда Р(х) тождественно ложный предикат. О высказывании xP(x) говорят, что оно получено из предиката Р навешиванием квантора по переменной х.

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

Те играют роль бесконечности конъюнкций и дизъюнкций

Аесли Р(х) – одноместный предикат определённый на конечном множестве S2 = {a1;a2;a3;…;an)

Тогда справедливо :

xP(x) ≡ Р(a1)^P(a2)^…^P(an)

xP(x) ≡ Р(a1)vP(a2)v…vP(an)

Доказательство очевидно из определения кванторов и логических операций.

Замечания 1 Высказывание можно считать предикатами, не содержащими переменных, т е

0-местными предикатами

34

2 Кванторы можно рассматривать как отображения уменьшающиеся местность на 1

3 Формулы алгебры высказываний от n высказывательных переменных можно рассматривать как n-местные предикаты от этих переменных.

Пусть Р(х1,...,хn) – n-местный предикат, определённый на S2 зафиксируем в нем значения переменных x1, xi-1, xi+1,xn на полученной одноместный предикат Q(xi) навесим квантор всеобщности (или существования), получим высказывание. Сопоставления любому набору значений переменных x1,…, xi-1, xi+1,…,xn вполне определённого высказывания

– это предикат от 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

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

35

называются связанными.

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

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

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

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

¬(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) ≡ Л

36

2)x2х1D(x1x2) ≡ л

3)x1x2D(x1x2) ≡ И

4)x2x1D(x1x2) ≡ и

5)x1x2D(x1x2) ≡ И

6)x2x1D(x1x2) ≡ и

7)x1x2D(x1x2) ≡ Л

8)x2x1D(x1x2) ≡ и

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

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

Опр. Подстановочное множества или просто подстановка есть множество Θ = {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}

37

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

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

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

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

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

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

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

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

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

Пример

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

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

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

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

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

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

38

(например 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)

(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

39

Пример

(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)]

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

Предложение ≡ формула

Теорема (Лёвенгейм, Сколем) : для каждого предложения ƍ логики предикатов мы можем построить универсальное предложение ƍ* такое, что ƍ выполняется тогда и только тогда, когда ƍ *выполнимо.

Алгоритм построения универсальной ƍ*

Шаг 1 Построить ПНФ предложения ƍ

Шаг 2 Последовательно (слева направо) вычёркиваем каждый квантор существования (у), заменяя все вхождения переменной у на новый, ещё не использованный функциональный символ f, в качестве аргументов f берём все переменные, связанные предшествующим ( у) кванторами всеобщности. Функциональный символ f называется Сколемовскмй функцией

Предложение ƍ*, полученное после выполнения алгоритма называется Сколемовской нормалной формой СНФ

Пример ƍ

(х) (у)( z) (ϑ) P(x,y,z,ϑ) находим в ПНФ

Вычёркиваем (ϑ) и заменяем на ϑ на Сколемовскую функцию g(x,z), так как кванторы А(х) А(z) предшествовали кванторы (ϑ). В итоге получим

(х) ( z) Р(х, f(x), z, g(x,y))

Если первым квантором предложение будет квантор существования, например

( у) ( х) ( z) ψ(x,y,z) то следовательно f не зависит ни от одной

40

переменной и функция f превращается в константу c то есть

ƍ*: А(х) А(z) ψ(x,с,z)

Метод семантических таблиц в логике предикатов

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

Семантические таблицы для логики предикатов получаются из соответствующих таблиц для логики высказываний путём добавления правил для кванторов: с помощью сематической таблицы

t ( (х)ƍ(x))

t ƍ(c) для всех с

Мы представляем факт “для истинности формулы хƍ(x) необходимо, чтобы ƍ(x) было истинным для всех констант С”

Семантическая таблица

t ((х)ƍ(x))

t ƍ(c) для новой с

Представляет факт “для истинности формулы хƍ(x) необходимо чтобы существовала константа с, которая ещё не появлялась в таблице, что ƍ(с) принимает истинное значение”

К атомарным таблицам для логики высказываний надо добавить ещё две для кванторов

41