в реляционном исчислении играют ту
Кванторы в реляционном исчислении играют ту же роль, что декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре.
Аналогично тому, как не все возможные комбинации букв алфавита образуют правильные слова, так и в реляционном исчислении не каждая последовательность формул является допустимой. Допустимыми формулами могут быть только недвусмысленные и небессмысленные последовательности.
Правильно построенные формулы определяются рекурсивно следующим образом [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
в формулу ? эта формула становится истинной.