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

UptoLike

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

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