Презентация по дисциплине "Элементы математической логики" на тему "Логика предикатов"

• 1 слайд

  КГБ ПОУ «Хабаровский машиностроительный техникум»
  Раздел 2. Логика предикатов
  

• 2 слайд

  Понятие предиката
  Высказывания, которые нельзя формализовать на языке логике высказываний:
  Каждый любит сам себя. Значит кто-то кого-то любит.
  Перья есть только у птиц. Ни одно млекопитающее не является птицей. Значит, все млекопитающие лишены перьев.
  

• 3 слайд

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

• 4 слайд

  Субъект – это то, о чем что-то утверждается.
  Предикат – это то, что утверждается о субъекте.
  Логика предикатов – это расширение логики высказываний за счет исполнения предикатов в роли логических функций.
  Предикатом называется функция, определённая на множестве M и принимающая значение «истина» или «ложь», то есть
  Множество M – контекст, или предметная область, или область определения предиката.
  Множество всех , при которых , называется множеством истинности предиката
  

• 5 слайд

  Примеры:
  1) Луна есть спутник Венеры – ложное высказывание, не являющееся предикатом, так как в нем нет аргумента – переменного х.
  2) - то же самое.
  3) - предикат. Здесь:
  

• 6 слайд

  Операции логики предикатов
  Предикат Р(х), определенный на множество M называется тождественно истинным, если область определения предиката , и называется тождественно ложным, если
  
  Говорят, что предикат Р(х) является следствием предиката Q(x) (Q(x)→Р (x)), если , и предикаты P(x) и Q(x) равносильны ( ), если
  

• 7 слайд

  Конъюнкция
  Конъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x)^Q(x) , который принимает значение «истина» при тех и только тех значениях xєM, при которых каждый из предикатов принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Областью истинности предиката P(x)^Q(x) является
  

• 8 слайд

  Дизъюнкция
  Дизъюнкцией двух предикатов P(x),Q(x) называется новый предикат P(x)vQ(x) , который принимает значение «ложь», при тех и только тех значениях xєM , при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката P(x)vQ(x) является
  

• 9 слайд

  Отрицание
  Отрицанием предиката P(x) называется новый предикат P(x), который принимает значение «истина» при всех значениях xєM, при которых P(x) принимает значение «ложь» и наоборот. Областью истинности предиката P(x) является
  
  

• 10 слайд

  Импликация
  Импликацией предикатов P(x) и Q(x) называется новый предикат P(x)→Q(x) , который являются ложными при тех и только тех значениях xєM , при которых P(x) одновременно принимает значение «истина», а Q(x) – значение «ложь», во всех остальных случаях это «истина».
  

• 11 слайд

  Эквиваленция
  Эквиваленцией предикатов P(x) и Q(x) называется новый предикат P(x)↔Q(x) , который являются истинным при тех и только тех значениях xєM, при которых одновременно P(x) и Q(x) принимает одинаковые значения значение «истина» или «ложь», и ложным во всех остальных случаях.
  

• 12 слайд

  Примеры
  1) На множестве M={3,4,5,6,7,8} заданы два предиката P(x):«х – простое число»,Q(x):«х – нечетное число». Составить их таблицы истинности. Равносильны ли предикаты P(x) и Q(x) на множествах L={2,3,4,5,6,7,8},K={3,4,5,6,7,8,9} ?
  
  
  
  
  Очевидно,что , . Таким образом, на множестве М P(x)=Q(x).
  На L и K предикаты не равносильны, ибо на L, например, 2 – простое число и четное, а на К число 9 – нечетное, но составное число.
  

• 13 слайд

  2) Найти область истинности предиката и изобразить на плоскости.
  Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенной между ветвями параболы y=x2.
  
  

• 14 слайд

  3) На множестве M={1,2,3…20} заданы предикаты A(x): «х не делиться на 5», B(x): «х –четное чиcло»,C(x): «х – число простое», D(x): «х кратно трем». Найти множества истинности предикатов A(x)^B(x)^C(x), A(x)vB(x),D(x)→C(x).
  1. A(x)^B(x)^C(x)= {х не делится на 5 и х – четное число и х кратно трем} = {х не делится на 5 и х делится на 6}. Действительно,
  2. A(x)vB(x)= {х не делится на 5 или х – четное число}.
  3. D(x)→C(x)= D(x)vC(x). = {х не кратно трем или х – непростое число}. Здесь рассуждения сложнее, однако, если перебрать все элементы множества М, то легко установить, что
  

• 15 слайд

  Кванторные операции
  Кванторные операции могут рассматриваться как обобщение операций конъюнкции и дизъюнкции в случае бесконечных областей.
  Квантор всеобщности (all - всякий)
  Под выражением xP(x) понимают высказывание, истинное, если P(x) истинно для каждого xєM, и ложное в противоположном случае.
  
  

• 16 слайд

  Кванторные операции
  Словесная интерпретация: «для каждого х P(x) истинно».
  Переменная х в предикате P(x) является свободной (х – любое из М), в высказывании хP(x) является связанной переменной, т.е. переменную, к которой относится квантор наз. связной, остальные переменные наз. свободными.
  Рассмотрим предикат P(x) , определенный на множестве M:{a1,…,an}. Справедлива равносильность
  
  

• 17 слайд

  В обычных выражениях квантор всеобщности выражается следующим образом:
  P(x), при произвольном х;
  P(x), при какого бы не было х;
  для каждого х верно P(x);
  всегда имеет место P(x);
  каждый обладает свойством P;
  всё удовлетворяет P.
  
  

• 18 слайд

  Квантор существования Ǝ
  (exist-существовать)
  Пусть P(x)- предикат,xєM. Под выражением Ǝx P(x) понимают высказывание, истинное, если существует xєM, для которого P(x) истинно, и ложное в противоположном случае.
  Переменная х в предикате является свободной (х – любое из М), в высказывании Ǝx P(x)- х является связанной переменной.
  Словесная интерпретация: «существует х, при котором P(x) истинно».
  Справедлива равносильность
  
  

• 19 слайд

  В обычных выражениях квантор существования выражается следующим образом:
  для некоторых х имеет место P(x);
  для подходящего х верно P(x);
  имеется х, для которого P(x);
  у некоторых вещей есть признак Р;
  кто-нибудь относится к (есть) Р.
  

• 20 слайд

  Если предикат является функцией нескольких переменных, то он называется n-местным или n-арным предикатом.
  Кванторные операции могут применять и к многоместным предикатам.
  Например, применение кванторной операции к предикату P(x,y) по переменной х ставит в соответствие ему одноместный предикат xP(x,y) или ƎxP(x,y), зависящий от y и не зависящий от x.
  К двухместному предикату при применении кванторов по обеим переменным получается 8 высказываний:
  xyP(x,y) yxP(x,y)
  ƎxyP(x,y) ƎyxP(x,y)
  xƎyP(x,y) yƎxP(x,y)
  ƎxƎyP(x,y) ƎyƎxP(x,y)
  

• 21 слайд

  В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логических значений, то есть, например, высказывания
  и различны.
  Квантор существования можно выразить через квантор всеобщности применительно к предикату A(x) следующим образом
  
  Квантор всеобщности можно выразить через квантор существования применительно к предикату A(x)следующим образом
  

• 22 слайд

  Пример:
  1) Пусть P(x,y) означает что х является матерью для у. Тогда выражение означает, что у каждого человека есть мать – это истинное утверждение. Выражение означает, что существует мать всех людей. Истинность этого утверждения зависит от множества значений, которые могут принимать y: если это множества братьев и сестер, то оно истинно, в противном случае ложно.
  

• 23 слайд

  2) Установить истинность или ложность высказывания
  
  Исходное высказывание преобразуем к виду:
  
  
  Исходное высказывание истинно.
  

• 24 слайд

  Формулы логики предикатов и интерпретация
  В логике предикатов используется символика:
  Символы p1, q2, r3, … – переменные высказывания;
  Предметные переменные и предметные константы;
  
  ,niєN, - предикатные символы, – ni-местный предикатный символ;
  , - функциональные символы, – nj-местный функциональный символ;
  Символы логических операций:
  Символы кванторных операций: ,Ǝ
  Вспомогательные символы: скобки, запятые.
  

• 25 слайд

  Формулой логики предикатов называется всякое выражение, содержащее символику 1…7 и удовлетворяющее следующим требованиям:
  атомарная формула есть формула;
  если A и B – формула, то A→B,A↔B ,AvB ,A^B - тоже формулы при условии, что одна и та же предметная переменная не является в А свободной, а в В связанной или наоборот;
  если А – формула, то и Ā - тоже формула;
  если A(x)- формула, то ƎxA(x) и xA(x) являются формулами, причем если в A(x) х – свободная переменная, то в ƎxA(x) и xA(x) будет уже связанной переменной.
  

• 26 слайд

  Интерпритация
  Формулы имеют смысл тогда, когда имеется какая-нибудь интерпретация входящих в неё символов.
  Под интерпретацией понимается всякая пара, состоящая из непустого множества М, названного областью интерпретации, и какого-либо отображения, относящему каждому предикатному символу арности N некоторое n-местное отношение на M.
  

• 27 слайд

  Пример:
  1) Является ли данное выражение формулой логики предикатов?
  – не является формулой, так как квантор существования употреблен для уже связной квантором всеобщности переменной y.
  - является формулой; x – связанная переменная; y – свободная;
  - не является формулой, ибо в первом логическом слагаемом х – связанная переменная, а во втором слагаемом свободная.
  

• 28 слайд

  2) Даны следующие утверждения
  A(n): «число n делится на 3»;B(n): «число n делится на 2»; С(n): «число n делится на 4»;D(n): «число n делится на 6»; E(n): «число n делится на 12».
  Указать, какие из следующих утверждений истинны, а какие ложны:
  а)
  A(n)^B(n): «число n делится на 6»,
  A(n)^B(n)→E(n): «если n делиться 6, то оно делится на 12». При n=6 импликация ложна, следовательно, исходная формула в общем ложна.
  б)
  B(n)^C(n):«число делится на 4»,B(n)^C(n)→¬D(n): «если число делиться на 4, то оно не делиться на 6». Такое может быть, например, при n=16. Следовательно, B(n)^C(n)→¬D(n) - не тождественно ложная формула, а тогда
  - истинная формула алгебры предикатов.
  

• 29 слайд

  Формулы
  Формула содержит только связанную переменную х. Эта формула является тождественно истинным высказыванием в любой интерпретации.
  Напротив, формула
  - тождественно ложная формула в любой интерпретации.
  

• 30 слайд

  Применение языка логики предикатов для записи математических предложений
  Определение экстремума функции (минимума в точке х0)
  , где
  

• 31 слайд

  Определение выпуклости (вогнутости) функции f(x)
  Если во всех точках интервала (a,b) вторая производная , то f(x) на (a,b) выпукла.