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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
119
(
)
(
)
(
)
(
)
[
]
()()
[]
.xfxf&xxx
xfxfxxxxfxflim
xx
εδδε
εδδε
≥−<−∃>∀>∃≡
≡<−⇒<−∀>∃>∀⇔≠
→
00
000
00
00
0
Построение отрицаний необходимо при доказательстве от противного :
PQQP →≡→
.
3. Многие теоремы формулируются в виде условного предложения: «Если
любой элемент
M
x
∈
обладает свойством
(
)
xP
, то он обладает свой-
ством
(
)
xQ
» , т.е.
(
)
(
)
[
]
xQxPMx
→
∈
∀
. (*)
Очевидно, что если теорема (*) неверна, то будет истинным утверждение
(
)
(
)
[
]
(
)
(
)
[
]
.xQ&xPMxxQxPMx ∈∃≡→∈∀
Поэтому для доказательства несправедливости теоремы (*) нужно указать
хотя бы один элемент из множества
M
, при котором условие
(
)
xP истин -
но, а значение
(
)
xQ
ложно. Другими словами, нужно привести контрпри -
мер.
4. Прямая, обратная и противоположная теоремы. Необходимые и
достаточные условия.
Определение. Теоремы
(
)
(
)
[
]
xQxPMx
→
∈
∀
и
(
)
(
)
[
]
xPxQMx
→
∈
∀
(**)
называются взаимно обратными, т. к. условие
(
)
xP
одной теоремы явля-
ется заключением второй, а условие
(
)
xQ второй теоремы является за -
ключением первой. При этом одна из них называется прямой теоремой,
другая — обратной.
Определение. Теоремы
(
)
(
)
[
]
xQxPMx
→
∈
∀
и
(
)
(
)
[
xQxPMx →∈∀
называются взаимно противоположными. В них условие
(
)
xP
и заключе-
ние
(
)
xQ одной являются отрицанием соответствующего условия
(
)
xP и
заключения
(
)
xQ
другой. Заметим, что теоремы
(
)
(
)
[
]
xQxPMx
→
∈
∀
и
(
)
(
)
[
xPxQMx →∈∀
всегда равносильны. На этом основывается метод доказательства от
противного .
Известно, что если
Qp
EE
⊂
, то предикат
(
)
xQ есть следствие пре -
диката
(
)
xP :
(
)
(
)
xQxP
⇒
. Отсюда следует , что предикат
(
)
(
)
xQxP
→
является истинным для
M
x
∈
∀
. При этом предикат
(
)
xP называют дос-
                                           119
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________

lim f ( x ) ≠ f ( x 0 ) ⇔ ∀ε >0 ∃δ >0 ∀ x [ x − x 0 <δ ⇒         f ( x ) − f ( x 0 ) <ε ] ≡
x→ x0

        ≡∃ε >0 ∀ δ >0 ∃x [ x − x 0 <δ & f (x ) − f ( x 0 ) ≥ε ].
Построение отрицаний необходимо при доказательстве от противного:
P → Q ≡Q → P .

3. Многие теоремы формулируются в виде условного предложения: «Если
   любой элемент x ∈ M обладает свойством P ( x ), то он обладает свой-
   ством Q( x )» , т.е.
                           ∀x ∈M [P ( x ) → Q( x )].                  (*)
Очевидно, что если теорема (*) неверна, то будет истинным утверждение
                                                        [
               ∀x ∈ M [P ( x ) → Q ( x )] ≡∃x ∈ M P ( x ) & Q ( x ) .  ]
Поэтому для доказательства несправедливости теоремы (*) нужно указать
хотя бы один элемент из множества M , при котором условие P ( x ) истин-
но, а значение Q ( x ) ложно. Другими словами, нужно привести контрпри-
мер.

4. Прямая, обратная и противоположная теоремы. Необходимые и
   достаточные условия.

                    Определение. Теоремы
               ∀x ∈ M [P ( x ) → Q( x )] и ∀x ∈ M [Q ( x ) → P ( x )] (**)
называются взаимно обратными, т. к. условие P ( x ) одной теоремы явля-
ется заключением второй, а условие Q( x ) второй теоремы является за-
ключением первой. При этом одна из них называется прямой теоремой,
другая — обратной.

                       Определение. Теоремы
             ∀x ∈M [P ( x ) → Q( x )] и ∀x ∈M [P (x ) → Q (x )]
называются взаимно противоположными. В них условие P ( x ) и заключе-
ние Q(x ) одной являются отрицанием соответствующего условия P ( x ) и
заключения Q ( x ) другой. Заметим, что теоремы
             ∀x ∈M [P ( x ) → Q( x )] и ∀x ∈M [Q ( x ) → P (x )]
всегда равносильны. На этом основывается метод доказательства от
противного.

        Известно, что если E p ⊂ E Q , то предикат Q( x ) есть следствие пре-
диката P ( x ): P ( x ) ⇒ Q(x ) . Отсюда следует, что предикат P ( x ) → Q(x )
является истинным для ∀x ∈ M . При этом предикат P ( x ) называют дос-

Страницы