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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

57
Из определений следует, что каждый тождественно истинный преди-
кат является выполнимым, но не является опровержимым, тогда как каж-
дый тождественно ложный предикат является опровержимым, но не явля-
ется выполнимым. Выполнимый предикат не обязательно является тожде-
ственно истинным. Опровержимый предикат не обязательно является тож-
дественно ложным.
Заметим, что отношение равносильности двух предикатов является
отношением эквивалентности. Переход от предиката
(
)
xP к равносильно-
му ему предикату
(
)
xQ называется равносильным преобразованием пер-
вого.
Уравнения и системы уравнений, неравенства и системы неравенств,
прочие математические объекты представляют собой предикаты. При их
решении мы проделываем равносильные преобразования над ними, целью
которых является поиск множества истинности данного исходного преди-
ката.
Имеет место утверждение.
Два предиката, имеющие одну область определения, равносильны
тогда и только тогда, когда один из них является следствием другого:
Q
P
Û
тогда и только тогда, когда
Q
P
Þ
и
P
Q
Þ
.
Так как предикаты могут принимать два значения 1 или 0, то к ним
применимы все логические операции алгебры высказываний. В резуль-
тате получаем новые предикаты.
Например, конъюнкцией двух предикатов
(
)
xP и
(
)
xQ называется
новый предикат
(
)
(
)
xQ&xP , который принимает значение 1 при тех и
только тех конкретных значениях
,
при которых каждый из преди-
катов
(
)
xP и
(
)
xQ принимает значение 1, и принимает значение 0 во всех
остальных случаях.
(
)
(
)
(
)
(
)
nnn
a,,a,aQ&a,,a,aPa,,a,aQ&P
K
K
K
212121
=
. Очевидно,
.EEE
QPQ&P
I
=
Аналогично определяются операции
Ú
(дизъюнкция),
®
(имплика-
ция),
«
(эквиваленция), ù (отрицание) и т.д.
Легко видеть, что
1.
QPQP
EEE
U
=
Ú
;
2.
PP
P
E\ME
~
E == ;
3.
QPQP
EE
~
E
U
=
®
;
4.
(
)
(
)
(
)
(
)
(
)
U
I
U
I
U
I
QPPQQPPqQPQP
E
~
E
~
EE
~
EE
~
EEE ===
®®«
(
)
(
)
(
)
(
)
(
)
QPQPPQPPQQ
EEE
~
E
~
EEEE
~
E
~
E
I
U
I
I
U
I
U
U
I
U
= ,
т.к. Æ=
QQ
E
~
E
I
и Æ=
PP
EE
~
I
. 
       Из определений следует, что каждый тождественно истинный преди-
кат является выполнимым, но не является опровержимым, тогда как каж-
дый тождественно ложный предикат является опровержимым, но не явля-
ется выполнимым. Выполнимый предикат не обязательно является тожде-
ственно истинным. Опровержимый предикат не обязательно является тож-
дественно ложным.
       Заметим, что отношение равносильности двух предикатов является
отношением эквивалентности. Переход от предиката P � x � к равносильно-
му ему предикату Q � x � называется равносильным преобразованием пер-
вого.
       Уравнения и системы уравнений, неравенства и системы неравенств,
прочие математические объекты представляют собой предикаты. При их
решении мы проделываем равносильные преобразования над ними, целью
которых является поиск множества истинности данного исходного преди-
ката.
       Имеет место утверждение.
       Два предиката, имеющие одну область определения, равносильны
тогда и только тогда, когда один из них является следствием другого:
                 P � Q тогда и только тогда, когда P � Q и Q � P .
   Так как предикаты могут принимать два значения 1 или 0, то к ним
   применимы все логические операции алгебры высказываний. В резуль-
   тате получаем новые предикаты.
       Например, конъюнкцией двух предикатов P � x � и Q � x � называется
новый предикат P � x � & Q � x � , который принимает значение 1 при тех и
только тех конкретных значениях x  M , при которых каждый из преди-
катов P � x � и Q � x � принимает значение 1, и принимает значение 0 во всех
остальных случаях.
       �P & Q ��a1 , a 2 ,� , a n � � P �a1 , a 2 ,� , a n � & Q �a1 , a 2 ,� , a n � . Очевидно,
E P &Q � E P � E Q .
       Аналогично определяются операции � (дизъюнкция), � (имплика-
ция), � (эквиваленция), � (отрицание) и т.д.
       Легко видеть, что
1. E P � Q � E P � E Q ;
            ~
2. E P � E P � M \ E P ;
              ~
3. E P � Q � E P � E Q ;
                                     �              � �          � �
4. E P � Q � �E P � Q � � �E q � P � � E P � E Q � E Q � E P � E P � E Q �
                                       ~                 ~                 ~
                                                                                 � ~

       �           �     �~
                                     �                    �   ~
                                                                   �
     � E Q � E Q � � E P � E P � �E Q � E P � � E P � E Q � �E P � E Q � ,
              ~                                                      ~
                ~             ~
    т.к. E Q � E Q � � и E P � E P � � .


                                               57

Страницы