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