в реляционном исчислении играют ту

Кванторы в реляционном исчислении играют ту же роль, что декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре.

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

Правильно построенные формулы определяются рекурсивно следующим образом [11, 17].

1. Каждый атом – это формула. Все вхождения переменных-кортежей, упомянутые в атоме, являются свободными.

2. Если ?1 и ?2 - формулы, то выражения ?1 ??2

(утверждает, что ?1 и ?2 истинны), ?1

??2

(утверждает, что ?1 или ?2, или обе истинны), ¬?1 (утверждает, что ?1 не истинна), также являются формулами.

Экземпляры переменных-кортежей – свободные или связанные в формулах (?1 ??

2), (?1 ??

2) и (¬?1) так же, как и в ?1 и ?2. Таким образом, свободными (связанными) являются те и только те вхождения переменных, которые происходят от свободных (связанных) вхождений переменных ?1 и ?2. Некоторое вхождение переменной может быть связанным в ?1 например, в то время как другое – свободным в ?2 и т.п.

3. Если ? – формула, то (

s)(?) – также формула. Свободные вхождения переменной s

в формуле ? становятся связанными квантором (

s) в формуле (

s)(?). Формула (

s)(?) утверждает, что при подстановке любого кортежа подходящей арности вместо свободных вхождений s формула становится истинной.

4. Если ? – формула, то (

s)(?) - также формула. Свободные вхождения переменной з в формуле ? также становятся связанными квантором (

s) в формуле (

s)(?). Формула (

s)(?) утверждает, что существует значение s, при подстановке которого вместо всех свободных вхождений s

в формулу ? эта формула становится истинной.

Содержание Назад Вперед