Université de Maroua Semestre 1 Session 2

FACULTE DES SCIENCES Niveau L1MA : Code : MAT111+INF141

Département de Mathématiques Enseignant : Pr. DONGHO Joseph
PREMIERE LECON
(Année Académique 2022-2023)
Durée : 08Heures00minutes

1 ELEMENTS DE LOGIQUE MATHEMATIQUES

1.1 Introduction
Dans un cours de mathematiques, on démontre les propriétés de différents types d’objets.
Pour cela, il faut bien sur que les objets sur lesquels on travaille soient clairement définis.

En logique du premier ordre et, en particulier, en théorie de la démonstration, les objets que
l’on étudie sont les formules et leurs démonstrations. Il faut donc donner une définition précise
de ce que sont ces notions. Les termes et les formules forment la grammaire d’une langue,
simplifiée àă l’extrème et construites exactement pour dire ce que l’on veut sans ambiguité et
sans détour inutile.

La mathématique est doc faite des énoncés déclaratifs qui ont été formé à l’aide des mots
"NON" ou en liant des énocés par des mots "ET, OU, IMPLIQUE, SI ET SEULEMENT SI".
Cest mots sont appelés des connecteurs logiques ou propositionnels. Le calcul propositionnel
est l’étude de ces connecteurs. Il a deux aspects ; Aspect syntaxique et Aspect semantique

En syntaxe, l’on construit des objets purement formels que l’on appelle formule proposi-
tionnelle. Ce sont des suites de symboles construits suivant des règles bien précises et à partir
d’un alphabet donné.

En sémantique, il faut donner un sens aux formules fabriquées, sachant pour chaque propo-
sition élémentaires intervenant dans une formule si elle est vraie ou fausse. Il faut etre capable
de décider si la formule elle même est vraie ou non. En sémantique on est conduit aux notions
de tautologie et d’équivalence logique.

1.2 Syntaxe du calcul propositionnel

1.2.1 Variables et connecteurs logiques
On se donne un esemble noté V ar fini ou non dont les éléments sont appelés variables
propositionnelles et notés par des lettre majuscules portant eventuellement des indices.
P, Q, R, ..., P1 , ..., Pn , Q1 , ..., Qn , ... On se donne 5 connecteurs ou symboles ∼, ∨, ∧, →, ↔, encore
appelés symboles de connection logique, que l’on lit comme suite :
(a) le connecteur unaire noté ¬ ou ∼ et se lit non
(b) les connecteurs binaires :
(i) ∧ qui se lit et c’est le symbole de conjonction
(ii) ∨ qui se lit ouc’est le symbole de disjonction
(iii) → se lit implique ou flèche
(iv) ←→ symbole d’équivalence
(c) Auxquels on ajoute aussi les parentheses ) ouvrante et ( fermante

1
on obtient ainsi l’alphabet A = V ar ∪ {∼, ∨, ∧, →, ↔, (, )}.
Definition 1 Un mot sur A est une suite finie d’éléments de A.

Exemple 1 P GR, P ∨ R, P ∧ Q, P ∨ Q → R

Definition 2 La longueur d’un mot w est le nombre entier naturel noté lg(w) représentant le
nombre d’éléments de A que compte w?

L’ensemble des mots sur A se note W (A) ou mot(A)

Definition 3 Un mot sur A est dit vide s’il ne contient aucun élément de A.
La longueur d’un mot vide est zéro.
Par abus de language, le mot (A) sera noté simplement A qui est un mot de longueur 3.

1.2.2 Formules propositionnelles

Definition 4 Formule propositionnelle
a1 Toute variable est une formule
a2 Si ϕ est une formule, alors ¬ϕ est une formule.
a3 Si ϕ et ψ sont des formules, alors (ϕδψ) est une formule ; avec δ ∈ {∨, ∧, →, ←→}
a4 Rien d’autre.

Autrement dit, si F désigne l’ensemble des formules, sur A, alors F est le plus petit sous
ensemble de mota(A) qui est fermé pour les opérations suivantes.
. F 7→ ¬F
. (F, G) 7→ (F ∨ G)
. (F, G) 7→ (F ∧ G)
. (F, G) 7→ (F → G)
. (F, G) 7→ (F ←→ G)
Autrement dit, l’ensemble des formules propositionnelle construit sur V ar est le plus petit sous
ensemble F de mot(A) ayant les clauses suivantes
C1 V ar ⊂ F
C2 Si ϕ ∈ F alors ¬ϕ ∈ F.
C3 Si ϕ, ψ ∈ F, alors ϕδψ ∈ F, δ ∈ {∧, ∨, →, ←→}

Exemple 2 Soient A, B, C ∈ V ar. Les mots suivants sont des formules sur V ar :
1. A
2. (A → (B → A))
3. (∼ A → A)
4. ∼ (A → A)
5. (((A ∧ (∼ B →∼ A)) ∧ (∼ B∨ ∼ C)) → (C →∼ A)
Les mots suivants ne sont pas des formules
1. A ∧ A
2. ∼ (A)
3. (A → B ∨ C)

2
 4. A → B, C
5. A ∧ B ∧ C
6. ∀A(A∨ ∼ A
7. ((A ∧ (B → C)) ∨ (∼ A → (B ∧ C)) ∧ (∼ A ∨ B))

Très souvent, on utilise aussi la définition suivante de F. Soit (Fn )n∈N une suite de sous en-
sembles de mot(A). On pose
F0 = V ar,
F1 = F0 ∪ {¬ϕ, ϕ ∈ F0 } ∪ {ϕδψ, ϕ, ψ ∈ F0 } où δ ∈ {∧, ∨, →, ←→}.
pour tout entier naturel n, on a : Fn+1 = Fn ∪ {¬ϕ, ϕ ∈ Fn } ∪ {ϕδψ, ϕ, ψ ∈ Fn } où
δ ∈ {∧, ∨, →, ←→}.
Nous pouvons à présent énoncer le théorème suivant :

Théorème 1 Soit F l’ensemble de toutes les formules propositionnelles sur A. Alors

F = ∪ Fn
n∈N

Preuve: Nous allons procéder par double inclusion.

Montrons que F ⊂ ∪ Fn
n∈N
Par définition, on a F0 = V ar ⊂ ∪ Fn . Par ailleurs, si ϕ, ψ ∈ Fn pour un certain n ∈ N, alors
n∈N
¬ϕ, (ϕδψ) sont dans Fn+1 ⊂ ∪ Fn . Ainsi ∪ Fn satisfait les clauses ci-dessus. Il contient donc
n∈N n∈N
le plus petit sous ensemble de mot(A) ayant ces clauses ; ce qui signifie que F ⊂ ∪ Fn .
n∈N
Réciproquement, pour montrer que ∪ Fn ⊂ F, il suffit de montrer que pour tout n ∈ N, Fn ⊂
n∈N
F. Nous allons le faire par récurrence sur n. Par définition, F0 = V ar ⊂ F. Supposons que
Fn ⊂ F et montrons que Fn+1 ⊂ F. Comme Fn ⊂ F, alors d’après les clauses C2 et C3
ci-dessus, Fn+1 ⊂ F

Definition 5 La hauteur d’une formule F est le plus petit entier naturel n tel que F ∈ Fn on
la note h[F ]

Exemple 3

1. Si A et B sont des variables propositionnelles, on a h[A] = 0.

2. h[((A ∨ B) ∧ (B ⇒ A))] = 2, h[¬¬¬¬¬A] = 5

Proposition 1 Pour tous F, G ∈ F on a :

1. h[∼ F ] ≤ h[F ] + 1
2. h[F 4G] ≤ sup(h[F ], h[G]) + 1

Preuve: Faire cette preuve en exercice

1.2.3 Démonstration par induction sur l’ensemble des formules

On se propose de démontrer qu’une certaine propriété χ(F ) est satisfaite pour toute formule
propositionnelle F. On peut le faire par induction sur la hauteur de la formule F. Pour cela,
(i) Vérifier que la propriété χ(F ) est satisfaite par toute formule F ∈ F0
(ii) Supposer que la propriété est vérifié pour F ∈ Fn , n ∈ N et
(iii) Montrer que χ(F ) est satisfait pour tout F ∈ Fn+1

3
Remarques 1 L’étape initiale de cette preuve consiste à montrer que χ(F ) est satisfaite pour
tout F ∈ V ar.
L’étape d’induction consiste à prouver d’une part que si F satisfait χ alors ¬F satisfait χ.
D’autre part, si F et G satisfont χ alors F δG satisfait χ, δ ∈ {∨, ∧, ⇒, ⇔}
Il faut remarquer que la notion hauteur d’une formule n’apparait pas explicitement dans ce
principe.

Théorème 2 La hauteur d’une formule est inférieure àăsa longueur

Preuve: Posons χ(F ) : h[F ] < lg[F ]. Si F ∈ V ar, alors h[F ] = 0 et lg[F ] = 1 l’inégalité
est satisfaites. Supposons que h[F ] < lg[F ] alors h[¬F ] < h[F ] + 1 < lg[F ] + 1 = lg[¬F ].
Ce qui montre que χ(¬F ) est vraie. Soient F et G deux formules telles que h[F ] < lg[F ] et
h[G] < lg[G]. Alors pour tout δ ∈ {∧, ∨, ⇒, 7−→} on a

h[(F δG)] ≤ Sup(h[F ], h[G]) + 1

< Sup(lg[F ], lg[G]) + 1
< lg[F ] + lg[G] + 3 = lg[(F δG)]

ce qui montre que χ((F δG)) est satisfait et ceci achève la preuve.
Conséquence 1 il n’existe pas de formule de longueur 0. Ce qui montre que le mot vide n’est
pas une formule. De plus ce théorème montre que seules les variables sont les formules de
longueur 1.
Soit χ(W ) une propriété sur un mot W ; qui n’est nécessairement pas une formule.
Lemme 1 Si d’une part χ(W ) est vraie pour tout W ∈ V ar. D’autre part, on suppose que pour
tout mots W, et V si χ(W ) et χ(V ) sont vraies alors χ(¬W ), χ(W ∧ V ), χ(W ∨ V ), χ(W ⇒ V ),
et χ(W ⇔ V ). sont aussi vraies Alors χ(F ) est aussi vraie pour toute formule propositionnelle
F.
Preuve: Posons Z = {W ∈ mot(A), χ(W )} D’après hypothèse, V ar ⊂ Z. De plus, Z est stable
pour les opérations suivantes W 7→ χ(¬W ), (W, V ) 7→ χ(W ∧V ), (W, V ) 7→ χ(W ∨V ), (W, V ) 7→
χ(W ⇒ V ), et (W, V ) 7→ χ(W ⇔ V ). C’est donc un sous ensemble de mot(A) contenant V ar
et fermé pour ces opérations. D’après la minimalité de F on a F ⊂ Z.
Lemme 2 On suppose que la prpriété χ(F ) est satisfaite pour tout F ∈ V ar et que pour toutes
formules propositionnelles F et G, si χ(F ) et χ(G) sont satisfaites alors χ(¬F ), χ(F ∧G), χ(F ∨
G), χ(F ⇒ G), et χ(F ⇔ G) sont aussi satisfaites, alors χ(F ) est satisfaite pour toute formule
F.
Preuve: Considérons une propriété Y (W ) : W ∈ F et χ(W ) laquelle est définie sur mot(A).
Puisque V ar ⊂ F et F est fermé pour les opérations W 7→ χ(¬W ), (W, V ) 7→ χ(W ∧
V ), (W, V ) 7→ χ(W ∨ V ), (W, V ) 7→ χ(W ⇒ V ), et (W, V ) 7→ χ(W ⇔ V ), alors si χsatisfait les
hypothèses, alors Y satisfait celle du lemme ci-dessus. On conclut donc que Y est satisfaite par
toute formule F et par suite χ(F ).

1.3 Arbre de décomposition d’une formule

Une formule peut etre vue comme un arbre dont les noeuds sont étiquetés par des connec-
teurs. L’existence d’un arbre de décomposition d’un mot permet de decider si ce dernier est
une formule ! Pour illustrer ce fait, considérons

ϕ : (((A ∧ (∼ B →∼ A)) ∧ (∼ B∨ ∼ C)) → (C →∼ A)).

4
Posons W0 = (((A ∧ (∼ B →∼ A)) ∧ (∼ B∨ ∼ C)), W1 = (C →∼ A). Alors ϕ s’écrit W0 → W1
W W / W00100
; 000 : 0010

W / W001 / W0011 / W00110

< 00

W0

"
W01 / W010 / W0100

#
W011 / W0110
Où on a W000 = A, W00100 = B, W00110 = A, W0100 = B, W0110 = C, W00 = A ∧ (∼ B →∼
A), W001 =∼ B →∼ A, W010 =∼ B, W01 =∼ B∨ ∼ C, W011 =∼ C
Le faite que cet arbre se termine par des variables montre qu’il a été construit à base d’un
nombre fini de variables et d’opérations. Ceci montre aussi que ϕ est une formule
Etant donnée une formule propositionnelle M,

1.3.1 Construction de l’arbre de décomposition

a) la racine de sonarbre est en haut, et les branches poussent vers le bas.
b) Chaque sommet (ou nIJud) de l’arbre est constitué par un mot N (qui est toujours une
formule si le mot à la racine en est une) ;
c) trois cas peuvent se présenter : ou bien N est une variable propositionnelle et constitue
alors une extrémité de l’arbre (les mots correspondant à ce cas ont été signalés par un
point noir dans notre schéma), ou bien N s’écrit ∼ N 0 et il part alors de N une unique
branche qui aboutit au niveau immédiatement inférieur au sommet N 0 , ou bien enfin N
s’écrit (N 0 δN ”) (δ étant un symbole de connecteur binaire) et il part alors de N deux
branches qui aboutissent au niveau inférieur à deux noeuds N 0 et N ” (on a fait alors
figurer entre les deux branches le symbole de connecteur binaire approprié).

1.3.2 Exemple de construction d’un arbre !

On considère le mot suivant M : (((A ∧ (∼ B →∼ A)) ∧ (∼ B∨ ∼ C)) → (C →∼ A)).
Posons M0 : ((A ∧ (∼ B →∼ A)) ∧ (∼ B∨ ∼ C)) et M1 : (C →∼ A) alors M : (M0 → M1 ).
Ensuite, en posant
M 00 : (A ∧ (∼ B →∼ A))
M 01 : (∼ B∨ ∼ C)
M 10 : C
M 11 :∼ C L’on obtient M 0 : (M 00 ∧ M 01) et M 1 : (M 10 → M 11)

5
1.3.3 Théoreme de l’ecriture unique
Soit W ∈ W (A). On note o[W ] le nombre de parenthèse ouvertes de W et c[W ] le nombre
de parenthèses fermantes de W.
Lemme 3 Dans toute formule, le nombre de parenthèse ouvertes est égale au nombre de pa-
renthèse fermantes : o[W ] = c[W ].
Preuve: Soient F ∈ F montrons par induction que o[F ] = c[F ]
Pour tout F ∈ V ar on a o[F ] = c[F ] = 0
Pour tout F ∈ F tel que o[F ] = c[F ], puisque o[¬F ] = o[F ] et c[¬F ] = c[F ], alors o[¬F ] = c[¬F ]
Pour toutes formules F, G telles que o[F ] = c[F ] on a
o[(F M G)] = o[F ] + o[O] + 1
= c[F ] + c[O] + 1
= c[(F M G)]
Donc o[F ] = c[F ] pour tout F ∈ F.
Definition 6 Soient W, W1 deux mots. On dit que W1 est un segment initial de W si il existe
un mot W2 tel que W = W1 W2 .

Lemme 4 Pour toute formule F et tout mot W, si W est un segment initial de F alors o[W ] ≥
c[W ]

Preuve: Par induction sur la formule F.

Si F ∈ V ar, alors pour tout segment initial W de F, on a o(W ) = c(W ) = 0.

Soit F une formule telle que pour tout segment initial W de F, on a o(W ) ≥ c(W ). Soit
V un segment initial de ∼ F. Si V est le mot vide, alors o(V ) = c(V ) = 0. Si non il existe
un segment initial W de F tel que V =∼ W. On a donc o(V ) = o(W ) et c(V ) = c(W ).
Puisque o(W ) ≥ c(W ), par hypothèse, on conclut que o(V ) ≥ c(V ).

6
 Soient F et G deux formules chacune ayant plus de parentheses ouvrante que de fermantes
dans les segments initiaux. Soit 4 un symbole de connecteur logique binaire. Si H =
(F 4G). Soit V un segment initial de H. on distingue 4 cas de figures
1er cas V est le mot vide. Dans ce cas o(V ) = c(V ) = 0
2em cas V = (W où W est un segment initiale de F. Alors o(V ) = o(W ) + 1 et c(V ) =
c(W ), puisque o(W ) ≥ c(W ), par hypothèse, nous pouvons conclure que o(V ) ≥ c(V ).
3em cas V = (F 4K où K est un segment initial de G, alors o(V ) = o(V ) + o(K) + 1 et
c(V ) = c(F )+c(K). Ce pendant, o(F ) = c(F ); d’après le lemme et on sait par hypothèse
d’induction que o(K) ≥ c(K). Ce qui nous permet de conclure que o(V ) ≥ c(V ).
4em cas V = H, auquel cas o(V ) ≥ c(V ) d’après le Lemme ci-dessus

Definition 7 Un segment initial d’une formule F est dit propre s’il est non vide et different
de F.

Proposition 2 Pour toute formule F ∈ F dont le premier symbole est une parenthèse ouvrante
et pour tout mot W ∈ W (A) qui est un segment initial propre de F, alors o(W ) > c(W ).

Preuve: Nous ferons cette démonstration par induction sur F. Soit F = (G4H) où H et G
sont des formules quelconque et 4 est un connecteur binaire. Soit W un segment initial de F.
Il y a deux cas possibles.
1er cas W = (K où K est un segment initial quelconque de G a lors o(W ) = o(K) + 1 et c(W ) =
c(K) et puis que o(K) ≥ c(K), d’apres le théorème 4, on conclut que o(W ) > c(W )
2e cas W = (G4L où L est un segment initial de H. dans ce cas, o(W ) = o(G) + o(L) + 1 et
c(W ) = c(G) + c(L). mais o(G) = c(G) et o(L) ≥ c(L). Ce qui implique o(W ) > c(W ).

Lemme 5 Pour toute formule F ∈ F et tout mot W ∈ W (A), si W est un segment initial
propre de F, alors W n’est pas une formule.

Preuve: Par induction sur la formule F .

a) Si F est une variable propositionnelle, alors elle n’a pas de segment initial propre.
b) Si F est une formule dont aucun segment initial propre n’est une formule, et si N est
un segment initial propre de ∼ F , alors ou bien N =∼ F et n’est pas une formule, ou
bien N =∼ M , M étant un segment initial propre de F ; dans ce cas, M n’est pas une
formule (hypothèse d’induction) et N =∼ M non plus. On observera que, contrairement
à ce que l’on serait tenté de croire, le fait que, si M n’est pas une formule, ∼ M n’en
est pas une non plus, n’est pas une simple application de la définition des formules, mais
exige une démonstration, que voici : si ∼ M est une formule, l’examen de son premier
symbole montre que ce ne peut être ni une variable propositionnelle, ni une formule du
type (HαK) ; il existe donc au moins une formule G telle que ∼ M =∼ G ; l’identité des
mots ∼ M et ∼ G exige celle des mots M et G, ce qui prouve que M est une formule.Ce
qui est absurde.
b) Soient F et G deux formules quelconques, α un symbole de connecteur binaire, et N un
segment initial propre de (F αG). On a o[N ] > f [N ]. On en déduit que N n’est pas une
formule. On peut remarquer qu’il n’a pas été nécessaire, dans cette partie du raisonnement
par induction, de supposer que les segments initiaux propres de F et de G ne sont pas
des formules.

7
Théorème 3 (Théorème d’unicité de décomposition)
Pour toute formule F ∈ F un seul des cas suivant est vérifié
C1. F ∈ V ar
C2. Il existe un unique G ∈ F tel que F =∼ G
C3. Il existe un unique G, H ∈ F tel que F = (F 4G) pour tout symbole de connection binaire
4

Preuve: C’est clair que ces propriétés sont exclusives l’une de l’autre. Que ce soit dans C1, C2
ou C3, le premier symbole de F est soit un élément de V ar soit ∼ soit (.
Il en découlle de la définition de F que soit F ∈ V ar ; soit F =∼ G, G ∈ F soit F = (G4H)
avec H, G ∈ F et 4 un symbole de connection binaire. Il reste à montrer l’unicité de la
décomposition aux cas 2 et 3.
Cas2
Supposons F =∼ G1 =∼ G2 alors G1 = G2 .
Cas3
Supposons qu’ils existent des formules G, H, K et L telles que F = (G4H) = (K 5 L). Alors
cela montrerait que les mot G4H et K 5 L sont égaux ? Ce qui impliquerait que l’une des
deux formules G ou K est segment initail de l’autre. Ce qui montre d’après le lemme qu’il ne
peut etre un segment initial propre. Mais comme le mot vide n’est pas une formule, on conclut
que G = K. Il s’en suit que 4H = 5L Ce qui montre que 4 = 5 et H = L

Corollaire 1 Pour toutes formules F et G, on a h[∼ F ] = h[F ]+1 et h[(F 4G)] = sup(h[H], h[G])+
1 Pour tout symbole de connection binaire 4.

Preuve: Posons H = (F 4G, ) puisque ce n’est pas un élément de V ar, il existe un unique entier
naturel n tel que f [H] = n+1 ce qui implique que H ∈ Fn+1 et H 6= Fn . d’apres la définition de
Fn+1 et compte tenu du fait que H commence par une parenthèse, on conclut qu’il existe deux
formules H1 et H2 dans Fn et un symbole de connection binaire α tel que (H1 αH2 ) = H. On en
déduit donc que (H1 αH2 ) = (F 4G). Ce qui implique d’après le théorème d’ecriture unique que
H1 = F, α = 4 et H2 = G. Consequence F et G sont dans Fn . S’il existe m < n tel que F et G
appartiennet à Fm alors (F 4G) ∈ Fm+1 et donc (F 4G) ∈ Fn . Ce qui est absurde ! Il s’ensuit
que l’une au moins des formules est de hauteur n. et donc h[(F 4G)] = sup(h[F ], h[G]) + 1

1.4 Definition par induction sur l’ensemble des formules

De même que pour la démonstration par induction sur l’ensemble des formules, on sait faire
en logique propositionnelle des définitions par induction sur l’ensemble des formules.

Definition 8 (Principe)
Etant donne un ensemble E, pour définir par induction φ : F → E il suffit :
D1 Définir φ(P ) pour tout P ∈ V ar.
D2 Determiner la règle permettant de définir pour tout F, G ∈ F, φ(∼ F ); φ((F 4G)) pour
tout connecteur binaire 4 ; à partir de φ(F ) et de φ(G).

Lemme 6 Soit φ0 une application de V ar dans E. f : E → E, g, h, i, j : E × E → E. Alors il

existe une unique application φ; F → E satisfaisant :
(i) φ|V ar = φ0
(ii) pour tout F ∈ F, φ(∼ F ) = f (φ(F ))

8
 (ii) Pour tous F, G ∈ F, φ((F ∧ G)) = g((φ(F ),
φ(G)), φ((F ∨ G)) = h((φ(F ),
φ(G)), φ((F → G)) = i((φ(F ),
φ(G)), φ((F ↔ G)) = j((φ(F ), φ(G)).

Preuve: Exercice
Definition 9 (Sous formule)
A chaque formule F ∈ F, on associe un sous-ensemble sf (F ) de F, appelé ensemble des sous-
formules de F, défini par induction par les conditions suivantes :
ax1. Si F ∈ V ar alors sf (F ) = {F }
ax2. Si F =∼ G, sf (F ) = Sf (G) ∪ {F }
ax3. Si F = (GαH), alors sf (F ) = sf (G) ∪ sf (H) ∪ {F }
En pratique, les sous formeules de F sont les noeuds de son arbre de décomposition.

1.4.1 Substitution dans une formule propositionnelle

Soit F une formule de F, et soient A1 , A2 , ..., An des variables propositionnelles de var,
deux à deux distinctes (cette hypothèse est essentielle). Nous utiliserons pour désigner F la
notation F [Al , A2 , ..., An ] lorsque nous voudrons préciser que les éléments de var qui ont au
moins une occurrence dans l’écriture de F se trouvent dans {Al , A2 , ..., An }. Par exemple, la
formule F = (A → (B ∨A)) pourra être notée F [A, B], mais aussi, si c’est utile dans le contexte,
F [A, B, C, D].
Etant données une formule F [A1 , A2 , ..., An , B1 , B2 , ..., Bm ] et n formules G1 G2 , ., Gn , consi-
dérons le mot obtenu en substituant la formule Gi (respectivement : G2 , ..., Gn ) à la va-
riable A1 (respectivement : A2 , ..., An ) dans toutes les occurrences de celle-ci dans F. Ce
mot sera noté FG1 /A1 ,G2 /A2 ,...,Gn /An ; mais nous utiliserons aussi pour le désigner la notation
F [G1 , G2 , ..., Gn , B1 , B2 , ..., Bn ].
Exemple 4 Soit F = F [A, B] est la formule (A → (B ∨ A)). Si G = (B → A), alors FG/A
est le mot ((B → A) → (B ∨ (B → A))), que l’on pourra donc noter aussi F [G, B] ou encore
F [(B → A), B].
Si on considère maintenant une variable propositionnelle C (distincte de A et B) et la formule
H = C, alors FH/A est le mot (C → (B ∨ C)), que l’on pourrait noter, F [C, B].
On donne une définition de FG1 /A1 ,G2 /A2 ,...,Gn /An par induction sur F.
Definition 10 Soient G1 , ..., Gn ∈ F et A1 , ..., An ∈ var tous fixés. On a :

Gk si F = Ak ; 1 ≤ k ≤ n
ax1 Si F ∈ V ar alors FG1 /A1 ,G2 /A2 ,...,Gn /An =
F si F ∈ / {A1 , ..., An }
ax2 Si F =∼ G, alors FG1 /A1 ,G2 /A2 ,...,Gn /An =∼ GG1 /A1 ,G2 /A2 ,...,Gn /An
ax3 Si F = (GαH), alors FG1 /A1 ,G2 /A2 ,...,Gn /An = (GG1 /A1 ,G2 /A2 ,...,Gn /An αHG1 /A1 ,G2 /A2 ,...,Gn /An )
quels que soient les formules G et H et le symbole de connecteur binaire α.
FG1 /A1 ,G2 /A2 ,...,Gn /An est appelée formule obtenue par substitution des variabmes A1 , ..., An res-
pectivement par les formules G1 , ..., An .

Théorème 4 Etant donnés un entier naturel n, des formules F, G1 G2 , ..., Gn , et des variables
propositionnelles A1 , A2 , ..., An , le mot FG1 /A1 ,G2 /A2 ,...,Gn /An est une formule.

Preuve: Soient G1 , G2 , ..., Gn ∈ F et A1 , A2 , ..., An ∈ var fixés. Démontrons la théorème par

induction sur la formule F .

9
 i) Si F ∈ var,alors d’après la définition ci-dessus, on a FG1 /A1 ,G2 /A2 ,...,Gn /An = Gk si F =
Ak ; 1 ≤ k ≤ n et F si F ∈
/ {A1 , ..., An }. de toute évidence c’est une formule dans les deux
cas.
ii) Si F =∼ G, et si on suppose que GG1 /A1 ,G2 /A2 ,...,Gn /An est une formule, alors FG1 /A1 ,G2 /A2 ,...,Gn /An ,
qui est le mot ∼ GG1 /A1 ,G2 /A2 ,...,Gn /An , est encore une formule.
iii) Si F = (GαH) (α étant un symbole de connecteur binaire), et si on suppose que les mots
GG1 /A1 ,G2 /A2 ,...,Gn /An et HG1 /A1 ,G2 /A2 ,...,Gn /An sont des formules, alors FG1 /A1 ,G2 /A2 ,...,Gn /An
qui est le mot (GG1 /A1 ,G2 /A2 ,...,Gn /An αHG1 /A1 ,G2 /A2 ,...,Gn /An ) est aussi une formule.

Il convient d’insister sur le fait que la formule FG1 /A1 ,G2 /A2 ,...,Gn /An est le résultat de la sub-
stitution simultanée des formules G1 , G2 , ..., Gn , aux variables A1 , A2 , ..., An dans la formule F .
On obtiendrait une formule a priori différente si on effectuait ces substitutions successivement ;
de plus, le résultat obtenu dépendrait de l’ordre dans lequel ces substitutions seraient effectuées.
Examinons un exemple : posons F = (A1 ∧ A2 ), G= (A1 ∨ A2 ) et G2 = (A1 → A2 ). On a alors :
FGl /A1 ,G2 /A2 = ((A1 ∨ A2 ) ∧ (A1 → A2 )) ; tandis que [FG1 /A1 ]G2 /A2 = ((A1 ∨ (A1 → A2)) ∧ (A1 →
A2 )) ; et [FG2 /A2 ]G1 /A1 = ((A1 ∨ A2 ) ∧ ((A1 ∨ A2 ) → A2 )).

On peut aussi, dans une formule F donnée, procéder à la substitution d’une formule G à
une sous-formule H de F . Le mot obtenu à l’issue de cette opération est encore une formule.

Exemple 5 Supposons que : F = (((A ∧ B) → (∼ B ∧ (A → C))) ∨ (B ↔ (B → (A ∨ C)))),

G = (A ↔ (B ∨ C)) et H = (∼ B ∧ (A → C)). Alors, en substituant dans la formule F la
formule G à la sous-formule H, on obtient la formule : (((A ∧ B) → (A ↔ (B ∨ C))) ∨ (B ↔
(B → (A ∨ C)))).

10