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

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

Содержание ▲

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

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

Слайд 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 – предикатная формула, имеющая вид ДНФ.

Теги Логика предикатов. ДМ.13

Похожие презентации