 |
Понятие предиката, квантора, формулы, интерпретации.
|
|
|
|
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
|
|
|
