Понятие предиката

1.

Модуль 3
Формальные теории и
исчисления
Занятие 3.3. Понятие
предиката
2020 г.

2.

Содержание
1.
2.
3.
4.
Одноместные и N-местные
предикаты
Логические операции над
предикатами
Кванторные операции над
предикатами
Обобщение конъюнкции и
дизъюнкции

3.

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

4.

.
Предикат
Множество М - область
определения предиката
P(x)
Множество Ip, на котором
предикат принимает только
истинные значения, называется
областью истинности предиката

5.

N-местный предикат
N-местным предикатом
Q(x1, x2,…,xn) называется всякая
функция n переменных,
определенная на множестве
M=M1xM2x…xMn и принимающая
значение на множестве {0,1}

6.

Тождественно
истинные предикаты
Предикат P(x) называется
тождественно истинным на
множестве М, если Ip=М
Предикат P(x) называется
тождественно ложным на
множестве М, если Ip- пустое
множество

7.

Следствие и
равносильность
Предикат P(x) является
Q(x) (Q(x)=>P(x)), если
следствием
I p IQ
Предикаты P(x) и Q(x) равносильны
(Q(x)=P(x)), если Ip=IQ, т.е. они
являются следствием друг друга

8.

Логические операции
над предикатами
•Конъюнкция &
•Дизъюнкция V
•Отрицание ¯
•Импликация →

9.

Конъюнкция
Конъюнкцией двух предикатов P(x) и Q(x)
называется новый предикат,
Q( x ) & P ( x )
который равен 1 при тех и только при тех
значениях , при которых каждый из
предикатов принимает значение
«истина», и принимает значение «ложь»
во всех остальных случаях
Областью истинности этого предиката
является
I
I
p
Q

10.

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

11.

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

12.

Импликация
Импликацией предикатов P(x) и Q(x)
называется новый предикат,
P(x)=>Q(x)
который равен 0 при тех и только при тех значениях ,
при которых Q(x) принимает значение «истина», а
P(x) - значение «ложь», и принимает значение
«истина» во всех остальных случаях
Область истинности предиката является
I P Q I P
IQ I P
IQ

13.

Кванторные операции
над предикатами
•Квантор существования
•Квантор всеобщности
Кванторные операции связывают
переменные, к которым применяются

14.

Квантор всеобщности
Пусть задан предикат P ( x ), определенный на
множестве М
Тогда под выражением xP ( x ) понимаем
высказывание, истинное тогда и только тогда,
P ( x ) истинен для каждого элемента х
когда
из М, и ложное в противном случае
Это высказывание читается«Для любого х
истинно P ( x ) »
Символ
называется квантором всеобщности

15.

Квантор существования
Под выражением xP ( x )
понимаем
высказывание, истинное тогда и только
тогда, когда существует элемент х из М,
для которого P(x) истинен, и ложное в
противном случае
Это высказывание читается «Существует
х, для которого P(x) истинно»
Символ называется квантором
существования

16.

Связывание переменных
Переменная х в предикате P(x)
свободна, в высказывании xP ( x )
переменная х связана квантором
всеобщности
Переменная х в предикате P(x)
свободна, в высказывании xP ( x )
переменная х связана квантором
существования

17.

Обобщение понятий
Обобщение конъюнкции
xP ( x ) P (a1 ) & P (a2 ) & ... & P ( an )
Обобщение дизъюнкции
xQ( x ) Q(a1 ) Q(a2 ) ... Q(an )