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

UptoLike

ВУЗ: 

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

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

Рубрика: 

37
Определение. Если
1
t ,
2
t , …,
n
t , – термы,
)(n
k
A – предикатная буква, то символ
()
n
n
k
tttA ,...,,
21
)(
называется элементарной формулой.
Другими словами, элементарная формула образуется при применении
предикатной буквы к термам.
Примеры. 1. В условиях первого примера, если
)2(
1
A
– предикатная буква, то
() ( )
(
)
21
)2(
21
)1(
1
)2(
1
,, xxfxfA – элементарная формула.
2. В условиях второго примера, если ""
)2(
2
≤=A – предикатная буква, то
≤
x
sin axcos – элементарная формула.
Теперь определим формулу логики предикатов.
Определение. 1) Всякая элементарная формула есть формула.
2) Если
A
,
B
– формулы, то формулами являются также символы
A
¬
,
B
A
→ ,
yA∀ .
3) Символ является формулой тогда и только тогда, когда это следует из 1) и
2).
Примеры. 1. В условиях первого примера,
()
(
)
(
)
21
)2(
21
)1(
1
)2(
11
,, xxfxfAx∀ –
формула.
2. В условиях второго примера,
(
)
axxx cossin
≤
∀
– формула.
В теории первого порядка, как и в исчислении высказываний, допускаются
формулы с другими логическими связками, а также допускается использование
квантора существования. Известна формула (см.
Глава 5. Предикаты.).
Здесь мы ненадолго отвлечемся от построения теории первого порядка и
рассмотрим некоторые понятия, связанные с формулами.
Определение. Пусть
A
– формула,
i
x – переменная, которая входит в
формулу
A
(один или несколько раз). Вхождение
i
x
в формулу
A
называется
связанным, если либо
i
x – переменная в кванторе (
i
x
∀
), либо
i
x находится в
области действия квантора
i
x∀ . Если вхождение
i
x в
A
не связано, то оно
называется свободным.
Пример. В формуле
()
ji
xxA ,
)2(
вхождения обеих переменных свободные.
В формуле
()
(
)
(
)
ijii
xAxxAx
)1()2(
, →∀ вхождения переменной
i
x в посылку
связаны, а вхождение в следствие свободно. Вхождение переменной
j
x свободно,
так как отсутствует квантор
j
x∀ . 
          Определение. Если t1 , t 2 , …, t n , – термы, Ak(n ) – предикатная буква, то символ
Ak( n ) (t1 , t 2 ,..., t n ) называется элементарной формулой.

     Другими словами, элементарная формула образуется при применении
предикатной буквы к термам.

          Примеры. 1. В условиях первого примера, если A1( 2) – предикатная буква, то
      (                      )
A1( 2) f1(1) ( x1 ), f 2( 2) ( x1 , x2 ) – элементарная формула.
       2. В условиях второго примера, если A2( 2) =" ≤" – предикатная буква, то
sin x ≤ cos ax – элементарная формула.

          Теперь определим формулу логики предикатов.

          Определение. 1) Всякая элементарная формула есть формула.
          2) Если A , B – формулы, то формулами являются также символы ¬A , A → B ,
∀yA .
          3) Символ является формулой тогда и только тогда, когда это следует из 1) и
2).

                                                                      (                   )
     Примеры. 1. В условиях первого примера, ∀x1 A1( 2) f1(1) ( x1 ), f 2( 2) ( x1 , x2 ) –
формула.
     2. В условиях второго примера, ∀x(sin x ≤ cos ax ) – формула.

     В теории первого порядка, как и в исчислении высказываний, допускаются
формулы с другими логическими связками, а также допускается использование
квантора существования. Известна формула (см. Глава 5. Предикаты.).
     Здесь мы ненадолго отвлечемся от построения теории первого порядка и
рассмотрим некоторые понятия, связанные с формулами.

     Определение. Пусть A – формула, xi – переменная, которая входит в
формулу A (один или несколько раз). Вхождение xi в формулу A называется
связанным, если либо xi – переменная в кванторе ( ∀xi ), либо xi находится в
области действия квантора ∀xi . Если вхождение xi в A не связано, то оно
называется свободным.

          Пример. В формуле A( 2) (xi , x j ) вхождения обеих переменных свободные.
                        (                 )
          В формуле ∀xi A( 2) (xi , x j ) → A(1) ( xi ) вхождения переменной xi в посылку
связаны, а вхождение в следствие свободно. Вхождение переменной x j свободно,
так как отсутствует квантор ∀x j .




                                                     37

Страницы