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.$
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 . 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 : 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). 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
  F	V

  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	P∧Q
  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	P∨Q
  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	P⟹Q
  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:
  n² 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 ⟹ x²>4 est vraie ; mais x²>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).
  • n² impair ⟹ n impair
  • n premier ⟹ n=2 ou n est impair
  • 8 ne divise pas n²-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.

• 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)) 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 » .
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 : 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. En raisonnant par l’absurde, montrer que $ \frac{ln(2)}{ln(3)}$ est irrationnel. Soit n un entier naturel non carré, c'est-à-dire ne s’écrivant pas sous la forme n=m² où m entier. En raisonnant par l’absurde et en utilisant le théorème de Bézout, montrer que $\sqrt n$ est irrationnel.

• Premier type de raisonnement par récurrence
  Soit n₀∈N et 𝒫 une propriété définie sur I={n∈ℕ/n≥n₀}. 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) 𝒫(n₀)
  (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>n₀ puisque 𝒫(n₀) 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≥n₀} où n₀ est un entier naturel donné.
  Si les deux propositions suivantes sont vraies :
  - 𝒫(n₀)
  - (∀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 n₀ un entier naturel donné et 𝒫 une propriété définie sur I={n∈ℕ,n≥n₀}.
  Supposons que les deux propositions suivantes soient vraies :
  (1) 𝒫(n₀)
  (2) (∀n∈I) ((𝒫(n₀),𝒫(n₀+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∈[n₀,n],𝒫(p))
  On a : Q(n₀).
  Supposons que 𝒬(n) soit vraie pour un entier naturel n supérieur ou égal à n₀, 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≥n₀} où n₀ est un entier naturel donné.
  Si les deux propositions suivantes sont vraies :
  (1)  𝒫(n₀)
  (2)  (∀n∈I) ((𝒫(n₀ ),𝒫(n₀+1),…,𝒫(n)) ⟹ 𝒫(n+1))
  Alors on a : (∀n∈I)   𝒫(n)

  Exemple ✍

  On considère la suite (u_n) 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,u_n=3n
  
  Corollaire (récurrence à deux pas)

  Soit 𝒫 une propriété définie sur l’ensemble I={n∈N,n≥n₀} où n₀ est un entier naturel donné.
  Si les trois propositions suivantes sont vraies :
  (1) 𝒫(n₀)
  (2) 𝒫(n₀+1)
  (3) Pour n>n₀ fixé quelconque,(𝒫(n-1) et 𝒫(n) ⟹ 𝒫(n+1))
  Alors on a : (∀n∈I)   𝒫(n)

  Exemple (suite de Fibonacci)✍

  On considère la suite (u_n ) définie par : u₀=1,u₁=1 et u_n+1=u_n+u_n-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 (u_n ) est divergente.
  3) Montrer que : ∀n≥1; u_n+1.u_n-1-u_n²=(-1)ⁿ.
  Exercice
  Donner une formule exprimant la somme : S_n=1+8+27+ ... +n³
  
  Exercice
  Soit la suite (u_n) définie sur ℕ par : U₀=1,U₁=6 et ∀n≥2,u_n=6u_n-1-9u_n-2.
  Montrer que : ∀n∈ ℕ ,u_n=(n+1)∙3ⁿ