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

UptoLike

ВУЗ: 

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

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

Рубрика: 

41
Теорема о полноте. Всякая логически общезначимая формула является
теоремой исчисления предикатов.
Рассмотрим несколько примеров теорий первого порядка с собственными
аксиомами, (приведем только собственные аксиомы). Для удобства вместо
предикатных и функциональных букв будем записывать привычные символы.
Теория равенства.
Теория равенства – теория первого порядка с предикатной буквой ""
)2(
1
==A .
Собственные аксиомы следующие:
1)
()
xxx =∀ .
2) )()(
y
A
x
A
y
x
=⇒= .
Здесь
A
– произвольная предикатная буква.
Формальная арифметика.
Формальная арифметика – теория первого порядка со следующими
специальными символами.
1)
Предметная константа 0.
2)
Двуместные функциональные буквы
(
)
yxyxf +=,
)2(
1
и
(
)
yxyxf ×=,
)2(
2
,
одноместная функциональная буква
(
)
xxf
′
=
)1(
1
.
3)
Двуместная предикатная буква ""
)2(
1
==A .
Собственные аксиомы следующие:
1)
()()
)(()()0( xxPxPxPxP ∀→
′
→∀∧ .
2)
()
212121
xxxxxx =→
′
=
′
∀∀ .
3)
()
0
1
=
′
¬ x .
4)
()()
313221321
xxxxxxxxx
=
→=→=∀∀∀ .
5)
()
212121
xxxxxx
′
=
′
→=∀∀
.
6)
()
111
0 xxx =+∀ .
7)
()
(
)
′
+=
′
+∀∀
212121
xxxxxx
.
8)
()
00
11
=×∀ xx .
9)
()
1212121
xxxxxxx +×=
′
×∀∀ .
Здесь
P
– произвольная предикатная буква.
Теория частично упорядоченных множеств.
Теория частично упорядоченных множеств – это теория первого порядка с
двумя предикатными буквами ""
)2(
1
≤=A , ""
)2(
1
==A .
Собственные аксиомы следующие: 
     Теорема о полноте. Всякая логически общезначимая формула является
теоремой исчисления предикатов.

     Рассмотрим несколько примеров теорий первого порядка с собственными
аксиомами, (приведем только собственные аксиомы). Для удобства вместо
предикатных и функциональных букв будем записывать привычные символы.

      Теория равенства.

      Теория равенства – теория первого порядка с предикатной буквой A1( 2) =" =" .
      Собственные аксиомы следующие:
1) ∀x( x = x ) .
2) x = y ⇒ A( x) = A( y ) .
      Здесь A – произвольная предикатная буква.

      Формальная арифметика.

     Формальная арифметика – теория первого порядка со следующими
специальными символами.
1) Предметная константа 0.
2) Двуместные функциональные буквы f1( 2) ( x, y ) = x + y и f 2( 2) ( x, y ) = x × y ,
   одноместная функциональная буква f1(1) ( x ) = x ′ .
3) Двуместная предикатная буква A1( 2) =" =" .
      Собственные аксиомы следующие:
1) (P(0) ∧ ∀x(P( x) → P( x ′)) → ∀xP( x) .
2) ∀x1∀x2 ( x1′ = x′2 → x1 = x2 ) .
3) ¬( x1′ = 0 ) .
4) ∀x1∀x2 ∀x3 ( x1 = x2 → ( x2 = x3 → x1 = x3 )) .
5) ∀x1∀x2 ( x1 = x2 → x1′ = x2′ ) .
6) ∀x1 ( x1 + 0 = x1 ) .
          (                   )   ′
7) ∀x1∀x2 x1 + x ′2 = ( x1 + x 2 ) .
8) ∀x1 ( x1 × 0 = 0 ) .
9) ∀x1∀x2 ( x1 × x2′ = x1 × x2 + x1 ) .
         Здесь P – произвольная предикатная буква.

      Теория частично упорядоченных множеств.

     Теория частично упорядоченных множеств – это теория первого порядка с
двумя предикатными буквами A1( 2) =" ≤" , A1( 2) =" =" .
     Собственные аксиомы следующие:



                                            41

Страницы