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

UptoLike

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

59
Определение 3. Квантором общности предиката
(
)
xP называется
высказывание
(
)
xPx
"
(читается: для всякого
x
(
)
xP истинно), которое
истинно, когда предикат
(
)
xP тождественно истинный, и ложно в против-
ном случае, т.е.

1, если Pxє1;
0,
если Px опровержимыйпредикат.
Переменную
x
в предикате
(
)
xP называют свободной, т. к. ей мож-
но придавать различные конкретные значения из множества
.
M
В выска-
зывании
(
)
xPx
"
переменную
x
называют связанной квантором общно-
сти
"
.
Определение 4. Квантором существования предиката
(
)
xP назы-
вается высказывание
(
)
xPx
$
(читается: существует
x
, при котором
(
)
xP
истинно), которое истинно, если существует хотя бы один элемент
,
xM
для которого
(
)
xP истинно, и ложно в противном случае, т.е.
()
(
)
()
î
í
ì
º
-
=$
.xPесли,
;предикатвыполнимыйxPесли,
xPx
00
1
В высказывании
(
)
xPx
$
переменная
x
связана квантором сущест-
вования
$
. Заметим, что символы
"
и
$
происходят от первых букв анг-
лийских слов «All» (все) и «Exist» (существовать).
Пример 2. Пусть
(
)
[
]
3
³
=
xxP , определенный на множестве нату-
ральных чисел
N
. Тогда высказывание
(
)
xPx
"
ложно, высказывание
(
)
xPx
$
истинно.
Пример 3. Даны предикаты
()
ú
û
ù
ê
ë
é
Î>++= Rx,xxxP 0
2
1
2
и
(
)
[
]
Rx,xxxQ
Î
=
+
-
=
065
2
, определенные на множестве действитель-
ных чисел. Установить, какие из следующих высказываний истинны, а ка-
кие ложны:
1.
(
)
xPx
"
; 3.
(
)
xQx
"
;
2.
(
)
xPx
$
; 4.
(
)
xQx
$
.
Решение. Т. к. квадратный трехчлен 0
4
1
2
1
2
1
2
2
>+
÷
ø
ö
ç
è
æ
+=++ xxx
при всех
R
x
Î
, то высказывания
(
)
xPx
"
и
(
)
xPx
$
истинны.
Т. к. уравнение
0
6
5
2
=
+
-
xx имеет два действительных корня
2
1
=
x и 3
2
=
x , то предикат
(
)
xQ принимает значение 1 только при
2
=
x
и при
3
=
x
, а значение 0 в остальных случаях. Поэтому высказывание
(
)
xQx
"
ложно, высказывание
(
)
xQx
$
истинно.
      Определение 3. Квантором общности предиката P � x � называется
высказывание �x P � x � (читается: для всякого x P � x � истинно), которое
истинно, когда предикат P � x � тождественно истинный, и ложно в против-
ном случае, т.е.
                         
                         1, если P  x є1;
            "x P  x  = 
                         
                         
                         0, если P  x   опровержимый предикат.
                         
      Переменную x в предикате P � x � называют свободной, т. к. ей мож-
но придавать различные конкретные значения из множества M . В выска-
зывании �x P � x � переменную x называют связанной квантором общно-
сти � .

       Определение 4. Квантором существования предиката P � x � назы-
вается высказывание �x P � x � (читается: существует x , при котором P � x �
истинно), которое истинно, если существует хотя бы один элемент x  M ,
для которого P � x � истинно, и ложно в противном случае, т.е.
                          �1, если P � x � � выполнимый предикат ;
             �x P � x � � �
                          �0 , если P � x � � 0.
       В высказывании �x P � x � переменная x связана квантором сущест-
вования � . Заметим, что символы � и � происходят от первых букв анг-
лийских слов «All» (все) и «Exist» (существовать).
       Пример 2. Пусть P � x � � � x � 3� , определенный на множестве нату-
ральных чисел N . Тогда высказывание �x P � x � ложно, высказывание
�x P � x � истинно.
                                                        �          1           �
      Пример 3. Даны предикаты                P � x � � � x 2 � x � � 0 , x � R� и
                                                        �          2           �
Q � x � � �x � 5 x � 6 � 0 , x � R � , определенные на множестве действитель-
            2


ных чисел. Установить, какие из следующих высказываний истинны, а ка-
кие ложны:
 1. �x P � x � ;       3. �x Q � x � ;
 2. �x P � x � ;       4. �x Q � x � .
                                                                        2
                                                           1 �    1�   1
      Решение. Т. к. квадратный трехчлен x � x � � � x � � � � 0
                                                    2

                                                           2 �    2�   4
при всех x � R , то высказывания �x P � x � и �x P � x � истинны.
      Т. к. уравнение x 2 � 5 x � 6 � 0 имеет два действительных корня
x1 � 2 и x 2 � 3 , то предикат Q � x � принимает значение 1 только при x � 2
и при x � 3 , а значение 0 в остальных случаях. Поэтому высказывание
�x Q � x � ложно, высказывание �x Q � x � истинно.
                                       59