Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Si (p) est vérifiée, alors (q) est vérifiée : on dit que (p) implique (q). On n

Si (p) est vérifiée, alors (q) est vérifiée : on dit que (p) implique (q). On note : (p) => (q). Pour que (q) soit vérifiée, il suffit que (p) soit vérifiée : on dit que (p) est une condition suffi sante pour que (q) soit vérifiée. Si (q) n'est pas vérifiée, alors (p) ne peut pas être vérifiée (puisque (p) implique (q)J : il faut donc que (q) soit vérifiée pour qüe (p) le soit ; on dit que (q) est une condition nécessaire pour que (p) soit vérifiée. (q) => (r) et (r) => (q) : on dit que (q) et (r) sont équivalentes ou que (q) est vérifiée si et seu lement si (r) est vérifiée. On note : (q) o (r). Lorsque deux conditions sont équivalentes, chacune d’elles est une condition nécessaire et suffisante pour que l’autre soit vérifiée. • D'une manière générale, on peut retenir que : la négation de [(p) ou (q)] est [(non p) et (non q)) ; la négation de [(p) et (q)] est [(non p) ou (non q)]. Exemples • La négation de (x inférieur à y/ ou égal à y) est (.v non inférieur à y et différent de y). Donc, la négation de (x y) est (x > y). On démontre de môme que la négation de (x < y) est (x y). • La négation de (—1 < x et x < 1) est (— 1 > x ou x 1). * * * * Donc, la négation de (-1 x * < 1) est (x * < -1 ou x > 1 ). La méthode de démonstration precedente est appelée raisonnement par l'absurde. Son principe est le suivant : pour démontrer qu'une proposition (p)2 est vraie, on prouve que la négation de cette proposition (non p) est fausse. Pour cela : - on suppose que (non p) est vraiç ; - on cherche à en déduire une proposition (q) que l'on sait fausse. Ainsi, lorsque l'on y parvient, on aboutit à une contradiction et on a démontré que (non p) est fausse, c'est-à-dire que (p) est vraie. Définition A et B sont des ensembles non vides. On appelle fonction de A vers B toute correspondance qui, à chaque élément de A, associe un ou zéro élément de B. Vocabulaire et notations On dit que /est la fonction de A vers B qui, à x, associe f[x) ; A est l'ensemble de départ, B l'ensemble d'arrivée de /; x est la variable, /(x) l'image de x par /. On note /: A—>B x»- * /[x). - Lorsque v est l’image de u par /, on dit que u est un antécédent de v par f. On écrit : v = J (u). - Lorsque l’ensemble d'arrivée d'une fonction/est un ensemble de nombres réels, on dit que/est une fonction numérique. - Lorsque l’ensemble de départ d'une fonction numérique/est un ensemble de nombres réels, on dit que / est une fonction numérique d’une variable réelle. ■ Implication • Dans un énoncé de propriété, « l’implication » se traduit par : si (p) alors (q) => (q) on note : on lit : (p) => (q) (p) implique (q) Cependant, dans certains énoncés de propriété, l’implication est implicite. • Dans une démonstration, l’utilisation d’une « implication » permet de déduire directement une conclusion C à partir d’une donnée D du problème, on évitera alors l’expression : « si D alors C », ce qui pourrait sous-entendre une supposition (ce qui n’est pas le cas d'une donnée D de problème). En général,on écrit indifféremment : (1) on a D ; donc C. (2) puisque D ; donc C. L’implication permet une démonstration par déduction directe d’une conclusion C à partir de I la donnée D d’un problème, ou de l’hypothèse H d’une propriété. ou bien l’implication : xa* * x 2 =❖ /(xJ * f(x 2] sa contraposée : /(xJ = f(x2) => x1 =x2 ■ Contraposée d’une implication_________________________________________ Définition - Propriété • On appelle contraposée de l’implication : (p) => (q) l’implication : non (q) => non (p). • On admet qu’une implication et sa contraposée sont logiquement équivalentes. Lorsqu'il est difficile de démontrer une implication (p) => (q), on peut penser à démontrer sa contrapo sée : non (q) => non (p). Exemple Pour reconnaître une injection, on peut utiliser : ■ Principe de la démonstration par récurrence La démonstration par récurrence comporte deux étapes avant la conclusion. Pour démontrer que : pour tout nombre entier naturel supérieur à n0, Pn, on peut procéder comme suit : lre étape : établissement de la condition initiale qui est « l'existence d’un héritage ». On vérifie que : Pno est vraie. 2° étape : démonstration d’un algorithme récurrent ; c’est « le principe d’un droit de succession » On établit que : si pour un nombre entier naturel k supérieur à noï eS( vraie, alors Pfc+1 est vraie. Conclusion : pour tout nombre entier naturel n supérieur à n0, Pn. Dnnczz3 Deux types d'énoncés mathématiques • On distingue deux types d’énoncés mathématiques liés à une propriété p définie sur un ensemble E. x0 éteint un élément particulier de E, p(x0) est une proposition ; elle est soit vraie, soit fausse ; on dit qu’elle possède une valeur de vérité. x étant un élément quelconque de E, p(x) est appelé fonction propositionnelle (de la variable x). En géné ral, elle ne fait pas l'objet d’une démonstration car elle ne possède pas une valeur de vérité. - Les énoncés universels Ce sont les propositions quantifiées du type : pour tout x élément de E, p(x) quantificateur universel - Les énoncés existentiels Ce sont les propositions quantifiées du type : il existe x élément de E, p(x) quantificateur existentiel • On admet que : - la négation d’un énoncé universel est un énoncé existentiel ; - la négation d’un énoncé existentiel est un énoncé universel. ssBoaua Différentes méthodes de démonstrations Tableau récapitulatif <D Démonstration par un exemple ou un contre-exemple • Démonstration par un exemple Pour établir un énoncé existentiel, (1) Il existe x élément de E, p(x) il suffît d’exhiber un exemple d'élément de E ayant la propriété énoncée p. • Démonstration par contre-exemple Pour établir un énoncé existentiel, négation d’un énoncé universel : (2) Il existe x élément de E, non q(x) il suffît d’exhiber un exemple à cet énoncé existentiel (2) ; on dit que l’on a produit un contre-eXempIe à sa négation, l'énoncé universel ci-dessus : (3) Pour tout x élément de E, q(x). @ Démonstration par implication et par contraposition I (p) => (q) | si et seulement si implication permettant une déduction directe I non (q) =» non (p) contra posé de (p) => (q) ® Démonstration par disjonction des cas • Naturellement, on convient de dire que la proposition suivante est vraie : (p) ou non (p) ; c’est le principe du tiers exclu. • La démonstration par disjonction des cas est basée sur ce principe, elle revient donc à exa miner exhautivement tous les cas. I ® Démonstration par l’absurde • Naturellement, on convient de dire que l’énoncé mathématique suivant est faux : (p) et non (p) ; I c’est le principe de non-contradiction. La démonstration par l’absurde est basée sur ce principe ; elle consiste donc, à rejeter toute hypothèse qui conduit à une contradiction. • Ainsi pour démontrer que l’énoncé mathématique (p) est vraie : - on suppose que non (p) est vraie ; - on en déduit un énoncé (q) que l’on sait être fausse ; - on conclut que (p) est vraie car il y a contradiction. (§) Démonstration par récurrence Pn est un énoncé mathématique qui dépend d’un nombre entier naturel n. Pour démontrer par récurrence que : « pour tout n supérieur à n0, Pn » est vraie. On procède comme suit, lrc étape : on vérifie que Pn(j est vraie ; 2e étape : on suppose que : « pour un nombre entier naturel k supérieur à n0, Pfc » est vraie, on démontre que : PA. +1 est vraie ; on conclut. I__________ B Partition d’un ensemble IMH» Bp B2, ... , Bn forment une partition de ^U. signifie que Bp B2, ... , Bn sont deux à deux disjoints et B] U B2 U ... U Bn = °ll. Br B2, B3 forment une partition de °U. signifie que Bj n B2 = 0 ; B2 A B3 = 0 ; Bt n B3 = 0 ; B. U B.. U B, = °lt. 1 4 J Pour démontrer qu’une proposition qui et ■:>><; ■■r un entier natiimi n. est vraie peut tout n SÈipérieur ou égal à bu, d u procède en deu^ étapes ; * on (Lïmiintrc que : P(^) esl vraie . • on démontre que : pour tout entier k supérieur ou i-nal à j i„. si P{fc) est vraie alors P(Jc + 1] est \T.iic. uploads/Litterature/ revision-logique-tle.pdf