Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
Î
"
. Ус-
Построение отрицаний необходимо при доказательстве от противного:
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 � называют дос-
таточным условием для Q � x � , а предикат Q � x � — необходимым услови-
ем для предиката P � x � .
      Если E p  EQ , то P � x � � Q � x � , т.е. эти предикаты равносильны.
В этом случае взаимно обратные теоремы (**) истинны при �x � M . Ус-
                                        65

Страницы