> "Je ne fais jamais deux fois la même erreur. Je la fais 5 ou 10 fois avant d'être sur" # Préambule >[!definition] >Pour un **résultat mathématique** (proposition, propriété). Il est toujours **vrai**. quand il est fort, majeur, on dit que c'est un **théorème**, et quand il est moins important on utilises le terme '**lemme**'. > >[!definition] Définition démonstration >Faire une **démonstration** (preuve) c'est réaliser un processus qui permet de passer d'une (ou plusieurs) proposition supposée vraie prise comme hypothèse à une proposition appelée conclusion et ce en utilisant les **règles de logique**. >On aura plusieurs modes de démonstrations logiques en mathématique: >- Raisonnement par hypothèse auxilière >- Contraposée >- Absurde >- disjonction de cas >- contre-exemple >- analyse synthèse >- récurrence ### Condition nécessaire et/ou suffisante Soit $P$ et $Q$ deux énoncés mathématiques. -> L'**implication** "$P => Qquot;, exprime une relation de cause à effet. $P$ est la cause, et $Q$ est l'effet. Elle signifie que pour avoir l'effet. il **suffit**, d'avoir la cause. En ce sens on dit que $P$ est une **condition suffisante** pour $Q$. -> Sa **contraposée**: quot;non"(Q) => "non"(P)$ traduit le fait que de l'absence de l'effet on peut déduire l'absence de la cause . Dans ce sens, on dit que $Q$ est une **condition nécessaire** pour P. "**Si je n'ai pas $Q$ alors je n'ai pas $P$, si je n'ai pas l'effet, je n'ai pas la cause**." On a l'équivalence logique: $P => Q$ $equiv "non"(Q) => "non"(P)$ -> En revanche les implications $P=>Q$ et $Q =>P$ ne sont pas logiquement équivalentes. $P=> Q !(equiv) Q => P$ - Rappelons que $P <==> Q$ est qualifié de double implication. Il se lit alors: "Pour que $P$, il faut et il suffit que $Qquot; et on dit que $P$ est une **condition necéssaire pour$Q$**. On le nomme aussi "Si et seulement si". (cours 22/09/2023) ## Raisonnement par hypothèse a+uxiliaire **But**: il sert à montrer qu'un énoncé $Q$ est vrai. **Principe**: il s'appuie sur $[P "et" (P => Q)] => Q$. Ainsi, si $P$ est vrai et si $P =< Q$ est vraie alors $Q$ est vrai. **Méthodologie**: on cherche une implication $P ==> Q$ que l'on sait vraie. Ainsi, au lieu de montrer que $Q$ est vrai, on montre que $P$ est vrai. $Q$ sera vrai car $P=> Q$ est vraie. >[!exemple] >Montrons que $A = {2,3}$ et $B = {x in RR | x^2 + x - 6 = 0}$ sont deux sous ensembles égaux. On va alors essayer de faire $A = B <=> A in B "et "B in A$. Mais il est plus intelligent de faire $A=B <== (A in B "et" "card"(A)="card"(B))$. >Donc, ici on a: $Q = "A = B"$ et $P = ' A in B "et" "card"(A) = "card"(B)''$. Il suffit donc de vérifier que $P$ est vrai. C'est immédiat puisque d'une part $2$ et $-3$ vérifient l'équation possédant deux racines réelles distinctes ($Delta = 25 > 0$), on a: quot;card"(B) = 2$ et donc: quot;card"(B) = "card"(A)$ >[!remarque] >quot;card"(B)$ représente le nombres d'éléments dans un ensemble. ## Raisonnement par contraposée >[!remarque] >Parfois c'est plus facile d'utiliser la contraposée. **But**: Il sert à montrer une implication $P => Q$. **Principe**: il s'appuie sur l'équivalence logique: $ (P ==> Q) equiv ["non"(P) ==> "non"(Q)] $ Au lieu de l'implication "$P ==> Qquot; on montre plutôt sa contraposée, càd l'implication: quot;non"(Q) ==> "non"(P)$. **Méthodologie**: On suppose l'énoncé "quot;non"(Q)$ vrai, et on montre que cela entraîne que l'énoncé quot;non"(P)$ est vrai. >[!exemple] >Montrons (par contraposée) que: $forall n in NN n^2 "pair" => n "pair"$ >Il faut donc montrer: $n "impair" => n^2 "impair"$ pour tout $n in NN$. >Soit $n in NN$. Supposons $n$ impair: $exists p in NN$ tel que: $n = 2p +1$. D'où: >$n^2 = (2p+1)^2 = 4p^2+4p+1=2(2p^2+2p)+1=2q+1$ > Avec $q =^"def" 2p^2 + 2p in NN$. Le nombre $n^2$ est donc pair. >[!remarque] >$q =^"def" c$ c'est que l'on pose une nouvelle définition. On pose une nouvelle variable qui __par définition__ est égal à $c$. >[!remarque] >Donc on doit montrer quelque soit $n$, alors c'est tout les $n$, donc on dit 'prenons un $n$ quelconque' => Soit $n in NN$. ## Raisonnement par l'absurde **But**: il sert à montrer qu'un énoncé $P$ est vrai. **Principe**: il s'appuie sur l'équivalence logique: $ {["non"(P) ==>Q] "et" ["non"(P) ==> "non"(Q)]} equiv P $ Il consiste donc à montrer que quot;non"(P)$ entraîne un énoncé $Q$ (que l'on doit trouver) et son contraire quot;non"(Q)$. **Méthodologie**: on suppose l'énoncé quot;non"(P)$ vrai et on cherche alors $Q$ qui, sous cette hypothèse, serait à la fois vrai et faux. On dit que l'on a obtenu une contradiction ou que l'hypothèse quot;non"(P)$ est contradictoire. >[!exemple] >Montrons (par l'absurde) que $sqrt(2) !in QQ$ (rappelons que $sqrt(2)$ est par définition, le nombre réel positif dont le carré vaut $2$). >Donc, on va prendre la négation de l'énoncé, ici: $sqrt(2) in QQ$, c'est à dire qu'il existe $(p,q) in NN * NN^*$ avec $p$ et $q$ **premiers entre eux** (fraction irréductible, ils ont aucun diviseurs en commun). Donc on va écrire $sqrt(2) = p/q$. On va donc l'élever au carré: >$sqrt(2) = p/q \ 2 = (p^2)/(q^2) \ p^2 = 2q^2$ >Donc, $p^2$ est pair, et donc, $p$ est pair. Donc il existe $m in NN$ tel que $p = 2m$. Remplaçons $p$ par $2m$ dans $p^2 = 2q^2$. >$2m^2 = 2q^2$ >ou encore: $q^2 = 2m^2$ càd que $q^2$ est pair. On en déduit que $q$ est pair, càd qu'il existe $m' in NN$ tel que $q = 2m'$. Donc, on a $p/q = (2m)/(2m')$ Donc, ils ont un diviseur commun ($2$). ce qui est contraire à notre hypothèse $p$ et $q$ sont premiers entre eux. La démonstration par l'absurde de $sqrt(2) !in QQ$ est donc terminée. ## Disjonction de cas **but**: montrer qu'un énoncé: $forall x in E P(x)$ est vrai. **Principe**: il s'appuie sur l'équivalence logique: $[forall x in E P(x)] equiv {[forall x in E_1 P(x) "et" ... "et" [forall x in E_n P(x)]]}$ Pour résumer, on va diviser l'ensemble $E$ en plusieurs sous groupes. ou éléments. où $E = E_1 union ... union E_n$ et $E_i sect E_j = emptyset$ si $i != j$. **Méthodologie**: On cherche des sous-ensembles $E_1, ..., E_n$ de $E$ tels que: $E_1 union E... union E_n$ et $E_i sect E_j = emptyset$ si $i != j$ et on sépare les raisonnements suivant que $x in E, ..., x in E_n$. >[!exemple] >Montrons que $n(n+1)/2 in NN$ pour tout $n in NN$. Utilisons pour cela un raisonnement par disjonction de cas. >1. Si $n$ est pair, càd: $n = 2p$ avec $p in NN$, alors: $n(n+1)/2 = (2p(2p+1))/2=p(2p+1) in NN$ >2. Si $n$ est impair, càd: $n = 2p+1$, avec $p in NN$, alors: $(n(n+1))/2=((2p+1)(2p+1))/2=(2p+1)(p+1) in NN$ >[!remarque] >On utilises souvent la disjonction de cas afin d'éviter un cas particulier, tel que $x = 0$ dans une division. ## Raisonnement par contre-exemple **But**: montrer qu'un énoncé: $forall x in E " " R(x)$ est faux. **Principe**: on montre que sa négation est vraie. Rappel: $ "non"(forall x in E " " R(x)) equiv exists x in E " " "non"(R(x)) $ **Méthodologie**: on cherche alors à exhiber (au moins) un élément $x$ in E et que la propriété $R(x)$ soit fausse. En d'autres termes, **l'exceptions infirme la règle**. >[!exemple] >On a l'énoncé: "Toute fonction de $RR$ dans $RR$ est soit paire, soit impaire" est faux puisqu'on peut trouver une fonction de $RR$ qui n'est ni paire, ni impaire. C'est par exemple le cas de l'exponentielle $x in R |-> exp(x) in RR$ > >De même , l'énoncé $forall n in NN " " (n-3)n > 0$ est faux puisqu'on peut trouver un entier naturel pour lequal $(n-3)n <= 0$. C'est le cas, par exemple, de $0$ **Contre-exemple pour une implication**: Un raisonnement par contre exemple sert aussi à montrer qu'un énoncé $forall x in E " " P(x) => Q(x)$ est faux. >[!remarque] >Rappelons que l'énoncé $forall x in E" " P(x) => Q(x)$ exprime une relation de cause à effet pour tout $x in E$. ici la cuse est $P(x)$. L'effet est $Q(x)$. Pour montrer par contre(exempl, qu'un tel énoncé est faux, on montre qu'il existe un $x in E$ pour lequel on a la cause (càd $P(x)$ est vrai) mais pas l'effet (càd $Q(x)$ est faux). > >On vient donc de justifier: >$"non"(forall x in E " " P(x) ==> Q(x)) equiv exists x in E " " P(x) "et" "non"(Q(x))$ > ## Raisonnement par analyse-synthèse **But**: déterminer la (les) solution(s) d'un problème. **Méthodologie**: il s'effectue en deux étapes: 1. **Étape d'analyse** - On suppose que le problème considéré possède déjà une solution et on en déduit que cette solution possède certaines propriétés (ce sont donc des conditions nécessaires puisqu'on procède par implication). - En pratique, cela permet d'identifier un (ou plusieurs) candidat(s). - S'il n'y a qu'un seul candidat, alors cette étape d'analyse montre **l'unicité** de la solution du problème considéré. 2. **Étape de synthèse** - On teste ensuite si les conditions nécessaires obtenues sont suffisantes. - En pratique, on teste chacun des candidats. - Si aucun candidat ne répond au problème. >[!remarque] >Si on procède par équivalence plutôt que par implication, on a pas forcément besoins de l'étape de synthèse. >[!exemple] >Montrons que toute fonction réelle est la somme d'une fonction paire et d'une fonction impaire, de manière unique. Soit $f$ une fonction définie sur $RR$, à valeurs dans $RR$. >**Étape d'analyse** - Supposons qu'il existe deux fonctions $g : RR -> RR$ paire et $h : R -> RR$ impaire telles que: >$forall x in RR " " f(x) = g(x) + h(x)$. >Puisque, $g$ est paire et $h$ est impaire, on a aussi: >$f(-x) &= g(-x) + h(-x) \ f(-x) &= g(x) - h(x)$. D'où: >$g(x) = (f(x) + f(-x))/2$ On a aussi: $h(x) = (f(x)-f(-x))/2$ pour tout $x in RR$. On remarque qu'il n'y a qu'un seul candidat pour $g$ et qu'un seul pour $h$ ce qui montre l'unicité de $g$ et celle de $h$. >**Étape de synthèse**: on vérifie que les fonctions $g$ et $h$ conviennent, càd que $g$ est paire, $h$ impaire (le faire) et que: >$forall x in RR " " g(x) + h(x) = (f(x) + f(-x))/2 + (f(x)-f(-x))/2=...=f(x) $ >[!remarque] >Si $g$ de $x$ est pair, alors $g(x) = g(-x)$ >Si $h$ de $x$ est impair, alors $h(x) = -h(-x)$.