1 Langage
-
V={x,y,z,...} un ensemble de variables ;
- S={a,b,f,g...}, la signature, un ensemble de
symboles fonctionnels, chacun muni d'une arité ÎN ; on
note Sn les symboles d'arité n ;
- P={p,q,...}, les symboles de prédicats, chacun muni
d'une arité ÎN ; Pn les symboles d'arité n ;
- Ù , Ú , ® , « , ¬ des
connecteurs ;
- " et $ des quantificateurs.
Définition 1 [terme]
L'ensemble des termes T est le plus petit ensemble contenant VÈS0
et clos par : si fÎ Sn, t1,...,tn des termes alors
f(t1,...,tn) est un terme.
En particulier, un symbole fonctionnel d'arité 0 est une constante.
Exemple : avec S={z0, s1}, on peut former les termes z, s(z),
s(s(z)) ...
Définition 2 [atome]
Pour tout pÎ Pn, quel que soient t1... tn des termes, p(t1,...,tn)
est un atome
En particulier, un symbole de prédicat d'arité 0 est une proposition.
Définition 3 [formule]
L'ensemble des formules F est le plus petit ensemble contenant l'ensemble
des atomes et vérifiant :
-
Si A et B sont des formules alors A Ù B est une formule ;
- Si A et B sont des formules alors A Ú B est une formule ;
- Si A et B sont des formules alors A ® B est une formule ;
- Si A et B sont des formules alors A « B est une formule ;
- Si A est une formule alors ¬ A est une formule ;
- Si A est une formule et x une variable alors " x A et $ x A sont
des formules.
Exemple : la continuité peut s'exprimer en calcul des prédicats
" x " e $ h " y
(p(x,y,h) ® q(x,y,e))
avec p(x,y,h)=def |x-y|<h et q(x,y,e)=def
|f(x)-f(y)|<e
Définition 4
Une variable libre est une variable non quantifiée, une variable
liée est une variable non libre (cf l-calcul).
Un terme (resp. une formule) clos est un terme (resp. une formule) sans variable
libre. On note V(t) les variables libres d'un terme t.
On parlera aussi de portée d'un quantificateur :
