[Ch5] Quelques notions de Demonstration

[Arthur - TitrOu]

I] Dans la suite, p et q sont deux propositions.

1. Règle de détachement :
   
   On montre q sachant [p et p=>q]
   { ABC est un triangle rectangle en B
   { Théorème de Pythagore => AC² = AB² + BC²
   
   p: ABC rectangle en B
   q: AC² = AB² + BC²
   p=>q : Théorème de pythagore
   
   
2. La contraposition :
   
   (p=>q) = (¬q=>¬p)
   
   Ex : Montrons que ∀n ∈ℕ, n² pair => n pair
   Pour celà, on montre n impair => n² impair
   
   n impair :
   ⇔ ∃k ∈ℕ, n=2k+1 => ∃k ∈ℕ, n²=4k²+4k+1
   ⇔ ∃(2k²+2k) ∈ℕ, n²=2(2k²+2k)+1
   ⇔ n² impair
   
   Par contraposition : ¬(n impair) => ¬(n² impair) donc n² pair => n pair
   
   
3. Raisonnement par l'absurde :
   
   Principe : (¬p => 0) = ¬(¬p) = p
   
   On suppose la négation ¬p de ce que l'ont veut montrer, et on exhibe une absurdité (0) pour déduire la proposition p.
   
   Ex : Montrons que √(2) est irrationnel
   
   Par l'absurde : Supposons que √(2) ∈ ℚ
   
   Alors ∃(a et b) ∈ (ℕ⁺)², (√(2) = a/b et PGCD(a;b) =1)
   √(2) =a/b => 2 = a²/b²
   => a² = 2b² => a² pair => a pair
   => ∃k ∈ℕ, a=2k
   
   Alors : a² =2b² => (2k)² = 2b²
   => 4k² = 2b² => b² pair => b pair
   
   {2divise a
   {2 divise b _______ => 1⩾2 ABSURDE
   {PGCD(a;b) =1
   
   Conclusion : √(2)∈ ℚ
   
   
4. Disjonction des cas :
   
   [(p => q) et (¬p => q)] => q
   
   Ex: Montrons ∀n ∈ℕ, (n[exp]3[/exp]+n) est pair
   
   
   • Si n est pair :
     ∃k ∈ ℕ, n=2k et n³+n = (2k)³ + 2k
     = 8k³ + 2k = 2(4k²+k) => n³ + n est pair
     
     
   • Sinon :
     n impair => ∃k ∈ ℕ, n = 2k +1et n³+n = (2k+1)³ + 2k +1
     = 8k³ + 12k² + 6k + 1 + 2k +1
     = 2-4k³ + 6k² + 4k +1) => n est pair.
     
     Conclusion : ∀n ∈ℕ, n³+n est pair
     

Contre-exemple : (Pour nier une propriété universelle)

Soit E un ensemble P(x) un prédicat d'univers E, alors :
¬[(∀x ∈E), P(x)] ⇔ (∃x ∈E), ¬(P(x))

Ex: Montrons que la soustraction n'est pas associative dans ℤ.
∃(10;5;4) ∈ℤ, [(10-5)-4]≠[10-(5-4)] (1≠9)

[Arthur - TitrOu]

II] Raisonnement par récurrence :

1. Induction faible :
   
   Soit P(n) un prédicat d'univers ℕ où d'univers {k∈ ℕ, k⩾i} avec i∈ ℕ.
   
   Alors :
   
   {P(o)
   {∀n ∈ ℕ, (P(n) => P(n+1) ____=> ∀n ∈ ℕ, P(n)
   
   Ex: Montrons ∀n ∈ ℕ, ⁿ∑_k=0(k) = n(n+1)/2
   
   Par récurrence :
   
   
   • Initialisation : ⁰∑_k=0(k) = 0 = 0*(0*1)/2 Donc vrai pour P(0)
     
     
   • Hérédité : Soit n∈ ℕ
     supposons ⁿ∑_k=0(k) = n(n+1)/2 [hypothèse de récurrence]
     
     Alors : ⁿ⁺¹∑_k=0(k) = [1+2+...+n+(n+1)]/2
     = n(n+1)/2 + (n+1)
     = n(n+1)/2 + 2(n+1)/2
     = [n(n+1) + 2(n+1)]/2
     = (n+1)[(n+1)+1]/2
     
     
   • Conclusion : ∀n ∈ ℕ, ⁿ∑_k=0(k) = n(n+1)/2
     

1. Principe d'induction forte :
   
   Soit P(n) un prédicat d'univers ℕ,
   
   {P(0)
   {∀n ∈ ℕ, (P(0) et P(1) et... et P(n) => P(n+1)
   
   Ex: Tout entier ⩾2 est premier ou produit de nombre premier.
   
   Par récurrence :
   
   
   • Rang initial : 2 est premier vrai pour n=2
     
     
   • Hérédité : Soit n∈ ℕ tel que n⩾2.
     Supposons que 2;3;4;5;..;n sont premiers ou produit de nombre premiers.
     
     Alors: n+1 est premier
     ou(sinon) ∃(p₁; p₂) ∈ [| 2;n |]² p₁, p₂ = n+1
     par hypothèse, p₁et p₂ premier
     => n+1 produit de nombres premiers.
     
     
   • Conclusion : ∀n ∈ ℕ\{0;1} n premier ou produit de nombres premiers.