Дискретная математика. Элементы теории задачи и упражнения. Часть 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
∀
∃
означа -
                                           113
Операция замыкания. Основные замкнутые классы.
__________________________________________________________________________________________
и при x =3 , а значение 0 в остальных случаях. Поэтому высказывание
∀x Q( x ) ложно, высказывание ∃x Q (x ) истинно.

       Если одноместный предикат P ( x ) задан на конечном множестве
M ={a 1 , a 2 , , a n }, то нетрудно видеть, что
       1. ∀x P ( x ) =P (a 1 ) & 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 ) означа-

Страницы