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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

Операция замыкания . Основные замкнутые классы .
__________________________________________________________________________________________
112
Пусть
(
)
xP
— одноместный предикат , определенный на множест -
ве
M
.
Определение 3: Квантором общности предиката
(
)
xP
называется
высказывание
(
)
xPx
∀
(читается: для всякого
x
(
)
xP истинно), которое
истинно, когда предикат
(
)
xP
тождественно истинный, и ложно в против-
ном случае, т.е.
()
(
)
()
−
≡
=∀
.предикатйопровржимыxPесли,
;xPесли,
xPx
0
11
Переменную
x
в предикате
(
)
xP
называют свободной, т . к. ей мож -
но придавать различные конкретные значения из множества
M
. В выска -
зывании
(
)
xPx
∀
переменную
x
называют связанной квантором общно-
сти
∀
.
Определение 4: Квантором существования предиката
(
)
xP
назы-
вается высказывание
(
)
xPx
∃
(читается: существует
x
, при котором
(
)
xP
истинно), которое истинно, если существует хотя бы один элемент
M
x
∈
,
для которого
(
)
xP истинно, и ложно в противном случае, т.е.
()
(
)
()
≡
−
=∃
.xPесли,
;предикатвыполнимыйxPесли,
xPx
00
1
В высказывании
(
)
xPx
∃
переменная
x
связана квантором сущест -
вования
∃
. Заметим, что символы
∀
и
∃
происходят от первых букв
английских слов «All» (все) и « Exist» (существовать).
Пример 2. Пусть
(
)
[
]
3≥= xxP , определенный на
множестве натуральных чисел
. Тогда высказыва -
ние
(
)
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
                                           112
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
     Пусть P ( x ) — одноместный предикат, определенный на множест-
ве M .
     Определение 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

Страницы