Похожие презентации:
Исчисление предикатов
1.
Исчисление предикатовЛектор: Завьялов Олег
Геннадьевич
кандидат физико-математических
наук, доцент
2. Предикаты
Многие утверждения, имеющие форму высказываний, на самомделе такими не являются, так как содержат переменные,
значения которых не указано.
Такие утверждения называются предикатами.
Предикат с одной переменной, называется одноместным
предикатом .
Предикат с двумя переменной, называется двуместным
предикатом .
Предикат с n переменными, называется n - местным
предикатом .
3. Некоторые предикаты истинны для каждого возможного набора значений переменных
Символ х называется универсальным квантором(квантором всеобщности).
Читается “для любого х”, “для каждого х”.
Множество значений, которое может принимать х, называется
универсом, или предметной областью.
4. Квантор всеобщности
Предикатх у R(x, y)
Читается “для каждого х, для каждого у имеет место R(x, y)”, или
“для каждого х и для каждого у имеет место R(x, y) ”.
5. Квантор существования
Символ х называется квантором существования.Выражение х относится к значению х из предметной области.
х P(x)
Читается “существует х”, “найдется х”.
6. Построение отрицания
Если D(x) – предикат, то высказывание х D(x) истинно толькотогда, когда высказывание D(x) истинно для любого х.
Отрицание для высказывания х D(x) :
х D(x)
или х ( D(x))
7. Построение отрицания
Если G(x) - предикат, отрицание существования такого х, чтоG(x) истинно, записывается в виде
( х G(x)) или x( G(x))
Тождества
х (D(x)) х ( D(x))
х (G(x)) x ( G(x))
8. Отрицание высказывания, содержащего более одного квантора, осуществляется путем последовательного рассмотрения каждого
квантора, начиная с первогоПерейдем к обозначениям, принятым в булевой записи
9. Соотношения
1) Универсальная конкретизацияИз универсальности х P(x) следует истинность P(a) для
произвольного а из универса
2) Универсальное обобщение
Если произвольное а из универса обеспечивает истинность
P(a), следовательно х P(x) истинно.
3) Экзистенциональная конкретизация
Из истинности х P(x) следует, что существует конкретное b
такое, что P(b) истинно.
4) Экзистенциональное обобщение
Из существования конкретного с из универса, для которого
P(с) истинно, следует х P(x) .
10. Теорема
Для произвольных предикатов P(x) и Q(x), имеющих однупредметную область
11. Диаграммы Эйлера
Для неформальной проверки правильности умозаключений,включающих утверждения типа “для всех”, “для каждого”.
Утверждение “Все p есть q”
Утверждение “Некоторые p есть q”
12. Пример
УмозаключениеВсе студенты IIT выдающиеся
Все выдающиеся люди - ученые
____________________________________
Все студенты IIT - ученые
СК – студенты IIT
ВЛ – выдающиеся люди
У - ученые
13. Теорема
Если n2 четно, то и n четно.Доказательство: Доказательство методом контрапозиции
p q q p
Т.е. доказательство q p эквивалентно доказательству
p q
Утверждение q p означает:
Если n не является четным, то n2 тоже не является четным.
Пусть n - целое число, не является четным
n = 2L +1
n2 = (2L + 1) 2 = 4L2 + 4L +1 = 2 (2L2 + 2L) + 1.
Если
J = 2L2 + 2L
n2 = 2J + 1
Ч.т.д.
14.
Множество целых чисел Z содержит подмножество Nположительных целых чисел.
Аксиомы:
1. Целое число 1 есть положительное целое число.
2. Множество положительных чисел замкнуто относительно
сложения и умножения, т.е. Если a и b - целые
положительные числа, то a + b и a b – целые
положительные числа.
3. (Аксиома трихотомии) Для каждого целого числа a
истинным является одно из утверждений:
а) a – положительное целое число;
б) a = 0;
в) – a - отрицательное целое число.
15. Применение доказательства методом перебора.
Выбор из трех возможностей обычно имеет вид16. Теорема
Пусть n - целое число. Тогда n2 0.Доказательство:
n – целое число, по аксиоме трихотомии либо положительное,
либо отрицательное, либо равно 0.
Если n положительно, то n n положительно по аксиоме 2,
n2 0.
Если отрицательно, то n = - m для некоторого положительного
целого m.
n2 = (-m)(-m) = m2 опять является положительным, n2 0.
Если n = 0, то n2 = 0 n2 0.
n2 0. Ч.т.д.