Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
   ществуют такие наборы �a1 , a 2 ,� , a n � � M , на которых предикат при-
   нимает значение 0.
      Например,
      P � x , y � � � x � y � 0 , x , y � R� — тождественно истинный преди-
кат.
      Q � x1 , x 2 x 3 � � �x12 � x 22 � x 32 � 0 , x i � R , i � 1, 2 , 3� — тождественно
ложный предикат, т.к. E Q � � .
      F � x � � � x � 3 � 1, x � N � – выполнимый предикат, т.к. E F � �� 2� � � .
      � � x , y � � �x 2 � y 2 � 0 , � x , y � � R � R � – опровержимый предикат, т.к.
E � � R � R \ ��0 ,0 ��; E � � M .

          Говорят, что предикат Q � x � является следствием предиката P � x �
� P � x � � Q� x �� , если E P является подмножеством E Q : E P � E Q .
     Определение 2: два предиката P � x � и Q � x � , определенные на одном
и том же множестве, одной и той же местности, называются равносиль-
ными � P � x � � Q � x �� , если их множества истинности совпадают: E P � E Q .

      Например,
      P � x , y � � �x 2 � y 2 � 1, x , y � Z � и Q � x , y � � � x � y � 1, x , y � Z � —
равносильные                      двухместные                 предикаты,                 т.к.
E P � E Q � ��0 ,1�, �1,0 �, �� 1,0�, �0 ,�1�� .
      Предикат A� x , y � � �x 2 � y 2 � 1, x , y � R� является следствием преди-
ката B� x , y � � � x � y � 1, x , y � R � , т.к. E B � E A (см. рис. 1)
                                           Y

                                                     1




                                   -1                    1        X


                                           -1




                                          Рис. 1



                                                56