Содержание
- 2. Алгоритм получения (приведения) ПНФ. Шаг 1. Исключить связки эквивалентности ( ~ ) и импликации (→). x
- 3. Шаг 3. Удалить те квантификации, область действия которых не содержит вхождений квантифицированной переменной. Шаг 4. Перенести
- 4. Пример
- 5. Скулемовские функции Приведение формулы ЛП к сколемовской форме (сколемизация) призвано обеспечить дальнейшее упрощение логических представлений и
- 6. Алгоритм получения сколемовской формы 1) сопоставить каждой Ǝ- квантифицированной переменной список ∀- квантифицированных переменных, предшествующих ей,
- 7. 2) в матрице формулы заменить каждое вхождение Ǝ-квантифицированной переменной на некоторый терм. Этот терм является функциональной
- 8. Каузальная форма -сколемовская форма, матрица которой приведена к КНФ. Любая сколемовская форма допускает эквивалентную каузальную форму
- 9. Пример
- 10. Общезначимость и выполнимость формул логики предикатов. Определение Формула А логики предикатов называется выполнимой в области М,
- 11. Все логические законы, представленный в ЛВ формулами являются общезначимыми формулами логики предикатов . Общезначимость формулы логики
- 12. Определение Формула А логики предикатов называется тождественно ложной в области М, если она принимает ложные значения
- 13. Теорема Черча Теорема (Теорема Черча). Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима
- 14. Пример Из тождественно истинной формулы логики высказываний Получаем общезначимую формулу
- 15. Проблема разрешимости Существуют ли алгоритмы, позволяющие для любой формулы А логики предикатов установить, к какому типу
- 16. Прямая, обратная и противоположная теоремы Определение Пара теорем, у которых условие одной является заключением второй, а
- 17. Определение Пара теорем, у которых условие и заключение одной являются отрицанием соответственно условия и заключения другой,
- 18. Пример Теорема “Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником ” (1) обратной является Теорема
- 19. Вывод: прямая и обратная теоремы, вообще говоря, не равносильны, т. е. одна из них может быть
- 20. Необходимые и достаточные условия Некоторые теоремы существования сформулированы в виде « … для того, чтобы…, необходимо
- 21. предикат является истинным для всех x в том и только в том случае, когда множество истинности
- 22. При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым
- 23. Неполнота математики Класс всех теорем исчисления предикатов совпадает с классом общезначимых формул . В 1889 г.
- 24. Аксиомы Пеано 1) 1 есть натуральное число; 2) следующее за натуральным числом есть натуральное число; 3)
- 25. Теорема Геделя о неполноте Теорема. Всякая естественная непротиворечивая аксиоматическая теория T (формализация) арифметики или любой другой
- 26. Вывод : в сложной аксиоматической системе существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в
- 27. Аксиомы и основные правила вывода исчисления предикатов Аксиомами ИП являются все 4 группы аксиом ИВ и
- 28. Правила вывода ИП 1) правила вывода ИВ (подстановка ПП и заключение ( МР));
- 30. Пример Даны два предиката: B(x) = "x делится на 6"; A(x) = "x делится на 3".
- 32. Дополнительные правила вывода для исчисления предикатов
- 34. Пример Всякое нечетное натуральное число есть разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно,
- 36. Скачать презентацию