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

КГБ ПОУ «Хабаровский машиностроительный техникум» Высказывания, которые нельзя формализовать на языке логике высказываний: Каждый любит сам себя. Значит кто-то кого-то любит.Перья есть только у птиц. Ни одно млекопитающее не является птицей. Значит, все млекопитающие лишены перьев. Понятие предиката Введём специальные обозначения: Специальные переменные, значениями которых являются объекты из соответствующих предметных областей:x и y.Свойства объектов и бинарные отношения между объектами: , .Фраза вида «Все х обладают свойством Р» записывать символически: «некоторые х обладают свойством P» записывать символически Введём специальные обозначения: Специальные переменные, значениями которых являются объекты из соответствующих предметных областей:x и y.Свойства объектов и бинарные отношения между объектами: , .Фраза вида «Все х обладают свойством Р» записывать символически: «некоторые х обладают свойством P» записывать символически Субъект – это то, о чем что-то утверждается.Предикат – это то, что утверждается о субъекте.Логика предикатов – это расширение логики высказываний за счет исполнения предикатов в роли логических функций. Предикатом называется функция, определённая на множестве M и принимающая значение «истина» или «ложь», то естьМножество M – контекст, или предметная область, или область определения предиката. Множество всех , при которых , называется множеством истинности предиката Примеры: 1) Луна есть спутник Венеры – ложное высказывание, не являющееся предикатом, так как в нем нет аргумента – переменного х.2) - то же самое.3) - предикат. Здесь: Операции логики предикатов Предикат Р(х), определенный на множество M называется тождественно истинным, если область определения предиката , и называется тождественно ложным, если Говорят, что предикат Р(х) является следствием предиката Q(x) (Q(x)→Р (x)), если , и предикаты P(x) и Q(x) равносильны ( ), если Конъюнкция Конъюнкцией двух предикатов P(x) и Q(x) называется новый предикат P(x)^Q(x) , который принимает значение «истина» при тех и только тех значениях xєM, при которых каждый из предикатов принимает значение «истина» и принимает значение «ложь» во всех остальных случаях. Областью истинности предиката P(x)^Q(x) является Дизъюнкция Дизъюнкцией двух предикатов P(x),Q(x) называется новый предикат P(x)vQ(x) , который принимает значение «ложь», при тех и только тех значениях xєM , при которых каждый из предикатов принимает значение «ложь» и принимает значение «истина» во всех остальных случаях. Областью истинности предиката P(x)vQ(x) является Отрицание Отрицанием предиката P(x) называется новый предикат P(x), который принимает значение «истина» при всех значениях xєM, при которых P(x) принимает значение «ложь» и наоборот. Областью истинности предиката P(x) является Импликация Импликацией предикатов P(x) и Q(x) называется новый предикат P(x)→Q(x) , который являются ложными при тех и только тех значениях xєM , при которых P(x) одновременно принимает значение «истина», а Q(x) – значение «ложь», во всех остальных случаях это «истина». Эквиваленция Эквиваленцией предикатов P(x) и Q(x) называется новый предикат P(x)↔Q(x) , который являются истинным при тех и только тех значениях xєM, при которых одновременно P(x) и Q(x) принимает одинаковые значения значение «истина» или «ложь», и ложным во всех остальных случаях. 0 1 0 1 0 1 Q(x) 0 1 0 1 0 1 P(x) 8 7 6 5 4 3 x Примеры 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 – нечетное, но составное число. 2) Найти область истинности предиката и изобразить на плоскости. Неравенство, составляющее исходный предикат, ограничивает часть плоскости, заключенной между ветвями параболы y=x2. 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). = {х не кратно трем или х – непростое число}. Здесь рассуждения сложнее, однако, если перебрать все элементы множества М, то легко установить, что Кванторные операции Кванторные операции могут рассматриваться как обобщение операций конъюнкции и дизъюнкции в случае бесконечных областей. Квантор всеобщности (all - всякий)Под выражением xP(x) понимают высказывание, истинное, если P(x) истинно для каждого xєM, и ложное в противоположном случае. Кванторные операции Словесная интерпретация: «для каждого х P(x) истинно».Переменная х в предикате P(x) является свободной (х – любое из М), в высказывании хP(x) является связанной переменной, т.е. переменную, к которой относится квантор наз. связной, остальные переменные наз. свободными. Рассмотрим предикат P(x) , определенный на множестве M:{a1,…,an}. Справедлива равносильность В обычных выражениях квантор всеобщности выражается следующим образом:P(x), при произвольном х;P(x), при какого бы не было х;для каждого х верно P(x); всегда имеет место P(x);каждый обладает свойством P;всё удовлетворяет P. Квантор существования Ǝ (exist-существовать) Пусть P(x)- предикат,xєM. Под выражением Ǝx P(x) понимают высказывание, истинное, если существует xєM, для которого P(x) истинно, и ложное в противоположном случае.Переменная х в предикате является свободной (х – любое из М), в высказывании Ǝx P(x)- х является связанной переменной. Словесная интерпретация: «существует х, при котором P(x) истинно». Справедлива равносильность В обычных выражениях квантор существования выражается следующим образом:для некоторых х имеет место P(x);для подходящего х верно P(x);имеется х, для которого P(x);у некоторых вещей есть признак Р;кто-нибудь относится к (есть) Р. Если предикат является функцией нескольких переменных, то он называется 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) В общем случае изменение порядка следования кванторов изменяет смысл высказывания и его логических значений, то есть, например, высказывания и различны.Квантор существования можно выразить через квантор всеобщности применительно к предикату A(x) следующим образом Квантор всеобщности можно выразить через квантор существования применительно к предикату A(x)следующим образом Пример: 1) Пусть P(x,y) означает что х является матерью для у. Тогда выражение означает, что у каждого человека есть мать – это истинное утверждение. Выражение означает, что существует мать всех людей. Истинность этого утверждения зависит от множества значений, которые могут принимать y: если это множества братьев и сестер, то оно истинно, в противном случае ложно. 2) Установить истинность или ложность высказыванияИсходное высказывание преобразуем к виду:Исходное высказывание истинно. Формулы логики предикатов и интерпретация В логике предикатов используется символика:Символы p1, q2, r3, … – переменные высказывания;Предметные переменные и предметные константы; ,niєN, - предикатные символы, – ni-местный предикатный символ; , - функциональные символы, – nj-местный функциональный символ;Символы логических операций: Символы кванторных операций: ,ƎВспомогательные символы: скобки, запятые. Формулой логики предикатов называется всякое выражение, содержащее символику 1…7 и удовлетворяющее следующим требованиям:атомарная формула есть формула;если A и B – формула, то A→B,A↔B ,AvB ,A^B - тоже формулы при условии, что одна и та же предметная переменная не является в А свободной, а в В связанной или наоборот; если А – формула, то и Ā - тоже формула;если A(x)- формула, то ƎxA(x) и xA(x) являются формулами, причем если в A(x) х – свободная переменная, то в ƎxA(x) и xA(x) будет уже связанной переменной. Интерпритация Формулы имеют смысл тогда, когда имеется какая-нибудь интерпретация входящих в неё символов. Под интерпретацией понимается всякая пара, состоящая из непустого множества М, названного областью интерпретации, и какого-либо отображения, относящему каждому предикатному символу арности N некоторое n-местное отношение на M. Пример: 1) Является ли данное выражение формулой логики предикатов? – не является формулой, так как квантор существования употреблен для уже связной квантором всеобщности переменной y. - является формулой; x – связанная переменная; y – свободная; - не является формулой, ибо в первом логическом слагаемом х – связанная переменная, а во втором слагаемом свободная. 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) - не тождественно ложная формула, а тогда - истинная формула алгебры предикатов. Формулы Формула содержит только связанную переменную х. Эта формула является тождественно истинным высказыванием в любой интерпретации. Напротив, формула - тождественно ложная формула в любой интерпретации. Применение языка логики предикатов для записи математических предложений Определение экстремума функции (минимума в точке х0) , где Определение выпуклости (вогнутости) функции f(x) Если во всех точках интервала (a,b) вторая производная , то f(x) на (a,b) выпукла.