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

UptoLike

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

56
ществуют такие наборы
(
)
Ma,,a,a
n
Î
K
21
, на которых предикат при-
нимает значение 0.
Например,
(
)
[
]
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
´
Î
>
+
=
F
0
22
опровержимый предикат, т.к.
(
)
{
}
.ME;,\RRE
¹
´
=
FF
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
Ì
(см. рис. 1)
X
Y
1-1
-1
1
Рис. 1