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

UptoLike

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

65
Построение отрицаний необходимо при доказательстве от противного:
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 называют дос-
таточным условием для
(
)
xQ , а предикат
(
)
xQ необходимым услови-
ем для предиката
(
)
xP .
Если
,
pQ
EE
то
(
)
(
)
xQxP
Û
, т.е. эти предикаты равносильны.
В этом случае взаимно обратные теоремы (**) истинны при
M
x
Î
"
. Ус-