Математическая логика и теория алгоритмов. Сергиевская И.М. - 26 стр.

UptoLike

ВУЗ: 

ПГУТИ | Самара

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

Рубрика: 

31
Пример. Очевидно, что высказывание
(
)
0=
+
∃
∀
yxyx (
R
X = ) истинно.
Поменяем кванторы местами. Получим высказывание
()
0=+∀
∃
yxxy , которое
является ложным.
Выражения с кванторами можно преобразовывать следующим образом:
()
)()()()( xxQxxPxQxPx ∀∧∀=∧∀
,
(
)
)()()()( xxQxxPxQxPx ∃∨
∃
=
∨
∃
.
Докажем первую эквивалентность. Пусть предикаты )(
x
P
и )(
x
Q
одновременно тождественно истинны. Тогда тождественно истинным будет и
предикат )()(
x
Q
x
P
∧ , следовательно, истинными будут высказывания
()
)()( xQxPx ∧∀ , )(
x
xP
∀ , )(
x
x
Q∀ , а также )()(
x
x
Q
x
xP
∀
∀
.
Пусть теперь хотя бы один из предикатов (например, )(
x
P
) не является
тождественно истинным. Тогда (по свойствам конъюнкции) тождественно
истинным не будет и предикат )()(
x
Q
x
P
, следовательно, ложным будет
высказывание
()
)()( xQxPx ∧∀ . Высказывания )(
x
xP
∀
и )()(
x
x
Q
x
xP
∀∧∀ также
будут ложными.
Таким образом, обе части эквивалентности одновременно истинны или
ложны, и эквивалентность доказана.
Замечание. Формула
(
)
)()( xQxPx ∨
∀
не эквивалентна формуле
)()(
x
x
Q
x
xP
∀∨∀ .
Доказательство. Рассмотрим обе формулы на множестве
R
. Пусть предикат
"0")( <=
x
x
P
, а предикат "0")( ≥
=
x
x
Q . Оба предиката не являются тождественно
истинными. Предикат "")()(
R
x
x
Q
x
P
∈
=
∨ – тождественно истинный, и
высказывание
()
)()( xQxPx ∨∀ истинно. Высказывания )(
x
xP
∀
и )(
x
x
Q∀ ложны,
следовательно, ложно и высказывание )()(
x
x
Q
x
xP
∀
∨
∀
. Таким образом, построен
пример, когда формулы
()
)()( xQxPx ∨∀
и )()(
x
x
Q
x
xP
∀
∨
∀
принимают различные
значения.
Тем не менее, справедливы эквивалентности:
=∀∨∀ )()(
x
x
Q
x
xP
=
∀∨∀ )()( yyQ
x
xP
(
)
=
∀
∨
∀
)()( yyQxPx
()
)()( yQxPyx ∨∀∀= .
Аналогично, формулы
(
)
)()( xQxPx
∧
∃
и )()(
x
x
Q
x
xP
∃
∃
не эквивалентны. Но
справедливы эквивалентности:
=∃∧∃ )()(
x
x
Q
x
xP
=
∃∧∃ )()( yyQ
x
xP
(
)
=
∃
∧
∃
)()( yyQxPx
()
)()( yQxPyx ∧∃∃= .
Имеют место формулы:
()
CxxPCxPx ∧∀=∧∀ )()(,
()
CxxPCxPx ∨
∃
=
∨∃ )()(,
()
CxxPCxPx ∨∀=∨∀ )()(,
()
CxxPCxPx
∧
∃
=
∧
∃ )()(.
Здесь
C
не содержит переменной
x
. 
      Пример. Очевидно, что высказывание ∀x∃y ( x + y = 0 ) ( X = R ) истинно.
Поменяем кванторы местами. Получим высказывание ∃y∀x( x + y = 0 ) , которое
является ложным.

     Выражения с кванторами можно преобразовывать следующим образом:
∀x(P( x) ∧ Q( x) ) = ∀xP( x) ∧ ∀xQ( x) , ∃x(P( x) ∨ Q( x) ) = ∃xP( x) ∨ ∃xQ( x) .
     Докажем первую эквивалентность. Пусть предикаты P( x) и Q ( x)
одновременно тождественно истинны. Тогда тождественно истинным будет и
предикат      P( x) ∧ Q( x) , следовательно, истинными будут высказывания
∀x(P( x) ∧ Q( x) ) , ∀xP( x) , ∀xQ( x) , а также ∀xP( x) ∧ ∀xQ( x) .
     Пусть теперь хотя бы один из предикатов (например, P( x) ) не является
тождественно истинным. Тогда (по свойствам конъюнкции) тождественно
истинным не будет и предикат P( x) ∧ Q( x) , следовательно, ложным будет
высказывание ∀x(P( x) ∧ Q( x) ) . Высказывания ∀xP( x) и ∀xP( x) ∧ ∀xQ( x) также
будут ложными.
     Таким образом, обе части эквивалентности одновременно истинны или
ложны, и эквивалентность доказана.

       Замечание.       Формула      ∀x(P( x) ∨ Q( x) )  не   эквивалентна   формуле
∀xP( x) ∨ ∀xQ( x) .
       Доказательство. Рассмотрим обе формулы на множестве R . Пусть предикат
P( x) =" x < 0" , а предикат Q( x) =" x ≥ 0" . Оба предиката не являются тождественно
истинными. Предикат           P( x) ∨ Q( x) =" x ∈ R" – тождественно истинный, и
высказывание ∀x(P( x) ∨ Q( x) ) истинно. Высказывания ∀xP( x) и ∀xQ( x) ложны,
следовательно, ложно и высказывание ∀xP( x) ∨ ∀xQ( x) . Таким образом, построен
пример, когда формулы ∀x(P( x) ∨ Q( x) ) и ∀xP( x) ∨ ∀xQ( x) принимают различные
значения.

      Тем не менее, справедливы эквивалентности:
∀xP( x) ∨ ∀xQ( x) = ∀xP( x) ∨ ∀yQ( y ) = ∀x(P( x) ∨ ∀yQ( y ) ) =
= ∀x∀y (P( x) ∨ Q( y ) ) .

      Аналогично, формулы ∃x(P( x) ∧ Q( x) ) и ∃xP( x) ∧ ∃xQ( x) не эквивалентны. Но
справедливы эквивалентности:
∃xP( x) ∧ ∃xQ( x) = ∃xP( x) ∧ ∃yQ( y ) = ∃x(P( x) ∧ ∃yQ( y ) ) =
= ∃x∃y (P( x) ∧ Q( y ) ) .
      Имеют место формулы:
∀x(P ( x) ∧ C ) = ∀xP( x) ∧ C , ∃x(P ( x) ∨ C ) = ∃xP( x) ∨ C ,
∀x(P ( x) ∨ C ) = ∀xP( x) ∨ C , ∃x(P( x) ∧ C ) = ∃xP( x) ∧ C .
      Здесь C не содержит переменной x .



                                             31

Страницы