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

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

Логика первого порядка. (Лекции 10-11), слайд №1

Логика первого порядка. (Лекции 10-11), слайд №2

Логика первого порядка. (Лекции 10-11), слайд №3

Логика первого порядка. (Лекции 10-11), слайд №4

Логика первого порядка. (Лекции 10-11), слайд №5

Логика первого порядка. (Лекции 10-11), слайд №6

Логика первого порядка. (Лекции 10-11), слайд №7

Логика первого порядка. (Лекции 10-11), слайд №8

Логика первого порядка. (Лекции 10-11), слайд №9

Логика первого порядка. (Лекции 10-11), слайд №10

Логика первого порядка. (Лекции 10-11), слайд №11

Логика первого порядка. (Лекции 10-11), слайд №12

Логика первого порядка. (Лекции 10-11), слайд №13

Логика первого порядка. (Лекции 10-11), слайд №14

Логика первого порядка. (Лекции 10-11), слайд №15

Логика первого порядка. (Лекции 10-11), слайд №16

Логика первого порядка. (Лекции 10-11), слайд №17

Логика первого порядка. (Лекции 10-11), слайд №18

Логика первого порядка. (Лекции 10-11), слайд №19

Логика первого порядка. (Лекции 10-11), слайд №20

Логика первого порядка. (Лекции 10-11), слайд №21

Логика первого порядка. (Лекции 10-11), слайд №22

Логика первого порядка. (Лекции 10-11), слайд №23

Логика первого порядка. (Лекции 10-11), слайд №24

Логика первого порядка. (Лекции 10-11), слайд №25

Логика первого порядка. (Лекции 10-11), слайд №26

Логика первого порядка. (Лекции 10-11), слайд №27

Логика первого порядка. (Лекции 10-11), слайд №28

Логика первого порядка. (Лекции 10-11), слайд №29

Логика первого порядка. (Лекции 10-11), слайд №30

Логика первого порядка. (Лекции 10-11), слайд №31

Логика первого порядка. (Лекции 10-11), слайд №32

Логика первого порядка. (Лекции 10-11), слайд №33

Логика первого порядка. (Лекции 10-11), слайд №34

Логика первого порядка. (Лекции 10-11), слайд №35

Содержание ▲

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

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

Слайд 1

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

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

Слайд 2

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

A – «каждый человек смертен», A – «каждый человек смертен», B – «Сократ — человек», C – «Сократ смертен». Исходное умозаключение будет соответствовать формуле логики высказываний A  B  C Приведем данную формулу к нормальной форме: A  B  C =  (A  B)  С = А  В  С

Слайд 3

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

Определен некоторый предикат, если: Определен некоторый предикат, если: Задано некоторое (произвольное) множество, называемое областью определения предиката (предметная область); Фиксировано множество {1, 0}, называемое областью значений; Указано правило, с помощью которого каждому элементу, взятому из предметной области, ставится в соответствие один из двух элементов из области значений.

Слайд 4

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

Понятие предиката является частным случаем понятия функции. Понятие предиката является частным случаем понятия функции. Отличие предиката от функции состоит в том, что у предиката четко фиксирована область значений.

Слайд 5

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

«х - действительное число» - одноместный предикат, «х - действительное число» - одноместный предикат, «у меньше z» - двуместный предикат, «х и у родители z» - трёхместный предикат.

Слайд 6

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

Если x, y и z замещены конкретными значениями (объектами), то предикат переходит в высказывание, которое рассматривается как нульместный предикат. Если x, y и z замещены конкретными значениями (объектами), то предикат переходит в высказывание, которое рассматривается как нульместный предикат. Пример: «Терм и квантор - понятия логики предикатов». Таким образом, если количество аргументов предиката Р(x1, x2,…, xn) n равно нулю, то предикат является высказыванием; если n=1, то предикат соответствует свойству; если n=2, то предикат является бинарным отношением; если n=3, то предикат - тернарное отношение.

Слайд 7

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

Предикат Р, имеющий n аргументов, называется n-местным предикатом, обозначается P(x1,x2,…,xn). Предикат Р, имеющий n аргументов, называется n-местным предикатом, обозначается P(x1,x2,…,xn). Количество аргументов предиката Р(x1, x2,…, xn) называется его порядком.

Слайд 8

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

В логике предикатов существует понятие функционального символа. В логике предикатов существует понятие функционального символа. Пример: минус(x, y) - функциональный символ «x - y»; отец(x) - функциональный символ «отец человека x».

Слайд 9

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

Если функциональный символ имеет n аргументов, то он называется n-местным функциональным символом Если функциональный символ имеет n аргументов, то он называется n-местным функциональным символом Пример: минус(x, y) - двухместный функциональный символ. Индивидуальный символ или константа может рассматриваться как функциональный символ без аргументов. Отличие функционального символа от предикатного в том, что предикат принимает значение из множества {0,1}, а функционального - любое из предметной области М.

Слайд 10

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

1. Индивидуальные символы (константы), которые обычно являются именами объектов. 1. Индивидуальные символы (константы), которые обычно являются именами объектов. 2. Символы предметных переменных, в качестве которых обычно выступают буквы латинского алфавита, возможно с индексами. 3. Функциональные символы – строчные буквы латинского алфавита или осмысленные слова из строчных букв. 4. Предикаты – прописные буквы или осмысленные слова из прописных букв.

Слайд 11

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

Аргументы предиката называются термами. Аргументы предиката называются термами. Терм определяется рекурсивно следующим образом:

Слайд 12

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

1. Константа есть терм. 1. Константа есть терм. 2. Переменная есть терм. 3. Если f является n-местным функциональным символом, а t1, t2,…, tn – термы, то f(t1, t2,…, tn) есть терм. 4. Никаких термов, кроме порожденных с помощью указанных выше правил, не существует.

Слайд 13

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

Пример. Пример. Перевести на естественный язык следующее высказывание логики предикатов. ЗНАТЬ(папа (Вася), математика).

Слайд 14

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

Решение. Решение. Функциональный символ «папа(х)» принимает значение из множества людей, соответствующее отношению «быть отцом х». Выражение папа(Вася) следует интерпретировать как «Васин папа».

Слайд 15

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

Продолжение примера. Продолжение примера. Предикат ЗНАТЬ(папа(Вася), математика) соответствует предложению «папа у Васи знает математику». «Вася» и «математика» являются константами, папа - функциональный символ. Любой функциональный символ от константы является термом, следовательно, папа(Вася) - терм.

Слайд 16

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

Кванторы – специальные символы, которые используются для характеристики переменных. Кванторы – специальные символы, которые используются для характеристики переменных. Существует два типа кванторов: (x) и (x)

Слайд 17

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

Пусть P(x) – предикат, определенный на M. Пусть P(x) – предикат, определенный на M. Высказывание «для всех x  M, P(x) истинно» обозначается (x)P(x). Знак  называется квантором всеобщности. Высказывание «существует такой x  M, что P(x) истинно» обозначается (x)P(x), где знак  называется квантором существования.

Слайд 18

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

Переход от P(x) к (x)P(x) или (x)P(x) называется связыванием переменной x, а сама переменная x в этом случае называется связанной. Переход от P(x) к (x)P(x) или (x)P(x) называется связыванием переменной x, а сама переменная x в этом случае называется связанной. Переменная, не связанная никаким квантором, называется свободной. Пример. Определить, какие переменные являются связанными, а какие - свободными в следующих формулах: A(x, y); ∃y (B(x) → ∀x A(x, y)); ∃x (B(x) → ∀x A(x, y)).

Слайд 19

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

Пример. Пример. Записать в виде предикатов с кванторами следующие высказывания: “Все студенты сдают экзамены”, “Некоторые студенты сдают экзамены на отлично”.

Слайд 20

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

Решение. Решение. Введем предикаты: P – «сдавать экзамены» Q – «сдавать экзамены на отлично». Предметная область данных предикатов представляет собой множество студентов. Тогда исходные выражения примут вид: (x) P(x) (x) Q(x)

Слайд 21

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

Если P - n-местный предикат и t1,…, tn - термы, то P(t1,…, tn) называется атомом или элементарной формулой логики предикатов. Если P - n-местный предикат и t1,…, tn - термы, то P(t1,…, tn) называется атомом или элементарной формулой логики предикатов. Пример ДЕЛИТСЯ(х, 13), ДЕЛИТСЯ(х, у), БОЛЬШЕ(плюс(х, 1), х), РАВНЯТЬСЯ(х,1), СДАВАТЬ(студенты, сессии).

Слайд 22

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

Правильно построенными формулами логики первого порядка называются формулы, которые можно рекурсивно определить следующим образом: Правильно построенными формулами логики первого порядка называются формулы, которые можно рекурсивно определить следующим образом: 1. Атом является формулой. 2. Если F и G – формулы, то (F), (FG), (FG), (FG), (F~G) также являются формулами. 3. Если F – формула, а х – свободная переменная, то (х)F и (x)F тоже формулы. 4. Никаких формул, кроме порожденных указанными выше правилами, не существует

Слайд 23

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

Интерпретация формулы F логики первого порядка состоит из Интерпретация формулы F логики первого порядка состоит из непустой предметной области D, значений всех констант, функциональных символов и предикатов, встречающихся в F. Указанные значения задаются следующим образом:

Слайд 24

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

1. Каждой константе ставится в соответствие некоторый элемент из D. 1. Каждой константе ставится в соответствие некоторый элемент из D. 2. Каждому n-местному функциональному символу ставится в соответствие отображение из Dn в D. Здесь Dn = (x1, x2,…, xn), где x1,…, xn D. 3. Каждому n-местному предикату ставится в соответствие отображение из Dn в {И, Л}.

Слайд 25

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

1. Если заданы значения формул F и G, то истинностные значения формул 1. Если заданы значения формул F и G, то истинностные значения формул (F), (FG), (FG), (FG), (F~G) получаются с помощью таблиц истинности соответствующих логических операций. 2. Формула (х)F получает значение И, если F получает значение И для каждого х из D, в противном случае она получает значение Л. 3. Формула (x)F получает значение И, если F получает значение И хотя бы для одного х из D, в противном случае она получает значение Л. PS: Формула, содержащая свободные переменные, не может получить истинностное значение.

Слайд 26

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

Формула F в логике первого порядка находится в предваренной нормальной форме (ПНФ) тогда и только тогда, когда она может быть представлена в виде Формула F в логике первого порядка находится в предваренной нормальной форме (ПНФ) тогда и только тогда, когда она может быть представлена в виде (Qlxl)...(Qnxn)(M), где каждое (Qixi), i=l, ... , n есть или (х), или (x), М – формула, не содержащая кванторов. (Qlxl)...(Qnxn) называется префиксом, а М — матрицей формулы F.

Слайд 27

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

Для преобразования выражений произвольной формы в ПНФ необходимо выполнить, следующие этапы преобразования: Для преобразования выражений произвольной формы в ПНФ необходимо выполнить, следующие этапы преобразования:

Слайд 28

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

1. Исключить логические связки эквиваленции (~) и импликации (), выразив их через операции дизъюнкции, конъюнкции и отрицания с помощью следующих законов: F ~ G = ( F  G)  ( G  F), F ~ G = ( F   G)  (G  F), F  G =  F  G.

Слайд 29

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

2. Опустить знаки операций отрицания непосредственно на предикаты, используя приведенные ниже законы. 2. Опустить знаки операций отрицания непосредственно на предикаты, используя приведенные ниже законы. а) Двойного отрицания:  ( F) = F. б) Де Моргана:  (F  G) =  F   G,  (F  G) =  F  G. в) Де Моргана для кванторов:  ((x) F(x)) = (x) ( F(x)),  ((x) F(x)) = (x) ( F(x)).

Слайд 30

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

3. Если необходимо – переименовать связанные переменные. 3. Если необходимо – переименовать связанные переменные. 4. Вынести кванторы в начало формулы, используя соответствующие законы, для получения предваренной нормальной формы.

Слайд 31

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

Пример. Пример. Привести формулу (x)P(x)  (x)Q(x) к ПНФ. Решение. (x)P(x)(x)Q(x) = = ((x)P(x))(x)Q(x) = = (x)(P(x))(x)Q(x) = = (x)(P(x)Q(x)).

Слайд 32

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

1. Замена связанной переменной 1. Замена связанной переменной (x) F(x) = (y) F(y); (x) F(x) = (y) F(y). 2. Коммутативные свойства кванторов (x) (y) P(x, y) = (y) (x) P(x, y); (x) (y) P(x, y) = (y) (x) P(x, y).

Слайд 33

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

3. Дистрибутивные свойства кванторов 3. Дистрибутивные свойства кванторов (x)F(x)  G = (x)(F(x)  G), (x)F(x)  G = (x)(F(x)  G), (x)F(x)  G = (x)(F(x)  G), (x)F(x)  G = (x)(F(x)  G), (x)F(x)  (x)H(x) =(x)(F(x)  H(x)), (x)F(x)  (x)H(x) = (x)(F(x)  H(x)).

Слайд 34

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

Для применения дистрибутивного закона заменим связную переменную в одной из частей формул: Для применения дистрибутивного закона заменим связную переменную в одной из частей формул: (x)F(x)  (x)H(x) = (x)F(x)  (y)H(y)= (x) (y) (F(x)  H(y)) (x)F(x)  (x)H(x)= (x)F(x)  (y)F(y) = (x)(y)(F(x) F(y)) 4. Закон де Моргана для кванторов  ((x)F(x)) = (x)F(x),  ((x)F(x)) = (x)F(x).

Слайд 35

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

Формула B является логическим следствием высказывания A, если формула Формула B является логическим следствием высказывания A, если формула AB является тождественно истинной. Формула B называется логическим следствием формул A1, A2, ..., An, если A1A2...AnB тождественно истинная формула .