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

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

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

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

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

предикатом, так как в нем нет аргумента – переменного х.
2) - то же самое.
3) - предикат. Здесь:

истинным, если область определения предиката , и называется тождественно ложным, если

Говорят, что предикат Р(х) является следствием предиката Q(x) (Q(x)→Р (x)), если , и предикаты P(x) и Q(x) равносильны ( ), если

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

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

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

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

являются истинным при тех и только тех значениях xєM, при которых одновременно 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 – нечетное, но составное число.

на плоскости.

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

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) , определенный на множестве M:{a1,…,an}. Справедлива равносильность

при какого бы не было х;
для каждого х верно P(x);
всегда имеет место P(x);
каждый обладает свойством P;
всё удовлетворяет P.

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

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

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)следующим образом

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

истинно.

q2, r3, … – переменные высказывания;
Предметные переменные и предметные константы;

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

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

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

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

делится на 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) выпукла.