Логика предикатов

1.

Логика
предикатов
Проф. Иванилова Т.Н.

2.

Предикатом Р(х1,…,хn) называется
функция, аргументы которой
принимают значения на некотором
множестве М, а сама функция
принимает два значения И или Л.
Р(х1,…,хn): Мn {И, Л}

3.

Так как предикаты принимают только
логические значения, из них можно
образовывать выражения, содержащие
логические связки.
Пример:
M={x|x N}
Р(х) – “х делится на 2”
Q(x) – “х делится на 3”
Р(х) Q(x) – “х делится на 2 и 3”.

4.

Интерпретация
Под интерпретацией понимают систему
<M, f>,
где М непустое множество,
называемое областью интерпретации,
f - соответствие, сопоставляющее
любому предикатному символу A
некоторое отношение в М.

5.

Пример:
While (x<>y) and (n <= 100) do
Begin
<оператор цикла>
end;
M={x|x N}, n N
P(x,y) - “x <> y”
Q(n) – “n <= 100”
P(x,y) Q(n) – “x<>y и n<=100”

6.

Операции связывания
квантором
Квантор общности

7.

Квантор существования

8.

Примеры:
1. M={x|x N}
Р(х) – “х делится на 2”
Q(x) – “х делится на 3”
х( Р(х) Q(x))=0 - “все х делятся на 2 и на 3”
2. Записать на языке логики предикатов:
“Никто не любит обмана”
М={x|x - человек}
P(x): x любит обман
х P(x) – “любой человек не любит обмана”

9.

Пример:
3. M={x|x N}
Р(х) – “х делится на 2”
Q(x) – “х делится на 3”
х(Р(х) Q(x))=
=1 – “существует такой х, который делится
на 2 и на 3”.

10.

Правила для кванторов
1. Перенос квантора через отрицание.
Пусть А содержит свободную
переменную х
( х) А(х) ( х) А(х)
( х) А(х) ( х) А(х)

11.

Правила для кванторов
2. Вынос квантора за скобки.
Пусть А(х) содержит свободную переменную х, В не содержит х.
( х) (А(х) В) ( х) А(х) В
( х) (А(х) В) ( х) А(х) В
( х) (А(х) В) ( х) А(х) В
( х) (А(х) В) ( х) А(х) В
Если не требовать, чтобы В не содержала x, тогда будут
выполняться такие равносильности:
( х) (А(х) В(х)) ( х) А(х) ( х) В(х)
( х) (А(х) В(х)) ( х) А(х) ( х) В(х)

12.

Правила для кванторов
3. Перестановка одноименных кванторов
( х) ( у) А(х, у) ( у) ( х) А(х, у)
( х) ( у) А(х, у) ( у) ( х) А(х, у)
4. Переименование связанной переменной
Можно заменить в формуле А какую-либо
переменную другой переменной, не
входящей в формулу А. Заменять нужно в
кванторе и всюду в области действия
квантора.

13.

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

14.

Пример:
M=Z
A(x): x – четное
B(y): y - положительное
D(x,y,z): x=y+z
F(x)=A(x)
G(x)= z y(D(x,y,z) A(y) A(z) B(y) B(z))
G(x) – x представимо в виде суммы двух нечетных
положительных чисел
Значит, в этой интерпретации F(x) и G(x) равносильны.

15.

Равносильность формул
Формулы логики предикатов F и G равносильны на
множестве М, если они равносильны во всех
интерпретациях, заданных на М.
Пример:
F= xA(x)
G= xA(x)
M={a}, то есть M –одноэлементное множество
Следовательно, F равносильна G на
одноэлементном множестве

16.

Равносильность формул
Формулы логики предикатов F и G
равносильны, если они равносильны на
всех множествах. (F G)
Примеры:
1. F(x)= (А(x) В(x))
G(x) = А(x) В(x)
F(x) G(x)
2. F(x)=А(x)
G(x)=(А(x) В(x)) (А(x) В(x))
F(x) G(x)

17.

Выполнимость. Общезначимость.
1. Формула А выполнима в данной
интерпретации, если существует набор
<а1,…,аn>, где аi М , значений свободных
переменных х1,…,хn формулы А такой, что
Пример:
M={x|x R}
A(x): x делится на 7
A(x)|x=7,49,… = 1 следовательно A(x) выполнима в
данной интерпретации.

18.

Выполнимость. Общезначимость.
2.Формула А истинна в данной
интерпретации, если она принимает
значение И на любом наборе <а1,…,аn>,
аi М значений своих свободных
переменных х1,…,хn.
Пример:
M={x| x – ворона}
P(x): x – плавает
B(x): x - летает
A(x)=P(x) B(x)=0 1=1 следовательно A
истинна в данной интерпретации.

19.

Выполнимость. Общезначимость.
3. Формула А общезначима или тождественноистинна, если она истинна в каждой
интерпретации.
Пример:
A(x) A(x)≡1
4. Формула А выполнима, если существует
интерпретация, в которой А выполнима.
Пример:
A(x) A(x)=0, эта формула не выполнима