Théorie du module : Logique

Propositions

Définition - Une proposition est un énoncé simple susceptible d'être vrai ou faux.

Sont exclus des énoncés agrammaticaux, ainsi que les énoncés dénués de sens. Le sont également les énoncés exclamatifs comme "Ciel mon mari !", les énoncés interrogatifs comme "Quelle heure est-il ?", impératifs comme "Donne-moi la main.", de même que les énoncés auto-référentiels comme "Je mens.". Pour les premiers, la question qu'ils soient vrais ou faux n'a pas de sens, pour les derniers la question conduit à des paradoxes. C'est ainsi que "Cette phrase a cinq mots." est un énoncé vrai, mais l'énoncé contraire "Cette phrase n'a pas cinq mots." est également vrai.

Des énoncés affirmatifs comme "\(2 + 3 = 5\)", "Il pleut", "16 est le carré de 3",\(\ldots\) ont la propriété d'être soit vrais, soit faux mais jamais les deux à la fois. On les appelle des propositions. La valeur, vraie (V) ou fausse (F), d'une proposition sera appelée valeur de vérité de la proposition. On se permettra l'abus de langage de dire qu'une proposition est vraie pour "la valeur de vérité de la proposition est vraie".

Le caractère simple d'un énoncé tient à ce qu'il ne puisse pas se décomposer en plusieurs énoncés.

Par exemple la proposition "Pierre est philosophe et mathématicien" est composée des deux propositions "Pierre estphilosophe", "Pierre est mathématicien" reliées par un "et".

Définition - Une proposition composée est une proposition construite à partir de propositions simples reliées par des connecteurs logiques.

Par exemple, les propositions "Il fait beau et \(4 + 1 = 5\)", "S'il pleut alors je prendrai mon parapluie" et "Pierre est philosophe et mathématicien" sont des propositions composées.

Dans la suite on sera souvent amené a faire référence à des propositions sans les préciser. On les désignera alors par des symboles comme \(p , q , r,\ldots\)

 

Connecteurs logiques

L'opération qui consiste à relier les propositions "Pierre est philosophe" et "Pierre est mathématicien" par la conjonction "et" pour obtenir la proposition composée "Pierre est philosophe et mathématicien" est une opération logique binaire dont l'opérateur logique est la conjonction "et". On parle d'opération binaire parce qu'elle porte sur deux opérandes. On considère également une opération logique unaire qui porte sur un opérande. On utilisera une notation des opérations logiques semblable à la notation habituelle des opérations algébriques sur des nombres. D'autres notations sont possibles.

Chaque opération est décrite complètement si on donne la valeur de vérité du résultat pour toutes les combinaisons possibles de valeurs de vérité des opérandes. Une table reprenant les différentes combinaisons de valeurs de vérité des opérandes, à raison d'une par ligne, et dans une colonne le résultat correspondant est une présentation commode de l'opération. C'est la table de vérité de l'opération. Elle présente deux lignes dans le cas d'une opération unaire, 4 dans le cas d'une opération binaire.

(a) Négation d'une proposition: \(\neg p\)

La négation d'une proposition \(p\) est une proposition prenant la valeur de vérité opposée à celle de \(p\). On dira "non \(p\)" et on écrira \(\neg p\). Si \(p\) représente la proposition "vous savez", \(\neg p\) représente "non (vous savez)", ou encore "vous ne savez pas" ou "vous ignorez".

Les valeurs de vérité de \(\neg p\) en fonction de celles de \(p\) sont représentées dans la table de vérité ci-dessous.

\(\begin{array}{|c|c|} \hline p&\neg p \\ \hline V&F \\ F&V \\ \hline \end{array}\)

On vérifie que la négation de la négation d'une proposition est cette proposition elle-même. On en retiendra que dans le langage courant, un nombre impair de négations équivaut à une négation.

(b) Conjonction de deux propositions : \(p \wedge q\)

Deux propositions reliées par le mot "et" forment une proposition composée appelée la conjonction des deux propositions. On dira "\(p\) et \(q\)" et on écrira \(p \wedge q\).

Les valeurs de vérité de \(p \wedge q\) en fonction de celles de \(p\) et \(q\) sont données dans la table de vérité ci-dessous.

\(\begin{array}{|c|c|c|} \hline p&q& p \wedge q \\ \hline V&V&V \\ V&F&F \\ F&V&F \\ F&F&F \\ \hline \end{array}\)

On observe que \(p \wedge q\) n'est vraie que lorsque les deux propositions sont vraies, autrement dit il suffit que l'une des deux propositions soit fausse pour que leur conjonction soit fausse. Cette opération est commutative.

Remarque : La forme du symbole \(\wedge\) rappelle celle du symbole \(\cap\) qui désigne l'intersection. Ceci n'est pas un hasard : \(x\in A\cap B\) signifique que \(x\in A\) et \(x\in B\).

(c) Disjonction de deux propositions : \(p \vee q\)

Deux propositions reliées par le mot "ou" (au sens non exclusif du langage courant, c'est-à-dire au sens et/ou), forment une proposition composée appelée la disjonction des deux propositions. On dira "\(p\) ou \(q\)" et on écrira \(p \vee q\).

Les valeurs de vérité de \(p \vee q\) sont données dans la table ci-dessous.

\(\begin{array}{|c|c|c|} \hline p&q& p \vee q \\ \hline V&V&V \\ V&F&V \\ F&V&V \\ F&F&F \\ \hline \end{array}\)

On observe que \(p \vee q\) n'est fausse que lorsque les deux propositions le sont, autrement dit il suffit que l'une des deux propositions soit vraie pour que leur disjonction soit vraie. La disjonction est une opération commutative.

Remarque : Le "ou" des mathématiciens est un "ou" inclusif : \(p \vee q\) sera vraie lorsque \(p\) et \(q\) sont vraies toutes les deux. Dans le langage courant le "ou" est ambigu. Quand on dit "Pierre boit un coca ou regarde la télévision", on n'exclut pas la situation où "Pierre boit un coca et regarde la télévision". Par contre quand on lit "fromage ou dessert" dans le menu d'un restaurant, on sait que c'est soit l'un, soit l'autre, mais pas les deux. Pour éviter toute ambiguïté on devrait dire "soit\(\ldots\), soit\(\ldots\)".

Remarque : La forme du symbole \(\vee\) rappelle celle du symbole \(\cup\) qui désigne l'union. Ceci n'est pas un hasard : \(x\in A\cup B\) signifique que \(x\in A\) ou \(x\in B\).

(d) Proposition conditionnelle : \(p \Rightarrow q\)

La proposition \(p \Rightarrow q\) se lit "si \(p\) alors \(q\)", ou "\(p\) implique \(q\)", ou "il suffit que \(p\) pour que \(q\)", ou "\(p\) est une condition suffisante pour \(q\)". Dans \(p\Rightarrow q\), \(p\) est l'antécédent de l'implication et \(q\) le conséquent de l'implication.

On peut envisager une série de situations correspondant à un énoncé "si \(\dots\) alors \(\dots\)":

  • pour indiquer une relation logique où le conséquent découle logiquement de l'antécédent :
    "Si \(\neg(\neg p)\) a la même valeur de vérité que \(p\) alors \(p\) peut remplacer \(\neg(\neg p)\)",
  • pour indiquer une relation causale :
    "Si Pierre lache ce caillou alors il va tomber sur mon pied",
  • pour indiquer qu'une certaine décision est prise par celui qui prononce la phrase si l'antécédent est vrai :
    "Si Pierre lache le caillou alors je lui flanque mon poing à la figure",
  • pour signifier une implication définitionnelle. Le conséquent résulte de l'antécédent de par la définition de ce dernier (résulte d'une relation définitionnelle entre antécédent et conséquent) :
    "Si Pierre conduit une Golf, alors Pierre conduit une voiture",
  • pour signifier l'implication purement matérielle sans qu'il y ait relation logique, causale ou définitionnelle entre antécédent et conséquent; on utilise une telle expression pour manifester son point de vue de manière sarcastique:
    "Si Pierre a 20/20 au test de mathématiques alors je chante comme la Callas".
    Le conséquent est manifestement faux, l'orateur veut ainsi insister sur le caractère faux de l'antécédent.

Les valeurs de vérité de \(p\Rightarrow q\) sont données dans la table de vérité ci-dessous.

\(\begin{array}{|c|c|c|} \hline p&q&p \Rightarrow q \\ \hline V&V&V \\ V&F&F \\ F&V&V \\ F&F&V\\ \hline \end{array}\)

On observe que \(p\Rightarrow q\) est fausse seulement dans le cas où \(p\) est vraie et \(q\) fausse. Pour vérifier que \(p\Rightarrow q\) est vraie, il suffira donc d'envisager le cas où \(p\) est vraie et de vérifier que \(q\) l'est aussi.

(e) Proposition biconditionnelle : \(p \Leftrightarrow q\)

La proposition \(p \Leftrightarrow q\), obtenue par l'opération logique appelée equivalence ou bi-implication, peut se formuler comme: "\(p\) si et seulement si \(q\)", ou "\(q\) si et seulement si \(p\)", ou "\(p\) est équivalent à \(q\)", ou "\(p\) est une condition nécessaire et suffisante pour \(q\)", ou "si \(p\) alors \(q\) et réciproquement".En écrivant \(p \Leftrightarrow q\) on met \(p\) et \(q\) mutuellement sous condition. Les valeurs de vérité de cette proposition sont données dans la table de vérité ci-dessous.

\(\begin{array}{|c|c|c|} \hline p&q&p \Leftrightarrow q \\ \hline V&V&V \\ V&F&F \\ F&V&F \\ F&F&V\\ \hline \end{array}\)

On observe que \(p \Leftrightarrow q\) est vraie seulement dans le cas où \(p\) et \(q\) ont la même valeur de vérité.

Tautologie ou loi logique

Définition - Une tautologie (ou loi logique) est une proposition composée qui est vraie quelles que soient les valeurs de vérité des propositions simples qui la composent.

Pour démontrer qu'une proposition composée est une tautologie, on construit sa table de vérité et on constate que la dernière colonne est formée uniquement de \(V\).

Par exemple, les propositions

\(\begin{array}{c} \neg(\neg p)\Leftrightarrow p\\ \neg (p\wedge\neg p) \\ (p\wedge q)\Leftrightarrow(q\wedge p) \\ (p\vee q)\Leftrightarrow(q\vee p) \end{array} \)

sont des tautologies.  Si vous êtes intéressé, vous pouvez regarder la preuve ici.

La proposition \(((P\wedge Q)\, \vee\, R)\Leftrightarrow(P\wedge(Q\, \vee\, R))\) n'est pas une tautologie car quand on regarde les tables de vérité, on remarque que la dernière colonne n'est pas composée uniquement de \(V\). Cette affirmation est donc vraie ou fausse selon les valeurs de vérité des différentes propositions qui la composent.

\(\begin{array}{|c|c|c|c|c|c|c|c|} \hline P & Q &R&P\wedge Q&(P\wedge Q)\vee R&Q\vee R&P\wedge(Q\vee R)&((P\wedge Q)\vee R)\\ &&&&&&&\Leftrightarrow(P\wedge(Q\vee R))\\ \hline V&V&V&V&V&V&V&V\\ V&V&F&V&V&V&V&V\\ V&F&V&F&V&V&V&V\\ V&F&F&F&F&F&F&V\\ F&V&V&F&V&V&F&F\\ F&V&F&F&F&V&F&V\\ F&F&V&F&V&V&F&F\\ F&F&F&F&F&F&F&V\\ \hline \end{array}\)

 

Quantificateurs logiques

Les connecteurs logiques ne sont pas les seuls "petits mots" importants dans les textes mathématiques : il ne faut pas oublier les quantificateurs "\(\forall\)" et "\(\exists\)".

(a) Quantificateurs universel et existentiel

"\(\forall\)" est le quantificateur universel qui signifie "pour tout", tandis que "\(\exists\)" est le quantificateur existentiel qui signifie "il existe (au moins un)".

Par exemple, la formule

\(\forall x\, :\, x+1>0\)

signifie que pour tout objet \(x\), on a \(x+1>0\), ou encore que quelle que soit la valeur prise par \(x\), on a \(x+1>0\). D'autre part, la formule

\(\exists\, x\, :\, x+30<15\)

signifie qu'il existe au moins une valeur de \(x\) telle que \(x+30<15\).

Pour pouvoir déterminer si ces formules sont vraies ou fausses, il faut fixer l'univers du discours, c'est-à-dire préciser quel est l'ensemble des valeurs possibles de la variable quantifiée. Ainsi, la formule

\(\exists\, x\, :\, x+30<15\)

est vraie si l'ensemble des valeurs permises pour \(x\) est \(\mathbb{R}\) ou \(\mathbb{Z}\), mais elle est fausse si cet ensemble est \(\mathbb{N}\).

(b) Ordre des quantificateurs

Lorsqu'on manipule des affirmations avec quantificateurs, il importe de veiller à ne pas permuter l'ordre des quantificateurs.

Par exemple, l'affirmation suivante signifie que tout nombre réel a un opposé :

\(\forall x\in\mathbb{R},\, \exists\, y\in\mathbb{R}\, :\, x+y=0.\)

Cette affirmation est bien vraie dans \(\mathbb{R}\) (il suffit que \(y=-x\); ces \(y\) diffèrent donc suivant \(x\)). Par contre l'affirmation

\(\exists\, y\in\mathbb{R},\, \forall x\in\mathbb{R}\, :\, x+y=0\)

est fausse. Elle signifie en effet qu'il existerait un nombre réel \(y\) qui serait un absorbant pour l'addition : ajouté à n'importe quel nombre réel \(x\), il donnerait toujours une somme égale à zéro. Un tel nombre réel \(y\) n'existe pas.

On peut cependant permuter l'ordre des quantificateurs si ceux-ci sont identiques et l'un à côté de l'autre.

Par exemple, l'affirmation

\(\forall n\in\mathbb{N},\, \forall m\in\mathbb{N}\, :\, n\neq 0\Rightarrow n+m>m\)

est équivalente à l'affirmation

\(\forall m\in\mathbb{N},\, \forall n\in\mathbb{N}\, :\, n\neq 0\Rightarrow n+m>m.\)

(c) Négation des quantificateurs

La négation du quantificateur universel est le quantificateur existentiel et la négation du quantificateur existentiel est le quantificateur universel. Ainsi, pour nier une proposition contenant des quantificateurs, on nie les quantificateurs et on nie l'affirmation qui les suit :

la négation de "\(\exists\, x\, :\, P(x)\)" est "\(\forall x\, : \neg P(x)\)"
la négation de "\(\forall x\, :\, P(x)\)" est "\(\exists\, x\, : \neg P(x)\)"

Réciproque et contraposée

Dans les ouvrages mathématiques, on rencontre souvent les mots "réciproque" et "contraposée", qui sont en rapport avec l'implication.

La réciproque de (\(p\Rightarrow q\)) est (\(q\Rightarrow p\)). On renverse donc le sens de l'implication pour obtenir la réciproque. Un énoncé n'est pas équivalent à sa réciproque.

Par exemple l'implication

\(x\in \mathbb{N}\Rightarrow x\in \mathbb{R}\)

est vraie, mais sa réciproque

\(x\in \mathbb{R}\Rightarrow x\in \mathbb{N}\)

est fausse.

La réciproque de \(p\Rightarrow q\) n'est pas non plus équivalente à la négation de \(p\Rightarrow q\). Il suffit de comparer les tables de vérité de \(q\Rightarrow p\) et \(\neg(p\Rightarrow q)\) pour s'en convaincre. Si vous êtes intéressé, vous pouvez regarder les tables de vérité ici.

La contraposée de (\(p\Rightarrow q\)) est (\(\neg q\Rightarrow \neg p\)). On nie les affirmations \(p\) et \(q\) et on renverse le sens de l'implication pour obtenir la contraposée. Un énoncé est équivalent à sa contraposée.
Si vous êtes intéressé, vous pouvez regarder les tables de vérité ici.

Par exemple, l'affirmation

"S'il pleut alors je prends mon parapluie"

est équivalente à sa contraposée

"Si je ne prends pas mon parapluie, c'est qu'il ne pleut pas".

Théorèmes et méthodes de démonstration

Nous allons ici expliquer ce qu'est une démonstration ainsi que donner différents types de démonstration.

Démontrer consiste à déduire la vérité d'une affirmation mathématique, appelée la thèse, à partir d'un ensemble d'affirmations mathématiques que l'on suppose être vraies le temps de la démonstration (les hypothèses) et à partir d'un ensemble d'affirmations mathématiques qui sont vraies (des axiomes ou des théorèmes qui ont déjà été démontrés auparavant). Notons que les hypothèses sont en général écrites explicitement dans l'énoncé que l'on cherche à démontrer, ce qui n'est pas le cas des axiomes et des théorèmes que l'on aura à utiliser au cours de la démonstration.

Il est important de bien comprendre que la démonstration d'un théorème sert uniquement à prouver que sa thèse est vraie lorsque ses hypothèses sont vraies. Lorsqu'on voudra utiliser un théorème, il faudra donc toujours commencer par vérifier que ses hypothèses sont bien satisfaites.

Remarque :Puisque l'énoncé "\(\neg(\forall x\, :\, P(x))\)" est équivalent à l'énoncé "\(\exists\, x\, :\, \neg P(x)\)", pour prouver qu'une propriété n'est pas vraie pour toutes les valeurs de \(x\), il suffit de trouver une valeur de \(x\) pour laquelle la propriété n'est pas satisfaite. Une telle valeur est appelée un contre-exemple.

Les hypothèses et thèse d'un théorème sont en général composées de plusieurs propositions \(p\), \(q\), \(r,\ldots\). Pour simplifier la présentation, nous écrirons \(P\) et \(Q\) au lieu de \(P(p, q, r,\ldots) \) et \(Q(p, q, r,\ldots) \).

Méthodes de démonstration de \(P\Rightarrow Q\)

Si on appelle théorème l'affirmation \(P\Rightarrow Q\), où \(P\) sont les hypothèses et \(Q\) les conclusions, démontrer le théorème \(P\Rightarrow Q\) revient à tester la validité de l'affirmation. Voici différentes manières de procéder.

  • Démonstration directe (modus ponens) :

Il faut montrer que \(P\Rightarrow Q\) est une tautologie donc, d'après la définition de l'opérateur logique \(\Rightarrow\), il convient de montrer que si \(P\) est vraie, alors \(Q\) est aussi vraie.

Par exemple, voyons que tout nombre naturel qui est un carré a un nombre impair de diviseurs. Soit

\(P\) : \(x\) est un nombre naturel qui est un carré.
\(Q\) : \(x\) a un nombre impair de diviseurs.

Preuve directe :
Le nombre \(x\) admet trivialement comme diviseurs \(1\) et lui-même \(x\). Comme \(x=y^2\) il admet \(y\) comme diviseur. Ce qui en fait déjà trois \(1\), \(y\) et \(x\). Pour tout autre nombre \(a\) (différent de \(1\), \(y\) et \(x\)), diviseur de \(x\), il doit y avoir un nombre \(b\) tel que \(x=a\cdot b\) Le nombre \(b\) est également diviseur de \(x\) et doit également être différent de \(1\), \(y\), \(x\) et \(a\). Donc s'il y a d'autres diviseurs que \(1\), \(y\) et \(x\), ils doivent être différents et exister par paires. Le nombre total de diviseurs est dès lors impair.

  • Démonstration par l'absurde (contradiction) :

Le principe de démonstration par l'absurde s'énonce de la manière suivante :

Principe de démonstration par l’absurde
Pour démontrer une affirmation \(P\) par l'absurde,
on suppose que \(\neg P\) est vraie (c'est-à-dire que \(P\) est fausse)
et on en déduit une absurdité.

 

Intuitivement, on comprend que si l'on déduit une absurdité de l'hypothèse \(\neg P\), c'est que cette hypothèse est fausse, ce qui revient à dire que \(P\) est vraie.

Reprenons l'exemple précédent. On va supposer que \(P\) est vraie et que \(Q\) est fausse et montrer que cela ne peut pas se produire.

Preuve par l'absurde :
Supposons que le nombre \(x\) est un carré et \(x\) possède \(2k\) diviseurs. Soit \(y\) tel que \(x=y\cdot y\). Enlevons \(1\), \(x\) et \(y\). Il reste un nombre impair de diviseurs. Formons parmi ceux-ci les couples \(z_1\), \(z_2\) de nombres différents tels que \(x=z_1\cdot z_2\). Cela en fait un nombre pair, il doit donc en rester un. Soit \(a\) ce nombre, comme il n'est pas \(1\), \(y\) ou \(x\), il doit alors vérifier \(x=a\cdot a\), ce qui est absurde car \(a\not= y\).

  • Démonstration par contraposée :

Grâce à l'équivalence entre un énoncé et sa contraposée, démontrer \(P \Rightarrow Q\) revient à démontrer\(\neg Q \Rightarrow \neg P\).

Principe de démonstration par contraposée
Pour démontrer une affirmation de la forme \(P\Rightarrow Q\) par contraposition,
on démontre la contraposée \(\neg Q\Rightarrow\neg P\),
c'est-à-dire : on suppose que \(Q\) est fausse et on en déduit que \(P\) est fausse.

 

Dans l'exemple ci-dessus, \(\neg Q\Rightarrow\neg P\) revient à "\(x\) possède un nombre pair de diviseurs \(\Rightarrow\) \(x\) n'est pas un carré".

Preuve par contraposition :
On doit pouvoir regrouper les diviseurs par paires de nombres différents \(y,z\) tels que \(x=y\cdot z\). Il ne peut donc pas rester un nombre unique \(a\), tel que \(x=a\cdot a\). Le nombre \(x\) n'est donc pas un carré.

Méthode de démonstration de \(P \Leftrightarrow Q\)

Une affirmation de la forme \(P \Leftrightarrow Q\) est équivalente à \((P\Rightarrow Q)\wedge (Q\Rightarrow P)\). Pour prouver \(P \Leftrightarrow Q\), il suffit donc de prouver \(P\Rightarrow Q\) et de prouver \(Q\Rightarrow P\).

Méthode de démonstration par récurrence (ou par induction)

On utilise le principe de démonstration par récurrence lorsqu'on veut prouver qu'une propriété est vraie pour tous les nombres naturels. Le principe est le suivant :

 

Principe de démonstration par récurrence
Pour prouver qu'une affirmation de la forme "\(\forall n\in\mathbb{N}\, :\, P(n)\)" est vraie, il suffit de prouver que
  • "\(P(0)\)" est vraie,
  • "\(\forall k\in \mathbb{N}\, :\, P(k)\Rightarrow P(k+1)\)" est vraie.

 

Par exemple, on veut prouver que pour tout \(n\in \mathbb{N}\), on a

\(0^3+1^3+2^3+\cdots +n^3=\displaystyle\frac{n^2(n+1)^2}{4}\)

Preuve par récurrence :

  • \(P(0)\) est l'affirmation

    \(0^3=\displaystyle\frac{0^2(0+1)^2}{4}.\)

    Cette affirmation est clairement vraie.
  • Supposons que \(P(k)\) soit vraie pour un certain \(k\in \mathbb{N}\), c'est-à-dire supposons que

    \(0^3+1^3+2^3+\cdots +k^3=\displaystyle\frac{k^2(k+1)^2}{4}\)

    (ceci est l'hypothèse de récurrence) et voyons que \(P(k+1)\) est encore vraie.
    On a par hypothèse de récurrence

    \(0^3+1^3+2^3+\cdots+k^3+(k+1)^3=\displaystyle\frac{k^2(k+1)^2}{4}+(k+1)^3.\)

    De plus,

    \(\begin{array}{rl} \displaystyle\frac{k^2(k+1)^2}{4}+(k+1)^3&=\displaystyle\frac{k^2(k+1)^2}{4}+\frac{4}{4}(k+1)(k+1)^2,\\ &=\displaystyle\frac{(k+1)^2}{4}(k^2+4(k+1)),\\ &=\displaystyle\frac{(k+1)^2}{4}(k+2)^2 \end{array}\)

    et on obtient

    \(0^3+1^3+2^3+\cdots+k^3+(k+1)^3=\displaystyle\frac{(k+1)^2((k+1)+1)^2}{4},\)

ce qui est exactement \(P(k+1)\). Puisque l'affirmation est vraie pour le premier entier et que si elle est vraie pour un entier quelconque, elle l'est aussi pour le suivant, on peut donc en conclure qu'elle est vraie pour tous les entiers.

Remarque : Si l'on veut prouver que l'énoncé "\(\forall n\geq c\, :\, P(n)\)" est vrai, il suffit de prouver que "\(P(c)\)" est vraie et que "\(\forall k\geq c\,:\, P(k)\Rightarrow P(k+1)\)" est vraie. De même, si l'on veut prouver qu'une propriété \(P\) est satisfaite par tous les nombres naturels pairs, il suffit de montrer que "\(P(0)\)" est vraie et que "\(\forall k\in\mathbb{N}\, :\, P(k)\Rightarrow P(k+2)\)" est vraie.

Exemples détaillés

  1. Traduire en mathématique l'énoncé "Tout nombre réel est majoré par un entier".
    Solution détaillée : Cela signifie que pour chaque nombre réel, on peut trouver un entier qui est plus grand que lui. Mathématiquement, on écrira

    \(\forall x\in \mathbb{R},\exists\, z\in \mathbb{Z}\, :\, x\leq z.\)

     

  2. Traduire en français l'énoncé \(\forall x,\forall A,\forall B\, :\, x\in (A\cap B)\Rightarrow x\in (A\cup B)\).
    Solution détaillée : Quels que soient les ensembles \(A\) et \(B\) que l'on considère, tout élément \(x\) qui se trouve dans \(A\cap B\) se trouve aussi dans \(A\cup B\). Tout élément de l'intersection de deux ensembles se trouve donc aussi dans leur union. On peut encore dire "l'intersection de deux ensembles est contenue dans leur union".
  3. Niez la phrase suivante "Dans tout pays, il y a une ville où les maisons qui sont à moins de 100 mètres du centre ont au moins un étage".
    Solution détaillée :La négation de "dans tout pays" est "il existe au moins un pays", la négation de "il y a une ville où les maisons qui sont à moins de 100 mètres du centre ont au moins un étage" est "toutes les villes où il y a au moins une maison qui est à moins de 100 mètres du centre et n'a pas au moins un étage". La négation demandée est donc "Il existe un pays où toutes les villes ont au moins une maison de plain-pied à moins de 100 mètres du centre".
  4. Montrez que pour tout \(n\in\mathbb{N}_0\),

    \(\displaystyle\sum_{i=1}^n i^2=\frac{n(n+1)(2n+1)}{6}.\)

    Solution détaillée : On va prouver cette affirmation par récurrence. Il faut montrer que pour tout \(n\in\mathbb{N}_0\), on a

    \(1^2+2^2+3^2+\cdots +n^2=\dfrac{n(n+1)(2n+1)}{6}.\)

    Puisqu'il faut prouver l'affirmation pour tout \(n\in\mathbb{N}_0\), on va commencer par la prouver pour \(n=1\).
    • \(P(1)\) est l'affirmation

      \(1^2=\dfrac{1\cdot 2\cdot 3}{6}.\)

      Cette affirmation est clairement vraie.
    • Soit \(k\in\mathbb{N}_0\), un entier quelconque et supposons que \(P(k)\) est vraie, c'est-à-dire supposons que

      \(1^2+2^2+3^2+\cdots +k^2=\dfrac{k(k+1)(2k+1)}{6}\)

      Voyons que \(P(k+1)\) est vraie. On a

      \(1^2+2^2+3^2+\cdots +(k+1)^2=(1^2+2^2+3^2+\cdots +k^2)+(k+1)^2\)

      et par hypothèse de récurrence, on peut écrire

      \((1^2+2^2+3^2+\cdots +k^2)+(k+1)^2=\dfrac{k(k+1)(2k+1)}{6}+(k+1)^2.\)

      De plus,

      \(\begin{array}{rcl} \dfrac{k(k+1)(2k+1)}{6}+(k+1)^2&= &\dfrac{k(k+1)(2k+1)+6(k+1)^2}{6}, \\ & = & \dfrac{(k+1)(2k^2+k+6k+6)}{6}, \\ &= &\dfrac{(k+1)(2k^2+7k+6)}{6}, \\ & = & \dfrac{(k+1)(k+2)(2k+3)}{6} . \end{array} \)

      On obtient ainsi

      \((1^2+2^2+3^2+\cdots +k^2)+(k+1)^2=\dfrac{(k+1)((k+1)+1)(2(k+1)+1)}{6},\)

      ce qui est exactement \(P(k+1)\).
    Par le principe de récurrence, on a bien prouvé l'affirmation pour tout \(n\in\mathbb{N}_0\).
  5. Démontrez que \(\sqrt{2}\not\in\mathbb{Q}\).
    Solution détaillée : On va faire une démonstration par l'absurde.
    Supposons que \(\sqrt{2}\in\mathbb{Q}\). Il existe donc \(p\in \mathbb{Z}\) et \(q\in\mathbb{Z}_0\) tels que \(\frac{p}{q}=\sqrt{2}\) avec \(p\) et \(q\) premiers entre eux.
    En élevant les deux membres au carré, on obtient \(\frac{p^2}{q^2}=2\), c'est-à-dire \(p^2=2q^2\). On en déduit que \(p^2\) est pair et donc \(p\) est pair. Puisque \(p\) et \(q\) sont premiers entre eux, cela signifie que \(q\) est impair.
    De plus, si \(p\) est pair, alors \(p^2\) est multiple de \(4\) et, q étant impair, il est impossible que \(2q^2\) soit un multiple de \(4\). On ne peut donc pas avoir \(p^2=2q^2\), c'est-à-dire qu'il est impossible que \(\sqrt{2}\) s'écrive sous la forme d'une fraction. Donc \(\sqrt{2}\not\in\mathbb{Q}\).
    1. Montrez, en utilisant les tables de vérité, que les deux propositions \(\neg (\neg p\vee q)\) et \((p\wedge\neg q)\) sont logiquement équivalentes.
    2. Formez la négation de la phrase "Les étudiants ne guindaillent pas ou ratent" en la transformant d'abord sous forme de propositions, ensuite appliquez les règles de la négation et la traduire à nouveau en phrase ordinaire.
    Solution détaillée :
    1. Les propositions \(\neg (\neg p\vee q)\) et \((p\wedge\neg q)\) sont logiquement équivalentes.

      \(\begin{array}{|c|c|c|c|c|c|c|} \hline p&q&\neg p&\neg q&\neg p \vee q&\neg (\neg p \vee q)&p \wedge \neg q \\ \hline V&V&F&F&V&F&F \\ V&F&F&V&F&V&V \\ F&V&V&F&V&F&F \\ F&F&V&V&V&F&F \\ \hline \end{array}\)

      Les deux dernières colonnes sont identiques, ce qui signifie que les deux propositions sont logiquement équivalentes.
    2. La phrase "Les étudiants ne guindaillent pas ou ratent" est constituée des propositions
      \(p\) : Les étudiants guindaillent.
      \(q\) : Les étudiants ratent.
      En utilisant \(p\) et \(q\), la phrase peut s'écrire sous forme \(\neg p\vee q\).
      On a vu au point ci-dessus que la négation de\((\neg p\vee q)\) est \((p\wedge\neg q)\). La négation de la phrase est donc "Les étudiants guindaillent et ne ratent pas".

     

    1. Montrez, en utilisant les tables de vérité, que les deux propositions \((p\Rightarrow\neg q)\) et \(\neg(p\wedge q)\) sont logiquement équivalentes.
    2. Formez la négation de la phrase "Il y a des contraintes en architecture et de la liberté en mathématiques" en la transformant d'abord sous forme de propositions, ensuite appliquez les règles de la négation et la traduire à nouveau en phrase ordinaire.
    Solution détaillée :
    1. Les propositions \((p\Rightarrow\neg q)\) et \(\neg(p\wedge q)\) sont logiquement équivalentes.

      \(\begin{array}{|c|c|c|c|c|c|} \hline p & q & \neg q&p\wedge q&\neg(p\wedge q)&p\Rightarrow\neg q \\ \hline V&V&F&V&F&F\\ V&F&V&F&V&V\\ F&V&F&F&V&V\\ F&F&V&F&V&V\\ \hline \end{array}\)

      Les deux dernières colonnes sont identiques, ce qui signifie que les deux propositions sont logiquement équivalentes.
    2. La phrase "Il y a des contraintes en architecture et de la liberté en mathématiques" est constituée des propositions
      \(p\) : Il y a des contraintes en architecture.
      \(q\) : Il y a de la liberté en mathématiques.
      En utilisant \(p\) et \(q\), la phrase peut s'écrire sous forme \(p\wedge q\).
      On a vu au point ci-dessus que la négation de \(p\wedge q\) est \((p\Rightarrow\neg q)\). La négation de la phrase est donc "S'il y a des contraintes en architecture alors il n'y a pas de liberté en mathématiques".

     

  6. La proposition \(((p\Rightarrow q)\wedge (\neg p\Rightarrow q))\Rightarrow q\) est-elle une tautologie ?
    Solution détaillée : Oui car quand on regarde les tables de vérité, on remarque que la dernière colonne est composée uniquement de V. Cette affirmation est donc toujours vraie, quelles que soient les valeurs de vérité des différentes propositions qui la composent.

    \(\begin{array}{|c|c|c|c|c|c|c|} \hline p & q & \neg p&p\Rightarrow q&\neg p\Rightarrow q&(p\Rightarrow q)\wedge (\neg p\Rightarrow q)&((p\Rightarrow q)\wedge (\neg p\Rightarrow q))\Rightarrow q \\ \hline V&V&F&V&V&V&V\\ V&F&F&F&V&F&V\\ F&V&V&V&V&V&V\\ F&F&V&V&F&F&V\\ \hline \end{array}\)

  7. Donnez la réciproque et la contraposée de la proposition "\(x\in\mathbb{N}\Rightarrow x\geq 0\)".
    Solution détaillée :Pour trouver la réciproque d'une implication, on renverse le sens de la flèche. La réciproque est donc

    \(x\geq 0\Rightarrow x\in\mathbb{N}.\)

     

    Pour trouver la contraposée d'une implication, on nie les deux propositions qui la composent, puis on renverse le sens de la flèche. La négation de "\(x\in \mathbb{N}\) " est "\(x\not\in\mathbb{N}\)" et la négation de "\(x\geq 0\)" est "\(x<0\)". La contraposée demandée est donc

    \(x<0\Rightarrow x\not\in\mathbb{N}.\)

     

Preuves

Les propositions

\(\begin{array}{c} \neg(\neg p)\Leftrightarrow p\\ \neg (p\wedge\neg p) \\ (p\wedge q)\Leftrightarrow(q\wedge p) \\ (p\vee q)\Leftrightarrow(q\vee p)\end{array} \)

sont des tautologies.

On remarque que la colonne correspondante dans les tables de vérité est constituée uniquement de \(V\) :

\(\begin{array}{|c|c|c|c|c|c|} \hline p & \neg p & \neg (\neg p)&\neg (\neg p)\Leftrightarrow p&p\wedge\neg p&\neg (p\wedge\neg p) \\ \hline V&F&V&V&F&V\\ F&V&F&V&F&V\\ \hline \end{array}\)

 

\(\begin{array}{|c|c|c|c|c|} \hline p & q & p\wedge q&q\wedge p&(p\wedge q)\Leftrightarrow(q\wedge p)\\ \hline V&V&V&V&V\\ V&F&F&F&V\\ F&V&F&F&V\\ F&F&F&F&V\\ \hline \end{array}\)

 

\(\begin{array}{|c|c|c|c|c|} \hline p & q & p\vee q&q \vee p&(p\vee q)\Leftrightarrow(q \vee p)\\ \hline V&V&V&V&V\\ V&F&V&V&V\\ F&V&V&V&V\\ F&F&F&F&V\\ \hline \end{array}\)

 

La proposition \((q\Rightarrow p)\) n'est pas équivalente à \((p\Rightarrow q)\) ni à la négation de \((p\Rightarrow q)\).

On remarque que les colonnes correspondantes dans les tables de vérité n'ont pas les mêmes valeurs de vérité :

\(\begin{array}{|c|c|c|c|c|} \hline p & q & p\Rightarrow q&q\Rightarrow p& \neg(p\Rightarrow q) \\ \hline V&V&V&V&F\\ V&F&F&V&V\\ F&V&V&F&F\\ F&F&V&V&F\\ \hline \end{array}\)

 

 

Un énoncé est équivalent à sa contraposée.

Soit \(p\Rightarrow q\) un énoncé et \(\neg q\Rightarrow\neg p\) sa contraposée. On remarque que les colonnes correspondantes dans les tables de vérité sont identiques :

\(\begin{array}{|c|c|c|c|c|c|} \hline p & q & p\Rightarrow q&\neg p&\neg q&\neg q\Rightarrow \neg p \\ \hline V&V&V&F&F&V\\ V&F&F&F&V&F\\ F&V&V&V&F&V\\ F&F&V&V&V&V\\ \hline \end{array}\)

 

 

Théorie