Plan du site  
français  English
pixel
pixel

Articles - Étudiants SUPINFO

Chapitre 01 - Introduction à la logique des propositions et à la logique des prédicats

Le but de ce premier chapitre va être d'introduire les bases de la branche des mathématiques appelée logique. On présentera en particulier les différences entre la logique des propositions et celle des prédicats. On s'attardera également sur quelques techniques fondamentales de preuves mathématiques.

Logique des propositions

Nous allons dans cette partie définir la notion de proposition et étudier différentes façons d'en connecter plusieurs.

Contexte

Commençons par un petit exemple en considérant cette assertion : SI je suis salarié ALORS je paie des impôts sur le revenu. Supposons maintenant que je ne paie pas d'impôts sur le revenu. On peut DONC en conclure que je ne suis pas salarié.

Le lecteur conviendra qu'il s'agit de pur bon sens.

La logique des propositions est une branche des mathématiques permettant d’étudier des raisonnements comme celui-ci.

Dans cette logique, on va étudier les relations possibles entre des énoncés, les propositions.

Ces relations s’exprimeront à l’aide de connecteurs logiques comme le SI ... ALORS précédent.

En logique des propositions, la validité des raisonnements ne dépendra pas de la signification même des propositions, mais uniquement du bon usage des connecteurs.

Le raisonnement suivant est ainsi tout aussi valide que le premier : SI j’ai soif ALORS je vais boire un verre. Je ne vais pas boire un verre DONC je n’ai pas soif.

La construction des deux raisonnements est en effet clairement la même.

Nous allons formaliser tout cela dans la suite de cette première partie.

La notion de proposition

Il est de rigueur de commencer par la définition.

Définition

On appelle proposition tout énoncé dont on peut affirmer sans ambiguïté qu’il est vrai ou faux.

[Note]

L'assertion de la définition précédente est aussi appelée principe de bivalence.

Example 1.1. Des propositions

  • "4 est un nombre impair" est une proposition fausse.

  • " 3 × 2 = 6 " est une proposition vraie.


[Note]

Cette définition exclut de fait des énoncés de la forme "cette phrase est fausse", connu également sous le nom de paradoxe du menteur.

En effet si cette phrase est vraie cela signifie que l'énoncé est faux, mais si elle fausse cela signifie que l'énoncé est vrai. Il y a donc ambiguïté.

Ne sont pas concernés également les sentences interrogatives, impératives ou exclamatives.

Dans cette partie, nous considérerons une proposition comme un énoncé pris en bloc, susceptible de recevoir l’une ou l’autre des deux valeurs logiques, le vrai et le faux. C’est la logique dite des propositions. Nous n’aurons donc qu’une vue externe des propositions.

[Note]

Nous ne nous intéresserons à la structure interne des propositions que dans la seconde partie de ce cours avec l'étude de la logique des prédicats.

Pour simplifier la manipulation des propositions, on utilisera des tables de vérité, dont le principe est très simple.

Nous utiliserons la lettre V pour indiquer qu'une proposition est vraie et la lettre F si elle est fausse :

P
V
F

Alternativement, on pourra également utiliser les valeurs 1 et 0 :

P
1
0

Les connecteurs logiques

Un connecteur logique va à partir d'une ou plusieurs propositions en construire une nouvelle. Présentons ici les principaux.

Connecteur unaire

Définition

On appelle négation d’une proposition P la proposition notée ¬ P ou P qui a des valeurs logiques opposées à celles de P.

Il s’agit d’un connecteur logique unaire, puisqu’il n’a qu’un seul opérande.

Voici la table de vérité de la négation :

P ¬ P
V F
F V

Donnons de suite un petit exemple.

Example 1.2. Négations

  • Si P est "5 est un nombre pair", proposition qui est fausse, sa négation est "5 est un nombre impair", qui elle est vraie.

  • Si P est " 2 × 4 = 8 ", proposition qui est vraie, sa négation est " 2 × 4 8 ", qui elle est fausse.


[Note]

Nous reviendrons plus tard sur les méthodes permettant d’obtenir la négation d’une proposition.

En effet, pour nier une proposition un tant soit peu complexe, il faut le faire en considérant sa structure interne, cela relève donc de la logique des prédicats.

Connecteurs binaires

Un connecteur logique binaire permet de relier deux propositions pour en former une nouvelle.

Pour étudier ces connecteurs on dressera donc des tables de vérités. Celles-ci devront couvrir toutes les valeurs possibles des deux propositions reliées. Elles auront ainsi cette allure :

P Q Connecteur ( P , Q )
F F ...
F V ...
V F ...
V V ...

Un calcul fort simple montre qu’il existe 16 connecteurs logiques binaires. Il y a en effet 2 valeurs possibles pour chacune des 4 lignes d'une telle table, ce qui fait bien 2 4 = 16 possibilités.

Pour notre part nous allons en privilégier 4, à savoir la conjonction, la disjonction, l’implication et l’équivalence.

Conjonction

Définition

On appelle conjonction des propositions P et Q la proposition notée P Q qui est vraie si P et Q sont vraies à la fois, et fausse dans tous les autres cas.

[Note]

De façon abrégée on dit également "P et Q".

Voici la table de vérité de la conjonction :

P Q P Q
F F F
F V F
V F F
V V V

Illustrons cette notion par un exemple.

Example 1.3. Conjonctions

Considérons les propositions suivantes :

  • A : 2 10 = 1024 . A est vraie.

  • B : 5 < 4 . B est fausse.

  • C : 3 est un nombre impair. C est vraie.

La proposition A B , i.e. ( 2 10 = 1024 ) ( 5 < 4 ) est une proposition fausse car B est fausse.

La proposition A C , i.e. ( 2 10 = 1024 ) ( 3 est un nombre impair ) est une proposition vraie car A et C sont vraies.


Présentons maintenant quelques résultats relatifs à la conjonction.

Propriétés

La conjonction est un opérateur commutatif, cela signifie que pour toutes propositions P et Q, on a P Q = Q P .

Pour toute proposition P, la proposition P ( ¬ P ) est toujours fausse. Ce dernier résultat est appelé principe de non-contradiction.

[Note]

Le principe de non-contradiction signifie qu’une proposition et sa négation ne peuvent être vraies en même temps.

Démonstration

Ces deux résultats se démontrent très aisément à l’aide de tables de vérités.

Par exemple pour le second :

P ¬ P P ( ¬ P )
V F F
F V F
Disjonction

Définition

On appelle disjonction des propositions P et Q la proposition notée P Q qui est fausse si P et Q sont fausses à la fois, et vraie dans tous les autres cas.

[Note]

De façon abrégée on dit également "P ou Q".

Voici la table de vérité de la disjonction :

P Q P Q
F F F
F V V
V F V
V V V

Voici un exemple de cette notion.

Example 1.4. Disjonctions

Considérons les propositions suivantes :

  • A : 2 10 = 1024 . A est vraie.

  • B : 5 < 4 . B est fausse.

  • C : 3 est un nombre pair. C est fausse.

La proposition A B , i.e. ( 2 10 = 1024 ) ( 5 < 4 ) est une proposition vraie car A est vraie.

La proposition B C , i.e. ( 5 < 4 ) ( 3 est un nombre impair ) est une proposition fausse car B et C sont fausses.


Présentons maintenant quelques résultats relatifs à la disjonction.

Propriétés

La disjonction est un opérateur commutatif, cela signifie que pour toutes propositions P et Q, on a P Q = Q P .

Pour toute proposition P, la proposition P ( ¬ P ) est toujours vraie. Ce dernier résultat est appelé principe du tiers exclu.

[Note]

Le principe du tiers exclu signifie qu'étant donné une proposition, soit elle est vraie, soit sa négation l'est.

Démonstration

Ces deux résultats se démontrent très aisément à l’aide de tables de vérités.

Par exemple pour le second :

P ¬ P P ( ¬ P )
V F V
F V V
[Note]

Cette disjonction est parfois qualifiée d’inclusive car elle est vraie aussi dans le cas où les deux propositions concernées sont vraies.

Elle est à opposer à la disjonction exclusive qui n’est vraie que si une seule des deux propositions concernée est vraie. Dans ce cas on utilise également le terme de ou exclusif.

Implication

Définition

On appelle implication de la proposition P par la proposition Q la proposition notée P Q qui est fausse si P est vraie et Q est fausse, et vraie dans tous les autres cas.

[Note]

De façon abrégée on dit également "P implique Q".

Voici la table de vérité de l'implication :

P Q P Q
F F V
F V V
V F F
V V V

Eclairons cette définition avec un exemple géométrique.

Example 1.5. Implications

  • Voici une implication vraie : Le quadrilatère ABCD est un losange AB = BC .

  • Voici une implication fausse : AB = BC Le quadrilatère ABCD est un losange .


[Note]

Rappelons pour la bonne compréhension de l'exemple précédent, même si c’est sans doute inutile, qu’un losange est un quadrilatère ayant quatre côtés de même longueur.

[Note]

En langage courant, l'implication correspond au raisonnement SI ... ALORS.

Par exemple, si le quadrilatère ABCD est un losange, alors AB = BC .

Equivalence

Définition

On appelle équivalence des propositions P et Q la proposition notée P Q qui est qui est vraie si P et Q ont la même valeur logique et fausse si P et Q ont des valeurs logiques différentes.

[Note]

Deux propositions sont donc équivalentes à l’unique condition d’avoir les mêmes valeurs de vérité.

Voici la table de vérité de l'équivalence :

P Q P Q
F F V
F V F
V F F
V V V

Comme toujours, un exemple nous aidera à bien apréhender cette définition.

Example 1.6. Equivalences

  • Voici une équivalence vraie : Le quadrilatère ABCD est un losange AB = BC = CD = DA .

  • Voici une implication fausse : Le quadrilatère ABCD est un losange AB = BC .


[Note]

En langage courant, l’équivalence correspond au raisonnement SI ET SEULEMENT SI .

Par exemple, le quadrilatère ABCD est un losagne si et seulement si ses quatre côtés ont la même longueur.

Propriétés importantes

Cette sous-partie sera consacrée à la présentation de diverses propriétés vérifiées par les connecteurs logiques.

Nous pouvons tout d'abord établir des relations de distributivité entre la conjonction et la disjonction.

Formules de distributivité

Soient P, Q et R des propositions.

La conjonction est distributive par rapport à la disjonction

P ( Q R ) ( P Q ) ( P R )

La disjonction est distributive par rapport à la conjonction

P ( Q R ) ( P Q ) ( P R )
[Note]

Une équivalence de ce type se montre sans difficultés, on établit la table de vérité de chacun des deux membres de l'équivalence et l'on constate qu’elles sont égales. Tout étudiant se doit de savoir le faire, c'est d'ailleurs au programme de la première séance d'exercices.

Ca sera également le cas pour la plupart des propriétés de cette sous-partie.

Les formules suivantes sont appelées lois de De Morgan, du nom de leur auteur Augustus De Morgan (1806-1871), qui fut un mathématicien britannique.

Lois de De Morgan

Soient P et Q des propositions.

Négation d'une conjonction

¬ ( P Q ) ( ¬ P ) ( ¬ Q )

Négation d'une disjonction

¬ ( P Q ) ( ¬ P ) ( ¬ Q )

Nous allons maintenant présenter une version équivalente de l'implication.

Réécriture de l’implication

Soient P et Q des propositions.

On a

( P Q ) ( ( ¬ P ) Q )

Cette dernière formule nous permet en particulier d'obtenir facilement une méthode pour nier une implication.

Négation de l’implication

Soient P et Q des propositions.

On a

¬ ( P Q ) ( P ( ¬ Q ) )

Démonstration

D'après la réécriture de l'implication on a

¬ ( P Q ) ¬ ( ( ¬ P ) Q )

On utilise alors la première loi de De Morgan pour obtenir

¬ ( ( ¬ P ) Q ) ( ¬ ( ¬ P ) ) ( ¬ Q )

Or ( ¬ ( ¬ P ) ) P , ce qui prouve le résultat.

Pour terminer cette première partie, montrons qu'une équivalence peut se ramener à une conjonction de deux implications.

Réécriture de l’équivalence

Soient P et Q des propositions.

On a

( P Q ) ( ( P Q ) ( Q P ) )

Cette formule est à l'origine de la méthode dite de double implication : pour démontrer que deux propositions sont équivalentes, on montre que la première implique la seconde et que réciproquement la seconde implique la première.

[Note]

Il est en effet assez rare de démontrer d'une seule étape une équivalence entre deux propositions. Les arguments utilisés pour prouver chacune des deux implications n'ayant en effet aucune raison d'être identiques.

Logique des prédicats

Intéressons nous maintenant dans cette seconde partie à la structure interne des propositions.

Contexte

En logique des prédicats, une proposition ne va plus être plus vue comme un bloc indivisible. Elle va être décomposée en un sujet et un prédicat.

Considérons par exemple la proposition "Laurent habite Tours" :

  • Le sujet est "Laurent". Il s'agit d'une constante mais cela aurait tout aussi bien pu être une variable.

  • Le prédicat est "habite Tours".

[Note]

En linguistique, un prédicat est la partie d'une phrase qui renseigne sur ce que fait le sujet. En logique, le sujet sera un élément d'un ensemble, mais le principe reste le même.

L'intérêt de procéder ainsi est de pouvoir analyser des situations un peu plus complexes qu’en logique des propositions.

Reprenons un exemple simple et valide en logique des propositions : SI Robert travaille ALORS il aura ses crédits ECTS. Supposons maintenant que Robert travaille. On peut DONC en conclure qu'il aura ses crédits ECTS. Simple tautologie.

Par contre le raisonnement suivant n'est pas valide en logique des propositions : SI Un étudiant travaille ALORS il aura ses crédits ECTS. Supposons maintenant que Robert soit un étudiant qui travaille. On peut DONC en conclure qu'il aura ses crédits ECTS. Cette déduction semble pourtant correcte mais la logique des propositions ne permet pas de la valider. En effet, dans cette logique on ne considère les propositions que de façon externe. Ainsi, le lien entre "un étudiant" et "Robert" ne se fait pas car ce sont deux sujets différents. Le premier est universel, on parle de tous les étudiants, alors que le second a une portée particulière, seul Robert est concerné.

La logique des prédicats va alors résoudre ce problème en s'attachant à analyser la structure interne des propositions, c'est-à-dire en regardant la façon dont elles sont construites.

Ceci dit, on continuera bien sûr d’utiliser les connecteurs logiques précédemment étudiés afin de relier entre elles les propositions.

Les énoncés en logique des prédicats

Pour écrire un énoncé en logique des prédicats, on utilisera :

  • Des constantes (Robert, Laurent, DS 3,…).

  • Des variables (x, y, z…), qui pourront prendre leurs valeurs dans un ensemble spécifié.

  • Des prédicats, qui pourront porter sur une ou plusieurs variables ou constantes.

  • Des connecteurs logiques (ceux étudiés dans la première partie de ce chapitre).

  • Des quantificateurs ( "quel que soit" et "il existe", voir sous-partie suivante).

Les quantificateurs

Nous allons présenter ici les deux quantificateurs usuellement utilisés en mathématiques.

Le premier concerne tous les éléments d'un ensemble.

Définition

Le quantificateur universel, noté , signifie que tous les éléments d’un ensemble possèdent une certaine propriété.

Il se lit "quelque soit" ou "pour tout".

Donnons un exemple d'énoncé utilisant ce quantificateur.

Example 1.7. Quantificateur universel

Le fait que tous les nombres réels aient un carré supérieur ou égal à 0 peut s'écrire

x, x 2 0

Le second quantificateur a lui une portée plus restreinte.

Définition

Le quantificateur existentiel, noté , signifie qu'un élément au moins d’un ensemble possède une certaine propriété.

Il se lit "il existe au moins un".

Voici un énoncé écrit avec ce quantificateur.

Example 1.8. Quantificateur existentiel

Le fait qu'il existe au moins un nombre réel dont le carré est inférieur ou égal à 0 peut s'écrire

x, x 2 0

[Note]

Dans ce dernier énoncé, la virgule signifie "tel que". On pourrait alternativement utiliser une barre oblique /.

On peut faire succéder plusieurs quantificateurs dans un même énoncé mathématique, mais le sens de cet énoncé dépendra de l’ordre dans lequel figurent ces quantificateurs.

Nous allons le constater sur un exemple.

Example 1.9. Importance de l'ordre des quantificateurs

La proposition suivante est fausse

x,y,x<y

En effet, elle signifie qu'il existe au moins un réel strictement plus petit que tous les autres réels, ce qui est bien sûr faux.

Par contre, cette proposition est vraie

y,x,x<y

Pour tout réel y, il existe en effet au moins un réel x qui lui est strictement inférieur (prendre par exemple x = y - 1 ).

Ces deux propositions n'ont donc clairement pas le même sens alors que seul l'odre dans lequel sont placés les quantificateurs les distinguent.


Voyons maintenant comment obtenir la négation d'une proposition contenant un quantificateur.

Propriétés

Voici la négation d'une proposition contenant le quantificateur universel

¬ ( x , P ( x ) ) x , ¬ P ( x )

Voici la négation d'une proposition contenant le quantificateur existentiel

¬ ( x , P ( x ) ) x , ¬ P ( x )
[Note]

Il s'agit de résultats de pur bon sens. Par exemple, la négation de "tous les étudiants jouent en ligne" est "il existe au moins un étudiant qui ne joue pas en ligne".

Exemple

Reprenons le raisonnement de la sous-partie 2.1 : SI Un étudiant travaille ALORS il aura ses crédits ECTS. Supposons maintenant que Robert soit un étudiant qui travaille. On peut DONC en conclure qu'il aura ses crédits ECTS.

Afin de le formaliser, introduisons les notations suivantes :

  • Soit S l'ensemble de tous les étudiants de SUPINFO.

  • Soit T ( . ) le prédicat "travailler".

  • Soit C ( . ) le prédicat "obtenir ses crédits ECTS".

Le raisonnement précédent peut alors se reformuler en

x S , T ( x ) C ( x )

Or on a à la fois RobertS et T ( Robert ) .

Donc C ( Robert ) , c'est-à-dire que Robert aura ses crédits ECTS.

Et dans ce contexte de logique des prédicats, ce raisonnement est cette fois ci complètement valide.

Quelques techniques de preuves mathématiques

Nous allons dans cette dernière partie présenter quatre techniques permettant de réaliser des démonstrations mathématiques. Il en existe bien sûr beaucoup d'autres mais les fondements de celles choisies ici utilisent les logiques des propositions et des prédicats.

Ces méthodes sont très classiques, le lecteur les aura peut-être déjà rencontrées.

Preuve par contraposée

Le raisonnement par contraposée, ou contraposition, est un raisonnement logique où pour démontrer une implication P Q , on montre que la négation du conséquent, i.e. ¬Q, implique la négation de l’antécédent, i.e. ¬P.

Autrement dit, puisque la cause P d’une implication engendre la conséquence Q, alors l’absence de la conséquence, i.e. ¬Q, implique automatiquement l’absence de la cause, i.e. ¬P.

Formalisons cela.

Raisonnement par contraposée

Pour démontrer une implication P Q , il est équivalent de démontrer que ¬ Q ¬ P .

[Note]

L’intérêt de recourir à cette méthode réside dans le fait que dans de nombreux cas, la contraposée est plus facile à démontrer que l’implication initiale.

Démonstration de la validité du raisonnement par contraposée

On peut justifier cette méthode en utilisant des tables de vérité.

On connaît la table de vérité de l'implication P Q :

P Q P Q
F F V
F V V
V F F
V V V

Etablissons maintenant celle de l'implication ¬ Q ¬ P :

P Q ¬P ¬Q ¬ Q ¬ P
F F V V V
F V V F V
V F F V F
V V F F V

Les colonnes donnant les valeurs de ¬P et ¬Q sont obtenues simplement en prenant les valeurs opposées à celles de P et Q. Pour avoir les valeurs de ¬ Q ¬ P , il faut utiliser la définition de l'implication, ¬ Q ¬ P sera fausse uniquement quand ¬Q est vraie et ¬P est fausse.

On constate alors que les deux tables sont les mêmes, Q.E.D.

On peut également justifier cette méthode en utilisant la réécriture de l'implication vue dans la première partie. On a en effet

( P Q ) ( ( ¬ P ) Q )

En utilisant cette formule avec ¬Q et ¬P à la place de P et Q, il vient

( ¬ Q ¬ P ) ( ( ¬ ( ¬ Q ) ) ( ¬ P ) )

D'où

( ¬ Q ¬ P ) ( Q ( ¬ P ) )

On conclut alors grâce à la commutativité de le disjonction.

Illustrons cette méthode par un exemple.

Example 1.10. Une preuve par contraposée

On cherche à démontrer que pour des réels x et y, on a

( x y 0 ) ( ( x 0 ) ( y 0 ) )

Il suffit donc de démontrer que la contraposée de cette implication est vraie. Pour établir celle-ci on utilise la première des lois de De Morgan. Il vient

( ( x = 0 ) ( y = 0 ) ) ( x y = 0 )

Or ceci est évident, car si un réel est nul, son produit par n'importe quel autre réel est nécessairement nul également.

La contraposée est donc vraie, ce qui prouve que l'implication initiale l'est également.


[Warning]

Il ne faut pas confondre contraposée et réciproque, la réciproque d'une implication P Q étant l'implication Q P .

D'ailleurs, une implication et sa réciproque n’ont pas nécessairement les mêmes valeurs de vérité. Par exemple pour un réel x, l'implication ( x [ 0 ; 2 ] ) ( x 2 [ 0 ; 4 ] ) est vraie mais sa réciproque ( x 2 [ 0 ; 4 ] ) ( x [ 0 ; 2 ] ) est fausse.

C’est bien sûr quand une implication et sa réciproque ont les mêmes valeurs de vérité qu’il y a équivalence.

Preuve par l’absurde

Le raisonnement par l’absurde consiste à démontrer la véracité d'une proposition P en supposant qu’elle est fausse, et par une suite de déductions logiques à aboutir à une absurdité. Ainsi P ne peut être fausse et est donc vraie.

Formalisons cela.

Raisonnement par l’absurde

Pour démontrer qu'une proposition P est vraie il suffit de démontrer que ¬P est fausse. Pour cela on suppose que ¬P est vraie et on prouve que cela est absurde.

Démonstration de la validité du raisonnement par l'absurde

Il s'agit d'une simple application du principe du tiers exclu, si ¬P est fausse alors nécessairement P est vraie.

Mettons en oeuvre cette méthode sur un exemple.

Example 1.11. Une preuve par l'absurde

Démontrons par l’absurde que

x , ( x 0 ) ( 1 x 0 )

Supposons donc que cette proposition est fausse c’est-à-dire que sa négation est vraie

x , ( x 0 ) ( 1 x = 0 )

Or si l'on multiplie cette dernière égalité par x, on obtient 1 = 0 (puisque x est différent de 0). Ce qui est absurde.

La négation de la proposition initiale est donc fausse, Q.E.D.


Preuve par disjonction de cas

Le raisonnement par disjonction de cas consiste à démontrer la véracité d'une proposition P en introduisant une autre proposition Q, et en prouvant que P Q et P ( ¬ Q ) sont toutes les deux vraies. On a ainsi disjoint les cas, ceux où la proposition Q est vraie et ceux où elle est fausse.

Formalisons cela.

Raisonnement par disjonction de cas

Pour démontrer qu'une proposition P est vraie, on montre que pour une autre proposition Q on a à la fois P Q et P ( ¬ Q ) de vraies.

[Note]

Il est clair qu'il faudra choisir judicieusement la proposition Q.

Démonstration de la validité du raisonnement par disjonction de cas

D'après la formule de distributivité de la conjonction par rapport à la disjonction, on a

( P Q ) ( P ( ¬ Q ) ) P ( Q ( ¬ Q ) )

Or le principe du tiers exclu stipule que Q ( ¬ Q ) est vraie. On a donc

P ( Q ( ¬ Q ) ) P

On en déduit que

( P Q ) ( P ( ¬ Q ) ) P

Q.E.D.

Appliquons cette méthode sur un exemple.

Example 1.12. Une preuve par disjonction de cas

Soit n un entier naturel, i.e. un élément de .

Démontrons par disjonction de cas la véracité de la proposition P : n × ( n + 1 ) est divisible par 2.

Pour cela, introduisons la proposition Q : n est pair.

Etudions alors les deux cas possibles :

  • Si n est pair, il est divisible par 2 et donc n × ( n + 1 ) aussi. Cela signifie que P Q est vraie.

  • Si n est impair, n + 1 est divisible par 2 et donc n × ( n + 1 ) aussi. Cela signifie que P ( ¬ Q ) est vraie.

On a à la fois P Q et P ( ¬ Q ) de vraies donc P est vraie.


[Note]

On retrouvera en particulier ce genre de raisonnement dans le cours d'arithmétique et cryptographie 1ARI.

Preuve par contre-exemple

Le raisonnement par contre-exemple consiste à démontrer qu'une généralité portant sur les éléments d'un ensemble est fausse en prouvant qu'au moins un élément de l'ensemble ne la vérifie pas. Il est donc très intuitif.

Formalisons cela.

Raisonnement par contre exemple

Soit E un ensemble quelconque et P ( x ) une proposition portant sur les éléments x de E.

Pour démontrer la fausseté de l'énoncé xE,P ( x ) , il suffit de démontrer que xE,¬P ( x ) .

Démonstration de la validité du raisonnement par contre-exemple

D'après la propriété vue dans la seconde partie de ce cours sur la négation d'une proposition avec un quantificateur, on a

¬ ( x , P ( x ) ) x , ¬ P ( x )

On applique alors le principe de non contradiction, si ¬ ( x , P ( x ) ) est vraie alors nécessairement xE,P ( x ) est faux.

Donnons au lecteur un petit exemple de ce type de preuve.

Example 1.13. Une preuve par contre-exemple

Montrons par contre-exemple la fausseté de l'énoncé x, x 2 > 0 .

Sa négation est x, x 2 0 , et il est facile de voir qu'elle est vraie en considérant x = 0 . Q.E.D.


A propos de SUPINFO | Contacts & adresses | Enseigner à SUPINFO | Presse | Conditions d'utilisation & Copyright | Respect de la vie privée | Investir
Logo de la société Cisco, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société IBM, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sun-Oracle, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Apple, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Sybase, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Novell, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Intel, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Accenture, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société SAP, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo de la société Prometric, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management Logo du IT Academy Program par Microsoft, partenaire pédagogique de SUPINFO, la Grande École de l'informatique, du numérique et du management

SUPINFO International University
Ecole d'Informatique - IT School
École Supérieure d'Informatique de Paris, leader en France
La Grande Ecole de l'informatique, du numérique et du management
Fondée en 1965, reconnue par l'État. Titre Bac+5 certifié au niveau I.
SUPINFO International University is globally operated by EDUCINVEST Belgium - Avenue Louise, 534 - 1050 Brussels