La logique

212763

1.Uneassertionest une phrase soit vraie, soit fausse, pas les deux en même temps.Exemples :-"Il pleut.»-"Je suis plus grand que toi.»-" 2Å2AE4 »-" 2£3AE7 »-"Pour tout x2R, on a x2Ê0.»SiPest une assertion etQest une autre assertion, nous allons définir de nouvelles assertionsconstruites à partir dePet deQ.L"opérateur logique "et»L"assertion "PetQ» est vraie siPest vraie etQest vraie. L"assertion "P et Q» est fausse sinon.On résume ceci en unetable de vérité:P\QVFVVFFF FFIGURE1 - Table de vérité de "P et Q»Par exemple siPest l"assertion "Cette carte est un as» etQl"assertion "Cette carte est coeur» alorsl"assertion "P et Q» est vraie si la carte est l"as de coeur et est fausse pour toute autre carte.L"opérateur logique "ou»L"assertion "PouQ» est vraie si l"une des deux assertionsPouQest vraie. L"assertion "PouQ»est fausse si les deux assertionsPetQsont fausses.On reprend ceci dans la table de vérité :P\QVFVVVFV FFIGURE2 - Table de vérité de "P ou Q»

SiPest l"assertion "Cette carte est un as» etQl"assertion "Cette carte est coeur» alors l"assertion"PouQ» est vraie si la carte est un as ou bien un coeur (en particulier elle est vraie pour l"as decoeur).RemarquePour définir les opérateurs "ou», "et» on fait appel à une phrase en français utilisant lesmotsou,et! Les tables de vérités permettent d"éviter ce problème.La négation "non»L"assertion "nonP» est vraie siPest fausse, et fausse siPest vraie.PV FnonPF VFIGURE3 - Table de vérité de "non P»L'implicationAE)La définition mathématique est la suivante :L"assertion "(non P) ou Q» est notée "PAE)Q».Sa table de vérité est donc la suivante :P\QVFVVFFVVFIGURE4 - Table de vérité de "PAE)Q»L"assertion "PAE)Q» se lit en français "P implique Q».Elle se lit souvent aussi "si P est vraie alors Q est vraie» ou "si P alors Q».Par exemple :-" 0ÉxÉ25AE)pxÉ5 » est vraie (prendre la racine carrée).-"x2]¡1,¡4[AE)x2Å3x¡4È0 » est vraie (étudier le binôme).-" sin(µ)AE0AE)µAE0 » est fausse (regarderpourµAE2¼par exemple).-p2AE2 » est vraie! Eh oui, siPest fausse alors l"assertion "PAE)Q» est" 2Å2AE5AE)toujours vraie.L'équivalence()L"équivalenceest définie par :"P()Q» est l"assertion "(PAE)Q) et (QAE)P)».On dira "Pest équivalent àQ» ou "Péquivaut àQ» ou "Psi et seulement siQ». Cette assertionest vraie lorsquePetQsont vraies ou lorsquePetQsont fausses. La table de vérité est :P\QV FVVFFF VFIGURE5 - Table de vérité de "P()Q»

Exemples :-Pourx,x02R, l"équivalence "x¢x0AE0()(xAE0ou x0AE0) » est vraie.-Voici une équivalencetoujours fausse(quelque soit l"assertionP) : "P()non(P) ».On s"intéresse davantage aux assertions vraies qu"aux fausses, aussi dans la pratique et en dehorsde ce chapitre on écrira "P()Q» ou "PAE)Q» uniquement lorsque ce sont des assertionsvraies. Par exemple si l"on écrit "P()Q» cela sous-entend "P()Qest vraie». Attention rienne dit quePetQsoient vraies. Cela signifie quePetQsont vraies en même temps ou fausses enmême temps.Proposition 1SoientP,Q,Rtrois assertions. Nous avons les équivalences (vraies) suivantes :1.P()non(non(P))2. (P et Q)()(Q et P)3. (P ou Q)()(Q ou P)4.non(P et Q)()(non P)ou(non Q)5.6.P et(Q ou R)non(Pou Q)()(non P)et(non Q)¡¢()(P et Q)ou(P et R)7.¡P ou(Q et R)¢()(P ou Q)et(P ou R)8. "PAE)Q»()"non(Q)AE)non(P) »DémonstrationVoici des exemples de démonstrations :4.Il suffit de comparer les deux assertions "non(P et Q) » et " (non P)ou(non Q) » pour toutes lesvaleurs possibles dePetQ. Par exemple siPest vrai etQest vrai alors "PetQ» est vrai donc"non(P et Q)» est faux; d"autre part (nonP) est faux, (nonQ) est faux donc "(non P)ou(non Q)»est faux. Ainsi dans ce premier cas les assertions sont toutes les deux fausses. On dresse ainsiles deux tables de vérités et comme elles sont égales les deux assertions sont équivalentes.P\QVFVFVFV VFIGURE6 - Tables de vérité de "non(P et Q) » et de " (non P)ou(non Q) »6.On fait la même chose mais il y a trois variables :P,Q,R. On compare donc les tables de vérité¢pd"abord dans le cas oùPest vrai¡(à gauche), uis dans le cas oùPest faux (à droite). Dans lesdeux cas les deux assertions "P et(Q ou R) » et " (P et Q)ou(P et R) » ont la même table devérité donc les assertions sont équivalentes.Q\RV FVVVFVFQ\RVFVFFFFF8. Par définition, l"implication "PAE)Q» est l"assertion "(non P) ou Q».Donc l"implication "non(Q)AE)non(P)» est équivalente à "non(non(Q))ou non(P)» qui équivautencore à "Q ou non(P) » et donc est équivalente à "PAE)Q». On aurait aussi pu encore unefois dresser les deux tables de vérité et voir quelles sont égales.

1.2. QuantificateursLe quantificateur8: "pour tout»Une assertionPpeut dépendre d'un paramètrex, par exemple "x2Ê1 », l'assertionP(x) est vraieou fausse selon la valeur dex.L'assertion8x2E P(x)est une assertion vraie lorsque les assertionsP(x) sont vraies pour tous les élémentsxde l'en-sembleE.On lit "Pour toutxappartenant àE,P(x) », sous-entendu "Pour toutxappartenant àE,P(x)estvraie».Par exemple :-"8x2[1,Å1[ (x2Ê1) » est une assertion vraie.-"8x2R(x2Ê1) » est une assertion fausse.-"8n2Nn(nÅ1)est divisible par2 » est vraie.Le quantificateur9: "il existe»L'assertion9x2E P(x)est une assertion vraie lorsque l'on peut trouver au moins unxdeEpour lequelP(x) est vraie. Onlit "il existe x appartenant à E tel que P(x)(soit vraie)».Par exemple :-"9x2R(x(x¡1)Ç0) » est vraie (par exemplexAE12vérie bien la propriété).-"9n2Nn2¡nÈn» est vraie (il y a plein de choix, par exemplenAE3 convient, mais aussinAE10 ou mêmenAE100, un seul suft pour dire que l'assertion est vraie).-"9x2R(x2AE¡1) » est fausse (aucun réel au carré ne donnera un nombre négatif).La négation des quantificateursLa négation de "8x2E P(x) » est "9x2E non P(x) » .Par exemple la négation de "8x2[1,Å1[ (x2Ê1) » est l'assertion "9x2[1,Å1[ (x2Ç1) ». Eneffet la négation dex2Ê1 est non(x2Ê1) mais s'écrit plus simplementx2Ç1.La négation de "9x2E P(x) » est "8x2E non P(x) ».Voici des exemples :-La négation de "9z2C(z2ÅzÅ1AE0) » est "8z2C(z2ÅzÅ16AE0) ».-La négation de "8x2R(xÅ12Z) » est "9x2R(xÅ1ÝZ) ».-Ce n'est pas plus difcile d'écrire la négation de phrases complexes. Pour l'assertion :8x2R9yÈ0 (xÅyÈ10)sa négationest9x2R8yÈ0(xÅyÉ10).

RemarquesL"ordre des quantificateurs est très important. Par exemple les deux phrases logiques8x2R9y2R(xÅyÈ0) et9y2R8x2R(xÅyÈ0).sont différentes. La première est vraie, la seconde est fausse. En effet une phrase logique se lit degauche à droite, ainsi la première phrase affirme "Pour tout réelx, il existe un réely(qui peut doncdépendre dex) tel quexÅyÈ0.» (par exemple on peut prendreyAExÅ1). C"est donc une phrasevraie. Par contre la deuxième se lit : "Il existe un réely, tel que pour tout réelx,xÅyÈ0.» Cettephrase est fausse, cela ne peut pas être le mêmeyqui convient pour tous lesx!On retrouve la même différence dans les phrases en français suivantes. Voici une phrase vraie"Pour toute personne, il existe un numéro de téléphone», bien sûr le numéro dépend de la personne.Par contre cette phrase est fausse : "Il existe un numéro, pour toutes les personnes». Ce serait lemême numéro pour tout le monde!Terminons avec d"autres remarques.-Quand on écrit "9x2R(f(x)AE0) » cela signifie juste qu"il existe un réel pour lequelfs"annule. Rien ne dit que cexest unique. Dans un premier temps vous pouvez lire la phraseainsi : "il existeau moinsun réelxtel quef(x)AE0 ». Afin de préciser quefs"annule en uneunique valeur, on rajoute un point d"exclamation :9!x2R(f(x)AE0).-Pour la négation d"une phrase logique, il n"est pas nécessaire de savoir si la phrase estfausse ou vraie. Le procédé est algorithmique : on change le "pour tout» en "il existe» etinversement, puis on prend la négation de l"assertionP.-Pour la négation d"une proposition, il faut être précis : la négation de l"inégalité stricte "Ç»est l"inégalité large "Ê», et inversement.-Les quantificateurs ne sont pas des abréviations. Soit vous écrivez une phrase en français :"Pour tout réel x, si f(x)AE1alors xÊ0.» , soit vous écrivez la phrase logique :8x2R(f(x)AE1AE)xÊ0).Mais surtout n"écrivez pas "8xréel, sif(x)AE1AE)xpositif ou nul». Enfin, pour passerd"une ligne à l"autre d"un raisonnement, préférez plutôt "donc» à "AE)».-Il est défendu d"écrire69,6AE). Ces symboles n"existent pas!Mini-exercices1.Écrire la table de vérité du "ou exclusif». (C"est leoudans la phrase "fromage oudessert», l"un ou l"autre mais pas les deux.)2. Écrire la table de vérité de "non (P et Q)». Que remarquez vous?3. Écrire la négation de "PAE)Q».4. Démontrer les assertions restantes de la proposition1.5. Écrire la négation de "¡¢P et(Q ou R) ».6.Écrire à l"aide des quantificateurs la phrase suivante : "Pour tout nombre réel, son carréest positif». Puis écrire la négation.

DémonstrationNous supposons quenn"est pas pair. Nous voulons montrer qu"alorsn2n"est pas pair. Commenn"est pas pair, il est impair et donc il existek2Ntel quenAE2kÅ1. Alorsn2AE(2kÅ1)2AE4k2Å4kÅ1AE2`Å1 avec`AE2k2Å2k2N. Et doncn2est impair.Conclusion : nous avons montré que sinest impair alorsn2est impair. Par contraposition ceciest équivalent à : sin2est pair alorsnest pair.2.4. AbsurdeLeraisonnement par l"absurdepour montrer "PAE)Q» repose sur le principe suivant : onsuppose à la fois quePest vraie et queQest fausse et on cherche une contradiction. Ainsi siPestvraie alorsQdoit être vraie et donc "PAE)Q» est vraie.Exemple 4Soienta,bÊ0. Montrer que sia1ÅbAEb1ÅaalorsaAEb.DémonstrationNous raisonnons par l"absurde en supposant quea1ÅbAEb1Åaeta6AEb. Commea1ÅbAEb1Åaalorsa(1Åa)AEb(1Åb) doncaÅa2AEbÅb2d"oùa2¡b2AEb¡a. Cela conduit à (a¡b)(aÅb)AE¡(a¡b).Commea6AEbalorsa¡b6AE0 et donc en divisant para¡bon obtientaÅbAE¡1. La somme de deuxnombres positifs ne peut être négative. Nous obtenons une contradiction.Conclusion : sia1ÅbAEb1ÅaalorsaAEb.Dans la pratique, on peut choisir indifféremment entre un raisonnement par contraposition ou parl"absurde. Attention cependant de bien écrire quel type de raisonnement vous choisissez et surtoutde ne pas changer en cours de rédaction!2.5. Contre-exempleSi l"on veut montrer qu"une assertion du type "8x2E P(x) » est vraie alors pour chaquexdeEil faut montrer queP(x) est vraie. Par contre pour montrer que cette assertion est fausse alorsil suffit de trouverx2Etel queP(x) soit fausse. (Rappelez-vous la négation de "8x2E P(x) »est "9x2E non P(x) »). Trouver un telxc"est trouver uncontre-exempleà l"assertion "8x2E P(x) ».Exemple 5Montrer que l"assertion suivante est fausse "Tout entier positif est somme de trois carrés».(Les carrés sont les 02, 12, 22, 32,... Par exemple 6AE22Å12Å12.)DémonstrationUn contre-exemple est 7 : les carrés inférieurs à 7 sont 0, 1, 4 mais avec trois de ces nombres onne peut faire 7.2.6. RécurrenceLeprincipe de récurrencepermet de montrer qu"une assertionP(n), dépendant den, estvraie pour toutn2N. La démonstration par récurrence se déroule en trois étapes : lors del"initialisationon prouveP(0). Pour l"étape d"hérédité, on supposenÊ0 donné avecP(n) vraie,et on démontre alors que l"assertionP(nÅ1) au rang suivant est vraie. Enfin dans laconclusion,on rappelle que par le principe de récurrenceP(n) est vraie pour toutn2N.

1.Uneassertionest une phrase soit vraie, soit fausse, pas les deux en même temps.Exemples :-"Il pleut.»-"Je suis plus grand que toi.»-" 2Å2AE4 »-" 2£3AE7 »-"Pour tout x2R, on a x2Ê0.»SiPest une assertion etQest une autre assertion, nous allons définir de nouvelles assertionsconstruites à partir dePet deQ.L"opérateur logique "et»L"assertion "PetQ» est vraie siPest vraie etQest vraie. L"assertion "P et Q» est fausse sinon.On résume ceci en unetable de vérité:P\QVFVVFFF FFIGURE1 - Table de vérité de "P et Q»Par exemple siPest l"assertion "Cette carte est un as» etQl"assertion "Cette carte est coeur» alorsl"assertion "P et Q» est vraie si la carte est l"as de coeur et est fausse pour toute autre carte.L"opérateur logique "ou»L"assertion "PouQ» est vraie si l"une des deux assertionsPouQest vraie. L"assertion "PouQ»est fausse si les deux assertionsPetQsont fausses.On reprend ceci dans la table de vérité :P\QVFVVVFV FFIGURE2 - Table de vérité de "P ou Q»

SiPest l"assertion "Cette carte est un as» etQl"assertion "Cette carte est coeur» alors l"assertion"PouQ» est vraie si la carte est un as ou bien un coeur (en particulier elle est vraie pour l"as decoeur).RemarquePour définir les opérateurs "ou», "et» on fait appel à une phrase en français utilisant lesmotsou,et! Les tables de vérités permettent d"éviter ce problème.La négation "non»L"assertion "nonP» est vraie siPest fausse, et fausse siPest vraie.PV FnonPF VFIGURE3 - Table de vérité de "non P»L'implicationAE)La définition mathématique est la suivante :L"assertion "(non P) ou Q» est notée "PAE)Q».Sa table de vérité est donc la suivante :P\QVFVVFFVVFIGURE4 - Table de vérité de "PAE)Q»L"assertion "PAE)Q» se lit en français "P implique Q».Elle se lit souvent aussi "si P est vraie alors Q est vraie» ou "si P alors Q».Par exemple :-" 0ÉxÉ25AE)pxÉ5 » est vraie (prendre la racine carrée).-"x2]¡1,¡4[AE)x2Å3x¡4È0 » est vraie (étudier le binôme).-" sin(µ)AE0AE)µAE0 » est fausse (regarderpourµAE2¼par exemple).-p2AE2 » est vraie! Eh oui, siPest fausse alors l"assertion "PAE)Q» est" 2Å2AE5AE)toujours vraie.L'équivalence()L"équivalenceest définie par :"P()Q» est l"assertion "(PAE)Q) et (QAE)P)».On dira "Pest équivalent àQ» ou "Péquivaut àQ» ou "Psi et seulement siQ». Cette assertionest vraie lorsquePetQsont vraies ou lorsquePetQsont fausses. La table de vérité est :P\QV FVVFFF VFIGURE5 - Table de vérité de "P()Q»

Exemples :-Pourx,x02R, l"équivalence "x¢x0AE0()(xAE0ou x0AE0) » est vraie.-Voici une équivalencetoujours fausse(quelque soit l"assertionP) : "P()non(P) ».On s"intéresse davantage aux assertions vraies qu"aux fausses, aussi dans la pratique et en dehorsde ce chapitre on écrira "P()Q» ou "PAE)Q» uniquement lorsque ce sont des assertionsvraies. Par exemple si l"on écrit "P()Q» cela sous-entend "P()Qest vraie». Attention rienne dit quePetQsoient vraies. Cela signifie quePetQsont vraies en même temps ou fausses enmême temps.Proposition 1SoientP,Q,Rtrois assertions. Nous avons les équivalences (vraies) suivantes :1.P()non(non(P))2. (P et Q)()(Q et P)3. (P ou Q)()(Q ou P)4.non(P et Q)()(non P)ou(non Q)5.6.P et(Q ou R)non(Pou Q)()(non P)et(non Q)¡¢()(P et Q)ou(P et R)7.¡P ou(Q et R)¢()(P ou Q)et(P ou R)8. "PAE)Q»()"non(Q)AE)non(P) »DémonstrationVoici des exemples de démonstrations :4.Il suffit de comparer les deux assertions "non(P et Q) » et " (non P)ou(non Q) » pour toutes lesvaleurs possibles dePetQ. Par exemple siPest vrai etQest vrai alors "PetQ» est vrai donc"non(P et Q)» est faux; d"autre part (nonP) est faux, (nonQ) est faux donc "(non P)ou(non Q)»est faux. Ainsi dans ce premier cas les assertions sont toutes les deux fausses. On dresse ainsiles deux tables de vérités et comme elles sont égales les deux assertions sont équivalentes.P\QVFVFVFV VFIGURE6 - Tables de vérité de "non(P et Q) » et de " (non P)ou(non Q) »6.On fait la même chose mais il y a trois variables :P,Q,R. On compare donc les tables de vérité¢pd"abord dans le cas oùPest vrai¡(à gauche), uis dans le cas oùPest faux (à droite). Dans lesdeux cas les deux assertions "P et(Q ou R) » et " (P et Q)ou(P et R) » ont la même table devérité donc les assertions sont équivalentes.Q\RV FVVVFVFQ\RVFVFFFFF8. Par définition, l"implication "PAE)Q» est l"assertion "(non P) ou Q».Donc l"implication "non(Q)AE)non(P)» est équivalente à "non(non(Q))ou non(P)» qui équivautencore à "Q ou non(P) » et donc est équivalente à "PAE)Q». On aurait aussi pu encore unefois dresser les deux tables de vérité et voir quelles sont égales.

1.2. QuantificateursLe quantificateur8: "pour tout»Une assertionPpeut dépendre d'un paramètrex, par exemple "x2Ê1 », l'assertionP(x) est vraieou fausse selon la valeur dex.L'assertion8x2E P(x)est une assertion vraie lorsque les assertionsP(x) sont vraies pour tous les élémentsxde l'en-sembleE.On lit "Pour toutxappartenant àE,P(x) », sous-entendu "Pour toutxappartenant àE,P(x)estvraie».Par exemple :-"8x2[1,Å1[ (x2Ê1) » est une assertion vraie.-"8x2R(x2Ê1) » est une assertion fausse.-"8n2Nn(nÅ1)est divisible par2 » est vraie.Le quantificateur9: "il existe»L'assertion9x2E P(x)est une assertion vraie lorsque l'on peut trouver au moins unxdeEpour lequelP(x) est vraie. Onlit "il existe x appartenant à E tel que P(x)(soit vraie)».Par exemple :-"9x2R(x(x¡1)Ç0) » est vraie (par exemplexAE12vérie bien la propriété).-"9n2Nn2¡nÈn» est vraie (il y a plein de choix, par exemplenAE3 convient, mais aussinAE10 ou mêmenAE100, un seul suft pour dire que l'assertion est vraie).-"9x2R(x2AE¡1) » est fausse (aucun réel au carré ne donnera un nombre négatif).La négation des quantificateursLa négation de "8x2E P(x) » est "9x2E non P(x) » .Par exemple la négation de "8x2[1,Å1[ (x2Ê1) » est l'assertion "9x2[1,Å1[ (x2Ç1) ». Eneffet la négation dex2Ê1 est non(x2Ê1) mais s'écrit plus simplementx2Ç1.La négation de "9x2E P(x) » est "8x2E non P(x) ».Voici des exemples :-La négation de "9z2C(z2ÅzÅ1AE0) » est "8z2C(z2ÅzÅ16AE0) ».-La négation de "8x2R(xÅ12Z) » est "9x2R(xÅ1ÝZ) ».-Ce n'est pas plus difcile d'écrire la négation de phrases complexes. Pour l'assertion :8x2R9yÈ0 (xÅyÈ10)sa négationest9x2R8yÈ0(xÅyÉ10).

RemarquesL"ordre des quantificateurs est très important. Par exemple les deux phrases logiques8x2R9y2R(xÅyÈ0) et9y2R8x2R(xÅyÈ0).sont différentes. La première est vraie, la seconde est fausse. En effet une phrase logique se lit degauche à droite, ainsi la première phrase affirme "Pour tout réelx, il existe un réely(qui peut doncdépendre dex) tel quexÅyÈ0.» (par exemple on peut prendreyAExÅ1). C"est donc une phrasevraie. Par contre la deuxième se lit : "Il existe un réely, tel que pour tout réelx,xÅyÈ0.» Cettephrase est fausse, cela ne peut pas être le mêmeyqui convient pour tous lesx!On retrouve la même différence dans les phrases en français suivantes. Voici une phrase vraie"Pour toute personne, il existe un numéro de téléphone», bien sûr le numéro dépend de la personne.Par contre cette phrase est fausse : "Il existe un numéro, pour toutes les personnes». Ce serait lemême numéro pour tout le monde!Terminons avec d"autres remarques.-Quand on écrit "9x2R(f(x)AE0) » cela signifie juste qu"il existe un réel pour lequelfs"annule. Rien ne dit que cexest unique. Dans un premier temps vous pouvez lire la phraseainsi : "il existeau moinsun réelxtel quef(x)AE0 ». Afin de préciser quefs"annule en uneunique valeur, on rajoute un point d"exclamation :9!x2R(f(x)AE0).-Pour la négation d"une phrase logique, il n"est pas nécessaire de savoir si la phrase estfausse ou vraie. Le procédé est algorithmique : on change le "pour tout» en "il existe» etinversement, puis on prend la négation de l"assertionP.-Pour la négation d"une proposition, il faut être précis : la négation de l"inégalité stricte "Ç»est l"inégalité large "Ê», et inversement.-Les quantificateurs ne sont pas des abréviations. Soit vous écrivez une phrase en français :"Pour tout réel x, si f(x)AE1alors xÊ0.» , soit vous écrivez la phrase logique :8x2R(f(x)AE1AE)xÊ0).Mais surtout n"écrivez pas "8xréel, sif(x)AE1AE)xpositif ou nul». Enfin, pour passerd"une ligne à l"autre d"un raisonnement, préférez plutôt "donc» à "AE)».-Il est défendu d"écrire69,6AE). Ces symboles n"existent pas!Mini-exercices1.Écrire la table de vérité du "ou exclusif». (C"est leoudans la phrase "fromage oudessert», l"un ou l"autre mais pas les deux.)2. Écrire la table de vérité de "non (P et Q)». Que remarquez vous?3. Écrire la négation de "PAE)Q».4. Démontrer les assertions restantes de la proposition1.5. Écrire la négation de "¡¢P et(Q ou R) ».6.Écrire à l"aide des quantificateurs la phrase suivante : "Pour tout nombre réel, son carréest positif». Puis écrire la négation.

DémonstrationNous supposons quenn"est pas pair. Nous voulons montrer qu"alorsn2n"est pas pair. Commenn"est pas pair, il est impair et donc il existek2Ntel quenAE2kÅ1. Alorsn2AE(2kÅ1)2AE4k2Å4kÅ1AE2`Å1 avec`AE2k2Å2k2N. Et doncn2est impair.Conclusion : nous avons montré que sinest impair alorsn2est impair. Par contraposition ceciest équivalent à : sin2est pair alorsnest pair.2.4. AbsurdeLeraisonnement par l"absurdepour montrer "PAE)Q» repose sur le principe suivant : onsuppose à la fois quePest vraie et queQest fausse et on cherche une contradiction. Ainsi siPestvraie alorsQdoit être vraie et donc "PAE)Q» est vraie.Exemple 4Soienta,bÊ0. Montrer que sia1ÅbAEb1ÅaalorsaAEb.DémonstrationNous raisonnons par l"absurde en supposant quea1ÅbAEb1Åaeta6AEb. Commea1ÅbAEb1Åaalorsa(1Åa)AEb(1Åb) doncaÅa2AEbÅb2d"oùa2¡b2AEb¡a. Cela conduit à (a¡b)(aÅb)AE¡(a¡b).Commea6AEbalorsa¡b6AE0 et donc en divisant para¡bon obtientaÅbAE¡1. La somme de deuxnombres positifs ne peut être négative. Nous obtenons une contradiction.Conclusion : sia1ÅbAEb1ÅaalorsaAEb.Dans la pratique, on peut choisir indifféremment entre un raisonnement par contraposition ou parl"absurde. Attention cependant de bien écrire quel type de raisonnement vous choisissez et surtoutde ne pas changer en cours de rédaction!2.5. Contre-exempleSi l"on veut montrer qu"une assertion du type "8x2E P(x) » est vraie alors pour chaquexdeEil faut montrer queP(x) est vraie. Par contre pour montrer que cette assertion est fausse alorsil suffit de trouverx2Etel queP(x) soit fausse. (Rappelez-vous la négation de "8x2E P(x) »est "9x2E non P(x) »). Trouver un telxc"est trouver uncontre-exempleà l"assertion "8x2E P(x) ».Exemple 5Montrer que l"assertion suivante est fausse "Tout entier positif est somme de trois carrés».(Les carrés sont les 02, 12, 22, 32,... Par exemple 6AE22Å12Å12.)DémonstrationUn contre-exemple est 7 : les carrés inférieurs à 7 sont 0, 1, 4 mais avec trois de ces nombres onne peut faire 7.2.6. RécurrenceLeprincipe de récurrencepermet de montrer qu"une assertionP(n), dépendant den, estvraie pour toutn2N. La démonstration par récurrence se déroule en trois étapes : lors del"initialisationon prouveP(0). Pour l"étape d"hérédité, on supposenÊ0 donné avecP(n) vraie,et on démontre alors que l"assertionP(nÅ1) au rang suivant est vraie. Enfin dans laconclusion,on rappelle que par le principe de récurrenceP(n) est vraie pour toutn2N.