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

UptoLike

ВУЗ: 

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

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

Рубрика: 

36
Глава 6. Исчисление предикатов.
Рассмотрим построение теории первого порядка.
Компонентами теории первого порядка являются следующие.
1. Алфавит составляют:
•
Предметные константы – буквы начала латинского алфавита с натуральными
индексами:
1
a ,
2
a , …,
1
b ,
2
b , … Предметные символы – это имена (обозначения)
предметов.
•
Предметные переменные – буквы конца латинского алфавита с натуральными
индексами:
1
x ,
2
x , …,
1
y ,
2
y , …
•
Функциональные буквы – строчные буквы латинского алфавита с натуральными
индексами (верхний индекс указывает число переменных, нижний – номер
функциональной буквы):
)(n
k
f ,
)(n
k
g , …
•
Предикатные буквы – заглавные буквы латинского алфавита с натуральными
индексами (верхний индекс указывает число переменных, нижний – номер
предикатной буквы):
)(n
k
A ,
)(n
k
B ,
)(n
k
C ,... (индексы можно не указывать).
•
Логические связки: →¬,.
•
Квантор всеобщности
∀
.
•
Синтаксические символы – скобки (, ) и запятая.
2. Формула определяется несколькими этапами. Вначале вводится понятие
терма.
Определение. 1) Предметные константы и предметные переменные есть
термы.
2) Если
1
t
,
2
t
, …,
n
t
, – термы,
)(n
k
f
– функциональная буква, то
(
)
n
n
k
tttf ,...,,
21
)(
– терм.
3) Символ является термом тогда и только тогда, когда это следует из 1) и 2).
Примеры. 1. Пусть
1
x – предметная переменная,
1
a – предметная константа,
)1(
1
f ,
)2(
1
f – функциональные буквы. Тогда
(
)
1
)1(
1
xf ,
(
)
(
)
11
)1(
1
)2(
1
,axff – термы.
2. Пусть
x
– предметная переменная, a – предметная константа, sin , cos –
функциональные буквы. Тогда
x
sin , axcos – термы. Здесь символы sin , cos имеют
только формальный смысл и не интерпретируются как обозначения
тригонометрических функций. 
Глава 6. Исчисление предикатов.

       Рассмотрим построение теории первого порядка.
       Компонентами теории первого порядка являются следующие.

       1. Алфавит составляют:
•   Предметные константы – буквы начала латинского алфавита с натуральными
    индексами: a1 , a2 , …, b1 , b2 , … Предметные символы – это имена (обозначения)
    предметов.
•   Предметные переменные – буквы конца латинского алфавита с натуральными
    индексами: x1 , x2 , …, y1 , y2 , …
•   Функциональные буквы – строчные буквы латинского алфавита с натуральными
    индексами (верхний индекс указывает число переменных, нижний – номер
    функциональной буквы): f k(n ) , g k(n ) , …
•   Предикатные буквы – заглавные буквы латинского алфавита с натуральными
    индексами (верхний индекс указывает число переменных, нижний – номер
    предикатной буквы): Ak(n ) , Bk(n ) , Ck(n ) ,... (индексы можно не указывать).
•   Логические связки: ¬, → .
•   Квантор всеобщности ∀ .
•   Синтаксические символы – скобки (, ) и запятая.

     2. Формула определяется несколькими этапами. Вначале вводится понятие
терма.

      Определение. 1) Предметные константы и предметные переменные есть
термы.
      2) Если t1 , t 2 , …, t n , – термы, f k(n ) – функциональная буква, то f k( n ) (t1 , t 2 ,..., t n )
– терм.
      3) Символ является термом тогда и только тогда, когда это следует из 1) и 2).

       Примеры. 1. Пусть x1 – предметная переменная, a1 – предметная константа,
                                                                       (            )
 f1(1) , f1( 2) – функциональные буквы. Тогда f1(1) ( x1 ) , f1( 2) f1(1) ( x1 ), a1 – термы.
         2. Пусть x – предметная переменная, a – предметная константа, sin , cos –
функциональные буквы. Тогда sin x , cos ax – термы. Здесь символы sin , cos имеют
только формальный смысл и не интерпретируются как обозначения
тригонометрических функций.




                                                    36

Страницы