sigmaths
avatar

Eléments de logique mathématiques


Eléments de logique mathématique
Elaboré par l’inspecteur : Mohamed Okbi AMRI
logique mathématiques
1/ Notions préliminaires :
Une assertion ou proposition logique ou tout simplement proposition est un énoncé dont on peut dire, sans ambiguïté, qu’il est vrai ou faux.
Soit P une assertion, deux issues seulement sont possibles : vrai ou faux. La table de vérité de P est :$\left\{{\begin{aligned}&{V}\\&{F}\end{aligned}}\right.$
Exemples:
  • L’énoncé « 2 < 5 » est une assertion vraie. L’énoncé « $\sqrt 2$ est un nombre rationnel » est une assertion fausse.
  • L’énoncé «$ cos⁡(nπ)=(-1)^n $» est une assertion vraie.
  • L’énoncé « la fonction f:R+→R,$x\longmapsto \sqrt{x}$ est dérivable à droite en 0 » est une assertion fausse.
Certains énoncés dépendent de variables $x_1,x_2,…,x_n$, et qui sont vrais pour certaines valeurs prises pour ces variables, faux pour d’autres. On les appelle des prédicats ou propositions fonctionnelles .
Exemples :
  • L’énoncé « $x\geqslant 3$ » est vrai pour les réels supérieurs ou égaux à 3, faux pour les autres ; c’est un prédicat.
  • L’énoncé « la hauteur du triangle T est médiane du triangle T » est vrai pour tous les triangles isocèles, faux dans tous les autres cas ; c’est un prédicat.
Il y a les énoncés qui se démontrent. Pour ce faire, on se donne des règles précises qui permettent de construire de nouvelles assertions à partir d’assertions données.
Il ne faut pas croire que dans une théorie donnée toute assertion P soit obligatoirement démontrable. À la base de toute théorie mathématique, on dispose d’un petit nombre d’assertions qui sont supposées vraies à priori et que l’on nomme axiomes ou postulats. Ces axiomes sont élaborés par abstraction à partir de l’intuition et ne sont pas déduits d’autres relations.
La notion de définition nous permet de décrire un objet ou une situation précise à l’aide du langage courant.
Les énoncés qui se démontrent sont classés en fonction de leur importance dans une théorie comme suit :
  • Un théorème est une assertion vraie déduite d’autres assertions, il s’agit en général d’un résultat important à retenir ;
  • Un lemme est un résultat préliminaire utilisé pour démontrer un théorème ;
  • Un corollaire est une conséquence importante d’un théorème.
Les axiomes et les théorèmes portent sur des objets mathématiques : nombres, figures, fonctions, ensembles, etc.
Les problèmes qui se posent au mathématicien sont, en gros, de deux sortes : trouver et démontrer.
Les données sont les objets sur lesquels porte le problème (telle fonction, une configuration, etc).
Les hypothèses sont les suppositions que l’on fait à propos des données (par exemple, que le triangle est rectangle). Au cours de la démonstration on ne doit faire appel qu’aux hypothèses du problème et aux connaissances acquises (définitions, théorèmes, axiomes).
2/ Les connecteurs logiques de base
L’élaboration de nouvelles assertions à partir d’autres se fait en utilisant les connecteurs logiques de négation, de conjonction, de disjonction, d’implication et d’équivalence. Dans ce qui suit, P et Q désignent des assertions.
  • Négation : la négation de P, notée $ non (P)$ ou $\overline P$, est l’assertion vraie, si P est fausse, et fausse, si P est vraie. La table de vérité de l’assertion $ non (P)$ est la suivante :
    $ \style{color:#00FB3F}{P} $ $ \style{color:#00FB3F}{\overline P}$
    V F
    FV
    On a bien évidemment $non(non(P))= \overline{\overline {P}}=P$ (l’égalité signifie que les deux assertions ont même table de vérité).
  • Conjonction : la conjonction de P et de Q , notée $\style{color: #00FB3F}{(P\;et\;Q)\; ou \; P\wedge Q}$ est la suivante :
    P Q PQ
    V V V
    F V F
    V F F
    F F F
    On a bien évidemment : (P et Q)=(Q et P).
    Deux assertions sont incompatibles si leur conjonction est toujours fausse. L’assertion $ (P\wedge \overline{P} )$ est toujours fausse (principe de non contradiction). C’est un cas particulier d’incompatibilité.
    Les assertions « ABC est un triangle rectangle » et « ABC est un triangle équilatéral » sont incompatibles.
    Les propositions « x≤2 » et « x>5 » sont incompatibles.
  • Disjonction : la disjonction de P et de Q, notée (P ou Q), ou P∨Q, est l’assertion fausse si P est fausse et Q fausse, vraie dans les autres cas. Remarquons qu’il s’agit d’un « ou » inclusif, c'est-à-dire que les propositions peuvent être vraies en même temps (contrairement au « ou » exclusif). La table de vérité de la proposition (P ou Q) est :
    P Q PQ
    V V V
    F V V
    V F V
    F F F
    On a bien évidemment : (P ou Q)=(Q ou P). L’assertion ($P \vee \overline P$ ) est toujours vraie (principe du tiers-exclu) ; c’est une tautologie.
  • Implication : l’assertion (P⟹Q) est définie par :
    P Q PQ
    V V V
    F V V
    V F F
    F F V
    L’implication est à la base du raisonnement mathématique. En partant d’une assertion P (ou de plusieurs), une démonstration aboutit à un résultat Q.
    Dans la pratique, pour montrer que :(P⟹Q) , on procède de la façon suivante : on suppose que P est vraie ; on doit alors montrer que Q est vraie. On dit : « pour que P soit vraie il faut que Q soit vraie » ou encore « pour que Q soit vraie il suffit que P soit vraie ». On dit aussi « P est une condition suffisante pour Q » ; « Q est une condition nécessaire pour P ».
    Pour prouver qu’une implication :(P⟹Q) est fausse, il suffit de prouver que l’on peut avoir simultanément P vraie et Q fausse.
    Exemple : l’implication $x^2>3\Longrightarrow x>\sqrt 3$ est fausse.
    Attention: la véracité de :(P⟹Q) n’a rien à voir avec celle de P , mais uniquement avec le fait que si P est vraie alors Q est vraie aussi. Par exemple : l’implication « (-1=1)⟹(0=2) est vraie.

    Remarques

    ★Le seul cas où (P⟹Q) est fausse, c’est lorsque P est vraie et Q fausse. Lorsque P est fausse, (P⟹Q) est donc toujours vraie, ce qui ne signifie pas que la proposition Q soit elle-même vraie.
    ★Si P et (P⟹Q) sont vraies, alors Q est vraie.
    ★En maths, on n’écrit que des affirmations vraies et on ne précise donc pas en général « est vraie ». Si la proposition P est fausse, on écrira « non(P) » (sous-entendu est vraie).
    Exercice
    Pour chacune des propositions suivantes, donner la valeur de vérité :
    • (xy=0) ⟹ (x=0 ou y=0).
    • (ABCD) est un rectangle ⟹ A*C=B*D
    • (x=10011) ⟹ x est écrit en base 2
    • ABC est un triangle isocèle ⟹ ABC est équilatéral
    • 4 est un nombre premier ⟹ (tunis est la capitale de la Tunisie)
    • 2 est un nombre impair ⟹ 6 est un nombre premier
    Réciproque, contraposée :
    • $(Q⟹P)$ est appelée la réciproque de $(P⟹Q)$.
    • $[(non Q)⟹(non P)]$ est appelée la contraposée de $(P⟹Q)$.
    Exercice
    Montre que les propositions $(P ⟹ Q)$ et $[non(P)\;ou\; Q]$ ont la même table de vérité. En déduire que les propositions $(P ⟹ Q)$ et $[non(Q) ⟹ non(P)]$ ont même table de vérité (raisonnement par contraposée)

    Remarque

    Une implication et sa contraposée sont vraies (ou fausses) en même temps. Ainsi, démontrer $(P ⟹ Q)$ revient au même que démontrer : $[non(Q) ⟹ non(P)]$, qui peut s’avérer plus facile.
    Exemple:
    Soit n ∈ ℤ; montrer que:
    n2 est pair ⟹ n est pair.

    Remarque

    une implication et sa réciproque n’ont pas nécessairement les mêmes valeurs de vérité.
    Exemple:
    x>2 ⟹ x2>4 est vraie ; mais x2>4 ⟹ x>2 est fausse.
  • Équivalence : l’équivalence $(P ⟺ Q)$ est définie par :
    P Q $P ⟺ Q$
    V V V
    F V F
    V F F
    F F V
    En pratique, on ne considère que la première ligne de cette table de vérité, c'est-à-dire que l’on traduit la proposition P ⟺ Q par : P est vraie si et seulement si Q est vraie, ou encore pour que P soit vraie il faut et il suffit que Q soit vraie. On dit que P (resp.Q) est une condition nécessaire et suffisante pour Q (resp. pour P).
    Exemple
    soit a et b deux réels ; montrer que : |a+b|=|a|+|b| ⟺ ab≥0.

    Remarque

    deux propositions qui ont la même table de vérité sont équivalentes.
    Théorème 1
    Soient P,Q,R des propositions. On a les équivalences :
    • Commutativité :
      (P ∧ Q) ⟺ (Q ∧ P)
      (P ∨ Q) ⟺ (Q ∨ P)
    • Associativité :
      (P∧(Q∧R)) ⟺ ((P∧Q)∧R)
      (P∨(Q∨R)) ⟺ ((P∨Q)∨R
    • Distributivité :
      (P∧(Q∨R)) ⟺ ((P∧Q)∨(P∧R))
      (P∨(Q∧R)) ⟺ ((P∨Q)∧(P∨R))
    • Négations :
      $(\overline{\overline{P}}) ⟺ (P) $
      $(\overline{P∧Q}) ⟺ (\overline{P} ∨ \overline{Q})$
      $(\overline{P∨Q}) ⟺ (\overline{P} ∧ \overline{Q})$
      $(P ⟹ Q) ⟺ (\overline{Q} ⟹ \overline{P})$
      $(P ⟹ Q) ⟺ (\overline{P} ∨ Q)$
      $\overline{(P ⟹ Q)} ⟺ (P ∧ \overline{Q})$
    Démonstration : exercice.

    Remarques

    ⦿Les équivalences :$(\overline{P∧Q}) ⟺ (\overline{P} ∨ \overline{Q})$ et $(\overline{P∨Q}) ⟺ (\overline{P} ∧ \overline{Q})$ sont appelées lois de Morgan.
    ⦿Une proposition logique, obtenue à partir d’autres propositions à l’aide de connecteurs, et qui est toujours vraie, est appelée une tautologie.
    Exemple : soit P:$0≤x≤1$ ; on a : non(P):$(x < 0)\;ou\;(x>1)$.
    Exercice
    Ecrire les contraposées des implications suivantes, puis les démontrer.
    • x≠y ⟹ (x+1)(y-1) ≠ (x-1)(y+1).
    • n2 impair ⟹ n impair
    • n premier ⟹ n=2 ou n est impair
    • 8 ne divise pas n2-1 ⟹ n pair
    Exercice (théorème de Wilson)
    Soit $n∈ℕ$; montrer que :
    n est premier ⟺ $(n-1)!+1 ≡ 0 \pmod n$.
    Solution
    • (⟹) : on suppose que n est premier. On a alors $\frac{ℤ}{nℤ} $ est un corps. Seuls $\mathop{1}\limits^{•} \;et\; \mathop{\overline{n-1}}\limits^{•}=\mathop{\overline{-1}}\limits^{•}$ sont leurs propres inverses donc : $\dot 2\times \dot 3\times \dots\times \mathop{\overline{n-2}}\limits^{•} = \dot 1$, donc $\dot 1\times\dot 2\times \dots\times \mathop{\overline{n-1}}\limits^{•} = \mathop{\overline{-1}}\limits^{•}$ donc $(n-1)! \equiv -1 \pmod n$, d'où $(n-1)!+1 \equiv 0 \pmod n$
    • (⟸) : On suppose que $(n-1)!+1 \equiv 0 \pmod n$. On doit montrer que n est premier.
      Si n n'est pas premier alors n=ab où a ∈ {2,3,...,n-1}. Par suite a ne divise pas (n-1)!+1 puisque a figure dans (n-1)!, donc n ne divise pas (n-1)!+1. Contradiction.
3/ Quantificateurs
  • Le quantificateur universel « quel que soit » ou « pour tout » noté utilisé pour signifier que tout élément x d’un ensemble E vérifie une propriété P(x) , la syntaxe étant :$(∀ x ∈ E)\;\;(P(x)) \tag{1}$
  • Le quantificateur existentiel « il existe » noté pour signifier qu’il existe au moins un élément x de E vérifiant la propriété P(x) , la syntaxe étant :$(∃x∈E)∕(P(x)) \tag{2}$
Pour signifier qu’il existe un et un seul x dans E vérifiant la propriété P(x) , on utilisera la syntaxe : $(∃!x∈E)∕(P(x))$.
Négation d’une proposition quantifiée :
La négation de l’assertion (1) est : $(∃x∈E)/\overline {(P(x))} $.
La négation de l’assertion (2) est : $(∀x∈E)\overline {(P(x))} $.
Justification :
Soit P une propriété définie sur E ; posons A={x∈E/P(x)}. On a : $(1) ⟺ A=E ⟺ \overline {A}= ∅$ donc : non(1) ⟺ $\overline{A}$ ≠ ∅ ⟺ ∃ x ∈E/non(P(x))
De même : (2) ⟺ A ≠ ∅; par suite on a : non(2) ⟺ A=∅ ⟺ $\overline{A}$=E ⟺ tout élément de E posséde non(P) ⟺ (∀ x ∈E)non(P(x))
Théorème 2
Les propositions suivantes sont des tautologies :
$non[∃x∈E,P(x)]$ ⟺ $[∀x∈E,non(P(x))]$.
$non[∀xϵE,P(x)]$ ⟺ $[∃x∈E,non(P(x))]$.
Exercice
1) écrire la négation de la propriété $«∀ x ∈ E, P(x) ⟹ Q(x)»$
Comment démontre-t-on qu’une implication est fausse ?
2) démontrer que l’énoncé «∀x ∈ ℝ, x < 3 ⟹ x2 < 9» est faux.
Exercice
Traduire en termes de quantificateurs les expressions suivantes :
  • La suite (Un) converge vers l ;
  • La suite (Un) ne converge pas vers l ;
  • La fonction f est majorée ;
  • La fonction f est bornée ;
  • La fonction f est paire ;
  • La fonction f n’est ni paire ni impaire ;
  • La fonction f est croissante ;
  • La fonction f ne s’annule jamais ;
  • La fonction f n’est pas la fonction nulle ;
  • La fonction f est inférieure à la fonction g ;
  • La fonction f n’est pas inférieure à la fonction g.
  • Tout réel positif est le carré d’un nombre réel.
  • Il existe un nombre rationnel dont le carré vaut 2. (attention : il s’agit ici de donner une traduction correcte d’un énoncé qui est faux)

Remarque

Les quantificateurs ∀ et ∃ ne commutent pas. Par exemple les énoncés suivants ne sont pas équivalents :
∀x∈ ℝ, ∃y ∈ ℝ, x ≤ y
∃y∈ ℝ, ∀x ∈ ℝ, x ≤ y
4/ Méthodes de raisonnement
4.1 Raisonnement inductif
On part de propositions singulières ou particulières pour aboutir à une proposition générale. Exemple : « émettre une conjecture ».
Citons la conjecture de Goldbach : « tout nombre pair, sauf 2, est la somme de deux nombres premiers » .
4.2 Raisonnement déductif
Il s’agit de déduire et de prouver des résultats à partir d’une ou plusieurs hypothèses. En général l’énoncé d’une proposition à démontrer est formé d’une ou plusieurs hypothèses qui constituent l’assertion H et d’une ou plusieurs conclusions qui constituent l’assertion C. Il s’agit donc de montrer l’implication H ⟹ C.
Si de plus, on peut montrer que C ⟹ H, on dira alors que la réciproque de la proposition est vraie.
Les idées de base que l’on peut utiliser sont les suivantes :
  • Une assertion peut toujours être remplacée par n’importe quelle assertion qui lui est équivalente.
  • On peut effectuer une démonstration directe, c'est-à-dire de déduire logiquement C de H.
  • L’implication étant transitive, on peut essayer de montrer que C ⟹ C' sachant par ailleurs que C' ⟹ H.
  • Dans le cas où une démonstration directe semble difficile, on peut essayer une démonstration par l’absurde.
  • On peut aussi faire une démonstration par contraposition.
  • La démonstration par contre-exemple permet d’infirmer un énoncé.
  • La démonstration par récurrence permet de montrer qu’une propriété portant sur des entiers naturels est toujours vraie.
4.3 Raisonnement par l’absurde
Soit à prouver que la proposition P est vraie ; le raisonnement consiste à introduire la proposition non(P) et démontrer une implication telle que :
non(P) ⟹ non(Q) où Q est une proposition vraie. On a:
(non(P) ⟹ non(Q)) ⟺ (Q ⟹ P).
Comme Q est vraie alors P est vraie.
Exemple : Démontrer que $\sqrt 2$ est irrationnel.
Exrcice
En raisonnant par l’absurde, montrer que $ \frac{ln(2)}{ln(3)}$ est irrationnel.
Exrcice
Soit n un entier naturel non carré, c'est-à-dire ne s’écrivant pas sous la forme n=m2 où m entier. En raisonnant par l’absurde et en utilisant le théorème de Bézout, montrer que $\sqrt n$ est irrationnel.
4.4 Les théorèmes de récurrence
  • Premier type de raisonnement par récurrence
    Soit n0∈N et 𝒫 une propriété définie sur I={n∈ℕ/n≥n0}. Si l’entier n possède la propriété 𝒫, on dit que : « la proposition 𝒫(n) est vraie » ou plus simplement « on a 𝒫(n) ».
    Si l’entier n ne possède pas la propriété 𝒫, on dit que : « la proposition 𝒫(n) est fausse » ou plus simplement « on a non(𝒫(n)) ».
    Nous allons donner un mode de raisonnement permettant d’affirmer que tous les éléments de I possèdent la propriété 𝒫.
    Supposons que les deux propositions suivantes soient vraies :
    (1) 𝒫(n0)
    (2) (∀n∈I) (𝒫(n) ⟹ 𝒫(n+1))
    Démontrons que l’on a : (∀n∈I) 𝒫(n)
    Notons :J={n∈I/non(𝒫(n))}. Si J≠∅ alors il admet un plus petit élément q. On a q>n0 puisque 𝒫(n0) est vraie. Par suite, q n’est pas nul et admet un prédécesseur ω=q-1. L’entier naturel ω n’appartient pas à J puisque q est le plus petit élément de J donc 𝒫(ω)est vraie. D’après (2) on a :𝒫(ω+1)est vraie c'est-à-dire que 𝒫(q)est vraie. Ce qui est en contradiction avec 𝒫(q)est fausse. Donc J est vide et la proposition (3) est vraie. D’où le théorème suivant :
    Théorème 3(récurrence simple)
    Soit 𝒫 une propriété définie sur I={n∈ℕ/n≥n0} où n0 est un entier naturel donné.
    Si les deux propositions suivantes sont vraies :
    - 𝒫(n0)
    - (∀n∈I) (𝒫(n) ⟹ 𝒫(n+1))
    Alors on a : (∀n∈I) 𝒫(n)

    Exemple

    Démontrer par récurrence que : $\forall n \in \Bbb {N}^{*}; \sum_{1}^{n}{\frac{1}{p(p+1)}}=\frac{n}{n+1}$
  • Autres formes de raisonnement par récurrence
    Soit n0 un entier naturel donné et 𝒫 une propriété définie sur I={n∈ℕ,n≥n0}.
    Supposons que les deux propositions suivantes soient vraies :
    (1) 𝒫(n0)
    (2) (∀n∈I) ((𝒫(n0),𝒫(n0+1),…,𝒫(n)) ⟹ 𝒫(n+1))
    Démontrons que l’on a : (∀n∈I)  𝒫(n)
    Considérons la propriété 𝒬 définie sur I par : 𝒬(n) ⟺ (∀p∈[n0,n],𝒫(p))
    On a : Q(n0).
    Supposons que 𝒬(n) soit vraie pour un entier naturel n supérieur ou égal à n0, alors 𝒫(n+1) est vraie. Nous avons donc :
    (∀n∈I) (𝒬(n) ⟹ 𝒬(n+1)) .
    D’après le théorème précédent, on a : (∀n∈I)  Q(n).
    Par suite on a : (∀n∈I)  𝒫(n).
    On peut énoncer :
    Théorème 4(récurrence forte)
    Soit 𝒫 une propriété définie sur l’ensemble I={n∈N,n≥n0} où n0 est un entier naturel donné.
    Si les deux propositions suivantes sont vraies :
    (1)  𝒫(n0)
    (2)  (∀n∈I) ((𝒫(n0 ),𝒫(n0+1),…,𝒫(n)) ⟹ 𝒫(n+1))
    Alors on a : (∀n∈I)   𝒫(n)

    Exemple

    On considère la suite (un) définie sur ℕ* par :
    \begin{cases} {u}_{1} &= 3 \\ {u}_{n+1} &= \frac{2}{n}({u}_{1}+{u}_{2}+ \dots +{u}_{n}) \end{cases} Montrer que : ∀n≥1,un=3n
    Corollaire (récurrence à deux pas)
    Soit 𝒫 une propriété définie sur l’ensemble I={n∈N,n≥n0} où n0 est un entier naturel donné.
    Si les trois propositions suivantes sont vraies :
    (1) 𝒫(n0)
    (2) 𝒫(n0+1)
    (3) Pour n>n0 fixé quelconque,(𝒫(n-1) et 𝒫(n) ⟹ 𝒫(n+1))
    Alors on a : (∀n∈I)   𝒫(n)

    Exemple (suite de Fibonacci)

    On considère la suite (un ) définie par : u0=1,u1=1 et un+1=un+un-1 pour n≥1
    1) Montrer que : ∀n≥1; ${u}_{n}=\frac{1}{\sqrt{5}} \left({{\alpha}^{n}-{\beta}^{n}}\right)$ où $\alpha=\frac{1+\sqrt 5}{2}$ , $\beta=\frac{1-\sqrt 5}{2}$
    2) Montrer que la suite (un ) est divergente.
    3) Montrer que : ∀n≥1; un+1.un-1-un2=(-1)n.
    Exercice
    Donner une formule exprimant la somme : Sn=1+8+27+ ... +n3
    Exercice
    Soit la suite (un) définie sur ℕ par : U0=1,U1=6 et ∀n≥2,un=6un-1-9un-2.
    Montrer que : ∀n∈ ℕ ,un=(n+1)∙3n

Autres articles

Commentaires


Connectez vous pour ajouter des commentaires.


Découvrir

Séries d'exercices en ligne

Autres documents

Niveaux scolaires

Programmes de mathématiques

Mes logiciels

Manuels scolaires

Outils mathématiques

Divertissements

Sujets de bac