Математическая логика. Исчисление предикатов. Пример решения контрольной работы

1.

Математическая логика
Исчисление предикатов
Пример решения контрольной
работы

2.

n-местным предикатом на множестве M называется n-местная функция
Р(x1,…, xn), аргументы которой принимают значение из множества M, а сама
функция принимает значения из множества {0(«ложь»), 1(«истина»)}.
М – область определения предиката
Нульместный предикат рассматривается как высказывание
1 M={1,2,3,…} – множество натуральных чисел;
а) Р(x):= «x делится на 2». Р(2)= «истина», Р(3)= «ложь»;
б) Р(x1, x2): «x1≥ x2». Р(1,2)= «ложь», Р(3,2)= «истина».
2 M=R=(-∞,+∞) – множество действительных чисел :
Р(x1, x2, x3):= x1+x2+x3=1
Р(1,0,0)=«истина», Р(0,0,0)=«ложь».
Областью истинности предиката P: М {0,1} называется множество
таких x М , что P(x) = 1. Обозначается: Tp
Областью ложности предиката P: М {0,1} называется множество
Fp =М \ Tp .
Предикат P: М {0,1} называется тождественно истинным, если
область истинности предиката P совпадает с его областью определения.

3.

Операции над предикатами
Функтор - средство преобразования знаковых выражений
и порождения одних выражений из других.
Напр., знак "+" можно рассматривать как Ф., преобразующий два числа в некоторое
третье число. В зависимости от числа объектов, к которым применяется Ф., последние
разделяются на нуль-местные, одноместные, двухместные и т. д.
К числу нуль-местных Ф. в математической логике относят константы.
Отрицанием предиката Р(х) на множестве M называется предикат Р(х) на том же
множестве, истинный для тех и только тех значений х∈М, для которых предикат Р(х)
ложен.
Конъюнкцией предикатов Р(х), Q(x) на множестве M называется предикат Р(х)∧Q(x) на
том же множестве, истинный для тех и только тех значений х∈М, для которых оба
предиката Р(х), Q(x) истинны. Операцию конъюнкции можно обозначать
Дизъюнкцией предикатов Р(х), Q(x) на множестве M называется предикат Р(х)∨Q(x) на
том же множестве, истинный для тех и только тех значений
х∈М, для которых истинен хотя бы один из предикатов Р(х), Q(x).
Пример – Даны предикаты: Р(х):= «х<5», Q(x):= «х≥2», х∈{1,2,3,4,5}=М.
Р(х):= «х≥5», Тогда: Р(х)∧Q(x):=«2≤х<5»; Р(1)∧Q(1)=0, Р(2)∧Q(2)=1.

4.

М
М
М
М

5.

Операции – квантификации
Для предикатов вводится также специфические логические операции,
или кванторы, - ∀ («каждый» или «для всех») – квантор общности и
∃ («существует» или «для некоторых») – квантор единичности
Операции квантификации не коммутативны.
М
М

6.

Квантор единичности
(существования)
М
М
М
ложно, тогда и только тогда, когда область
ложности совпадает с областью определения
То есть утверждение
М
М
М

7.

Свободные и связанные переменные
Константы, переменные или функторы называются термами. Предикат,
аргументами которого являются термы, называется атомом.
Вхождения переменных в атом называются свободными.
Свободные вхождения переменных в предикаты Р и Q остаются свободными в
предикатах Р, Р→Q.
Вхождения переменой в предикат ∀хР(х) и ∃хР(х) называются связанными.
В предикате ∀хР(х,у)∨∃уQ(у)∨ R(х)
первое вхождение переменной х связано, второе - свободно, переменная у
при первом вхождении свободна, при втором - связана.

8.

Доказательство тождеств
∀