🗊Презентация Исчисление предикатов

Категория: Математика
Нажмите для полного просмотра!
Исчисление предикатов, слайд №1Исчисление предикатов, слайд №2Исчисление предикатов, слайд №3Исчисление предикатов, слайд №4Исчисление предикатов, слайд №5Исчисление предикатов, слайд №6Исчисление предикатов, слайд №7Исчисление предикатов, слайд №8Исчисление предикатов, слайд №9Исчисление предикатов, слайд №10Исчисление предикатов, слайд №11Исчисление предикатов, слайд №12Исчисление предикатов, слайд №13Исчисление предикатов, слайд №14Исчисление предикатов, слайд №15Исчисление предикатов, слайд №16Исчисление предикатов, слайд №17Исчисление предикатов, слайд №18Исчисление предикатов, слайд №19Исчисление предикатов, слайд №20Исчисление предикатов, слайд №21Исчисление предикатов, слайд №22Исчисление предикатов, слайд №23Исчисление предикатов, слайд №24Исчисление предикатов, слайд №25Исчисление предикатов, слайд №26Исчисление предикатов, слайд №27Исчисление предикатов, слайд №28Исчисление предикатов, слайд №29Исчисление предикатов, слайд №30Исчисление предикатов, слайд №31Исчисление предикатов, слайд №32Исчисление предикатов, слайд №33Исчисление предикатов, слайд №34Исчисление предикатов, слайд №35
Скачать

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Исчисление предикатов. Доклад-сообщение содержит 35 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1


Лекция Исчисление предикатов
Описание слайда:
Лекция Исчисление предикатов

Слайд 2


Алгоритм получения (приведения) ПНФ. Шаг 1. Исключить связки эквивалентности ( ~ ) и импликации (→). x ~ у = (x → у) & (y →x), A → B =(Ā v B). Шаг 2. Переименовать, если необходимо, связанные переменные таким образом, чтобы никакая переменная не имела бы одновременно свободных и связанных вхождений
Описание слайда:
Алгоритм получения (приведения) ПНФ. Шаг 1. Исключить связки эквивалентности ( ~ ) и импликации (→). x ~ у = (x → у) & (y →x), A → B =(Ā v B). Шаг 2. Переименовать, если необходимо, связанные переменные таким образом, чтобы никакая переменная не имела бы одновременно свободных и связанных вхождений

Слайд 3


Шаг 3. Удалить те квантификации, область действия которых не содержит вхождений квантифицированной переменной. Шаг 4. Перенести отрицания внутри формулы в соответствия со следующими правилами:
Описание слайда:
Шаг 3. Удалить те квантификации, область действия которых не содержит вхождений квантифицированной переменной. Шаг 4. Перенести отрицания внутри формулы в соответствия со следующими правилами:

Слайд 4


Пример
Описание слайда:
Пример

Слайд 5


Скулемовские функции Приведение формулы ЛП к сколемовской форме (сколемизация) призвано обеспечить дальнейшее упрощение логических представлений и облегчить введение процедур машинной обработки в ЛП. Отправной точкой сколемизации является предваренная нормальная форма, матрица которой приведена к конъюнктивной нормальной форме (КНФ). Цель сколемизации - исключение Ǝ- квантификаций.
Описание слайда:
Скулемовские функции Приведение формулы ЛП к сколемовской форме (сколемизация) призвано обеспечить дальнейшее упрощение логических представлений и облегчить введение процедур машинной обработки в ЛП. Отправной точкой сколемизации является предваренная нормальная форма, матрица которой приведена к конъюнктивной нормальной форме (КНФ). Цель сколемизации - исключение Ǝ- квантификаций.

Слайд 6


Алгоритм получения сколемовской формы 1) сопоставить каждой Ǝ- квантифицированной переменной список - квантифицированных переменных, предшествующих ей, а также некоторую еще не использованную функциональную константу, число мест, у которой равно мощности списка. Данная константа будет представлять сколемовскую функцию;
Описание слайда:
Алгоритм получения сколемовской формы 1) сопоставить каждой Ǝ- квантифицированной переменной список - квантифицированных переменных, предшествующих ей, а также некоторую еще не использованную функциональную константу, число мест, у которой равно мощности списка. Данная константа будет представлять сколемовскую функцию;

Слайд 7


2) в матрице формулы заменить каждое вхождение Ǝ-квантифицированной переменной на некоторый терм. Этот терм является функциональной константой, соответствующей данной переменной и снабженной списком аргументов, также соответствующим той же самой переменной; 3) устранить из формулы все Ǝ - квантификации.
Описание слайда:
2) в матрице формулы заменить каждое вхождение Ǝ-квантифицированной переменной на некоторый терм. Этот терм является функциональной константой, соответствующей данной переменной и снабженной списком аргументов, также соответствующим той же самой переменной; 3) устранить из формулы все Ǝ - квантификации.

Слайд 8


Каузальная форма -сколемовская форма, матрица которой приведена к КНФ. Любая сколемовская форма допускает эквивалентную каузальную форму
Описание слайда:
Каузальная форма -сколемовская форма, матрица которой приведена к КНФ. Любая сколемовская форма допускает эквивалентную каузальную форму

Слайд 9


Пример
Описание слайда:
Пример

Слайд 10


Общезначимость и выполнимость формул логики предикатов. Определение Формула А логики предикатов называется выполнимой в области М, если существуют значения переменных входящих в эту формулу и отнесенных к области М (иначе – существует модель), при которых формула А принимает истинные значения. Определение Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели).
Описание слайда:
Общезначимость и выполнимость формул логики предикатов. Определение Формула А логики предикатов называется выполнимой в области М, если существуют значения переменных входящих в эту формулу и отнесенных к области М (иначе – существует модель), при которых формула А принимает истинные значения. Определение Формула А логики предикатов называется общезначимой, если она тождественна истинна на всякой области (на любой модели).

Слайд 11


Все логические законы, представленный в ЛВ формулами являются общезначимыми формулами логики предикатов . Общезначимость формулы логики предикатов, например, F обозначается ├F Все общезначимые формулы могут быть источниками новых ├ формул.
Описание слайда:
Все логические законы, представленный в ЛВ формулами являются общезначимыми формулами логики предикатов . Общезначимость формулы логики предикатов, например, F обозначается ├F Все общезначимые формулы могут быть источниками новых ├ формул.

Слайд 12


Определение Формула А логики предикатов называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу ( на данной модели).
Описание слайда:
Определение Формула А логики предикатов называется тождественно ложной в области М, если она принимает ложные значения для всех значений переменных, входящих в эту формулу ( на данной модели).

Слайд 13


Теорема Черча Теорема (Теорема Черча). Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.
Описание слайда:
Теорема Черча Теорема (Теорема Черча). Не существует алгоритма, который для любой формулы логики предикатов устанавливает, общезначима она или нет.

Слайд 14


Пример Из тождественно истинной формулы логики высказываний Получаем общезначимую формулу
Описание слайда:
Пример Из тождественно истинной формулы логики высказываний Получаем общезначимую формулу

Слайд 15


Проблема разрешимости Существуют ли алгоритмы, позволяющие для любой формулы А логики предикатов установить, к какому типу (классу) она относится, т.е. является ли она общезначимой, выполнимой или тождественно ложной (невыполнимой). Если бы такой алгоритм существовал, то он сводился бы к критерию тождественной истинности любой формулы логики предикатов. Отметим, что, в отличие от алгебры логики, в логике предикатов не применим метод перебора всех вариантов значений переменных, входящих в формулу, так как таких вариантов может быть бесконечное множество
Описание слайда:
Проблема разрешимости Существуют ли алгоритмы, позволяющие для любой формулы А логики предикатов установить, к какому типу (классу) она относится, т.е. является ли она общезначимой, выполнимой или тождественно ложной (невыполнимой). Если бы такой алгоритм существовал, то он сводился бы к критерию тождественной истинности любой формулы логики предикатов. Отметим, что, в отличие от алгебры логики, в логике предикатов не применим метод перебора всех вариантов значений переменных, входящих в формулу, так как таких вариантов может быть бесконечное множество

Слайд 16


Прямая, обратная и противоположная теоремы Определение Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу.
Описание слайда:
Прямая, обратная и противоположная теоремы Определение Пара теорем, у которых условие одной является заключением второй, а условие второй является заключением первой, называются взаимно обратными друг другу.

Слайд 17


Определение Пара теорем, у которых условие и заключение одной являются отрицанием соответственно условия и заключения другой, называются взаимно противоположными
Описание слайда:
Определение Пара теорем, у которых условие и заключение одной являются отрицанием соответственно условия и заключения другой, называются взаимно противоположными

Слайд 18


Пример Теорема “Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником ” (1) обратной является Теорема “Если четырехугольник является прямоугольником, то его диагонали равны” (2). противоположной является Теорема «Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником ” (3), а для теоремы (2) противоположной является Теорема “Если четырехугольник не является прямоугольником, то его диагонали не равны ” (4). теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными.
Описание слайда:
Пример Теорема “Если в четырехугольнике диагонали равны, то четырехугольник является прямоугольником ” (1) обратной является Теорема “Если четырехугольник является прямоугольником, то его диагонали равны” (2). противоположной является Теорема «Если в четырехугольнике диагонали не равны, то четырехугольник не является прямоугольником ” (3), а для теоремы (2) противоположной является Теорема “Если четырехугольник не является прямоугольником, то его диагонали не равны ” (4). теоремы (1) и (4) являются одновременно ложными, а теоремы (2) и (3) одновременно истинными.

Слайд 19


Вывод: прямая и обратная теоремы, вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая – ложной. Однако легко показать, что теоремы (1) и (4), а также (2) и (3) всегда равносильны
Описание слайда:
Вывод: прямая и обратная теоремы, вообще говоря, не равносильны, т. е. одна из них может быть истинной, а другая – ложной. Однако легко показать, что теоремы (1) и (4), а также (2) и (3) всегда равносильны

Слайд 20


Необходимые и достаточные условия Некоторые теоремы существования сформулированы в виде « … для того, чтобы…, необходимо и достаточно, что …», или « … тогда и только тогда, когда …», а это конструкция
Описание слайда:
Необходимые и достаточные условия Некоторые теоремы существования сформулированы в виде « … для того, чтобы…, необходимо и достаточно, что …», или « … тогда и только тогда, когда …», а это конструкция

Слайд 21


предикат является истинным для всех x в том и только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x).
Описание слайда:
предикат является истинным для всех x в том и только в том случае, когда множество истинности предиката Р(х) содержится в множестве истинности предиката Q(x).

Слайд 22


При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) – достаточным условием для Q(x
Описание слайда:
При этом говорят, что предикат Q(x) логически следует из предиката Р(х), и предикат Q(x) называют необходимым условием для предиката Р(х), а предикат Р(х) – достаточным условием для Q(x

Слайд 23


Неполнота математики Класс всех теорем исчисления предикатов совпадает с классом общезначимых формул . В 1889 г. Пеано предложил свои аксиомы для аксиоматизации понятия натурального числа и, после этого была создана формальная теория, известная под названием формальная арифметика. Это теория является расширением исчисления предикатов
Описание слайда:
Неполнота математики Класс всех теорем исчисления предикатов совпадает с классом общезначимых формул . В 1889 г. Пеано предложил свои аксиомы для аксиоматизации понятия натурального числа и, после этого была создана формальная теория, известная под названием формальная арифметика. Это теория является расширением исчисления предикатов

Слайд 24


Аксиомы Пеано 1) 1 есть натуральное число; 2) следующее за натуральным числом есть натуральное число; 3) 1 не следует ни за каким натуральным числом; 4) если натуральное число a следует за натуральным числом b и за натуральным числом c, то натуральные числа b и c тождественны; 5) если какое-либо предложение доказано для 1 и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за n натурального числа, то это предложение верно для всех натуральных чисел (принцип математической индукции).
Описание слайда:
Аксиомы Пеано 1) 1 есть натуральное число; 2) следующее за натуральным числом есть натуральное число; 3) 1 не следует ни за каким натуральным числом; 4) если натуральное число a следует за натуральным числом b и за натуральным числом c, то натуральные числа b и c тождественны; 5) если какое-либо предложение доказано для 1 и если из допущения, что оно верно для натурального числа n, вытекает, что оно верно для следующего за n натурального числа, то это предложение верно для всех натуральных чисел (принцип математической индукции).

Слайд 25


Теорема Геделя о неполноте Теорема. Всякая естественная непротиворечивая аксиоматическая теория T (формализация) арифметики или любой другой математической теории, содержащей арифметику (например, теория множеств), неполна и непополнима в том смысле, что а) в T имеются содержательно истинные неразрешимые формулы, т. е. такие формулы A, что ни A, ни отрицание A не выводимы (не доказуемы) в T; б) каким бы конечным множеством дополнительных аксиом не расширить систему T, в новой, усиленной таким образом формальной системе неизбежно появятся свои неразрешимые формулы.
Описание слайда:
Теорема Геделя о неполноте Теорема. Всякая естественная непротиворечивая аксиоматическая теория T (формализация) арифметики или любой другой математической теории, содержащей арифметику (например, теория множеств), неполна и непополнима в том смысле, что а) в T имеются содержательно истинные неразрешимые формулы, т. е. такие формулы A, что ни A, ни отрицание A не выводимы (не доказуемы) в T; б) каким бы конечным множеством дополнительных аксиом не расширить систему T, в новой, усиленной таким образом формальной системе неизбежно появятся свои неразрешимые формулы.

Слайд 26


Вывод : в сложной аксиоматической системе существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все задачки имеют решения?!
Описание слайда:
Вывод : в сложной аксиоматической системе существуют формулы, которые нельзя ни доказать, ни опровергнуть. Может в этом причина, что не все задачки имеют решения?!

Слайд 27


Аксиомы и основные правила вывода исчисления предикатов Аксиомами ИП являются все 4 группы аксиом ИВ и 5 группа :
Описание слайда:
Аксиомы и основные правила вывода исчисления предикатов Аксиомами ИП являются все 4 группы аксиом ИВ и 5 группа :

Слайд 28


Правила вывода ИП 1) правила вывода ИВ (подстановка ПП и заключение ( МР));
Описание слайда:
Правила вывода ИП 1) правила вывода ИВ (подстановка ПП и заключение ( МР));

Слайд 29


Исчисление предикатов, слайд №29
Описание слайда:

Слайд 30


Пример Даны два предиката: B(x) = "x делится на 6"; A(x) = "x делится на 3". применение правила П2 неправомерно, если B зависит от x
Описание слайда:
Пример Даны два предиката: B(x) = "x делится на 6"; A(x) = "x делится на 3". применение правила П2 неправомерно, если B зависит от x

Слайд 31


Исчисление предикатов, слайд №31
Описание слайда:

Слайд 32


Дополнительные правила вывода для исчисления предикатов
Описание слайда:
Дополнительные правила вывода для исчисления предикатов

Слайд 33


Исчисление предикатов, слайд №33
Описание слайда:

Слайд 34


Пример Всякое нечетное натуральное число есть разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно, 5 – разность квадратов двух натуральных чисел Решение A(x) = “x – нечетное число”. B(x) – “x – разность квадратов двух чисел”.
Описание слайда:
Пример Всякое нечетное натуральное число есть разностью квадратов двух натуральных чисел. 5 – натуральное число. Следовательно, 5 – разность квадратов двух натуральных чисел Решение A(x) = “x – нечетное число”. B(x) – “x – разность квадратов двух чисел”.

Слайд 35


Метод резолюций в ИП Главная идея метода резолюций если одна и та же формула появляется в одном дизъюнкте без отрицания, а в другом - с отрицанием, то дизъюнкт, называемый резольвентой и получаемый в результате соединения этих двух дизъюнктов, из которых вычеркнута упоминавшаяся повторяющаяся формула является следствием указанных дизъюнктов
Описание слайда:
Метод резолюций в ИП Главная идея метода резолюций если одна и та же формула появляется в одном дизъюнкте без отрицания, а в другом - с отрицанием, то дизъюнкт, называемый резольвентой и получаемый в результате соединения этих двух дизъюнктов, из которых вычеркнута упоминавшаяся повторяющаяся формула является следствием указанных дизъюнктов

Скачать

Похожие презентации
Mypresentation.ru
Загрузить презентацию