Презентация Логика предикатов. ДМ. 13 онлайн
На нашем сайте вы можете скачать и просмотреть онлайн доклад-презентацию на тему Логика предикатов. ДМ. 13 абсолютно бесплатно. Урок-презентация на эту тему содержит всего 60 слайдов. Все материалы созданы в программе PowerPoint и имеют формат ppt или же pptx. Материалы и темы для презентаций взяты из открытых источников и загружены их авторами, за качество и достоверность информации в них администрация сайта не отвечает, все права принадлежат их создателям. Если вы нашли то, что искали, отблагодарите авторов - поделитесь ссылкой в социальных сетях, а наш сайт добавьте в закладки.
Оцените презентацию от 1 до 5 баллов!
- Тип файла:ppt / pptx (powerpoint)
- Всего слайдов:60 слайдов
- Для класса:1,2,3,4,5,6,7,8,9,10,11
- Размер файла:489.00 kB
- Просмотров:73
- Скачиваний:0
- Автор:неизвестен
Слайды и текст к этой презентации:
№1 слайд
Содержание слайда:
№2 слайд
Содержание слайда: Предикаты
Предикат – это функция вида
Р(х1, х2, …, хn)=y,
Здесь х1, х2, …, хn - предметные переменные; y - значение предиката.
№3 слайд
Содержание слайда: Предикаты
где предметные множества,
поле предиката.
№4 слайд
Содержание слайда: Предикаты
Переменная y – может принимать значения из множества
В={0, 1}.
Здесь 0 – «нет», «ложь»;
1 – «да», «истина».
№5 слайд
Содержание слайда: Предикаты
Например:
1) на множестве N задан предикат Р(х) – «х является четным числом».
Тогда Р(1)=0, Р(2)=1.
2) На множестве N×N задан предикат Q(x,y) – «x≤y».
Тогда
Q(1,1)=1; Q(1,2)=1; Q(3,2) =0.
№6 слайд
Содержание слайда: Предикаты
Подмножество I множества М называется областью истинности предиката Р, если наборы значений предметных переменных из множества I обращают предикат P в 1.
№7 слайд
Содержание слайда: Предикаты
Например:
Для предиката Q(x,y) область истинности I – множество всех точек плоскости с натуральными координатами, лежащие на диагонали первого координатного угла и выше.
№8 слайд
Содержание слайда: Предикаты
№9 слайд
Содержание слайда: Предикаты
Над предикатами можно совершать знакомые нам логические операции:
Конъюнкцию, дизъюнкцию, отрицание, импликацию, и т. д.
Например:
Р(х,у) – «х<y», R(x,y) – «x=y».
Тогда ⌐ Р(х,у) – «х≥у»,
Р(х,у)V R(x,y) – «х≤у» и т. д.
№10 слайд
Содержание слайда: Предикаты
При этом область истинности полученных предикатов изменяется по тем же правилам:
и так далее.
№11 слайд
Содержание слайда: Предикаты
Однако в логике предикатов есть операция, которая отсутствуют в логике высказываний.
Квантификация или квантирование
В результате этой операции на переменную предиката навешивается квантор (переменная связывается квантором). Переменная при этом становится связанной. Переменная, не связанная называется свободной.
№12 слайд
Содержание слайда: Предикаты
Существуют два вида кванторов:
Квантор общности «для любого, для каждого».
Квантор существования «существует, найдется».
№13 слайд
Содержание слайда: Предикаты
Предикатная формула:
истинна тогда и только тогда, когда предикат Р(х)=1 при любом х,
ложна тогда и только тогда, когда найдется х, при котором предикат Р(х)=0.
№14 слайд
Содержание слайда: Предикаты
Предикатная формула:
истинна тогда и только тогда, когда найдется х, при котором предикат Р(х)=1,
ложна тогда и только тогда, когда предикат Р(х)=0 при любом х.
№15 слайд
Содержание слайда: Замечание
Когда в предикате Р(х) переменная х связывается квантором, она перестает влиять на значение предиката и предикат становится высказыванием, принимающим фиксированное значение Истина или Ложь.
№16 слайд
Содержание слайда: Предикаты
Например: Р(х) – «х является четным числом» на множестве N
Тогда
так как есть х=3, при котором Р(3)=0.
Тогда
так как есть х=2, при котором Р(2)=1.
№17 слайд
Содержание слайда: Предикаты
Если предикат имеет более 1 переменной, то ее квантификация приводит к уменьшению числа переменных на 1.
Например:
предикат Q(x,y) – «x≤y» на множестве N×N.
№18 слайд
Содержание слайда: Предикаты
новый предикат от одной переменной у – «любое натуральное число х меньше либо равно у».
При у=1 это не так (любой х ≤1) ,
При у=2 это не так (любой х ≤2),
№19 слайд
Содержание слайда: Предикаты
Таким образом, предикат
то есть является функцией -константой
№20 слайд
Содержание слайда: Предикаты
новый предикат от одной переменной у – «найдется натуральное число х меньше либо равно у».
При у=1 это так (найдется х ≤ 1) ,
При у=2 это так (найдется х ≤2),
№21 слайд
Содержание слайда: Предикаты
Таким образом, предикат
то есть тоже является функцией -константой
№22 слайд
Содержание слайда: Предикаты
Кванторы можно навесить на все переменные предиката. Тогда предикат станет высказыванием.
Например:
предикат Q(x,y) – «x≤y».
№23 слайд
Содержание слайда: Предикаты
так как неверно то, что любой натуральный х меньше либо равен любого натурального у.
Например, при х=5, у=2.
№24 слайд
Содержание слайда: Предикаты
так как верно то, что любой натуральный х меньше либо равен некоторого натурального у.
Например, при х=1, у=1; при х=2, у=2, …
№25 слайд
Содержание слайда: Предикаты
так как неверно то, что найдется такой натуральный у, который будет больше либо равен любого натурального х.
Это связано с тем, что натуральное множество не ограничено сверху.
№26 слайд
Содержание слайда: Предикаты
так как верно то, что найдется такой натуральный х, который будет меньше либо равен любого натурального у.
Этот х=1. Если бы неравенство было строгое, высказывание было бы ложным.
№27 слайд
Содержание слайда: Предикаты
так как верно то, что любой натуральный у, больше либо равен некоторого натурального х.
Например, у=1, х=1;
у=2, х=2,…
№28 слайд
Содержание слайда: Предикаты
так как верно то, что найдутся такие натуральные х и у, что х меньше либо равен этого у.
Например х=3, у=7.
№29 слайд
Содержание слайда: Логика предикатов
Логика предикатов, как и логика высказываний, – свод правил, по которым строятся формулы связывающие простые предикаты в предикатные формулы и порядок определения истинности/ложности этих формул.
№30 слайд
Содержание слайда: Логика предикатов
Равносильные предикатные формулы – те, у которых область истинности совпадает.
№31 слайд
Содержание слайда: Логика предикатов
Интерпретация – это сопоставление каждому предикатному символу в формуле определенного предиката.
№32 слайд
Содержание слайда: Логика предикатов
Пусть формулы F и G содержат одно и тоже множество свободных переменных. Формулы F и G равносильны в данной интерпретации – если они выражают один и тот же предикат.
№33 слайд
Содержание слайда: Логика предикатов
Например:
Тогда предикатные формулы:
являются равносильными в данной интерпретации, так как
При других интерпретациях предикатов P и Q формулы могут не быть равносильными.
№34 слайд
Содержание слайда: Логика предикатов
Формулы F и G равносильны на множестве М – если они равносильны во всех интерпретациях на этом множестве.
№35 слайд
Содержание слайда: Логика предикатов
Например:
Равносильны в любой интерпретации на множестве М, если М состоит из одного элемента. Если
Если
На другом множестве формулы F и G могут не быть равносильными.
№36 слайд
Содержание слайда: Логика предикатов
Формулы F и G равносильны в логике предикатов – если они равносильны на всех множествах.
№37 слайд
Содержание слайда: Логика предикатов
Например:
Тогда F и G равносильны на любых множествах и при любых интерпретациях предиката P(x).
№38 слайд
Содержание слайда: Равносильные формулы
Для предикатных формул сохраняются все равносильности (эквивалентности) алгебры логики. Например, закон де Моргана:
№39 слайд
Содержание слайда: Свойства операций над предикатами
Перенос квантора через отрицание
Здесь и далее, знак равносильности ≡ заменен знаком равенства.
№40 слайд
Содержание слайда: Свойства операций над предикатами
Вынос квантора за скобки
№41 слайд
Содержание слайда: Свойства операций над предикатами
Вынос квантора за скобки
№42 слайд
Содержание слайда: Свойства операций над предикатами
Закон коммутативности для одноименных кванторов:
№43 слайд
Содержание слайда: Свойства операций над предикатами
Коммутативность дает возможность использовать более краткую запись:
№44 слайд
Содержание слайда: Равносильные формулы
Проверить равносильность формулы в логике предикатов, не так просто, как в логике высказываний. Высказывание может принимать значения 0 и 1. Формула с 2 высказываниями содержит 2² возможных значений, и так далее.
Предикат имеет бесконечное множество интерпретаций.
№45 слайд
Содержание слайда: Истинность в логике предикатов
Предикатная формула F называется выполнимой (непротиворечивой), если существует интерпретация входящих в нее предикатов, в которой F принимает значение истина. То есть ее область истинности не пуста.
№46 слайд
Содержание слайда: Истинность в логике предикатов
Предикатная формула F называется тождественно истинной (общезначимой), если при любой интерпретация входящих в нее предикатов, область истинности совпадает с областью определения.
№47 слайд
Содержание слайда: Истинность в логике предикатов
Предикатная формула F называется тождественно ложной (противоречивой), если при любой интерпретация входящих в нее предикатов, область истинности пуста.
№48 слайд
Содержание слайда: Истинность в логике предикатов
Например:
Тождественно истинная формула.
Тождественно ложная формула
№49 слайд
Содержание слайда: Истинность в логике предикатов
Замечание 1
Формула F – общезначима тогда и только тогда, когда
¬F – противоречива.
Замечание 2
Формула F – выполнима тогда и только тогда, когда
¬F – не является общезначимой.
№50 слайд
Содержание слайда: Истинность в логике предикатов
Замечание 3
Если F и G – равносильные формулы в логике предикатов, то формула
W = F ~ G
общезначима и выполняется равенство:
№51 слайд
Содержание слайда: Истинность в логике предикатов
Замечание 4
Если формула
W = F → G
общезначима, то выполняется:
№52 слайд
Содержание слайда: Истинность в логике предикатов
Замечание 5
Если y не входит в формулу P(x), то следующие формулы являются общезначимыми:
№53 слайд
Содержание слайда: Истинность в логике предикатов
Квантор общности является обобщением конъюнкции, поэтому справедлива формула:
№54 слайд
Содержание слайда: Истинность в логике предикатов
Квантор существования является обобщением дизъюнкции, поэтому справедлива формула:
№55 слайд
Содержание слайда: Истинность в логике предикатов
Замечание 6
Если в формулах (11) и (12) поменять местами кванторы, то получаются выражения, истинные лишь в одну сторону:
№56 слайд
Содержание слайда: Истинность в логике предикатов
В таких случаях говорят, что левая часть утверждения более сильная, чем правая.
№57 слайд
Содержание слайда: Истинность в логике предикатов
В таком случае, надо воспользоваться правилом:
То есть, если переменная связана квантором, то неважно, как она называется.
№58 слайд
Содержание слайда: Истинность в логике предикатов
В выражениях (13) и (14) надо сделать замену переменной, после чего воспользоваться формулами (4) и (5):
№59 слайд
Содержание слайда: Истинность в логике предикатов
№60 слайд
Содержание слайда: Префиксная нормальная форма
Префиксной нормальной формой (ПНФ) называется формула, имеющая вид:
где кванторы,
F – предикатная формула, имеющая вид ДНФ.
Скачать все slide презентации Логика предикатов. ДМ. 13 одним архивом:
