Содержание
- 2. Предикаты Предикат – это функция вида Р(х1, х2, …, хn)=y, Здесь х1, х2, …, хn -
- 3. Предикаты где предметные множества, поле предиката.
- 4. Предикаты Переменная y – может принимать значения из множества В={0, 1}. Здесь 0 – «нет», «ложь»;
- 5. Предикаты Например: 1) на множестве N задан предикат Р(х) – «х является четным числом». Тогда Р(1)=0,
- 6. Предикаты Подмножество I множества М называется областью истинности предиката Р, если наборы значений предметных переменных из
- 7. Предикаты Например: Для предиката Q(x,y) область истинности I – множество всех точек плоскости с натуральными координатами,
- 8. Предикаты
- 9. Предикаты Над предикатами можно совершать знакомые нам логические операции: Конъюнкцию, дизъюнкцию, отрицание, импликацию, и т. д.
- 10. Предикаты При этом область истинности полученных предикатов изменяется по тем же правилам: и так далее.
- 11. Предикаты Однако в логике предикатов есть операция, которая отсутствуют в логике высказываний. Квантификация или квантирование В
- 12. Предикаты Существуют два вида кванторов: Квантор общности «для любого, для каждого». Квантор существования «существует, найдется».
- 13. Предикаты Предикатная формула: истинна тогда и только тогда, когда предикат Р(х)=1 при любом х, ложна тогда
- 14. Предикаты Предикатная формула: истинна тогда и только тогда, когда найдется х, при котором предикат Р(х)=1, ложна
- 15. Замечание Когда в предикате Р(х) переменная х связывается квантором, она перестает влиять на значение предиката и
- 16. Предикаты Например: Р(х) – «х является четным числом» на множестве N Тогда так как есть х=3,
- 17. Предикаты Если предикат имеет более 1 переменной, то ее квантификация приводит к уменьшению числа переменных на
- 18. Предикаты новый предикат от одной переменной у – «любое натуральное число х меньше либо равно у».
- 19. Предикаты Таким образом, предикат то есть является функцией -константой
- 20. Предикаты новый предикат от одной переменной у – «найдется натуральное число х меньше либо равно у».
- 21. Предикаты Таким образом, предикат то есть тоже является функцией -константой
- 22. Предикаты Кванторы можно навесить на все переменные предиката. Тогда предикат станет высказыванием. Например: предикат Q(x,y) –
- 23. Предикаты так как неверно то, что любой натуральный х меньше либо равен любого натурального у. Например,
- 24. Предикаты так как верно то, что любой натуральный х меньше либо равен некоторого натурального у. Например,
- 25. Предикаты так как неверно то, что найдется такой натуральный у, который будет больше либо равен любого
- 26. Предикаты так как верно то, что найдется такой натуральный х, который будет меньше либо равен любого
- 27. Предикаты так как верно то, что любой натуральный у, больше либо равен некоторого натурального х. Например,
- 28. Предикаты так как верно то, что найдутся такие натуральные х и у, что х меньше либо
- 29. Логика предикатов Логика предикатов, как и логика высказываний, – свод правил, по которым строятся формулы связывающие
- 30. Логика предикатов Равносильные предикатные формулы – те, у которых область истинности совпадает.
- 31. Логика предикатов Интерпретация – это сопоставление каждому предикатному символу в формуле определенного предиката.
- 32. Логика предикатов Пусть формулы F и G содержат одно и тоже множество свободных переменных. Формулы F
- 33. Логика предикатов Например: Тогда предикатные формулы: являются равносильными в данной интерпретации, так как При других интерпретациях
- 34. Логика предикатов Формулы F и G равносильны на множестве М – если они равносильны во всех
- 35. Логика предикатов Например: Равносильны в любой интерпретации на множестве М, если М состоит из одного элемента.
- 36. Логика предикатов Формулы F и G равносильны в логике предикатов – если они равносильны на всех
- 37. Логика предикатов Например: Тогда F и G равносильны на любых множествах и при любых интерпретациях предиката
- 38. Равносильные формулы Для предикатных формул сохраняются все равносильности (эквивалентности) алгебры логики. Например, закон де Моргана:
- 39. Свойства операций над предикатами Перенос квантора через отрицание Здесь и далее, знак равносильности ≡ заменен знаком
- 40. Свойства операций над предикатами Вынос квантора за скобки
- 41. Свойства операций над предикатами Вынос квантора за скобки
- 42. Свойства операций над предикатами Закон коммутативности для одноименных кванторов:
- 43. Свойства операций над предикатами Коммутативность дает возможность использовать более краткую запись:
- 44. Равносильные формулы Проверить равносильность формулы в логике предикатов, не так просто, как в логике высказываний. Высказывание
- 45. Истинность в логике предикатов Предикатная формула F называется выполнимой (непротиворечивой), если существует интерпретация входящих в нее
- 46. Истинность в логике предикатов Предикатная формула F называется тождественно истинной (общезначимой), если при любой интерпретация входящих
- 47. Истинность в логике предикатов Предикатная формула F называется тождественно ложной (противоречивой), если при любой интерпретация входящих
- 48. Истинность в логике предикатов Например: Тождественно истинная формула. Тождественно ложная формула
- 49. Истинность в логике предикатов Замечание 1 Формула F – общезначима тогда и только тогда, когда ¬F
- 50. Истинность в логике предикатов Замечание 3 Если F и G – равносильные формулы в логике предикатов,
- 51. Истинность в логике предикатов Замечание 4 Если формула W = F → G общезначима, то выполняется:
- 52. Истинность в логике предикатов Замечание 5 Если y не входит в формулу P(x), то следующие формулы
- 53. Истинность в логике предикатов Квантор общности является обобщением конъюнкции, поэтому справедлива формула:
- 54. Истинность в логике предикатов Квантор существования является обобщением дизъюнкции, поэтому справедлива формула:
- 55. Истинность в логике предикатов Замечание 6 Если в формулах (11) и (12) поменять местами кванторы, то
- 56. Истинность в логике предикатов В таких случаях говорят, что левая часть утверждения более сильная, чем правая.
- 57. Истинность в логике предикатов В таком случае, надо воспользоваться правилом: То есть, если переменная связана квантором,
- 58. Истинность в логике предикатов В выражениях (13) и (14) надо сделать замену переменной, после чего воспользоваться
- 59. Истинность в логике предикатов
- 61. Скачать презентацию