Element de logique et methodes de raisonnement avec Exercices Corriges 1.Z/k(k + 1) = 2k 0 , d'ou n 2 - 1 = 4(2k 0 ) = 8k 0 => n 2 - 1 est divisible par 8.(P ? Q P ? Q P ? preuve. Q P ? Q P ? Q P => Q Q => P 1 1 0 0 1 1 1 1 0 0 1 0 0 0 0 1 1 0 1 1 1 0 0 1 1 1 1 1 1.2. Les quantificateurs. Remarque 1.23. Remarque 1.25. ELEMENT DE LOGIQUE ET METHODES DE RAISONNEMENT AVEC EXERCICES CORRIGES Exemple 1.26. ? etudiant ? section 1, ? un groupe sanguin, etudiant a un groupe sanguin. ? un groupe sanguin O-, ? l'etudiant de section 1, l'etudiant a O-. Fausse (cela veut dire que tous les etudiants ont le meme groupe sanguin ce qui est peut probable).(b) n est pair => n 2 est pair, par l'absurde : on suppose que n est pair et que n 2 est impaire contradiction (4) Contre exemple Pour montrer qu'une proposition est fausse il suffit de donner ce qu'on appelle un contre-exemple c'est a dire un cas particulier pour lequel la proposition est fausse.L'implication de deux propositions P, Q est notee : P => Q on dit P implique Q ou bien si P alors Q. P => Q est fausse si P est vraie et Q est fausse, sinon (P => Q) est vraie dans les autres cas.(3) Raisonnement par l'absurde Pour montrer que R est une proposition vraie on suppose que R est vrai et on tombe sur une contradiction (quelque chose d'absurde), quand R : P => Q est une implication par l'absurde on suppose que R : R ?Soit P une proposition, la negation de P est une proposition designant le contraire qu'on note (nonP), ou bien P , on peut aussi trouver la notation eP. Voici sa table de verite.Exprimer les assertions suivantes a l'aide des quantificateurs et repondre aux questions : (1) Le produit de deux nombres pairs est-il pair ?IN/n = 2k, ainsi 2b 2 = 4k 2 b 2 = 2k 2 , on deduit que b est pair aussi or a, b sont premier entre eux contradiction, ce que nous avons suppose au depart est faux c'est a dire ?(2) Methodes du raisonnement par la contraposee Sachant que (P => Q) (Q => P), pour montrer que P => Q on utilise la contraposee, c'est a dire il suffit de montrer que Q => P de maniere directe, on suppose que Q est vraie et on montre que P est vraie.(Q => P) (P Q) 1 1 1 1 1 1 1 0 0 1 0 0 0 1 1 0 0 0 0 0 1 1 1 1 8)Proprietes des connecteurs logiques Quelle que soit la valeur de verite des propositions P, Q, R les proprietes suivantes sont toujours vraies.Montrons que k(k + 1) est pair on a deux cas : Si k est pair alors k + 1 est impair donc le produit d'un nombre pair et d'un nombre impair est pair voir exercice 2 question (3). Si k est impair, alors k + 1 est pair donc le produit est pair c'est le meme raisonnement, (il faut savoir que le produit de deux nombre consecutifs est toujours pair).(1) La contraposee de :(Il pleut, alors je prends mon para- pluie), est (je ne prends pas mon parapluie, alors il ne pleut pas).Ecrire a l'aide des quantificateurs les propositions suivantes : (1) P(x) : La fonction f est nulle pour tous x ?Methodes de raisonnement Pour montrer que (P => Q) est vraie on peut utiliser ce qui suit : (1) Methode de raisonnement direct On suppose que P est vraie et on demontre que Q l'est aussi.Par contraposee, on doit montrer que n est impair => n 2 est impair, c'est vrai cas particulier de la question 2), ainsi la proposition n 2 pair => n est pair est verifiee, de plus n pair => n 2 est pair => ?n ?Indiquer lesquelles des propositions suivantes sont vraies et celles qui sont fausses.une proposition est une expression mathematique a laquelle on peut attribuer la valeur de verite vrai ou faux.(1) La negation de : (il pleut, alors je prends mon parapluie), est : (il pleut et je ne prends pas mon parapluie).(1) PQ c'est a dire P n'est pas equivalente a Q lorsque P ; Q ou Q ; P. (2) P Q peut etre lue P si et seulement si Q. Exemple 1.21.Les relations ?x, ?y, P(x, y) et ?y, ?x, P(x, y) sont differentes, dans la premiere y depend de x tandis que dans la seconde y ne depend pas de x. 122.IR : (2x + y0 et 2x + y = 0) est fausse car on ne peut jamais avoir (2x + y0 et 2x + y = 0) en meme temps.Q est fausse si P et Q sont fausses toutes les deux, sinon (P ?Il suffit de montrer que (P => Q) a la meme valeur de verite que (P ?Q), on le voit bien dans la table de verite suivante : P Q P P => Q P ?E, P(x, y) veut dire que x est constante (fixe), il est independant de y qui varie dans E. (2) ?x ?Par contrapo- see il suffit de montrer que si n est pair => n 2 est pair voir l'exemple precedent.IN, n >= n0, Pn(x) est vraie on suit les etapes suivantes : (a) On montre que P(n0) est vraie, (valeur initiale).Z tel que n = 2k + 1 et donc n 2 = 4k 2 + 4k + 1 => n 2 - 1 = 4k 2 + 4k = 4k(k + 1) il suffit de montrer que k(k + 1) est pair.Toute proposition demontree vraie est appelee theoreme (par exemple le theoreme de PYTHAGORE, Thales...) La negation (nonP) , P : Definition 1.4.(1) 2 est un nombre pair et 3 est un nombre premier, cette proposition est vraie (2) 3 = 2, cette proposition est fausse.On dit que P Q si P et Q ont la meme valeur de verite, sinon (P Q) est fausse.Vraie (cela veut dire que chaque etudiant a un groupe sanguin).(b) On suppose que P(n) est vraie a l'ordre n (c) On montre que P(n + 1) est vraie a l'ordre n + 1 Alors P est vrai pour tous n >= n0.IN par l'absurde supposons que n 2 est pair et n est impair, alors ?k ?Ce que nous avons suppose au depart est faux c'est a dire ?n ?(1) Montrons que sa contraposee :( n est impair => (n 2 - 1) est divisible par 8) est vraie.(1) Tout nombre premier est pair , cette proposition est fausse.Q) est vraie si P et Q le sont toutes les deux.x n est pair.(2) P : la fonction f est positive, alors eP : la fonction f n'est pas positive. Soit P, Q deux propositions 1) La conjonction et , ?la conjonction est le connecteur logique et , ? Q) est la conjonction des deux propositions P, Q. - (P ?ELEMENT DE LOGIQUE ET METHODES DE RAISONNEMENT AVEC EXERCICES CORRIGES P Q P ?la disjonction est un connecteur logique ou , ?(2) La contraposee de :( Omar a gagne au loto => Omar a joue au loto), est : (Omar n'a pas joue au loto => Omar n'a pas gagne au loto).la relation il existe un x tel que P(x) est notee : ?x, P(x).(1) Tous les etudiants de la section 1 ont un groupe sanguin. IR : x + y = 0) est vraie en effet ?x ?(3) On peut permuter entre deux quantificateurs de la meme nature : ?x, ?y, P(x, y) ?y, ?x, P(x, y).(5) Raisonnement par recurrence Pour montrer que P(n) : ?n ?ELEMENT DE LOGIQUE ET METHODES DE RAISONNEMENT AVEC EXERCICES CORRIGES (3) ?x ?(4) Un nombre entier est pair si et seulement si son carre est pair ?Z} l'ensemble des nombres pairs.Z} l'ensemble des nombres impairs.(4) Un nombre entier est pair si et seulement si son carre est pair ?Par l'absurde montrer que : (1) ?Exemple 1.2.(2) ?1.1.7 82.[0, 1] ?102.1.3.3.(2) ?> 0, ??< ?< .142.> 0, ??< ?> 0, ??< ??3.(2) (?3.