Презентация Логика первого порядка. (Лекции 10-11) онлайн

Содержание слайда: Логика первого порядка

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Содержание слайда: Переход от 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)).

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

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

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

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

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

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

Содержание слайда: 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: Формула, содержащая свободные переменные, не может получить истинностное значение.

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

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

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

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

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

Содержание слайда: Пример. Пример. Привести формулу (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)).

Содержание слайда: 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).

Содержание слайда: 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)).

Содержание слайда: Для применения дистрибутивного закона заменим связную переменную в одной из частей формул: Для применения дистрибутивного закона заменим связную переменную в одной из частей формул: (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).

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