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