Дискретная математика. Элементы теории, задачи и упражнения. Часть 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
. Это высказывание, очевидно, ложно. 
       Если одноместный предикат P � x � задан на конечном множестве
M � �a1 , a 2 ,� , a n �, то нетрудно видеть, что
       1. �x P � x � � P �a1 � & P �a 2 � & � & P �a n � ;
       2. �x P � x � � P �a1 � � P �a 2 � � � � P �a n � ,
т. е. кванторные операции обобщают операции & и � на случай бесконеч-
ных множеств.
       Считается, что кванторы «связывают» сильнее, чем операции логики
высказываний.
       Имеют место формулы связи кванторов:
                           �x P � x � � � x P � x � и � x P � x � � �x P � x � ,
которые широко используются при равносильных преобразованиях в логи-
ке предикатов.
       Докажем первое равенство: пусть
        x P  x   0  x P  x   1  P  x   1  P  x   0  x P  x   0.
       Второе равенство доказывается аналогично.

     Кванторные операции применяются и к многоместным предикатам.
     Например, применяя квантор общности по переменной x к двухме-
стному предикату P � x , y � � � x � y � 0 , x , y � R � получаем одноместный
предикат, зависящий от переменной y :
            �x P � x , y � � � � y �;
              � �1� � �x P � x,1� � �x � x � 1 � 0� � 1 (истина ),
               � �� 1� � �x P � x,�1� � �x � x � 1 � 0� � 0 ( ложь).
      К предикату � � y � можно применить кванторные операции по пере-
менной y . В результате получим высказывание: �y � � y � � �y ��x P � x , y ��
или �y � � y � � �y ��x P � x , y �� .
      Заметим, что перестановка любых кванторов местами, вообще гово-
ря, изменяет логическое значение высказывания.
      Пример 4. Показать, что высказывания �x �y P � x , y � и
�y �x P � x , y � имеют различные логические значения, где двухместный
предикат P � x , y � � � x � y � определен на множестве M � N � N .
      Решение: Высказывание �x �y P � x , y � означает утверждение, что
для любого натурального числа x найдется натуральное число y , большее
числа x . Это высказывание истинно. Высказывание �y �x P � x , y � означа-
ет, что существует натуральное число y , которое больше любого нату-
рального числа x . Это высказывание, очевидно, ложно.


                                         60

Страницы