Математическая логика и теория алгоритмов. Стенюшкина В.А. - 32 стр.

UptoLike

ВУЗ: 

ОГУ | Оренбург

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

Рубрика: 

10 Исчисление предикатов
Задача исчисления предикатов
(ИП) – описание всех тождественно- ис-
тинных предикатных формул.
10.1 Определение исчисления предикатов
Классическое исчисление предикатов первого порядка- это формальная
теория К, в которой:
-алфавит есть множество символов:
1)a,b, …, a
1
,b
1
, …, и x,y,…,x
1
,y
1
,… - (предметные) константы и предмет-
ные переменные соответственно;
2)Ρ
n
, Q
n
, …,Ρ
1
n
, Q
1
n
, … и f
n
, g
n
, …, f
1
n
, g
1
n
, …, n= 0, 1,2, …) – n – мест-
ные (предметные) предикатные переменные и (предметные) функциональные
переменные соответственно;
3) , → - связки;
4) ∀ , ∃ - кванторы;
5)(,) , , - служебные символы;
-множество формул есть множество цепочек символов, задаваемых син-
таксическими правилами:
1)(предметные) константы и (предметные) переменные, как цепочки, суть
термы;
2) если t
1
,…,t
n
– термы, f
n
- n –местная функциональная переменная, то це-
почка f
n
(t1,…,t
n
) – терм;
3)если t
1
,…,t
n
– термы, P
n
– n – местная предикатная переменная, то цепо-
чка P
n
(t1,…,t
n
) – атом;
4)атом есть формула;
5)если F, G - формула, x – ( предметная) переменная, то цепочки ( F), (∀x
F), ( ∃ x F), (F→ G) – тоже формулы;
-множество аксиом ( один из вариантов) задается схемами:
1)схемы вида А1, А2, А3 исчисления высказываний (но с предикатными
формулами);
2) P1: = ∀ x F(F(→ F( t); P2: = F( t) → ∃ x ∃(x), где t-терм, свободный для
переменной x в формуле F;
-множество правил вывода задается схемами:
1)
G
GFF →,
MP,
2)
)(
)(
xxFG
xFG
∀→
→
R
∀
,
3)
GxxF
GxF
→∃
→
)(
)(
R
∃
,
где формула F содержит свободные вхождения переменной x, а формула G их
не содержит. 
       10 Исчисление предикатов

     Задача исчисления предикатов (ИП) – описание всех тождественно- ис-
тинных предикатных формул.

       10.1 Определение исчисления предикатов

       Классическое исчисление предикатов первого порядка- это формальная
теория К, в которой:
       -алфавит есть множество символов:
       1)a,b, …, a1,b1, …, и x,y,…,x1,y1,… - (предметные) константы и предмет-
ные переменные соответственно;
       2)Ρn , Qn , …,Ρ1n, Q1n, … и fn, gn , …, f1n, g1n, …, n= 0, 1,2, …) – n – мест-
ные (предметные) предикатные переменные и (предметные) функциональные
переменные соответственно;
       3) , → - связки;
       4) ∀ , ∃ - кванторы;
       5)(,) , , - служебные символы;
       -множество формул есть множество цепочек символов, задаваемых син-
таксическими правилами:
       1)(предметные) константы и (предметные) переменные, как цепочки, суть
термы;
       2) если t1,…,tn – термы, fn- n –местная функциональная переменная, то це-
почка fn (t1,…,tn) – терм;
       3)если t1,…,tn – термы, Pn – n – местная предикатная переменная, то цепо-
чка Pn(t1,…,tn) – атом;
       4)атом есть формула;
       5)если F, G - формула, x – ( предметная) переменная, то цепочки ( F), (∀x
F), ( ∃ x F), (F→ G) – тоже формулы;
       -множество аксиом ( один из вариантов) задается схемами:
       1)схемы вида А1, А2, А3 исчисления высказываний (но с предикатными
формулами);
       2) P1: = ∀ x F(F(→ F( t); P2: = F( t) → ∃ x ∃(x), где t-терм, свободный для
переменной x в формуле F;
       -множество правил вывода задается схемами:
         F, F → G
      1)           MP,
             G
          G → F ( x)
      2)              R∀,
         G → ∀xF ( x)
                                        F ( x) → G
      3)                                                                         R∃,
                                       ∃xF ( x) → G
где формула F содержит свободные вхождения переменной x, а формула G их
не содержит.

Страницы