🗊Презентация Логика предикатов

Категория: Математика
Нажмите для полного просмотра!
Логика предикатов, слайд №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Логика предикатов, слайд №36Логика предикатов, слайд №37Логика предикатов, слайд №38Логика предикатов, слайд №39Логика предикатов, слайд №40Логика предикатов, слайд №41Логика предикатов, слайд №42
Скачать

Содержание ▲

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

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

Слайд 1


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

Слайд 2


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

Слайд 3


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

Слайд 4


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

Слайд 5


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

Слайд 6


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

Слайд 7


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

Слайд 8


Определение Двухместный предикат Р(x,y) - функция двух переменных x и y, определенная на множестве М=М1хМ2 и принимающая значения из множества {1;0}. Пример Q(x, y) – “x=y” - предикат равенства на множестве RхR=R2 "Икс любит Игрека" -двухместный предикат.
Описание слайда:
Определение Двухместный предикат Р(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 –предметными переменными
Описание слайда:
Определение n-местный предикат - это функция определенная на наборах длины n элементов некоторого множества M, принимающая значения в области True, False. Множество М называется предметной областью предиката, а x1, x2, ..xn –предметными переменными

Слайд 10


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

Слайд 11


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

Слайд 12


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

Слайд 13


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

Слайд 14


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

Слайд 15


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

Слайд 16


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

Слайд 17


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

Слайд 18


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

Слайд 19


Логика предикатов, слайд №19
Описание слайда:

Слайд 20


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

Слайд 21


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

Слайд 22


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

Слайд 23


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

Слайд 24


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

Слайд 25


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

Слайд 26


Логика предикатов, слайд №26
Описание слайда:

Слайд 27


«квантор можно вносить и выносить за скобки в конъюнкции»
Описание слайда:
«квантор можно вносить и выносить за скобки в конъюнкции»

Слайд 28


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

Слайд 29


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

Слайд 30


Логика предикатов, слайд №30
Описание слайда:

Слайд 31


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

Слайд 32


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

Слайд 33


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

Слайд 34


Логика предикатов, слайд №34
Описание слайда:

Слайд 35


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

Слайд 36


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

Слайд 37


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

Слайд 38


Логика предикатов, слайд №38
Описание слайда:

Слайд 39


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

Слайд 40


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

Слайд 41


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

Слайд 42


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

Скачать

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