Главная | Обратная связь
МегаЛекции

Понятие предиката, квантора, формулы, интерпретации.





N местным предикатом от <x1,…,xn> называют функцию, переменные которой принимают значение из множества M, а значение которой лежит в множестве {и,л}.

Если M=Æ, то это высказывание.

С предикатом можно производить логические операции.

Квантор:

Определение № 1:

Пусть P(x) – одноместный предикат, определённый на M, тогда выражение ("x)P(x) = И ó "aÎM, P(a)=И.

Определение № 2:

…($x)P(x) = И ó $aÎM, P(a)=И.

Формулы логики предикатов:

Алфавит логики предикатов:

1) x1,…,xn –предметные переменные

2) Ai(j) – предметные символы.

3) Ø, &, V, É, ~ - символы логики.

4) ", $

5) ), (

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

1) Если Ai(j)(x1,…,xn) – атомарная формула где x1,…,xn – свободные переменные.

2) A и B – формулы логики предикатов такие, что свободные переменные одной не являются связными другой.

(ØA), (A&B), (AVB), (AÉB), (A~B) – также формулы.

3) A(x) – x свободная и возможно есть ещё другие переменные.

("x) A(x), ($x)A(x) – тоже формулы. X стала связанной, а остальные как были свободными (связными) так и остались.

4) Других правил нет.

Интерпретация. Определение:

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

<M,f> f,Anj (x1,…,xn) à P(x1,….,xn).

 

32. Основные равносильности логики предикатов.

Пусть F1 и F2 формулы логики предикатов на списке переменных <x1, …, xn>.

Определение 1: пусть I = <M, f>. Будем говорить, что F1 = F2 в данной интерпретации I, если на любой оценки списка переменных <a1,..., an> Î Mn. Формулы принимают одинаковые истинностные значения.

Определение 2: F1~F2 на множестве M, если в любой интерпретации на любой оценке формулы принимают одинаковые истинностные значения.

Определение 3: Будем говорить, что формулы F1 и F2 равносильны, если они равносильны на всех множествах оценок.

Основные равносильности:

1) справедливы все равносильности логики высказываний.



2.1)Ø("x)A(x)=($x)ØA(x) – перенос отрицание через квантор.

2.2)Ø($x)A(x)=("x)ØA(x)

3.1) ("x) (A(x) V B(x))= ("x)A(x)V("x)B(x) - неверно

3.2) ("x) (A(x) & B(x))= ("x)A(x)&("x)B(x)

3.3) ($x) (A(x) V B(x))= ($x)A(x)V($x)B(x)

3.4) ($x) (A(x) & B(x))=($x)A(x)& ($x)B(x) – неверно

4.1) ("x1)("x2)A1(x1, x2)= ("x2)("x1)A1(x1, x2) ß одноименные кванторы

4.2) ($x1)($x2)A1(x1, x2)= ($x2)($x1)A1(x1, x2) можно переставлять

4.3) перестановка различных кванторов неверна.

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

 

33. Приведенная нормальная форма формул предикатов.

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

1) Если в формуле присутствуют только логические символы &,Ø,V, причем Ø стоит только перед предикатами, то формула считается приведенной.

Ø ("x)A(x) <– не является ($x)ØA(x) <– является

2) Правильная форма называется нормальной, если она не содержит кванторов " и $ или если все они стоят впереди, т.е. все предикаты находятся под действием этих кванторов.

("x)($y)("z)(A1(x, y)VA2(z))

Теорема 2:

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

Доказательство:

Теорема 2 = теорема 2.1 + теорема 2.2.

Теорема 2.1:

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

а) избавимся от É,~,+ по равносильностям логики высказываний(&, V, Ø, ", $).

Для n=0 формула атомарная и она находится уже в ПФ

A(x1,x2,…,xn) не содержат никаких операций, значит утверждение справедливо.

Пусть для всех случаев меньших n – верно. Докажем для n:

1) F=GVH

2) F=G&H

3) F=ØG

4) F=("x)G(x)

5) F=($x)G(x)

 

1) Если {G1=G и H1=H} – приведенные формы, на основании того, что операций < n, то F=G1VH1 – приведенная форма.

2) Аналогично первому пункту.

3.1) G=AVB => G=Ø(AVB)= ØA&ØB

3.2) G=A&B => G=Ø(A&B)= ØAVØB

3.3) G=ØA => G=ØØA=A

3.4) G=("x)A(x) => ØG=Ø("x)A(x) = ($x) ØA(x)

3.5) G=($x)A(x) => ØG=Ø($x)A(x)=("x) ØA(x)

4, 5) уже доказаны.

Теорема 2.2:

Если F приведенная, то можно указать равносильную ей формулу в ПНФ.

Для n=0 формула атомарная и она находится уже в ПНФ

Пусть для всех случаев меньших n – верно. Докажем для n:

F=GVH

1.1) не содержат кванторов, уже в ПНФ

1.2) G содержит x с квантором ". Т.к. в G число символов меньше n, то мы можем вынести этот квантор и получить G=("x)G(x).

1.3) аналогично для квантора $ и для случая, если H содержит x, G не содержит.

1.4) G содержит x, то $ G=($x)G1(x),

H содержит x, то $ H=($x)H1(x), где H1 и G1 – приведенные, то получаем:

F=GVH=($x)G1(x)V(x)H1(x)=($x)(G1(x)H1(x))

1.5) Если G и H содержат x с квантором " или переменные с разными кванторами, то в одной из формул делаем замену переменных, т.е. x меняем на y, если y не является свободно переменной F.

Пример:

($x)G1(x)V("x)H(x)=($x)G1(x)V("y)H1(y)=($x)(G1(x)V"(y)H1(y))=($x)("y)(G1(x)VH1(y))

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

1) Избавиться от логических символов по равносильностям логики высказываний.

2) Внести Ø в сковки по законам Де Моргана.

3) Если Ø стоят перед кванторами " или $, то перенести через них Ø по равносильностям перехода через квантор.

4) Вынести кванторы за скобки по соответствующим равносильностям.

Пример:
("x)A1(x)&($x)("y)A2(x, y)=("x)A2(x)&($z)("y)A2(z, y)=

=($z)(("x)A1(x)&("x)A2(z, x))=($z)("x)(A1(x)&A2(x))

 

34. Выполнение и общезначимость формул.

Определение 1: Говорят, что F выполнима в интерпретации I, если существует оценка на списке оценок <a1,a2,…,an>, что F(a1,a2,…,an)=TRUE

Определение 2: Говорят, что F выполнима в логике предикатов, если в некоторой интерпретации, на некоторой оценке списка своих переменных, она, если существует оценка на списке оценок <a1,a2,…,an>, что F(a1,a2,…,an)=TRUE

Определение 3: Говорят, что F общезначима в логике предикатов, если для каждой интерпретации на любой оценке списка свободных переменных, она принимает значение истины.

F общезначима ó F невыполнима

 

F=($x)A(x) I1=<z, f>

f: A(x) => x- четное

B(x) & C(x)|true = TRUE I2=<N, f>

f : B(x) – x – нечетное

C(x) – x – простое

("x)A(x)~($x)A(x): M=a – True

 

Пример невыполнимости:

F=($x)"(y)(A1(x, x)&A1(x, y))

$ I=<M, f>

$ x=a0ÎM

("y)(A1(a0Ç0)&ØA1(a0, y))=True

A1(a0, a0)&(("y)ØA1(a0, y))=True

A1(a0, a0)=True

("y)ØA(a0, y)=True => y =a0

ØA1(a0, a0)=True

A1(a0, a0)=False

Эти два уравнения противоречат друг другу, => формула невыполнима.

 

Пример общезначимости:

("x) ØA(x)~ Ø($x)A(x)

($x)A(x)&B~($x)A(x)&B

 

Утверждение 1:

A(x) не содержит y

("x)A(x) É A(y)

Доказательство:

A(x) - <x, x1, …, xn>

("x)A(x)ÉA(y) - <y, x1, …, xn>

I = <M, f>, <a, x1, …, xn>, <b, x1, …, xn>

("x) A(x)ÉA(y)

1) "uÎM => ("x)A(x)|<u, x1, …, xn>=True

2) $a0ÎM : A(x)|<a0, a1, …, an>=FALSE

("x)A(x)É=> ("x)A(x)|<a, a1, …, an>=False

Утверждение 2:
A(X) не содержит y

A(y) É($x)A(x) – общезначима

Доказательство:

("x)ØA(x)ÉA(y)= Ø("x)) ØA(x)VØA(Y)=

=($x) ØØA(X0)VØA(y)= ØA(y)V($x)A(x)=A(y)É($x)A(x) – общезначима

 

("x)($y)A(x, y) ~ ($x)("x)A(x, y)

A(y)É("x)A(x) I=<Z, f>

A(x) – x – четно

($y)("x)A(x, y)É("x)($y)A(x, y)

$I=<M, f> ($x)("x)A(x, y)=True

("x)($y)A(x, y)=False

($x)("y) ØA(x, y)=True

$y=b("x)A(x, b)=True

$x=a("y) ØA(a, y)=True

"xØx=a A(a, b) = True

"yØy=b ØA(a, b) = True

 





Рекомендуемые страницы:

Воспользуйтесь поиском по сайту:
©2015- 2021 megalektsii.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав.