Презентация на тему ЛОГИКА ПРЕДИКАТОВ

функция, аргументы которой определены на некотором множестве М,

x1, x2, ... , xn ∈ M, а сама она принимает два значения: И (истина) и Л (ложь). Таким образом, предикат осуществляет отображение
М → {И, Л}.
Переменные x1, x2, ... , xn называются предметными переменными, а множество M – предметной областью.

Предикат от n переменных называется n-местным предикатом. Высказывание есть 0-местный предикат.

Над предикатами можно производить обычные логические операции и получать при этом другие предикаты. Таким образом, можно говорить об алгебре предикатов.

для каждого x  М. Тогда выражение xP(x) является

истинным высказыванием, если P(x) истинно для всякого x  М и ложным в противном случае.
Символ x называется квантором общности. Выражение xP(x) читается: “Для всех x имеет место P(x)”. В обычной речи квантору общности соответствуют слова: все, всякий, каждый, любой. Возможно отрицание квантора общности: ØxP(x): “Не для всех x имеет место P(x)”.
Пример .
Пусть P(x) – предикат “x – четное число”.
Тогда xP(x) есть высказывание “Всякое x – четное число" = «Все числа – четные».
Отрицание ØxP(x) есть высказывание «Не всякое x – четное число» = «Не все числа – четные».

x  М. Тогда выражение xP(x) является истинным

высказыванием, если P(x) истинно хотя бы для одного x  М и ложным в противном случае.
Символ x называется квантором существования. Выражение xP(x) читается: “Существует x, для которого имеет место P(x)”. В обычной речи квантору существования соответствуют слова: некоторый, несколько. Возможно отрицание квантора существования: ØxP(x): “Не существует x, для которого имеет место P(x)”.
Пример.
Пусть, P(x) – предикат “x – четное число”. Тогда xP(x) есть высказывание “Некоторые x – четные числа” = “Существуют четные числа” .
Высказывание ØxP(x) = “Неверно, что некоторые x – четные числа” = “Не существует четных чисел”.

стоящая справа от квантора, называется кванторной переменной и должна

присутствовать обязательно.

Переменная, стоящая под знаком квантора, называется также связанной переменной.

Несвязанная переменная называется свободной.

предикатов определяется индуктивно следующим образом:
1. Любая формула логики высказываний

есть формула логики предикатов.
К новым формулам логики предикатов относятся следующие выражения:
2. Предметные переменные x, y, z, ... есть формулы.
3. Предикаты P(x), Q(x, y), ... , а также выражения с кванторами xP(x), xR(x), xyQ(x, y),... есть формулы.
4. Если A и B – формулы, то ØA, AVB, A&B, AÞB, AB есть формулы, в которых свободные переменные формул A и B остаются свободными, а связанные переменные формул A и B остаются связанными.
5. Ничто, кроме указанного в пунктах 1 – 4, не есть формула.

& B ÞC, где A, B, C – высказывания.
б)

xyQ(x, y, z) & xyP(x, y, u).
Проанализируем последовательно это выражение.
Предикат Q(x, y, z) – формула;
Выражение xyQ(x, y, z) – формула; переменные x, y – связанные, переменная z – свободная.
Предикат P(x, y, u) – формула.
Выражение xyP(x, y, u) – формула; переменные x, y – связанные, переменная u – свободная.
Выражение xyQ(x, y, z) & xyP(x, y, u) – формула; переменные x, y – связанные, переменные z, u – свободные.

2. Выражение xyP(x, y, z) ÞQ(x, y, z) формулой не является. Действительно, выражение xyP(x, y, z) есть формула, в которой переменные x и y связанные, а переменная z свободная. Выражение Q(x, y, z) также формула, но в ней все переменные x, y, z свободные.

множестве М, называются равносильными на этом множестве, если при

любых подстановках констант вместо переменных они принимают одинаковые значения.
Определение. Формулы, равносильные на любых множествах, будем называть просто равносильными.
 Переход от одних формул к равносильным им другим формулам логики предикатов может быть произведен по следующим правилам:
1. Все равносильности, имеющие место для логики высказываний, переносятся на логику предикатов.
2. Перенос квантора через отрицание.
Пусть A – формула, содержащая свободную переменную x. Тогда
Ø(xA(x)ºx(ØA(x)). (2.1)
Ø(xA(x))ºxØ(A(x)). (2.2)

переменную x, а формула B не содержит переменной x,

и все переменные, связанные в одной формуле, связаны в другой. Тогда
 
xA(x)VBºx(A(x)VB).
xA(x)&Bºx(A(x)&B).
xA(x)VBºx(A(x)VB).
xA(x)&Bºx(A(x)&B).

4. Дистрибутивность квантора общности относительно конъюнкции и квантора существования относительно дизъюнкции.
Пусть формула B, так же, как и формула A, зависит от х. Тогда
xA(x) & xB(x)ºx(A(x) & B(x)).
xA(x) V xB(x)ºx(A(x) V B(x)).

xyA(x,y) ºyxA(x,y).

Разноименные кванторы переставлять, вообще говоря, нельзя!
 
6. Переименование связанных переменных.
Заменяя связанную переменную формулы A другой переменной, не входящей в эту формулу, всюду: в кванторе и в области действия квантора, получим формулу, равносильную A.
 
Пример 2.11.
A = xF(x) Þ xG(x).
Заменяя связанную переменную x на y в первом члене импликации и на z во втором, получим равносильную формулу:
B = yF(y) Þ zG(z).
A ºB.

логических символов имеются только символы &, V и Ø,

причем символ Ø встречается лишь перед символами предикатов, называются приведенными формулами.

Пример.
A(x)&B(x, y).
xA(x) V xØB(x, y).
Ø(A(x)&B(x, y)).
xA(x) Þ xØB(x, y).
Ø(xA(x) Þ xØB(x, y)).

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

задачи, определяющие связь между суждениями и формулами логики предикатов:
1)

выражение суждения в виде формулы логики предикатов;
2) интерпретация формулы логики предикатов.
Суждение – это мысль, в которой утверждается наличие или отсутствие свойств предметов, отношений между предметами.
Простым суждением назовем суждение, в котором нельзя выделить часть, в свою очередь являющуюся суждением. Среди простых суждений выделяют атрибутивные суждения и суждения об отношениях.
Все атрибутивные суждения можно разделить на следующие типы:
"a есть P", "Все S есть P", "Ни один S не есть P", "Некоторые S есть P", "Некоторые S не есть P". Эти суждения следующим образом переводятся на язык логики предикатов:
"a есть P" – P(a);
"Все S есть P" – x(S(x) Þ P(x));
"Ни один S не есть P" – x(S(x) Þ ØP(x));
"Некоторые S есть P" – x(S(x) & P(x));
"Некоторые S не есть P" – x(S(x) & ØP(x)).

в формуле используется знак импликации (Þ), а если кванторная

переменная связана квантором существования (), то в формуле используется знак конъюнкции (&).
 
Пример 2.17.
Перевести на язык логики предикатов следующие суждения:
а) Веста – собака.
Заменим имя "Веста" символом "в" и введем предикат P(x) = "x – собака". Наше суждение можно выразить формулой: P(в).
 б) Всякая логическая функция может быть задана таблицей.
Введем предикаты S(x) = "x – логическая функция"; P(x) = "x может быть задана таблицей". Искомая формула: x(S(x) Þ P(x)).
в) Ни один народ не хочет войны.
Введем предикаты S(x) = "x – народ"; P(x) = "x хочет войны".
Наше суждение можно выразить формулой: x(S(x) Þ ØP(x)).
г) Некоторые журналисты были в космосе.
Введем предикаты S(x) = "x – журналист"; P(x) = "x был в космосе".
Наше суждение можно выразить формулой: x(S(x) & P(x)).
д) Некоторые современники динозавров не вымерли.
Введем предикаты S(x) = "x – современник динозавров"; P(x) = "x вымер".
Наше суждение можно выразить формулой: x(A(x) & ØP(x)).

определений, теорем, необходимых и достаточных условий.
Пример.
«Для любого целого

n > 2 не существует натуральных чисел x, y, z, удовлетворяющих равенству: xn+yn = zn».
Введем предикаты: N(x) = "x – натуральное число";
M(x) = "x > 2"; P(x, y, z, n) = "xn + yn = zn".
Для любых чисел x, y, z, n условие (посылка) теоремы Ферма есть конъюнкция N(x)&N(y)&N(z)&N(n)&M(n), а заключение есть ØP(x, y, z, n).
Поэтому теорема Ферма формулируется следующим образом:
 
xyzn(N(x)&N(y)&N(z)&N(n)&M(n) Þ ØP(x, y, z, n)).