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

UptoLike

ВУЗ: 

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

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

Рубрика: 

32
Определение. Предикатная формула находится в приведенной форме, если в
ней использованы только кванторные операции, а также операции инверсии,
конъюнкции, дизъюнкции, причем инверсия относится только к предикатным
буквам.
Определение. Предикатная формула находится в предваренной форме
(предваренной нормальной форме), если она имеет вид
AxQxQxQ
kk
...
2211
, где
k
QQQ ,...,,
21
- кванторы всеобщности или существования, а формула
A
находится в
приведенной форме и не содержит кванторов.
Пример. Записать формулу
)(),(),(
x
R
y
x
yQ
x
y
x
y
P
x
A
∨∃∀→∀∃=
в предваренной нормальной форме.
Решение.
=
∨
∃
∀
→∀
∃
= )(),(),(
x
R
y
x
yQ
x
y
x
y
P
x
A
=
∨
∃
∀∨∀¬∃= )(),(),(
x
R
y
x
yQ
x
y
x
y
P
x
).(),(),(
)(),(),(
xRyxyQxyxPyx
x
R
y
x
yQ
x
y
x
y
P
x
∨∃∀∨¬∃∀=
=
∨
∃
∀∨¬∀∀=
Полученная формула записана в приведенной форме. Для того чтобы квантор
всеобщности можно было вынести за скобки, переобозначим переменные и
выполним преобразования:
()
=∨∃∀∨¬∃∀=
=
∨
∃
∀∨¬∃∀=
)(),(),(
)(),(),(
xRyzyQzytPyt
x
R
yzyQzy
t
P
y
t
A
()
=
∨
∃
∨¬∃∀∀= )(),(),( xRyzyQytPyzt
()
)(),(),( xRyzQytPyzt ∨∨¬∃∀∀= .
Рассмотрим предикат )(
x
P
, определенный на конечном множестве
{}
n
aaaX ,...,,
21
= . Если предикат )(
x
P
является тождественно истинным, то
истинными будут высказывания
)(
1
aP
,
)(
2
aP
, …,
)(
n
aP
. При этом истинными
будут высказывания )(
x
xP
∀
и конъюнкция )(
1
aP )(
2
aP … )(
n
aP .
Если же хотя бы для одного элемента
Ma
k
)(
k
aP
будет ложно, то ложными
будут высказывания )(
x
xP
∀
и )(
1
aP )(
2
aP … )(
n
aP .
Таким образом, имеет место эквивалентность
=
∀
)(
x
xP
)(
1
aP )(
2
aP … )(
n
aP .
Справедлива и аналогичная эквивалентность
=∃ )(
x
xP
)(
1
aP ∨ )(
2
aP ∨ … ∨ )(
n
aP .
Пример. Найти предикат, логически эквивалентный предикату
),(),(
y
x
x
BzyyAz ∀∨∀∃ , но не содержащий кванторов. Предикаты
A
и
B
определены на множестве
{}
cba ,,.
Решение.
=
∀∨∀∃ ),(),( y
x
x
BzyyAz 
        Определение. Предикатная формула находится в приведенной форме, если в
ней использованы только кванторные операции, а также операции инверсии,
конъюнкции, дизъюнкции, причем инверсия относится только к предикатным
буквам.
        Определение. Предикатная формула находится в предваренной форме
(предваренной нормальной форме), если она имеет вид Q1 x1Q2 x2 ...Qk xk A , где
Q1 , Q2 ,..., Qk - кванторы всеобщности или существования, а формула A находится в
приведенной форме и не содержит кванторов.

      Пример. Записать формулу
A = ∃x∀yP( x, y ) → ∀x∃yQ( x, y ) ∨ R ( x)
в предваренной нормальной форме.
      Решение. A = ∃x∀yP( x, y ) → ∀x∃yQ( x, y ) ∨ R ( x) =
= ¬∃x∀yP( x, y ) ∨ ∀x∃yQ( x, y ) ∨ R ( x) =
= ∀x¬∀yP( x, y ) ∨ ∀x∃yQ( x, y ) ∨ R( x) =
= ∀x∃y¬P ( x, y ) ∨ ∀x∃yQ( x, y ) ∨ R ( x).
       Полученная формула записана в приведенной форме. Для того чтобы квантор
всеобщности можно было вынести за скобки, переобозначим переменные и
выполним преобразования:
A = ∀t∃y¬P(t , y ) ∨ ∀z∃yQ( z , y ) ∨ R( x) =
= ∀t (∃y¬P(t , y ) ∨ ∀z∃yQ( z , y ) ∨ R( x) ) =
= ∀t∀z (∃y¬P(t , y ) ∨ ∃yQ( z, y ) ∨ R( x) ) =
= ∀t∀z∃y (¬P (t , y ) ∨ Q( z , y ) ∨ R ( x) ) .

      Рассмотрим предикат P( x) , определенный на конечном множестве
X = {a1 , a2 ,..., an }. Если предикат P( x) является тождественно истинным, то
истинными будут высказывания P(a1 ) , P(a 2 ) , …, P(a n ) . При этом истинными
будут высказывания ∀xP( x) и конъюнкция P(a1 ) P (a 2 ) … P (a n ) .
      Если же хотя бы для одного элемента ak ∈ M P(ak ) будет ложно, то ложными
будут высказывания ∀xP( x) и P(a1 ) P (a 2 ) … P (a n ) .
      Таким образом, имеет место эквивалентность ∀xP( x) = P(a1 ) P(a 2 ) … P(an ) .
      Справедлива и аналогичная эквивалентность
∃xP( x) = P(a1 ) ∨ P (a 2 ) ∨ … ∨ P (a n ) .

     Пример.         Найти      предикат,   логически эквивалентный предикату
∃z∀yA( y, z ) ∨ ∀xB( x, y ) , но не содержащий кванторов. Предикаты A и B
определены на множестве {a, b, c} .
     Решение. ∃z∀yA( y, z ) ∨ ∀xB( x, y ) =




                                            32

Страницы