[PDF] Logique et raisonnements

View - Download Logique et raisonnements

Previous PDF

Next PDF

9782340-019263_001-840.indd 303/07/2017 17:17

9782340-019263_001-840.indd 403/07/2017 17:17

??R´esum´edecours ?Notions de logique

D´efinition : Proposition -.Uneproposition(ou assertion) est un ´enonc´emath´ematique qui

peut prendre deux valeurs : vrai (V) ou faux (F). D´efinition : N´egation d"une proposition -.SoitPune proposition. On appellen´egationdeP et on notenon Pla proposition d´efinie par :?non Pest vraie lorsquePest fausse; ?non Pest fausse lorsquePest vraie. D´efinition : Conjonction de deux propositions -.SoitPetQdeux propositions. On appelle conjonction dePetQla proposition not´eePetQ,etd´efinie de la mani`ere suivante : ?PetQest vraie lorsquePetQsont vraies; ?PetQest fausse lorsque l"une au moins des deux propositions est fausse. D´efinition : Disjonction de deux propositions -.SoitPetQdeux propositions. On appelle

disjonction dePetQla proposition not´eePouQ,etd´efinie de la mani`ere suivante :?PouQest vraie lorsque l"une au moins des deux propositions est vraie;

?PouQest fausse lorsquePetQsont fausses. D´efinition : Implication -.SoitPetQdeux propositions. On appelle implication deQparPla propositionnon P ou Q. Cette proposition se noteP?Q. Vocabulaire :la propositionP?Qse lit?PimpliqueQ?ou encore?siPalorsQ? Remarque :lorsqueP?Qest vraie, on dit quePest unecondition suffisantepour avoirQ, ou queQest unecondition n´ecessairepour avoirP. D´efinition : R´eciproque -.SoitPetQdeux propositions. On appelle r´eciproque deP?Q l"implicationQ?P. D´efinition :´Equivalence -.SoitPetQdeux propositions. On appelle ´equivalence dePetQ la propositionP?QetQ?P. Cette proposition se noteP?Q. Vocabulaire :la propositionP?Qse lit?Psi et seulement siQ?. Remarque :lorsqueP?Qest vraie,Pest unecondition n´ecessaire et suffisantepour avoir Q. Ainsi, les ´equivalences sont les conditions n´ecessaires et suffisantes. Table de v´erit´e des connecteurs logiques :PQnon PPetQPouQP?QP?Q

VVFVVVV

VFFFVFF

FVVFVVF

FFVFFVV

LOGIQUE ET RAISONNEMENTS5??

Remarque :d"apr`es cette table de v´erit´e, siPetP?Qsont vraies alorsQest vraie. C"est le principe de d´eduction.

D´efinition : Contrapos´ee -.SoitPetQdeux propositions. On appelle contrapos´ee de l"implica-

tionP?Ql"implicationnon Q?non P Th´eor`eme 1.1.-SoitPetQdeux propositions. L"implicationP?Qet sa contrapos´ee sont

´equivalentes. Autrement dit :

(P?Q)??(non Q?non P) Proposition 1.2.-SoitPetQdeux propositions. Alors : ?non(non P)??P ?non(PetQ)??(non P)ou(non Q) ?non(PouQ)??(non P)et(non Q) ?non(P?Q)??Pet(non Q) ?Quantificateurs

D´efinition :SoitP(x)une propri´et´ed´ependant d"un param`etrex,o`uxest un ´el´ement d"un en-

sembleE.

•Quantificateur universel :Pour signifier que la propri´et´eP(x)est vraie pour tous les ´el´ements

xdeE,on´ecrit : ?x?E, P(x) Le symbole?est appel´equantificateur universelet se lit?quel que soit?. •Quantificateur existentiel -.Pour signifier que la propri´et´eP(x)est vraie pour au moins un ´el´ementxdeE,on´ecrit : ?x?E, P(x) Le symbole?est appel´equantificateur existentielet se lit?il existe?. Proposition 1.3.- N´egation des propositions avec quantificateurs -. ?La n´egation de la proposition?x?E, P(x)est:?x?E, non P(x). ?La n´egation de la proposition?x?E, P(x)est:?x?E, non P(x). Remarque :attention, l"ordre des quantificateurs est tr`es important. Lorsque plusieurs quantifi- cateurs apparaissent dans une proposition, on ne peut pas intervertir leur ordre sans changer (en g´en´eral) le sens de la proposition. Pour s"en convaincre, on pourra consulter leVrai/Faux. ??6CHAPITRE 1 ?Raisonnement par r´ecurrence Th´eor`eme 1.4." Propri´et´e fondamentale deN-.Toute partie non vide deNadmet un plus petit ´el´ement. Th´eor`eme 1.5.- Principe de r´ecurrence -.SoitP(n) une proposition d´ependant den?N,et n 0 ?N.Si

•Initialisation :la propositionP(n

0 )estvraie,

•H´er´edit´e:pour tout entiern?n

0 ,P(n) impliqueP(n+1); alors la propositionP(n) est vraie pour tout entiern?n 0 Th´eor`eme 1.6.- R´ecurrence double -.SoitP(n) une proposition d´ependant den?N,et n 0 ?N.Si

•Initialisation :les propri´et´esP(n

0 )etP(n 0 +1)sontvraies,

•H´er´edit´e:pour tout entiern?n

0 ,(P(n)etP(n+ 1)) impliqueP(n+2); alors la propositionP(n) est vraie pour tout entiern?n 0

Th´eor`eme 1.7.- Principe de r´ecurrence forte (ou r´ecurrence avec pr´ed´ecesseurs) -.Soit

P(n) une proposition d´ependant den?N,etn

0 ?N.Si

•Initialisation :la propositionP(n

0 )estvraie,

•H´er´edit´e:pour tout entiern?n

0 P(n 0 )etP(n 0 +1)et···etP(n)? impliqueP(n+1); alors la propositionP(n) est vraie pour tout entiern?n 0

LOGIQUE ET RAISONNEMENTS7??

??M´ethodes ?D´emontrer une proposition ?M´ethode 1.1.- Comment d´emontrer une proposition par d´eduction SiPetP?Qsont vraies, alorsQest vraie. C"est leprincipe de d´eduction.C"estun principe tr`es simple que l"on utilise en permanence : si l"on sait qu"une propositionPest

vraie (propri´et´educours,r´esultat d"une question ant´erieure...) et que l"on sait d´emontrer

P?Q, alors on a d´emontr´e que la propositionQest vraie.

Exemple :montrer que, pour toutx?R,x

2 -4x+5>0. On ax 2 -4x+5=x 2 -4x+4+1=(x-2) 2 +1.Or,(x-2) 2 ?0 (le carr´e d"un r´eel est positif) et 1>0. Par cons´equent, (x-2) 2 +1>0, c"est-`a-direx 2 -4x+5>0.

Mise en œuvre : tous les exercices!

?M´ethode 1.2.- Comment d´emontrer une proposition par disjonction de cas On est parfois amen´e`a distinguer plusieurs cas pour d´emontrer qu"une proposition est vraie. C"est le principe d"une d´emonstration pardisjonction de cas. En particulier, si l"on souhaite d´emontrer qu"une propositionP(x) est vraie pour tous les ´el´ementsxd"un ensembleE, on peut prouver la proposition pour tous les ´el´ements d"une partieAdeE, puis pour les ´el´ements deEn"appartenant pas `aA.

Exemple :montrer que, pour toutn?N,

n(n+1) 2 est un entier naturel.

Soitn?N.Onvad´emontrer que

n(n+1) 2 ?Nen distinguant les casnpair ou impair. ?Sinest pair, on peut ´ecriren=2k,o`uk?N.Alors n(n+1) 2

2k(2k+1)

2 =k(2k+1)?N. ?Sinest impair, on an=2p+1,o`up?N.Alors n(n+1) 2 (2p+1)(2p+2) 2 =(2p+1)(p+1)?N.

Finalement, pour tout entier natureln,

n(n+1) 2 ?N.

Mise en œuvre : exercice 1.5, exercice 1.6.

?M´ethode 1.3.- Comment d´emontrer une proposition par l"absurde Pour d´emontrer qu"une propositionPest vraie, on peut utiliser unraisonnement par l"absurde. Pour cela, on suppose quePest fausse et on d´emontre que l"on aboutit alors `a une contradiction. Exemple :montrer qu"il n"existe pas d"entier naturel sup´erieur `a tous les autres. Nous allons d´emontrer cette proposition en raisonnant par l"absurde. Pour cela, on suppose qu"il existe un entier naturelN 0 sup´erieur `a tous les autres. On a alors, pour toutn?N,n?N 0 .La relation est donc vraie pour l"entiern=N 0 +1,doncN 0 +1?N 0 ; d"o`u1?0, ce qui est faux! Par cons´equent, il n"existe pas d"entier naturel sup´erieur `a tous les autres.

Mise en œuvre : exercice 1.9, exercice 1.12.

??8CHAPITRE 1 ?D´emontrer une implication ?M´ethode 1.4.- Comment d´emontrer une implication par raisonnement direct Pour montrer directement l"implicationP?Q, on suppose quePest vraie et on d´emontre queQest vraie. La d´emonstration commence par ?supposons quePest vraie ?et se termine par?Qest vraie?.

Exemple :d´emontrer que, pourxetyr´eels,x

2 =y 2 =?|x|=|y|.

Soitxetydeux r´eels tels quex

2 =y 2 . On a doncx 2 -y 2 =0,soit(x-y)(x+y)=0. Par cons´equent,x-y=0oux+y= 0. Ainsi,x=youx=-y,cequisignifieque|x|=|y|(xet ysont ´egaux ou oppos´es). On a donc d´emontr´e l"implication attendue. ?M´ethode 1.5.- Comment d´emontrer une implication par contraposition Le raisonnement par contraposition est bas´esurleth´eor`eme 1.1: l"implicationP?Qest ´equivalente `a sa contrapos´eenon Q?non P. Ainsi, pour montrer que l"implicationP?Qest vraie, on peut prouver que l"implication non Q?non Pest vraie. En pratique, on suppose donc quenon Qest vraie et on montre quenon Pest vraie.

Exemple :soitnun entier naturel. Montrer que, sin

2 est pair, alorsnest pair.

La proposition `ad´emontrer s"´ecrit :

?n 2 est pair?nest pair?. Nous allons raisonner par contraposition en d´emontrant la proposition (´equivalente) : ?nn"est pas pair?n 2 n"est pas pair ?,c"est-`a-dire?nest impair?n 2 est impair?.Consid´erons un entier impairn:ilexiste donck?Ntel quen=2k+ 1. On a alorsn 2 =(2k+1) 2 =4k 2 +4k+1,cequis"´ecrit aussi n 2 =2p+1,o`up=2k 2 +2k.Parcons´equent,n 2 est un entier impair, ce qui d´emontre l"implication : sinest impair, alorsn 2 est impair. Par contraposition, nous avons donc montr´e l"implication : si n 2 est pair, alorsnest pair.

Exemple :montrer l"implication

?x/?Q?1+x/?Q?. Nous allons de nouveau utiliser la contrapos´ee en d´emontrant l"implication ?1+x?Q?x?Q?. Soitxun r´eel tel que 1+x?Q.Onpeut´ecrirex=(1+x)-1. Or 1+xest un nombre rationnel (hypoth`ese), et 1 aussi. Par cons´equent, (1 +x)-1 est un nombre rationnel, ce qui montre que x?Q. Par contraposition, on a d´emontr´e l"implication ?x/?Q?1+x/?Q?.

Mise en œuvre : exercice 1.8

?M´ethode 1.6.- Comment d´emontrer une implication par l"absurde L"implicationP?Qest la propositionnonP ou Q,san´egation est doncPetnonQ.quotesdbs_dbs35.pdfusesText_40

[PDF] raisonnement par l'absurde français

[PDF] cadhérine

[PDF] fonction des récepteurs membranaires

[PDF] matrice extracellulaire

[PDF] molecule arn

[PDF] principe de raisonnement ? partir de cas

[PDF] phase de raisonnement synonyme

[PDF] raisonnement par cas

[PDF] lemme

[PDF] case based reasoning example

[PDF] samarium

[PDF] case based reasoning algorithm

[PDF] molecule de l'air

[PDF] molécule d'air formule

[PDF] l'air un mélange de molécules 4ème