Дискретная математика. Элементы теории задачи и упражнения. Часть 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
                                           108
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
       Например,
        P (x , y ) =[ x + y ≥0 , x , y ∈ R ] — тождественно истинный преди-
кат;
       Q (x 1 , x 2 x 3 ) =[x 12 + 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 (см. рис.)
                                          Y

                                              1




                                  -1                  1         X


                                         -1

Страницы