Дискретная математика. Элементы теории задачи и упражнения. Часть 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 называют дос-