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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
108
Например,
(
)
[
]
Ry,x,yxy,xP += 0 тождественно истинный преди-
кат;
(
)
[
]
3210
2
3
2
2
2
1321
,,i,Rx,xxxxx,xQ
i
=<++= тождественно
ложный предикат, т.к.
=
Q
E .
(
)
[
]
Nx,xxF
=
+
=
13
выполнимый предикат, т.к.
{
}
=
2
F
E .
(
)
(
)
[
]
RRy,x,yxy,x ×>+ 0
22
опровержимый предикат,
т.к.
(
)
{
}
.ME;,\RRE
×
=
ΦΦ
00
Говорят , что предикат
(
)
xQ
является следствием предиката
(
)
xP
(
)
(
)
(
)
xQxP
, если
P
E
является подмножеством
Q
E
:
QP
EE
.
Определение 2: Два предиката
(
)
xP
и
(
)
xQ
, определенные на одном
и том же множестве, одной и той же местности, называются равносиль -
ными
(
)
(
)
(
)
xQxP
, если их множества истинности совпадают:
QP
EE
=
.
Например,
(
)
[
]
Zy,x,yxy,xP =+= 1
22
и
(
)
[
]
Zy,x,yxy,xQ =+= 1
равносильные двухместные предикаты, т.к.
(
)
(
)
(
)
(
)
{
}
10010110
=
=
,,,,,,,EE
QP
.
Предикат
(
)
[
]
Ry,x,yxy,xA += 1
22
является следствием
предиката
(
)
[
]
Ry,x,yxy,xB += 1
, т.к.
AB
EE
(см . рис.)
X
Y
1-1
-1
1