Theorie des ensembles et Logique(MAT356)

Cours du 19 Mars 2020: 16H-18H

Joseph DONGHO
March 23, 2020

1.7: Méthodes de Démonstrations

Bien que la preuve formelle soit standard dans les mécanismes de démonstration,
il arrive très souvent des situations dans lesquelles sont utilisation est assez
laborieuse. L’on fait donc recours à d’autre techniques de preuve que nous
presenterons dans cette leçon.

Théorème de déduction
Définition 0.1 Soient P et Q deux formes propositionnelles. Lorsqu’il existe
une preuve formelle de Q à partir de P utilisant uniquement:les axiomes de
Frege-Lukasiewicz, le Modus Ponens et la substitution. Dans ce cas, on note :
P `∗ Q.

Lorqu’il existe une preuve formelle de Q utilisant uniquement les axiomes de

Frege-Lukasiewicz, le Modus Ponens et la substitution, on note `∗ Q.

Exemple 0.1 P, Q, ¬P ∨ (Q → R) `∗ R

1. P Donnée
2. Q Donnée
3. ¬P ∨ (Q → R) Donnée
4. P → (Q → R) 3 et Impl
5. Q→R 1,4 et MP
6. R 2, 5 et MP

Nous allons à présent démontrer que toute forme propositionnelle démontrable

à l’aide des règles d’inférences et des formules de substitution se démontre à
l’aide du Modus Sponens et des règle de substitution uniquement.

Proposition 0.1 Pour toutes formes propositionelles P et Q, P `∗ Q ssi P ` Q

Preuve: Il est clair que si P et Q, P `∗ Q alors P ` Q Réciproquement,
on suppose que P ` Q alors nous devons montrer que sous l’hypothèse des
axiomes FL et des règles de remplacements et du Modus Sponens, les autres
règles d’inférences sont satisfaites.

1
 [MT ] P → Q, ¬Q ⇒ ¬P

1. P →Q Donnéé
2. ¬Q Donnée
3. ¬¬P → ¬¬Q DN
4. ¬¬P → ¬¬Q → (¬Q → ¬P ) FL3
5. ¬Q → ¬P 3, 4 et MP
6. ¬P 2, 5 et MP
On déduit donc que P → Q, ¬Q `∗ ¬P

[Add ]P `∗ P ∨ Q On a la preuve formelle suivante

1. P Donnée
2. P → (¬Q → P ) FL1
3. ¬Q → P 1, 2 et MP
4. ¬¬Q ∨ P 3 et Impl
5. Q∨P 4DN
6. P ∨Q 5com

[DL ] Faites le en exercice

[DD ] Faites le en exercice
[SD ] Faites le en exercice

[Simp ] Faites le en exercice

[Conj ]Faites le en exercice
[SH ] P → Q, Q → R `∗ R

1. P →Q Donnée
2. Q→R Donnée
3. ¬Q ∨ R 2Impl
4. ¬Q ∨ R ∨ ¬P 3Add
5. ¬P ∨ (¬Q ∨ R) 4Com
6. P → (Q → R) 5Imp
7. P → (Q → R) → (P → Q → (P → R)) FL2
8. P → Q → (P → R) 6, 7MP
9. P →R 1,8 MP

ce qui montre que l’on n’a pas besoin du syllogisme hypothetique

S le Modus Sponens à lui seul suffit pour faire toutes les preuves; à quoi
servent les autres règles d’inférences? La réponse à cette question est que les
autres règles d’inférence sont naturelles et facilitent la rédaction des preuves
formelles. Sans elles les preuve au MP se compliquent substentiellement.

Lemme 0.1 Soient `∗ Q alors `∗ P → Q

Preuve: Si `∗ Q alors d’apres FL1, on a `∗ Q → (P → Q) et d’apres MP, on
a `∗ P → Q

2
Théorème 0.1 (TD) (Théorème de déduction)
Pour toutes formes propositionnelles P, Q, P ` Q ssi ` P → Q

Preuve: A faire
Corollaire 0.1 Pour toutes formes propositionnelles P0 , P1 , ..., Pn−1 , Q, R, on
a P0 , P1 , ..., Pn−1 , Q ` R si et seulement si P0 , P1 , ..., Pn−1 , ` Q → R
Preuve: A faire

Théorème 0.2 (PD) Pour toutes formes propositionnelles P0 , P1 , ..., Pn−1 , Q, R,

si P0 , P1 , ..., Pn−1 , Q ` R alors P0 , P1 , ..., Pn−1 ⇒ Q → R
Preuve: A faire
Comment comprendre la Preuve Directe [PD]? Etudions l’exemple
suivant:P ∨ Q → (R ∧ S) ` R → P. Pour démontrer que P ∨ Q → (R ∧ S) `
R → P, le théorème de Preuve Directe ([PD]) nous dit qu’il suffit de prouver
P ∨ Q → (R ∧ S), P ` R. Démontrons donc P ∨ Q → (R ∧ S), P ` R.

1. P ∨ Q → (R ∧ S) Donnée
2. P Donnée
3. P ∨Q 2Add
3. R∧S 1, 3MP
4 R 4Simp

Par suite, le Théorème de Preuve Directe entraine que P ∨ Q → (R ∧ S) ⇒ R →

P. On peut donc effectuer la preuve de la proposition P ∨Q → (R∧S) ` R → P.

1 P ∨ Q → (R ∧ S) Donnée
2. R→P 1PD

On peut faire une preuve directe.

1. P ∨ Q → (R ∧ S) Donnée
2. P Hypothèse
3. P ∨Q 2Add
4. R∧S 1.3MP
5. R 4Simp
6. R→P 2-5 PD

Dans cette preuve, P infere R est une sous preuve de de la preuve principale .
Exercice 0.1 Montrer que:

1. P → ¬Q, ¬R ∨ S ` R ∨ Q → (P → S)
2. P ∧ Q → R → S, ¬Q ∨ R ` S
3. ` P ∨ ¬P

Théorème 0.3 (PI) (Preuve Indirecte) Pour toute forme propositionnelles P

et Q, on a :¬P → (P ∧ ¬P ) ⇒ Q

3
Preuve: Pour faire cette preuve, on rappelle le théorème suivant: ` P → P

1. ¬Q → (P ∧ ¬P ) Donnée
2. P →P Théoreme
3. ¬(P ∧ ¬P ) → ¬¬Q 1Contra
4. ¬(P ∧ ¬P ) → Q 3DN
5. ¬P ∨ ¬¬P → Q 4DeM
6. ¬P ∨ P → Q 5DN
7. P →P →Q 6Impl
8. Q 2,7MP

Exemple 0.2 P ∨ Q → R, R ∨ S → ¬P ∧ T ` ¬P

1. P ∨Q→R Donnée
2. R ∨ S → ¬P ∧ T Donnée
3. ¬¬P Hypothese
4. P 4DN
5. P ∨Q 4Add
6. R 1,5MP
7. R∨S 6Add
8. ¬P ∨ T 2,7MP
9. ¬P 8Simpl
10. P ∧ ¬P 4, 9Conj
11. ¬P 3-4PI

1.8. Trois Propriétés importantes

Séance du 24 Mars 2020

Pour terminer ce chapitre d’introduction à la logique propositionnelle, nous

allons montrer que ce systeme logique possede trois propriétés importantes; à
savoir:
1. Consistence
2. Rigidité
3. completude

1.8.1. Consistence
Etant donné qu’on peut utiliser plusieurs formes propositionnelles dans une
preuve; bien que seul un nombre fini suffit pour la preuve, nous désignerons notre
liste de formes propositionnelles par P0 , ..., Pn , ... et la notation P0 ...Pn .. ` Q
signifiera qu’uil existe une sous suite i0 , ..., in de 0, ..., n, ... telle que Pi0 , ..., Pin `
Q Par contre P0 ...Pn .. 0 Q signifiera qu’une telle sous suite n’existe.
Définition 0.2 Les formes propositionnelle P0 , ..., Pn , ... sont dites consistentes
si pour toute forme propositionnelle Q, P0 ...Pn .. 0 Q ∧ ¬Q. Dans ce cas on écrit
Con(P0 ...Pn ..) et dans le cas contraire on dit que P0 ...Pn .. est inconsistente

4
 Définition 0.3 Un systeme logique est dit consistent si aucune contradiction
n’est un théorème.

Nous visons deux objectifs: Le premier est de montrer que la logique proposi-
tionnelle est consistente et le second est de Wehavetwogoals est de déterminier
les propriétés des suites de formes propositionnelles consistentes qui nous per-
mettrons de montrer d’autres propriétés de logique propositionnelle.
Théorème 0.4 Si P0 , P1 , P2 ... sont des formes propositionnelles, alors les pro-
priétés suivantes sont équivalentes
(i) Con(P0 , P1 , P2 , ...)

(ii) Toute sous suite finie de P0 , P1 , P2 , ... est consistente,

(iii) Il existe une forme propositionnelle P telle que P0 , P1 , P2 , ... 0 P
Preuve:
(i) ⇒ (ii) On suppose que pour une certaine forme propositionnelle Q, il existe
une sous suite Pi0 , ..., Pin permettant de prouver Q ∧ ¬Q. Alors il ex-
iste une preuve formelle de Q ∧ ¬Q à partir de P0 , P1 , P2 , ... et donc non
Con(P0 , P1 , P2 , ...).
(ii) ⇒ (ii) On suppose que P0 , P1 , P2 , ... permet de prouver toutes formes proposi-
tionnelles. En particulier pour une forme propositionnelle Q, on aura
P0 , P1 , P2 , ... ` Q ∧ ¬Q. Ce qui signifie que qu’il existe une sous suite finie
Pi0 , ..., Pin permettant de prouver Q ∧ ¬Q.
(iii) ⇒ (i) On suppose qu’il existe une forme propositionnelle Q telle que P0 , P1 , P2 , ... `
Q ∧ ¬Q. Alors il existe une sous suite Pi0 , ..., Pin−1 et des formes propo-
sitionnelles r1 , ..., rm−1 telles que Pi0 , ..., Pin−1 , r1 , ..., rm−1 , Q∧¬Q est une
preuve. Alors pour toute forme propositionnelle P, Pi0 , ..., Pin−1 , r1 , ..., rm−1 , Q∧
¬Q, ¬P, P est une preuve de P d’après le théorème de preuve indirecte
(PI). D’ou P0 , P1 , P2 , ... ` Q ∧ P.

Définition 0.4 L’équivalence entre (i) et (ii) est appelée Théorème de com-
pacité
Bien que la suite P → Q, P, Q soit consistente, elle peut etre ajouté à une suite
de formes propositionnelles sans changer le resultat.
Définition 0.5 Une suite de formes propositionnelles P0 , P1 , P2 , ... est dite max-
imalement consistente si chaque fois que l’on a P0 , P1 , P2 , ... et pour toute forme
propositionnelle P, Con(P, P0 , P1 , P2 , ...) alors il existe i tel que P = Pi .

Théorème 0.5 Toute suite de forme propositionnelle consistente est une sous
suite d’une suite de formes propositionnelles consistentes.

Preuve: Faire comme TPE à remettre le jeudi 26 Mars 2020

5
1.8.2. Rigidité
Définition 0.6 (i) Une logique est dite rigide ou solide si tout théorème est
une tautologie
(ii) Une logique est dite complete si toute tautologie est un théorème
Lemme 0.2 Les règles d’inférences sont des tautologie.
Lemme 0.3 Soient P, Q et R des formes propositionnelles
(i) Si P ⇒ Q alors P → Q est une tautologie
(ii) si P, Q ⇒ R alors P ∧ Q → R est une tautologie.
Lemme 0.4 Si P → Q et P sont des tautologies, alors Q est une tautologie.
Théorème 0.6 (Théorème de Rigidité (TR))
Tout théorème de la logique propositionnelle est une tautologie.
Preuve: Exercice
Corollaire 0.2 Pour toutes formes propositionnelles P1 , P2 , ..., Pn−1 , Q
Si P1 , P2 , ..., Pn−1 ` Q alors P1 , P2 , ..., Pn−1 |= Q
Corollaire 0.3 La logique propositionnelle est consistente

1.8.3. Completude
On utilise la consistence de la logique propositionnelle permet de prouver que
la logique propositionnelle est complète.
Lemme 0.5 Si nonCon(¬Q, P0 , P1 , P2 , ...) alors P0 , P1 , P2 , ... ` Q
Preuve: Si nonCon(¬Q, P0 , P1 , P2 , ...) alors d’après le théorème O4 ¬Q, P0 , P1 , P2 , ... `
Q. Supposons donc Con(P0 , P1 , P2 , ...). Supposons qu’il existe une forme R
telle que ¬Q, P0 , P1 , P2 , ... ` R ∧ ¬R ceci implique qu’il existe une preuve
formelle Pi0 , ..., Pin−1 , ¬Q, s0 , ..., sm−1 , R ∧ ¬R où ¬Q est la preuve puisque
Con(P0 , P1 , P2 , ...). Donc Pi0 , ..., Pin−1 , Q est une preuve où Q est d’après le
théorème de preuve indirecte (PI) une sous preuve. Par suite, P0 , P1 , P2 , ... ` Q.

Lemme 0.6 Si P0 , P1 , P2 , ... est maximalement consistent alors pour toute forme
propositionnelle Q il existe i tel que Q = Pi ou ¬Q = Pi
Preuve: Exercice de TD
Pour comprendre la preuve du lemme suivant, se souvenir de la technique de
preuve par induction sur l’ensemble des formules
Lemme 0.7 Si Con(P0 , P1 , P2 , ...), alors il existe une valuation v telle que
v(P ) = V ssi P = Pi pour un certain i ∈ {0, 1, 2...}
Preuve: TPE
Théorème 0.7 (Théorème de Complétude (TC)) Toute tautologie de la logique
propositionnelle est un théorème.
Corollaire 0.4 Si P0 , P1 , P2 , ... |= Q alors P0 , P1 , P2 , ... ` Q pour toutes formes
propositionnelle P0 , P1 , P2 , ...

6
Chapitre 2: LOGIQUE DE PREMIER ORDRE