Séquence 2/6 : Le calcul relationnel

Les notions d'occurrence de variables libres et liées dans une formule sont définies de la manière usuelle. Une occurrence d'une variable \(x\) est libre dans une formule \(\varphi\) si :

• \(\varphi\) est un atome ;

• ou \(\varphi = (\psi \wedge \xi)\) et l'occurence de \(x\) dqns \(\psi\) ou \(\xi\) est libre ;

• ou \(\varphi = \exists y \ \psi, x\) et \(y\) sont des variables distinctes, et l'occurrence de \(x\) est libre dans \(\psi\).

L'ensemble \(libre(\varphi)\) est l'ensemble des variables qui ont au moins une occurrence libre dans \(\varphi\). Une variable est liée si elle n'est pas libre.