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

UptoLike

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
113
и при
3
=
x
, а значение 0 в остальных случаях. Поэтому высказывание
(
)
xQx
ложно, высказывание
(
)
xQx
истинно.
Если одноместный предикат
(
)
xP
задан на конечном множестве
{
}
n
a,,a,aM K
21
=
, то нетрудно видеть, что
1.
(
)
(
)
(
)
(
)
n
aP&&aP&aPxPx K
21
=
;
2.
(
)
(
)
(
)
(
)
n
aPaPaPxPx
=
K
21
,
т.е. кванторные операции обобщают операции & и
на случай бесконеч-
ных множеств.
Считается, что кванторы «связывают» сильнее, чем операции логики
высказываний.
Имеют место формулы связи кванторов:
(
)
(
)
xPxxPx =∀ и
(
)
(
)
xPxxPx =∃ ,
которые широко используются при равносильных преобразованиях в логи -
ке предикатов.
Докажем первое равенство: пусть
(
)
(
)
(
)
(
)
(
)
00110 ===∀ xPxxPxPxPxxPx
.
Второе равенство доказывается аналогично.
Кванторные операции применяются и к многоместным предикатам.
Например, применяя квантор общности по переменной
x
к двухме-
стному предикату
(
)
[
]
Ry,x,yxy,xP >+= 0 получаем одноместный
предикат, зависящий от переменной
y
:
(
)
(
)
()()
[]
()()
[]
).(,
),(,
;,
ложьxxxPx
истинаxxxPx
yyxPx
00111
10111
=>==−Φ
=>+=
Φ
=
К предикату
(
)
y
Φ
можно применить кванторные операции по пере -
менной
y
. В результате получим высказывание:
(
)
(
)
(
)
y,xPxyyy
=
Φ
или
(
)
(
)
(
)
y,xPxyyy
=
Φ
.
Заметим, что перестановка любых кванторов местами, вообще гово-
ря, изменяет логическое значение высказывания.
Пример 4. Показать, что высказывания
(
)
y,xPyx
и
(
)
y,xPxy
имеют различные логические значения, где двухместный
предикат
(
)
[
]
yxy,xP
<
=
определен на множестве
N
N
M
×
=
.
Решение: Высказывание
(
)
y,xPyx
означает утверждение, что
для любого натурального числа
x
найдется натуральное число
y
, большее
числа
x
. Это высказывание истинно. Высказывание
(
)
y,xPxy
означа -