Chapitre 2

LOGIQUES ET DEMONSTRATIONS
Il n’existe pas de technique universelle de démonstration (heureusement pour les mathéma-
ticiens d’ailleurs). Chaque théorème nécessite une ou plusieurs idées qui lui sont propres pour
être démontré et il n’y a pas de moyen automatique d’obtenir cette ou ces idées.
Pour faire une démonstration il faut d’abord avoir les idées claires sur ce qu’il faut démontrer,
c’est-à-dire procéder à l’analyse logique complète du théorème, bien repérer quelles sont les
hypothèses, quelle est la conclusion, décomposer les hypothèses en énoncés simples en utilisant
les dé…nitions, etc.
Il y a plusieurs formes logique de raisonnement que l’on retrouve et qu’il faut connaître.

2.1 LOGIQUE DES PROPOSITIONS ET DEMONTRA-

TION
On dé…nit les propositions comme des énoncés, phrases décrivant une situation, une pro-
priété, une relation, un jugement, auxquelles on serait susceptible d’associer dans des circons-
tances précises une valeur vrai/faux. La logique se place essentiellement sous le signe de la
non-contradiction. Pour bien contraster le vrai et le faux et éviter les paradoxes, on s’interdit
les phrases à autoréférence telles que « cette phrase contient cinq mots » ou « quand je ne suis
pas lue, je suis écrite en arabe » . Sous cette réserve, on suppose les propositions élémentaires
traitées en bloc, sans attention aux sujets, compléments... comme pour l’énoncé « il fait beau
» . C’est pourquoi ce niveau peut être mis en rapport direct avec l’algèbre de Boole.

2.1.1 Formalisation des propositions

Dé…nition 2.1.1 - Les énoncés élémentaires seront représentés par des variables, dites va-
riables propositionnelles. Les énoncés composés seront formés d’un ou plusieurs énoncés
(élémentaires ou composés) combinés par des connecteurs :

L’énoncé composé est une qui dénote un énoncé

A^B conjonction vrai si et seulement si A et B sont tous vrais
A_B adjonction vrai dès que l’un des A ou B est vrai
:A négation vrai si A est faux, et réciproquement
A!B implication vrai sauf si A est vrai et B faux
A$B double implication vrai si A et B sont tous deux vrais, ou tous deux faux
Des combinaisons plus complexes pourront être formées par parenthèsage. Ainsi : ((A !
D) ! (D ! B)) ! (A ! B) se lira si A alors D implique que si D alors B, alors A implique
B.

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.1 LOGIQUE DES PROPOSITIONS ET DEMONTRATION 17

2.1.2 Substitutions
Dé…nition 2.1.2 - Soit E un énoncé contenant une variable propositionnelle p. L’énoncé ob-
tenu en remplaçant dans E chaque occurrence de p par un énoncé F sera dit substitué de E,
et noté E(pjF ). On pourra procéder à plusieurs substitutions d’un seul coup s’il n’y a pas
d’ambiguïté.

Exemple 2.1.1 E p ! (q ! p) donne E(pja ! b) (a ! b) ! (q ! (a ! b)):

2.1.3 Règles d’inférences

Dé…nition 2.1.3 - Toute logique possède des mécanismes générateurs, qui doivent per-
mettre d’ajouter un énoncé à un contexte. Ces …gures de raisonnement licites sont dites règles
d’inférence.

Les règles d’inférence sont notées X; Y; Z ) T , pour signi…er que l’énoncé de forme T , ou
conséquent, est valablement déduit d’énoncés de forme X; Y; Z, les antécédents.
Pour éviter les confusions, on réserve en général les majuscules aux (métavariables des)
règles d’inférence, et les minuscules aux (variables des) énoncés spéci…ques du problème.

2.1.4 Démonstrations
Dé…nition 2.1.4 - Soit E1 , E2 , ..., En une suite d’énoncés. On dira qu’il s’agit d’une dé-
monstration de germe E1 , ... Ek ; si :
E1 , ..., Ek sont des énoncés au sens précédent,
chaque énoncé Ei de la sous-suite d’énoncés Ek+1 , ..., En est dérivé de la sous-suite E1 ,
..., Ei 1 au sens suivant :
- il existe une règle d’inférence notée X, Y , Z ) T ,
- il existe une substitution d’énoncés s telle que les substitués s(X), s(Y ), s(Z) soient
précisément des énoncés de E1 , ..., Ei 1 ;
- et en…n, Ei = s(T ).
Alors, chacun des Ek+1 , ..., En est vrai si chacun des E1 , ..., Ek est vrai.

2.1.5 Systèmes et démonstrations

Soit un certain système à étudier. Nous connaissons au moins certaines de ses lois, causales
ou empiriques, et au moins partiellement son état.
Avec cela, on peut constituer un germe :
en associant des énoncés élémentaires aux caractéristiques de l’état, une situation du
système sera dé…nie par une suite de ces énoncés ou de leurs négations ;
les lois connues du système (causales ou factuelles) mèneront en général à des implications.
Dans ces conditions, une démonstration au sens ci-dessus fournit des énoncés vrais, appli-
cables au système dès lors que le système véri…e les lois et l’état dé…nis par le germe.
Si le germe se limite à des lois du système, les démonstrations (ne) produisent (que) des lois
secondaires. Les résultats seront d’autant plus concrets que le germe comprendra une dé…nition
plus …ne de l’état du système.

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.1 LOGIQUE DES PROPOSITIONS ET DEMONTRATION 18

2.1.6 Principales règles d’inférence

Règles d’inférences positives, sans négation
Ces règles sont essentiellement celles des tableaux 1 et 2.
Tableau 1 Règles d’inférence positive.
Nom Notation Signi…cation
recopie X)X
détachement X; X ! Z ) Z Si on a X, et "X implique Z", alors on a Z
conjonction X; Y ) X ^ Y Si X, et Y , (isolément) alors "X et Y "(ensemble)
ventillation X ^ Y , X; Y Si "X et Y "(ensemble) si et seulement si
X, et aussi Y , sont vrais iso lément
équivalence (X $ Y ) , (X ! Y ) ^ (Y ! X) "X équivaut à Y "si et seulement si
"X implique Y "et "Y implique X"
adjonction X )X _Y Si X est vrai, "X ou Y "l’est
dilemme (X _ Y ) ; (X ! R) ; (Y ! R) ) R si "X ou Y ", et "X implique R", et
"Y implique R",alors R (sans avoir à
déterminer lequel, de X, ou Y ,est vrai)
Tableau 2 Règles d’articulation des démonstrations.
Nom Notation Signi…cation
composition (X ) Y; Y ) Z) ) (X ) Z) Si X entaîne Y et si Y entaîne Z
alors X entaîne Z
déduction (X ) Y ) ) (X ! Y ) Si X entaîne Y (par quelque raisonnement
valide), alors le fait "X implique Y "est vrai
La règle de déduction engendre une implication comme trace utile d’une démonstration
auxiliaire imbriquée localement dans la démonstration principale, ou faite séparément comme
dans certains lemmes ou théorèmes techniques.

Règles d’inférence avec la négation

Le rôle de l’adjonction se précise. S’introduisent également des règles sur le thème si la
présence de A entraîne toujours celle de B, l’absence de B entraîne celle de A.
On détecte les contradictions, notées ?, et toute cause de contradiction est réfutée (tab. 3).
Tableau 3 Règles exploitant la négation.
Nom Notation Signi…cation
adjonction (X _ Y ) ) (:X ! Y ) ; (:Y ! X) Si X ou Y , alorst si l’un est faux
/élimination alors l’autre est vrai
contraposition (X ! Z) ) (:Z ! :X) Si un e¤et Z a une cause X alors
l’absence de l’e¤et implique
l’absence de la cause
réfutation (X ! Z) ; :Z ) :X Si un e¤et a une cause, et
si l’e¤et est absent, alors
la cause est absente par
contraposition + détachement
contradiction Z; :Z )? ? dénote la contradiction
/détection (X !?) ) :X ce qui mène à une
/élimination contradiction est faux

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.1 LOGIQUE DES PROPOSITIONS ET DEMONTRATION 19

Ces règles su¢ ront à établir au paragraphe 1.1.8 le principe de noncontradiction (ex. 6).

Règles aristotéliciennes
Avec l’involution, la négation se durcit ; la possibilité d’e¤acer les doubles négations donne
des résultats plus forts car plus simples ; la contraposition est symétrisée, la réfutation engendre
la reductio ad absurdum .
Ces règles, anciennes et e¢ caces, sont classiques en mathématiques, où la droite coupe ou
non le plan. Elles ont été isolées car elles sont inadéquates pour modéliser les systèmes
où les attributs ne sont pas bipolaires (X n’est ni pauvre ni riche...) ;
où la double négation est une forme faible de l’a¢ rmation (ce n’est pas inintéressant <
c’est intéressant).
Tableau 4 Règles aristotéliciennes.
Nom Notation Signi…cation
involution ::X ) X double négation vaut a¢ rmation
contraposition (X ! Z) ) (:Z ! :X) Symétrisation par e¤ecement des
doubles négations
absurdité (:X !?) ) X Si nier une hypothèse entraîne une
contradiction, l’hypothèse est établie
(par réfutation + involution)

2.1.7 Inférences fondamentales et secondaires

Lorsqu’on rencontre plusieurs fois une même suite d’inférences ayant des e¤ets globaux
simples et caractérisés, on peut considérer ce stéréotype comme constituant une nouvelle règle
d’inférence, ou règle d’inférence secondaire, qui peut se révéler plus commode que les règles
fondamentales.
Un raisonnement est valide s’il emploie des règles d’inférence valides, fondamentales ou se-
condaires. En pratique, l’homme a tendance à multiplier les stéréotypes pour aller plus vite.
Cependant, certains raisonnements sont faux (ou plutôt invalides) du fait de stéréotypes inva-
lides.
En cas de doute, expliciter un raisonnement facilite sa véri…cation.
Voici quelques exemples dans lesquels nous numérotons les énoncés dans un style niveau.rang
qui permet d’imbriquer des démonstrations. A chaque niveau, un trait horizontal séparera le
germe (ou l’hypothèse) de sa dérivation. Une barre verticale commune marquera les énoncés
d’une même démonstration locale.
Sans négation
Exemple 2.1.2 Soit un système formellement régi par :
0:1 : h ! (r _ p) = énoncés initiaux
0:2 : r ! m = :::
0:3 : p ! m = :::
Qu’en tirer ? h semble être la clé du système.
Posons : 1:0 : h = hypothèse pour une sous-démonstration
on en déduit 1:1 : r _ p = détachement 0:1; 1:0 (Xjh; Y jr _ p)
puis 1:2 : m = dilemme 1:1; 0:2; 0:3 (Xjh; Y jr _ p; Rjm)
d’où la propreté 0:4 : h ! m = déduction 1:0 1:2 (Xjh; Y jm)

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.1 LOGIQUE DES PROPOSITIONS ET DEMONTRATION 20

Exemple 2.1.3 Montrer que l’on a toujours X ! (X _ Y ).

Partant d’un germe vide, nous tentons une sous-démonstration sur une proposition quel-
conque :
1:0 x = hypothèse niveau 1
1:1 x _ y = adjonction 1:0 (Xjx; Y jy)
0:1 x ! (x _ y) = déduction 1:0 1:1 (Xjx; Y jy)
Cette démonstration est correcte quelles que soient les propositions substituées à x et y, elle
peut donc être vue comme tout à fait générale, et on retient son abstraction : X ! (X _ Y ).
Ce résultat a la forme d’un énoncé, mais n’utilise que des métavariables : c’est un méta-
énoncé qui vient d’être établi. Il constitue un métathéorème ou modèle de tautologie,
fournissant des énoncés vrais pour toute substitution d’énoncé à X et/ou Y .
Un modèle de tautologie est assimilable à une règle d’inférence sans antécédent : tout substi-
tué est une tautologie ou énoncé universellement vrai, i.e. indépendamment de la vérité de
ses variables ; ces tautologies peuvent toujours être utilisées comme étape d’une démonstration.
Une tautologie est une cheville ou un lieu commun de la logique : n’apportant rien en elle-
même, elle permet de relancer une démonstration, par combinaison avec des énoncés spéci…ques
au problème, et/ou en facilitant l’application de règles d’inférence plus constructives.
Ainsi peut-on, si nécessaire, insérer dans une démonstration un énoncé tel que ((a ! b) !
c) ! (((a ! b) ! c) _ (p ^ a)) comme tautologie obtenue par substitution de ((a ! b) ! c) à
X, et de (p ^ a) à Y , dans le modèle de tautologie X ! (X _ Y ).
En remplaçant l’adjonction en 1.1 par d’autres …gures, on obtiendra d’autres modèles de
tautologies, tels que : (X ! X) par simple recopie, (X ! (X ^X)) par conjonction, (X ^Y ) !
X par ventilation, (X _ X) ! X par dilemme...

Exemple 2.1.4 Montrer que X ! (X ! Y ) ) X ! Y:

0:1 x ! (x ! y) hypothèse initiale
1:0 x hypothèse niveau 1
1:1 (x ! y) détachement 0:1; 1:0 (Xjx; Y j(x ! y))
1:2 y détachement 1:1; 1:0 (Xjx; Y jy))
0:2 (x ! y) déduction 1:0; 1:2 (Xjx; Y jy)

Cette démonstration n’a rien de circonstanciel. Pouvant supporter toute substitution de

proposition aux variables prépositionnelles x et y, elle peut être considérée comme faisable en
toute généralité. L’in…nité des démonstrations possibles se résume par l’abstraction obtenue en
substituant des métavariables aux variables : (X ! (X ! Y )) ) (X ! Y )
Cette règle introduit un procédé de simpli…cation d’énoncé, et aussi le modèle de tautologie
((X ! (X ! Y )) ) (X ! Y ))

Exemple 2.1.5 SYLLOGISME. Montrer que (A ! B); (B ! C) ) (A ! C).

La démonstration ci-après pouvant supporter toute substitution de proposition aux variables

a, b, c, elle pourra être considérée comme faisable en toute généralité.

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.1 LOGIQUE DES PROPOSITIONS ET DEMONTRATION 21

0:0 (a ! b) germe
0:1 (b ! c) germe
1:0 a hypothèse
1:1 b détachement 0:0; 1:0
1:2 c détachement 0:1; 1:1
0:2 (a ! c) déduction 1:0; 1:2
On pourra admettre comme règle d’inférence son abstraction :
(A ! B); (B ! C) ) (A ! C)
Le procédé s’étend aux sorites ou syllogismes en chaîne
(A ! B); (B ! C); (C ! D); (D ! E); (E ! F ) ) (A ! F )
Des démonstrations semblables engendrent des tautologies apparentées :
((A ! B) ^ (B ! C)) ! (A ! C)
((A ! B) ! ((B ! C) ! (A ! C))):::
Avec négation, sans involution
Exemple 2.1.6 Montrer que (A ! :A) ) :A.
0:1 (a ! :a) germe
1:0 a hypothèse
1:1 :a détachement 0:0; 1:0 (Xja; Y j:a))
1:2 ? détection contradiction 1:0; 1:1
0:2 (a !?) déduction 1:0 à 1:2
0:3 :a élimination contradiction
Cette démonstration, supportant toute substitution sur a, peut être considérée comme fai-
sable en toute généralité, et on peut admettre son abstraction : (A ! :A) ) :A
Plus directement, on pourrait écrire la méta-déduction :
0:1 (A ! :A) germe
1:0 A hypothèse
1:1 :A détachement 0:0; 1:0
1:2 ? détection contradiction 1:0; 1:1
0:2 (A !?) déduction
0:3 :A élimination contradiction
Résumée par : (A ! :A) ) :A
qui mène au schéma de tautologie : (A ! :A) ! :A
Exemple 2.1.7 PRINCIPE DE NON-CONTRADICTION (LUKASIEWICZ).
Le principe « une proposition et sa contraire ne sont jamais simultanément vraies » s’établit
en supposant une telle conjonction, qui entraîne une contradiction et se trouve ainsi réfutée.
1:0 (A ^ :A) hypothèse
1:1 A ventillation 1:0
1:2 :A ventillation 1:1
1:3 ? contradiction 1:1; 1:2
0:0 :(A ^ :A) réfutation 1:0; 1:3
Ce principe fondamental découle de la seule réfutation.

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.1 LOGIQUE DES PROPOSITIONS ET DEMONTRATION 22

Exemple 2.1.8 PREMIÈRE RÈGLE DE DE MORGAN :(X _ Y ) ! (:X ^ :Y )

1:0 X hypothèse
1:1 X _ Y adjonction 1:0
0:0 X ! (X _ Y ) déduction 1:0; 1:1
1:0 Y hypothèse
1:1 X _ Y adjonction 1:0
0:1 Y ! (X _ Y ) déduction 1:0; 1:1
1:0 :(X _ Y ) hypothèse
1:1 :X contransposition 0:0; 1:0
1:2 :Y contransposition 0:1; 1:0
1:3 (:X) ^ (:Y ) conjonction 1:2; 1:3
0:2 :(X _ Y ) ! ((:X) ^ (:Y )) déduction 1:0; 1:3

Exemple 2.1.9 PRINCIPE DU TIERS EXCLUS «tertium non datur»

Le principe « d’une proposition et sa contraire, au moins l’une est vraie » , noté A _ :A,
s’établit par l’absurde, en montrant que : (A _ :A) entraîne une contradiction sur :A.
1:0 A hypothèse
1:1 A _ :A adjonction 1:0
0:0 A ! (A _ :A) déduction 1:0; 1:1
1:0 :A hypothèse
1:1 A _ :A adjonction 1:0
0:1 :A ! (A _ :A) déduction 1:0; 1:1
1:0 :(A _ :A) hypothèse
1:1 :A contransposition 0:0; 1:0
1:2 ::A contransposition 0:1; 1:0
1:3 ? contradiction sur :A; 1:1; 1:2
0:2 :: (A _ :A) réfutation 1:0; 1:3
0:3 (A _ :A) involution 0:2, ou absurdité 1:0; 1:3

Exemple 2.1.10 SECONDE RÈGLE DE DE MORGAN :(X ^ Y ) ! (:X _ :Y )

1:0 :X hypothèse
1:1 :X _ :Y adjonction 1:0
0:0 :X ! (:X _ :Y ) déduction 1:0; 1:1
1:0 :Y hypothèse
1:1 :X _ :Y adjonction 1:0
0:1 :X ! (:X _ :Y ) déduction 1:0; 1:1
1:0 :(:X _ :Y ) hypothèse
1:1 ::X contransposition 0:0; 1:0
1:2 ::Y contransposition 0:1; 1:0
1:3 X involution 1:1
1:4 Y involution 1:2
1:5 X ^ Y conjonction 1:3; 1:4
0:2 :(:X _ :Y ) ! (X ^ Y ) déduction 1:0; 1:5
0:3 :(X ^ Y ) ! ::(:X _ :Y ) contransposition 0:2
0:4 :(X ^ Y ) ! (:X _ :Y ) involution 0:3

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.2 LOGIQUE DES PREDICATS ET DEMONTRATION 23

2.2 LOGIQUE DES PREDICATS ET DEMONTRATION

C’est la logique la plus utilisée, ni trop simpliste, ni trop complexe.

2.2.1 Prédicats
On s’intéresse toujours aux phrases auxquelles on devrait pouvoir associer dans des circons-
tances précises une valeur vrai/faux.
Les énoncés élémentaires ou prédicats portent maintenant sur la vérité/le jugement
d’une relation entre des objets ou termes, correspondants aux sujets, compléments.. . de la
phrase.
Ainsi, « Pierre est au jardin » pourra être ici noté estEn(Pierre, jardin) où estEn désignera
une relation entre un objet (ici Pierre) et son emplacement (ici jardin).

2.2.2 Formalisation des termes

Dé…nition 2.2.1 Un terme est un objet ou individu dénoté :
soit par une constante ; ex : Pierre, jardin,
soit par une variable ; ex : x, y...
soit par une notation fonctionnelle f (t1 ; t2 ; :::; tk ), où f est un symbole fonctionnel ou
nom de fonction, et où les t1 ; t2 ; :::; tk sont des termes ;
ex : père(Pierre), premier(enfants(Pierre, Marie)).

On appelle terme clos un terme n’utilisant pas de variables, et qui dénote ainsi indirecte-
ment des constantes.

2.2.3 Formalisation des énoncés

Enoncés élémentaires

Dé…nition 2.2.2 - En logique des prédicats, un énoncé élémentaire ou prédicat atomique

est une écriture fonctionnelle p(t1 ; t2 ; :::; tk )
où p est un symbole prédicatif ou nom de prédicat,
et dont les arguments t1 ; t2 ; :::; tk sont des termes.
Un tel énoncé
dénote une relation précisée par le symbole prédicatif, et portant sur les termes mention-
nés ;
a pour valeur non un terme mais une valeur de vérité associée à cette relation, satisfaite
ou non par ce jeu de termes.

Exemple 2.2.1 estEn(pere(P ierre); jardin) pour « le père de Pierre est au jardin » (vrai/faux),
plus(X; 0; X) pour « X + 0 = X » (vrai/faux).

Enoncés composés

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.2 LOGIQUE DES PREDICATS ET DEMONTRATION 24

Dé…nition 2.2.3 Plus généralement on appellera énoncé :

tout énoncé élémentaire,
si E, E1 , E2 sont des énoncés, l’une des notations du tableau 5.

Tableau 5 Énoncés composés.

Notation Signi…cation
(E1 ^ E2 ) E1 et E2
(E1 _ E2 ) E1 ou E2
(E1 ! E2 ) E1 implique E2
(E1 $ E2 ) E1 équivaut à E2 , E1 si seulement si E2
:E non E
8x E (x) pour tout x, E (x) / où x est une variable muette
9x E (x) il existe au moins un x tel qUE E (x) / où x est une variable muette

Les symboles _, ^, !, $ et : sont des connecteurs, les nouveaux symboles 8 et 9 sont dits
quanti…cateurs.
Les deux dernières formes, dites quanti…ées, généralisent l’énoncé interne.
L’énoncé s’interprète
8x plus(x; 0; x) pour tout x, x + 0 = x
8x 9y plus(x; y; 0) pour tout x, il existe au moins un y tel que x + y = 0
8x (homme (x) ! mortel (x)) pour tout x, si x est un homme alors x est mortel ou :
tout homme est mortel
Lexiques
Pour éviter toute confusion, on utilise des lexiques disjoints pour les variables, les fonctions,
les prédicats.
Arités

Dé…nition 2.2.4 On appelle arité d’une fonction ou d’un prédicat, le nombre de termes qu’il
faut associer à son nom.
Le lexique des constantes symboliques s’identi…e au lexique des fonctions d’arité 0.
On appelle souvent propositions les prédicats d’arité 0, et propriétés les prédicats d’arité
1.

2.2.4 Systèmes et démonstrations

Comme précédemment on modélise un système en exprimant sous forme logique ses lois et
son état.
Ceci constituera le germe de démonstrations exploitant les règles d’inférence.
Si le germe est réduit aux lois du système, la démonstration établit des lois secondaires
du système. Si le germe contient des énoncés sur l’état du système, on obtient des résultats
factuels.

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.2 LOGIQUE DES PREDICATS ET DEMONTRATION 25

2.2.5 Règles d’inférence

Comme dans la section 1, elles sont notées antécédents ) conséquent, et signi…ent : si
le contexte satisfait les antécédents à une substitution s près, alors on peut, dans la logique
considérée, ajouter au contexte le conséquent soumis à la même substitution s, où le contexte
désigne les énoncés du germe, augmenté des conséquents déjà établis.
Les nouveautés sont relatives aux quanti…cateurs, et à la nécessité pour les substitutions
d’accorder entre eux les énoncés d’une part, les termes de l’autre.
Pour éviter une dé…nition trop complexe des ces règles, commençons par celles qui per-
mettent de faire apparaître ou d’éliminer les connecteurs et les quanti…cateurs (en rapport avec
les termes).
Nous pouvons utiliser le système du tableau 6, où le symbole ? dénote une contradiction,
complété par les tableaux 7 et 8.

Tableau 6 Règles d’inférence sur les connecteurs.

Nom Introduction Elimination
implication (A ) B) ) (A ! B) A; (A ! B) ) B
conjonction A; B ) A ^ B (A ^ B) ) A; B
équivalence (A ! B) ^ (B ! A) ) (A $ B) (A $ B) ) (A ! B) ^ (B ! A)
contradiction A; :A )? réfutation (A )?) ) :A
absurdité (:A )?) ) A
involution A ) ::A ::A ) A
adjonction A ) (A _ B) ; (B _ A) par dilemme (A _ B) ; (A ! C) ; (B ! C) ) C
par implication (A _ B) ) (:A ! B) ; (:B ! A)
Tableau 7 Règles sur les quanti…cateurs.
Quanti…cation Généralisation Spéci…cation
universelle A (t) ) 8x A (x), où t est 8x A (x) ) A (t), où t est un terme
une variable libre quelconque
existentielle A (a) ) 9x A (x), où a est 9x A (x) ) A (a), où a est une nouvelle
un terme clos constante, ajoutée au lexique
Tableau 8 Règles globales.
Nom Elimination
dualité 8x E (x) , :9x :E (x)
:8x E (x) , 9x :E (x)
9x E (x) , :8x :E (x)
récurrence E (0) ; 8n (E (n) ! E (n + 1)) ) 8n E (n)

2.2.6 Exemples
Exemple 2.2.2 Prouver que si un entier a n’est pas divisible par 3, alors a2 1 est divisible
par 3.

Notons mod(a; p; r) le prédicat « a divisé par p a pour reste r » .

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024
2.2 LOGIQUE DES PREDICATS ET DEMONTRATION 26

0:1 8a8b8p mod(a; p; 0) ! mod(a b; p; 0) def mod

0:2 8a mod(a; 3; 0) _ mod(a 1; 3; 0) _mod(a + 1; 3; 0) spec mod 3
0:3 8a8b8p mod(a 1; p; 0) ! mod((a 1) b; p; 0) 0:1 (aja 1)
0:4 8a8p mod(a 1; p; 0) ! mod((a 1) (a + 1) ; p; 0) 0:3 (bja + 1)
0:5 8a8p mod(a 1; p; 0) ! mod(a2 1; p; 0) propriété de
0:6 8a8b8p mod(a + 1; p; 0) ! mod((a + 1) b; p; 0) 0:1 (aja + 1)
0:7 8a8p mod(a + 1; p; 0) ! mod((a + 1) (a 1) ; p; 0) 0:3 (bja 1)
0:8 8a8p mod(a + 1; p; 0) ! mod(a2 1; p; 0) propriété de
0:9 8a :mod(a; 3; 0) ! (mod(a 1; 3; 0) _mod(a + 1; 3; 0)) élim. adj. 0:2
1:0 :mod(a; 3; 0) hypothèse
1:1 :mod(a; 3; 0) ! (mod(a 1; 3; 0) _mod(a + 1; 3; 0)) spec 0:9
1:2 (mod(a 1; 3; 0) _mod(a + 1; 3; 0)) détachement 1:0; 1:1
1:3 mod(a 1; 3; 0) ! mod(a2 1; 3; 0) spec 0:5
2
1:4 mod(a + 1; 3; 0) ! mod(a 1; 3; 0) spec 0:8
1:5 mod(a2 1; 3; 0) dilemme 1:2; 1:3; 1:4
2
0:10 :mod(a; 3; 0) ! mod(a 1; 3; 0) déduction 1:1; 1:5
2
0:11 8a :mod(a; 3; 0) ! mod(a 1; 3; 0) généralisation 0:10

Exemple 2.2.3 Montrer qu’une relation R intransitive est irré‡exive.

Argument : si un élément a est en relation avec lui-même par R, il l’est autant de fois que
l’on veut ; or s’il l’est deux fois, l’intransitivité interdit une troisième, d’où contradiction.
0:1 8a8b8c R (a; b) ^ R (b; c) ! :R (a; c) def intransitivité
0:2 8a8b (R (a; b) ^ R (b; b)) ! :R (a; b) spec univ 0:1; (cjb)
0:3 8a (R (a; a) ^ R (a; a)) ! :R (a; a) spec univ 0:2; (bja)
1:0 R (a; a) hypothèse locale
1:1 R (a; a) ^ R (a; a) conjonction 1:0; 1:0
1:2 (R (a; a) ^ R (a; a)) ! :R (a; a) spec univ 0:3
1:3 :R (a; a) détachement 1:1; 1:2
1:4 ? contradiction 1:0; 1:3
0:4 :R (a; a) réfutation 1:0; 1:4
0:5 8a :R (a; a) généralisation univ 0:4

@HugueTchantcho, PhD. Université Saint Jean de Yaoundé Maths discrètes Lic Pro1 Année 2023-2024