Формулы, свободные и связанные вхождением пременных-кортежей в эти формулы, определяются рекурсивно следующим образом.

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, при подстановке которого вместо всех свободных вхождений S в формулу Ψ эта формула становится истинной.

5.                 Формулы могут при необходимости заключаться в скобки. Используется следующий порядок старшинства: арифметические операторы сравнения; кванторы ", $;   ┐,٧,٨.

6.                 Ничто иное не является формулой. Для приведенных выше основных операций реляционной алгебры укажем следующие соответствующие выражения реляционного исчисления на переменных-кортежах:

·                           Операции объединения (R1UR2) соответствует выражение {t/R1(t)VR2(t)}.

·                           Операции разности (R1-R2) соответствует выражение {t/R1(t) ٨┐R2(t)}. Рассматривается все множество кортежей t, таких, что t принадлежит R1 и не принадлежит R2.

·                           Операции декартова произведения (R1xR2) соответствует выражение  {t^(k+m)|( $U)( $V)(R1(U) ٨R2(U) ٨t[1]=U[1] ٨…٨t[k]=U[k] ٨t[k+1]=V[1] ٨…٨t[k+m]=V[m])}. Рассматривается все множество кортежей t арности (k+m) таких, что существует кортеж u, принадлежащий R1, и существует кортеж v, принадлежащий R2, причем k первых компонентов кортежа t образуют компоненты кортежа u, а следующие m компонентов кортежа t образуют компоненты кортежа V.

·                           Операции проекции π_i1,i2,…,ik(R) соответствует выражение {t^(k)|( $u)(R1٨t[1]=u[i₁] ٨ … ٨t[k]=u[i_k])}.

·                           Операции селекции σ_F(R) соответствует выражение {t|R(t) ٨ F’}, где F’ – это выражение F, в котором каждый операнд, обозначающий компонент i, заменен на t[i]. Примером одного из первых реальных языков, реализующего реляционное исчисление с переменными-кортежами, является язык запросов QUEL.

Замечание. В реляционном исчислении с переменными на доменах не существует переменных-кортежей. Вместо них существуют переменные на доменах. В остальном реляционное исчисление с переменными на доменах строится так же, как и реляционное исчисление с переменными-кортежами с использованием тех же операторов.