Математическая логика и теория алгоритмов. Анкудинов Г.И - 24 стр.

UptoLike

ВУЗ: 

СЗТУ | Санкт-Петербург

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

Рубрика: 

Пример 2.10. ∃x
1
A(x
1
,x
2
,...,x
n
) - (n-1)-местный предикат, у которого
x
1
- связанная переменная, а x
2
,x
3
, ..., x
n
- свободные переменные. Если все
переменные n-местного предиката связаны, получаем 0-местный предикат, или
высказывание, например:
(∃x
1
,x
2
,...,x
n
) A(x
1
,x
2
,...,x
n
);
(∃x
1
,x
2
) (∀x
3
) B(x
1
,x
2
,x
3
).
2.5. Исчисление предикатов
Введем символы двух видов:
предметные переменные (x,y,z,x
1
,x
2
...) и
предикатные буквы (P,Q,R,P
1
,P
2
,...).
Из предикатных букв, предметных переменных, логических сим-
волов и скобок можно сформировать различные выражения,
некоторые из которых называются формулами.
Формулами исчисления предикатов являются
а) каждая предикатная буква и предикатная буква со
следующими за ней в скобках предметными переменными;
б) выражения ⎤(Ф), (Ф
1
)&(Ф
2
), (Ф
1
)\/(Ф
2
),(Ф
1
)→(Ф
2
),
(Ф
1
)↔(Ф
2
), ∀x (Ф) и ∃x Ф(x), где Ф,Ф
1
,Ф
2
– некоторые формулы; x –
некоторая индивидная переменная, причем ⎤(Ф) называется
отрицанием формулы Ф, а (Ф
1
)&(Ф
2
), (Ф
1
)\/(Ф
2
), (Ф
1
)→(Ф
2
),
(Ф
1
)↔(Ф
2
) называются конъюнкцией, дизъюнкцией, импликацией и
эквивалентностью формул Ф
1
и Ф
2
соответственно; ∀x(Ф) и ∃x(Ф)
называются квантификацией формулы Ф по переменной x квантором
общности и существования соответственно.
Предметная переменная называется свободной, если она не
следует непосредственно за квантором и не входит в область
действия квантора по этой переменной, все другие переменные,
входящие в формулу, называются связанными.
Примечание. В общем случае формула исчисления предикатов может
иметь вид предикатной буквы, за которой в скобках следуют предикатные
переменные или функциональные буквы.
108

Страницы