Логика первого порядка. (Лекции 10-11)

Июль 28, 2022

Главная
Математика
Логика первого порядка. (Лекции 10-11)

Содержание

2. Понятие терма, предиката A – «каждый человек смертен», B – «Сократ — человек», C – «Сократ
3. Понятие предиката Определен некоторый предикат, если: Задано некоторое (произвольное) множество, называемое областью определения предиката (предметная область);
4. Понятие предиката Понятие предиката является частным случаем понятия функции. Отличие предиката от функции состоит в том,
5. Примеры «х - действительное число» - одноместный предикат, «у меньше z» - двуместный предикат, «х и
6. Понятие предиката Если x, y и z замещены конкретными значениями (объектами), то предикат переходит в высказывание,
7. Понятие предиката Предикат Р, имеющий n аргументов, называется n-местным предикатом, обозначается P(x1,x2,…,xn). Количество аргументов предиката Р(x1,
8. Функциональный символ В логике предикатов существует понятие функционального символа. Пример: минус(x, y) - функциональный символ «x
9. Функциональный символ Если функциональный символ имеет n аргументов, то он называется n-местным функциональным символом Пример: минус(x,
10. Типы символов в ЛПП 1. Индивидуальные символы (константы), которые обычно являются именами объектов. 2. Символы предметных
11. Понятие терма Аргументы предиката называются термами. Терм определяется рекурсивно следующим образом:
12. Понятие терма 1. Константа есть терм. 2. Переменная есть терм. 3. Если f является n-местным функциональным
13. Понятие терма, предиката Пример. Перевести на естественный язык следующее высказывание логики предикатов. ЗНАТЬ(папа (Вася), математика).
14. Понятие терма, предиката Решение. Функциональный символ «папа(х)» принимает значение из множества людей, соответствующее отношению «быть отцом
15. Понятие терма, предиката Продолжение примера. Предикат ЗНАТЬ(папа(Вася), математика) соответствует предложению «папа у Васи знает математику». «Вася»
16. Кванторы Кванторы – специальные символы, которые используются для характеристики переменных. Существует два типа кванторов: (∀x) и
17. Кванторы Пусть P(x) – предикат, определенный на M. Высказывание «для всех x ∈ M, P(x) истинно»
18. Кванторы Переход от P(x) к (∀x)P(x) или (∃x)P(x) называется связыванием переменной x, а сама переменная x
19. Кванторы Пример. Записать в виде предикатов с кванторами следующие высказывания: “Все студенты сдают экзамены”, “Некоторые студенты
20. Кванторы Решение. Введем предикаты: P – «сдавать экзамены» Q – «сдавать экзамены на отлично». Предметная область
21. Атом Если P - n-местный предикат и t1,…, tn - термы, то P(t1,…, tn) называется атомом
22. Правильно построенные формулы в ЛПП Правильно построенными формулами логики первого порядка называются формулы, которые можно рекурсивно
23. Интерпретация формул в ЛПП Интерпретация формулы F логики первого порядка состоит из непустой предметной области D,
24. Интерпретация формул в ЛПП 1. Каждой константе ставится в соответствие некоторый элемент из D. 2. Каждому
25. Интерпретация формул в ЛПП 1. Если заданы значения формул F и G, то истинностные значения формул
26. Предваренные нормальные формы Формула F в логике первого порядка находится в предваренной нормальной форме (ПНФ) тогда
27. Преобразования выражений произвольной формы в ПНФ Для преобразования выражений произвольной формы в ПНФ необходимо выполнить, следующие
28. 1. Исключить логические связки эквиваленции (~) и импликации (→), выразив их через операции дизъюнкции, конъюнкции и
29. 2. Опустить знаки операций отрицания непосредственно на предикаты, используя приведенные ниже законы. а) Двойного отрицания: ¬
30. 3. Если необходимо – переименовать связанные переменные. 4. Вынести кванторы в начало формулы, используя соответствующие законы,
31. Преобразования выражений произвольной формы в ПНФ Пример. Привести формулу (∀x)P(x) → (∃x)Q(x) к ПНФ. Решение. (∀x)P(x)→(∃x)Q(x)
32. Законы логики первого порядка 1. Замена связанной переменной (∃x) F(x) = (∃y) F(y); (∀x) F(x) =
33. Законы логики первого порядка 3. Дистрибутивные свойства кванторов (∀x)F(x) ∨ G = (∀x)(F(x) ∨ G), (∃x)F(x)
34. Законы логики первого порядка Для применения дистрибутивного закона заменим связную переменную в одной из частей формул:
36. Скачать презентацию

Слайд 2

Понятие терма, предиката
A – «каждый человек смертен»,
B – «Сократ —

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

Слайд 3

Понятие предиката
Определен некоторый предикат, если:
Задано некоторое (произвольное) множество, называемое областью

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

Слайд 4

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

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

Слайд 5

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

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

Слайд 6

Понятие предиката
Если x, y и z замещены конкретными значениями (объектами), то

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

Слайд 7

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

xn) называется его порядком.

Слайд 8

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

- функциональный символ «x - y»;
отец(x) - функциональный символ «отец человека x».

Слайд 9

Функциональный символ
Если функциональный символ имеет n аргументов, то он называется n-местным функциональным

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

Слайд 10

Типы символов в ЛПП
1. Индивидуальные символы (константы), которые обычно являются именами объектов.
2.

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

Для построения атомов логики предикатов разрешается использовать следующие типы символов:

Слайд 11

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

Слайд 12

Понятие терма
1. Константа есть терм.
2. Переменная есть терм.
3. Если f является n-местным

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

Слайд 13

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

математика).

Слайд 14

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

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

Слайд 15

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

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

Слайд 16

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

кванторов:
(∀x) и (∃x)

Слайд 17

Кванторы
Пусть 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 в этом случае называется связанной.
Переменная, не связанная никаким квантором, называется свободной.
Пример.
Определить, какие переменные являются связанными, а какие - свободными в следующих формулах:
A(x, y);
∃y (B(x) → ∀x A(x, y));
∃x (B(x) → ∀x A(x, y)).

Решение:
Обе переменные в формуле 1 являются свободными. В формуле 2 переменная y является связанной, а переменная x - и связанной и свободной (переменная x свободна в предикате B(x) и связана в предикате A(x,y)). В формуле 3 переменная x является связанной, а переменная y - свободной.

Слайд 19

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

экзамены”,
“Некоторые студенты сдают экзамены на отлично”.

Слайд 20

Кванторы
Решение.
Введем предикаты:
P – «сдавать экзамены»
Q – «сдавать

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

Слайд 21

Атом
Если 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 логики первого порядка состоит из

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

Слайд 24

Интерпретация формул в ЛПП
1. Каждой константе ставится в соответствие некоторый элемент

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

Слайд 25

Интерпретация формул в ЛПП
1. Если заданы значения формул F и G,

то истинностные значения формул
(¬F), (F∨G), (F∧G), (F→G), (F~G)
получаются с помощью таблиц истинности соответствующих логических операций.
2. Формула (∀х)F получает значение И, если F получает значение И для каждого х из D,
в противном случае она получает значение Л.
3. Формула (∃x)F получает значение И, если F получает значение И хотя бы для одного х из D, в противном случае она получает значение Л.
PS: Формула, содержащая свободные переменные, не может получить истинностное значение.

Для каждой интерпретации на области D формула может получить истинностное значение И или Л согласно следующим правилам:

Слайд 26

Предваренные нормальные формы
Формула 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. Опустить знаки операций отрицания непосредственно на предикаты, используя приведенные ниже

законы.
а)    Двойного отрицания:
¬ (¬ F) = F.
б)    Де Моргана:
¬ (F ∨ G) = ¬ F ∧ ¬ G,
¬ (F ∧ G) = ¬ F ∨ ¬G.
в)    Де Моргана для кванторов:
¬ ((∀x) F(x)) = (∃x) (¬ F(x)),
¬ ((∃x) F(x)) = (∀x) (¬ F(x)).

Преобразования выражений произвольной формы в ПНФ

Слайд 30

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. Замена связанной переменной
(∃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. Дистрибутивные свойства кванторов
(∀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).

Логика первого порядка. (Лекции 10-11)

Содержание

Понятие терма, предикатаA – «каждый человек смертен», B – «Сократ —

Понятие предиката Определен некоторый предикат, если: Задано некоторое (произвольное) множество, называемое областью

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

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

Понятие предикатаЕсли x, y и z замещены конкретными значениями (объектами), то

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

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

Функциональный символЕсли функциональный символ имеет n аргументов, то он называется n-местным функциональным

Типы символов в ЛПП 1. Индивидуальные символы (константы), которые обычно являются именами объектов. 2.

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

Понятие терма1. Константа есть терм.2. Переменная есть терм.3. Если f является n-местным

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

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

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

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

Кванторы Пусть P(x) – предикат, определенный на M. Высказывание «для всех x

Кванторы Переход от P(x) к (∀x)P(x) или (∃x)P(x) называется связыванием переменной x,

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

Кванторы Решение. Введем предикаты: P – «сдавать экзамены» Q – «сдавать

АтомЕсли P - n-местный предикат и t1,…, tn - термы, то P(t1,…, tn) называется атомом или элементарной

Правильно построенные формулы в ЛПП Правильно построенными формулами логики первого порядка называются

Интерпретация формул в ЛПП Интерпретация формулы F логики первого порядка состоит из

Интерпретация формул в ЛПП 1. Каждой константе ставится в соответствие некоторый элемент

Интерпретация формул в ЛПП1. Если заданы значения формул F и G,

Предваренные нормальные формы Формула F в логике первого порядка находится в

Преобразования выражений произвольной формы в ПНФ Для преобразования выражений произвольной формы

1. Исключить логические связки эквиваленции (~) и импликации (→), выразив их

2. Опустить знаки операций отрицания непосредственно на предикаты, используя приведенные ниже

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

Преобразования выражений произвольной формы в ПНФ Пример. Привести формулу (∀x)P(x) → (∃x)Q(x) к

Законы логики первого порядка 1. Замена связанной переменной (∃x) F(x)

Законы логики первого порядка 3. Дистрибутивные свойства кванторов (∀x)F(x) ∨ G =

Законы логики первого порядка Для применения дистрибутивного закона заменим связную переменную

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

Понятие терма, предиката
A – «каждый человек смертен»,
B – «Сократ —

Понятие предиката
Определен некоторый предикат, если:
Задано некоторое (произвольное) множество, называемое областью

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

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

Понятие предиката
Если x, y и z замещены конкретными значениями (объектами), то

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

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

Функциональный символ
Если функциональный символ имеет n аргументов, то он называется n-местным функциональным

Типы символов в ЛПП
1. Индивидуальные символы (константы), которые обычно являются именами объектов.
2.

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

Понятие терма
1. Константа есть терм.
2. Переменная есть терм.
3. Если f является n-местным

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

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

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

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

Кванторы
Пусть P(x) – предикат, определенный на M.
Высказывание
«для всех x

Кванторы
Переход от P(x) к (∀x)P(x) или (∃x)P(x) называется связыванием переменной x,

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

Кванторы
Решение.
Введем предикаты:
P – «сдавать экзамены»
Q – «сдавать

Атом
Если P - n-местный предикат и t1,…, tn - термы, то P(t1,…, tn) называется атомом или элементарной

Правильно построенные формулы в ЛПП
Правильно построенными формулами логики первого порядка называются

Интерпретация формул в ЛПП
Интерпретация формулы F логики первого порядка состоит из

Интерпретация формул в ЛПП
1. Каждой константе ставится в соответствие некоторый элемент

Интерпретация формул в ЛПП
1. Если заданы значения формул F и G,

Предваренные нормальные формы
Формула F в логике первого порядка находится в

Преобразования выражений произвольной формы в ПНФ
Для преобразования выражений произвольной формы

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

Преобразования выражений произвольной формы в ПНФ
Пример.
Привести формулу
(∀x)P(x) → (∃x)Q(x) к

Законы логики первого порядка
1. Замена связанной переменной
(∃x) F(x)

Законы логики первого порядка
3. Дистрибутивные свойства кванторов
(∀x)F(x) ∨ G =

Законы логики первого порядка
Для применения дистрибутивного закона заменим связную переменную