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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
109
Из определений следует , что каждый тождественно истинный преди-
кат является выполнимым , но не является опровержимым , тогда как каж -
дый тождественно ложный предикат является опровержимым , но не явля-
ется выполнимым . Выполнимый предикат не обязательно является тожде-
ственно истинным . Опровержимый предикат не обязательно является тож -
дественно ложным .
Заметим, что отношение равносильности двух предикатов является
отношением эквивалентности. Переход от предиката
(
)
xP
к равносильно-
му ему предикату
(
)
xQ
называется равносильным преобразованием пер-
вого .
Уравнения и системы уравнений, неравенства и системы неравенств,
прочие математические объекты представляют собой предикаты. При их
решении мы проделываем равносильные преобразования над ними, целью
которых является поиск множества истинности данного исходного преди-
ката.
Имеет место утверждение:
Два предиката, имеющие одну область определения, равносильны
тогда и только тогда, когда один из них является следствием другого :
Q
P
тогда и только тогда, когда
Q
P
и
P
Q
.
Так как предикаты могут принимать два значения 1 или 0, то к ним при -
менимы все логические операции алгебры высказываний. В результате
получаем новые предикаты.
Например, конъюнкцией двух предикатов
(
)
xP и
(
)
xQ называется
новый предикат
(
)
(
)
xQ&xP
, который принимает значение 1 при тех и
только тех конкретных значениях
M
x
, при которых каждый из преди-
катов
(
)
xP
и
(
)
xQ
принимает значение 1, и принимает значение 0 во всех
остальных случаях .
(
)
(
)
(
)
(
)
nnn
a,,a,aQ&a,,a,aPa,,a,aQ&P KKK
212121
. Очевидно,
.EEE
QPQ&P
I
Аналогично определяются операции
(дизъюнкция),
(имплика -
ция),
(эквиваленция), (отрицание) и т.д .
Легко видеть, что
1.
QPQP
EEE U
;
2.
PP
P
E\ME
~
E == ;
3.
QPQP
EE
~
E U=
;