Дискретная математика. Элементы теории, задачи и упражнения. Часть 2. Булгакова И.Н. - 55 стр.

UptoLike

Составители: 

55
9. ПРЕДИКАТЫ. ОПЕРАЦИИ НАД ПРЕДИКАТАМИ
Понятие предиката обобщает понятие высказывания.
Предложение или утверждение, содержащее одно или несколько пе-
ременных, при подстановке вместо которых конкретных значений из неко-
торых множеств мы получаем высказывание (истинное или ложное), назы-
вается предикатом. Количество переменных, от которых зависит преди-
кат, называется местностью или арностью.
Пусть
n
M,,M,M
K
21
множества элементов произвольной природы.
Определение 1:
n
-местным предикатом называется функция
(
)
n
x,,x,xP
K
21
, зависящая от
n
переменных, определенная на множестве
n
MMMM
´
´
´
=
K
21
и принимающая на этом множестве значение
1(истина) или 0 (ложь).
Например,
(
)
xP = [натуральное число
x
кратно 5] одноместный
предикат:
(
)
,P 04
=
(
)
,P 115
=
(
)
,P 011
=
(
)
.P 120
=
(
)
=
y,xQ [город
x
нахо-
дится на территории государства y] двухместный предикат:
(
)
,Россия,МоскваQ 1
=
(
)
,Венгрия,ПарижQ 0
=
(
)
.Франция,ПарижQ 1
=
Само высказывание считается нуль-местным предикатом.
Переменные
n
x,,x,x
K
21
, от которых зависит предикат, называются
предметными переменными. Конкретные значения предметных перемен-
ных называются предметными константами.
Множество
M
, на котором задан предикат, называется областью
определения предиката.
Множество ME
p
, на котором предикат принимает только ис-
тинные значения, называется множеством истинности предиката
(
)
n
x,,x,xP
K
21
:
(
)
(
)
{
}
1
2121
=Î=
nnp
a,,a,aPMa,,a,aE
K
K
.
Различают четыре типа предикатов:
1. Предикат
(
)
n
x,,x,xP
K
21
называется тождественно истинным на
множестве
n
MMMM
´
´
´
=
K
21
, если ME
p
=
, т.е. если на любом
наборе
(
)
Ma,,a,a
n
K
21
предикат принимает значение 1 (истина).
2. Предикат
(
)
n
x,,x,xP
K
21
называется тождественно ложным на
множестве
M
, если
Æ
=
p
E , т.е. если на любом наборе значений пере-
менных предикат принимает значение 0 (ложь).
3. Предикат
(
)
n
x,,x,xP
K
21
называется выполнимым, если его множест-
во истинности
p
E не пусто:
Æ
¹
p
E .
4. Предикат
(
)
n
x,,x,xP
K
21
называется опровержимым, если его множе-
ство истинности
p
E не совпадает с его областью определения, т.е. су-