Логика предикатов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Содержание ▲

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

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

Слайд 1

Описание слайда:

Лекция Логика предикатов

Слайд 2

Описание слайда:

Логика высказываний оперирует простейшими высказываниями, которые могут быть или истинными, или ложными. В разговорном языке встречаются более сложные повествовательные предложения, истинность которых может меняться при изменении объектов, о которых идет речь.

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

Определение предиката Формально предикат - функция, аргументами которой могут быть ПРОИЗВОЛЬНЫЕ ОБ'ЕКТЫ из некоторого множества, а значения функции "истина" или "ложь". Предикат можно рассматривать как расширение понятия высказывания.

Слайд 5

Описание слайда:

Пример "Маша любит кашу" "Даша любит кашу" "Саша любит кашу« предикат "Икс любит кашу" и вместо неизвестного Икс могут быть либо Маша, либо Даша, либо Саша. Подстановка вместо Икс имени конкретного ребенка превращает предикат в обычное высказывание.

Слайд 6

Описание слайда:

Определение Предикат - это высказывание-функция, значение (истина/ложь) которого зависит от параметров

Слайд 7

Описание слайда:

Определение Одноместным предикатом Р(x) -произвольная функция переменного x, определенная на множестве M и принимающая значение из множества {1; 0}. "ВСЕ любят Игрека" - одноместный предикат. Замечание Высказывания – это 0(нуль)-местный предикат, булева функция – n-местный предикат. "ВСЕ любят КОЙ-КОГО [некоторого]" - нульместный предикат, то есть высказывание.

Слайд 8

Описание слайда:

Определение Двухместный предикат Р(x,y) - функция двух переменных x и y, определенная на множестве М=М1хМ2 и принимающая значения из множества {1;0}. Пример Q(x, y) – “x=y” - предикат равенства на множестве RхR=R2 "Икс любит Игрека" -двухместный предикат.

Слайд 9

Описание слайда:

Определение n-местный предикат - это функция определенная на наборах длины n элементов некоторого множества M, принимающая значения в области True, False. Множество М называется предметной областью предиката, а x1, x2, ..xn –предметными переменными

Слайд 10

Описание слайда:

Определение. Предикат называется тождественно истинным (тождественно ложным), если на всех наборах своих переменных принимает значение 1 (0), выполнимым, если на некотором наборе своих переменных принимает значение 1

Слайд 11

Описание слайда:

Логические операции над предикатами Замечание Предикаты при подстановки переменных становятся высказываниями, поэтому с предикатами можно производить все логические операции Для предикатов справедливы логические операции и две новые операции, специфические. - операциями навешивания кванторов или операциями квантификации. Эти операции соответствуют фразам "для всех" - квантор общности и "некоторые" - квантор существования. Выражение "существует точно одно Х такое, что..." - квантор существования и единственности

Слайд 12

Описание слайда:

Пример (Экзюпери) "Ты любишь потому, что ты любишь. Не существует причин, чтобы любить." можно записать в виде:

Слайд 13

Описание слайда:

Определение Присоединение квантора с переменной к предикатной формуле называется навешивание квантора на переменную х. Переменная при этом называется связанной и вместо нее подставлять константы уже нельзя. Если квантор навешивается на формулу с несколькими переменными, то он уменьшает число несвязанных переменных в этой формуле

Слайд 14

Описание слайда:

Переменную х в предикате Р(х) называют свободной (ей можно придавать различные значения из М), в высказывании же х называют связанной квантором всеобщности.

Слайд 15

Описание слайда:

Переменная , на которую навешивается квантор называется связанной. Выражение, на которое навешивается квантор, называется областью действия квантора

Слайд 16

Описание слайда:

Пример Предикат "ВСЕ любят кашу": Возьмем отрицание "НЕ ВЕРНО, что ВСЕ любят кашу". Это равносильно (по закону Де Моргана!) заявлению: "НЕКОТОРЫЕ НЕ любят кашу. отрицание "задвинули" за квантор, в результате чего квантор сменился на противоположный

Слайд 17

Описание слайда:

Кванторы общности и существования называют двойственными относительно друг друга. Вот некоторые "классические примеры"несоответствия языка предикатов и естественного языка

Слайд 18

Описание слайда:

Пример предикат "Собакам и кошкам вход воспрещен". "ДЛЯ ВСЕХ иксов справедливо: ЕСЛИ икс - собака И икс - кошка, ТО иксу вход запрещен" Ясно что таких иксов, которые бы были одновременно собакой и кошкой не существует! Как, впрочем, и таких игреков. Поэтому ЕСЛИ икс - собака ИЛИ икс - кошка, ТО иксу вход запрещен"

Слайд 19

Описание слайда:

Слайд 20

Описание слайда:

Пример

Слайд 21

Описание слайда:

Свойства кванторов 1. Коммутативность одноименных кванторов 2.

Слайд 22

Описание слайда:

Основные законы, содержащие кванторы

Слайд 23

Описание слайда:

Равносильные формулы логики предикатов Определение Две формулы логики предикатов А и В называются равносильными на области М, если они принимают одинаковые логические значения при всех значениях входящих в них переменных, отнесенных к области М.

Слайд 24

Описание слайда:

Правила переноса кванторов через отрицание или законы де Моргана для кванторов Пусть А(х) и В(х) – переменные предикаты, а С – переменное высказывание (или формула, не содержащая х). Тогда имеют место равносильности

Слайд 25

Описание слайда:

Правила переноса кванторов через отрицание или законы де Моргана для кванторов

Слайд 26

Описание слайда:

Слайд 27

Описание слайда:

«квантор можно вносить и выносить за скобки в конъюнкции»

Слайд 28

Описание слайда:

постоянное высказывание можно вносить под знак квантора всеобщности и выносить из под знака в конъюнкции, дизъюнкции и импликации

Слайд 29

Описание слайда:

квантор существования можно вносить и выносить за скобки в дизъюнкции»

Слайд 30

Описание слайда:

Слайд 31

Описание слайда:

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

Слайд 32

Описание слайда:

Среди нормальных форм формул логики предикатов выделяют так называемую предваренную (префиксную) нормальную форму (ПНФ). В ней кванторные операции либо полностью отсутствуют, либо они используются после всех операций алгебры логики

Слайд 33

Описание слайда:

Пример

Слайд 34

Описание слайда:

Слайд 35

Описание слайда:

Алгоритм получения (приведения) ПНФ. Формула B называется предваренной нормальной формой формулы A , если она удовлетворяет ниже перечисленным требованиям: 1. Формулы А и B равносильны. 2. Формула B удовлетворяет следующим условиям: а) используются логические операции ┐, v , & , при этом отрицание применяется только в атомарных формулах; б) операции кванторов следуют за операциями алгебры ┐, v , &

Слайд 36

Описание слайда:

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

Слайд 37

Описание слайда:

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

Слайд 38

Описание слайда:

Слайд 39

Описание слайда:

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

Слайд 40

Описание слайда:

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

Слайд 41

Описание слайда:

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