Éléments de logique

5 1 Montrer une inclusion d’ensembles Soit A et B deux sous-ensembles d’un ensemble E Pour montrer que A ⊂ B, on cosid´ere un ´el´ement quelconque de l’ensemble A et on montre qu’il est ´el´ement de B Exercice -Montrer que A ⊂ A∪ B et A ∩B ⊂ A 5 2 Montrer une ´egalit´e d’ensembles

Chapitre 2 : ensembles - CEREMADE

Un ensemble est une collection d’objets Ces objets sont appelés éléments de l’ensemble Pour dire que x est un élément de l’ensemble E, on écrit x ∈ E Pour dire que x n’est pas un élément de E, on écrit x /∈ E Un ensemble est caractérisé par ses éléments Deux ensembles A et B sont donc égaux s’ils ont les mêmes

M1201 - Mathématiques discrètes Cours 2 - Ensemble

Opérations sur les parties d'un ensemble Règles opératoires Deux autres opérations sur les parties d'un ensemble : la di érence et la di érence symétrique Produit cartésien Cette notion fournit une autre manière de dé nir un ensemble lorsqu'il s'agit d'une partie : F ˘ ' x 2E j P(x) “ Autrement dit, 8 x2E, ¡ 2F ()P( ) ¢

10 Ensembles et applications

10 1 1 Inclusion et ensemble des parties d’un ensemble Définition 10 1 Un ensemble E est une collection ou un groupement d’objets distincts Les objets x de E s’appellent les éléments de E Si E est un ensemble et si x est un élément de E, on dit que x appartient à E et on écrit x 2E

Éléments de logique

Donc démontrer une égalité entre deux ensembles, peut se faire en démontrant une double inclusion – Le produit cartésien se généralise à trois ensembles ou plus généralement à n ensembles : E1 £¢¢¢£En ˘{(x1, ,xn)jx1 2E1, ,xn 2En} Lorsque tous les ensembles sont égaux au même ensemble E, on note E £¢¢¢£E ˘ En

page - 1 - NIVEAU : 1 SM LES ENSEMBLES

B d / k ,20 k d - C p / p 3 2p 5 0 II L’INCLUSION - DOUBLE INCLUSION – ENSEMBLE DES PARTIES D’UN ENSEMBLE: A L’INCLUSION - DOUBLE INCLUSION : 1 L’INCLUSION : a Définition : On dit qu’un ensemble A est un inclus dans un ensemble B si et seulement si tout élément x de A est

Chapitre 0: Logique et raisonnements cours / TD Ce document

• Un ensemble ne contenant qu'un seul élément s'appelle un singleton On note E = {a} • Deux ensembles sont égaux ssi ils ont les mêmes éléments 2 2 Parties d'un ensemble, inclusion: Def: Soit E et A deux ensembles A est une partie, ou un sous-ensemble, de E lorsque tout élément de A est dans E

MATHS BCPST 1 - Dunod

— Pour démontrer l’inclusion E ⊂F ondémontre l’implication x ∈E=⇒ x ∈F → Exercices1 10et1 15 — Pour démontrer l’égalité E =F on raisonne par double-inclusion : ondémontre l’inclusion E ⊂F etl’inclusion réciproque F ⊂E → Exercices1 10,1 15et1 16 — Dans les deux cas, on peut aussi utiliser les opérations

Dénombrement - Mathématiques en ECS1

Il peut donc être intéressant de démontrer une égalité d'ensembles en montrant une inclusion et une égalité de cardinaux Nous verrons cela souvent en algèbre linéaire Méthode 11 1 108 Cours ECS1

Chapitre 1Éléments de logiqueSommaireI Notions ensemblistes. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .11) Vocabulaire lié aux ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .12) Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .3II Notions de logique. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31) Propositions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .32) Connecteurs logiques. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .43) Propriétés. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .54) Quantificateurs. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .65) Retour sur les ensembles. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .6III Le raisonnement. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .81) Raisonnement par l"absurde. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .82) Raisonnement par analyse-synthèse. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .83) Démontrer une implication. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .84) L"équivalence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .95) La récurrence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .9IV Solution des exercices. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .10I NOTIONS ENSEMBLISTES1) Vocabulaire lié aux ensemblesNous ne définirons pas rigoureusement la notion d"ensemble, celle-ci sera considérée comme intuitive.Nous nous contenterons de la "définition» suivante :Un ensembleEest une collection d"objets1, ceux-ci sont appelésélémentsdeE. Sixest un élémentdeEon écrirax2E(se lit "xappartient àE»), dans le cas contraire on écriraxÝE. SiEn"a pasd"éléments on dira que c"est l"ensemble vide et on le notera?. Deux ensemblesEetFsont dits égauxsi et seulement si ils ont les mêmes éléments, on écrira alorsEAEF.Définition 1.1ZExemples:-Les ensembles de nombres :N,Z,D,Q,R,C.-L"ensemble des fonctions deRdansR:F(R,R).-Ensembles définis enextension, comme :EAE{1;8;6;2}(éléments non ordonnés et devant apparaîtreune seule fois dans la liste).-Ensembles définis encompréhension, comme : EAE©p2N¯¯pest impairªAE{2kÅ1jk2N}.1. Cependant toute collection d"objets ne constitue pas forcément un ensemble. Par exemple, le paradoxe de Bertrand Russela montré que l"ensemble des ensembles ne peut pas exister, sinon, la considération de l"ensembleyAE{xjxÝx}conduit à uneabsurdité.MPSI3 (2018-19) LYCÉEMONTAIGNE- 1 -©Fradin Patrick -

Notions de logique Chapitre 1 : Éléments de logiqueABA\BBACB(A)FExercice1.1DécrireP(E)lorsqueEAE{1;2;3}.Remarque 1.1 :-Dire que deux ensemblesAetBsont égaux, revient à dire queAest inclus dansB, et queBest inclusdansA. Doncdémontrer une égalité entre deux ensembles, peut se faire en démontrant une doubleinclusion.-Le produit cartésien se généralise à trois ensembles ou plus généralement à n ensembles :E1£¢¢¢£EnAE{(x1,...,xn)jx12E1,...,xn2En}Lorsque tous les ensembles sont égaux au même ensembleE, on noteE£¢¢¢£EAEEn(ensemble desn-listes, ou n-uplets d"éléments deE).2) PropriétésSoientA,BetCtrois ensembles, on aA[(B\C)AE(A[B)\(A[C). C"est ladistributivitéde la réunionsur l"intersection.De même, on aA\(B[C)AE(A\B)[(A\C). C"est ladistributivitéde l"intersection sur la réunion.Théorème 1.1(Propriétés de la réunion et de l"intersection)Preuve: Ceci sera démontré un peu plus loin.SiAetBsont deux parties d"un ensembleE:-A[CE(A)AEE.-CE(E)AE?,CE(?)AEE.-CE(CE(A))AEA.-CE(A[B)AECE(A)\CE(B)(loi deDe Morgan2).-CE(A\B)AECE(A)[CE(B)(2eloi deDe Morgan).Théorème 1.2(Propriétés du complémentaire)Preuve: Ceci sera démontré un peu plus loin.II NOTIONS DE LOGIQUE1) PropositionsNous nous contenterons de la "définition» suivante :Une proposition est une phrase (ou assertion) qui a un sens mathématique et qui est soit vraie soitfausse3. On dira qu"une proposition n"a que deux valeurs de vérité : vraie (notée V) et fausse (notée F).SiPdésigne une assertion, on notera:Psa négation (lire "nonP»).Définition 1.3(Proposition)ZExemples:-"2 est un entier pair» est une proposition vraie.-"3 est un entier pair» est une proposition fausse.2.DE MORGAN Augustus(1806 - 1871) logicien anglais.3. Il ne doit pas y avoir d"autre alternative selon le principe du tiers exclu.MPSI3 (2018-19) LYCÉEMONTAIGNE- 3 -©Fradin Patrick -

Notions de logique Chapitre 1 : Éléments de logique-"nest un entier pair» n"est pas une proposition car sa valeur de vérité dépend de la valeur den, un tellephrase est appeléeprédicatportant sur la variablenà valeurs dansZ, on pourrait noter ce prédicatP(n) par exemple.-SiAetBdésignent deux ensembles, alors la phraseA½Best une proposition (tous les éléments deAsont éléments de B). Sa négation s"écrit A6½B (un élément de A n"est pas forcément un élément de B).-L"expression "N2R» est une proposition, elle est fausse carNn"est pas un réel.-L"expression "N½R» est une proposition, elle est vraie car tout naturel est aussi un réel.SiPest une proposition, la valeur de vérité de:Pse déduit de celle dePconformément à la table devérité suivante :P:PVFFVPar convention :Dans les raisonnements mathématiques on n"écrit que des propositions vraies. SiPest une proposition,au lieu d"écrire "Pest vraie», on écrit plus simplement "P», et au lieu d"écrire "Pest fausse», on écrit plussimplement ":P », c"est à dire la négation.2) Connecteurs logiquesCeux-ci permettent de relier deux propositions pour en donner une troisième.SoientPetQdeux propositions. On dit que :•la proposition "P^Q» (lire "PetQ») est vraie lorsque les deux propositions le sont simultanément,sinon on dira qu"elle fausse.•la proposition "P_Q» (lire "PouQ») est vraie lorsqu"au moins une des deux propositions est vraie(voire les deux), sinon on dira qu"elle fausse.Définition 1.4(conjonction, disjonction inclusive)PQP^QP_QVVVVVFFVFVFVFFFFSoientPetQdeux propositions. On dit que :• la proposition "PAE)Q» (lire "PimplicationQ») est fausse lorsquePest vraie mais pasQ.•la proposition "P()Q» (lire "PéquivalenceQ») est vraie lorsque les deux propositions ont lamême valeur de vérité.Définition 1.5(implication, équivalence)PQPAE)QP()QVVVVVFFFFVVFFFVVZExemples:-La proposition "(2 est pair)AE)(3 est impair)» est vraie.-La proposition "(2 est impair)AE)(3 est pair)» est vraie4.-La proposition "(2 est pair)AE)(3 est pair)» est fausse.-La proposition "(2 est impair)()(3 est pair)» est vraie.4. Ceci peut paraître surprenant au premier abord, mais nous verrons qu"en écrivant la négation cela devient évident.MPSI3 (2018-19) LYCÉEMONTAIGNE- 4 -©Fradin Patrick -

Notions de logique Chapitre 1 : Éléments de logiqueSoientPetQdeux propositions.• Lorsque la proposition "PAE)Q» est vraie on dit "PimpliqueQ» (ou "siPalorsQ»).•Lorsque la proposition "P()Q» est vraie on dit que "Péquivaut àQ» (ou "Pest équivalent àQ»ou encore "Psi et seulement siQ»).Définition 1.6(implique, équivaut)Principe de déductionSoientPetQdeux propositions, si on sait quePimpliqueQ, et quePest vraie, alors on a forcémentQvraie d"après la définition de l"implication. C"est leprincipe de déduction5.3) PropriétésMaintenant que nous savons ce que sont des propositions équivalentes, nous allons pouvoir établir lespropriétés suivantes :SoientPetQdeux propositions :-La proposition "::P» est équivalente à "P».-La proposition ":(P^Q)» est équivalente à "(:P)_(:Q)» (1reloi deDe Morgan).-La proposition ":(P_Q)» est équivalente à "(:P)^(:Q)» (2eloi deDe Morgan).-L"implication "PAE)Q» est équivalente à "(:P)_Q».-La proposition ":(PAE)Q)» est équivalente à "P^(:Q)».-La proposition "P()Q» est équivalente à "(PAE)Q)^(QAE)P)».-La proposition "P()Q» est équivalente à "(:P)()(:Q)».Théorème 1.3Preuve: La première propriété est évidente. Les autres se montrent avec une table de vérité (à compléter en exercice) :PQ:(P^Q)(:P)_(:Q):(P_Q)(:P)^(:Q)PAE)Q(:P)_QVVVFFVFFPQ:(PAE)Q)P^(:Q)P()Q(PAE)Q)^(QAE)P)(:P)()(:Q)VVVFFVFFZExemple: La négation de la proposition "(2 est impair)AE)(3 est pair)» est équivalente à la proposition "(2est impair)^(3 est impair)», or celle-ci est fausse, et donc la première est vraie.FExercice1.2Sans utiliser de table de vérité, redémontrer (en utilisant les autres propriétés) que :":(PAE)Q)» est équivalente à "P^(:Q)».SoientPetQdeux propositions.• La réciproque de l"implication "PAE)Q» est l"implication "QAE)P».• La contraposée de l"implication "PAE)Q» est l"implication "(:Q)AE)(:P)».Définition 1.7(réciproque, contraposée)Il découle alors du théorème précédent :Une implication et sa contraposée sont équivalentes.Deux propositions sont équivalentes si et seulement si les implications dans les deux sens sont vraies.Théorème 1.45. Par contre, si P implique Q, et que P est fausse, alors on ne peut rien dire de Q.MPSI3 (2018-19) LYCÉEMONTAIGNE- 5 -©Fradin Patrick -

Notions de logique Chapitre 1 : Éléments de logiqueRemarque 1.2 -Ce résultat est à connaître car très utilisé dans les raisonnements (raisonnements par contra-position, raisonnements par double implication).4) QuantificateursLes quantificateurs servent à construire des propositions à partir d"un prédicatP(x), dont la variablexprend ses valeurs dans un certain ensemble E. On rencontre :-Le quantificateuruniversel: "8x2E,P(x)» (se lit "pour toutxdansE,P(x) [sous entendu est vraie]»).Par exemple, la proposition "8x2R,x2>0» se lit "pour tout réelx, le carré dexest positif ou nul», oubien encore "le carré de tout réel est positif».-Le quantificateurexistentiel: "9x2E,P(x)» (se lit "il existe au moins unxdeEtel queP(x) [sousentendu est vraie]»). Par exemple, la proposition "9x2C,x2AE¡1», se lit "il existe au moins un nombrecomplexe dont le carré vaut¡1».Remarque 1.3 :-On rencontre aussi parfois la proposition "9!x2E,P(x)» (se lit "il existe un uniquexdeEtel queP(x)[sous entendu est vraie]»). Par exemple, "9!x2RÅ,x2AE2».-On peut trouver plusieurs quantificateurs dans une même proposition. Par exemple, "8y2RÅ,9!x2RÅ,x2AEy » traduit que tout réel positif est le carré d"un unique réel positif.Les propositions "8x2A,9y2B,P(x,y)» et "9y2B,8x2A,P(x,y)», n"ont pas le même sens. En effet, dans lapremière le ydépendde x alors que dans la seconde il s"agit dumêmey pour tous les x.Attention!Celle-ci est régie par les règles suivantes :a)La négation de8est9(et vice - versa).b)On peut intervertir deux quantificateurs de même nature.c)On ne peut pas intervertir deux quantificateurs de nature différente.À retenir: utilisation des quantificateursZExemples:-L"assertion "8x2RÅ,9y2RÅ,y2AEx» est vraie, elle traduit que tout réel positif (x) est le carré d"aumoins un réel positif (y). Mais l"assertion "9y2RÅ,8x2RÅ,y2AEx» traduit que tout réel positif (x) estle carré d"unmême réel(y), ce qui est évidemment faux. Sa négation est "8y2RÅ,9x2RÅ,y26AEx».-On a toujours l"implication suivante :¡9x2A,8y2B,P(x,y)¢AE)¡8y2B,9x2A,P(x,y)¢.-La négation de "8x2A,9y2B,P(x,y)» est "9x2A,8y2B,:(P(x,y))».FExercice1.31/Traduire dans le langage mathématique : la suite(un)est majorée. Écrire la négation. Qu"en est-il de la suite définiepar unAEn2? Justifier.2/Traduire dans le langage courant les propositions suivantes :a)9y2R,8x2R,x6y.b)9y2N,8x2N,y6x.5) Retour sur les ensemblesSoient A et B deux parties d"un ensemble E.Intersection d"ensemblesSixdésigne un élément deE, démontrer quex2A\B, c"est démontrer la proposition "(x2A) et (x2B)».On peut donc écrire : A\BAE{x2Ejx2A etx2B}.Réunion d"ensemblesSixdésigne un élément deE, démontrer quex2A[B, c"est démontrer la proposition "(x2A) ou (x2B)».On peut donc écrire : A[BAE{x2Ejx2A oux2B}.MPSI3 (2018-19) LYCÉEMONTAIGNE- 6 -©Fradin Patrick -

Notions de logique Chapitre 1 : Éléments de logiqueComplémentaireSixdésigne un élément deE, démontrer quex2CE(A), c"est démontrer la proposition "(xÝA). On peutdonc écrire :CE(A)AE{x2EjxÝA}.Différence d"ensemblesSixdésigne un élément deE, démontrer quex2A\B, c"est démontrer la proposition "(x2A) et (xÝB)».On peut donc écrire : A\BAE{x2Ejx2A etxÝB}, il en découle que A\BAEA\CE(B).Inclusion d"ensemblesDémontrer queAest inclus dansB, c"est démontrer que les éléments deAsont également des élémentsdeB, c"est à dire, pour tout élémentxdeE, on a :x2AAE)x2B. Pour établir ceci, on prend un élémentxquelconquede E, et on démontre la propositionx2AAE)x2B.Égalité d"ensemblesDémontrer que A est égal à B, c"est démontrer la double inclusion : A½B et B½A, c"est à dire, pour toutélémentxdeE, on a : (x2AAE)x2B) et (x2BAE)x2A), ce qui équivaut à :x2A()x2B. Pour établirceci, on prend un élémentxquelconquede E, et on démontre la propositionx2A()x2B.Démontrer que A½B, c"est démontrer :8x2E,x2AAE)x2B.Démontrer que AAEB, c"est démontrer :8x2E,x2A()x2B.À retenirZExemples:-SoientA,BetCtroispartiesd"unensembleE,démontrerladistributivitédelaréunionsurl"intersectionc"est démontrer :8x2E,¡x2A[(B\C)¢()¡x2[A[B]\[A[C]¢On considère unxquelconque dansE, on peut alors montrer l"équivalence avec une table de vérité (àcompléter en exercice) :x2Ax2Bx2Cx2A[(B\C)x2[A[B]\[A[C]VVVVVFVFVVFFFVVFVFFFVFFF-Soient A et B deux parties d"un ensemble E, soitxun élément quelconque de E, alors :x2CE(A[B)() :(x2A[B)() :([x2A]_[x2B])()[xÝA]^[xÝB]()[x2CE(A)]^[x2CE(B)]()x2CE(A)\CE(B)Ce qui prouve queCE(A[B)AECE(A)\CE(B).FExercice1.4En s"inspirant des deux exemples ci-dessus, démontrer le théorème1.1et le théorème1.2.Résoudre une équationUne équation dansR, d"inconnuexréelle peut toujours se mettre sous la formef(x)AE0. Résoudrecette équation dansRc"est déterminer la partieSdeRtelle que "8x2R,f(x)AE0()x2S» (Sest appelél"ensemble des solutions réelles). La définition est la même pour une inéquation dansR.MPSI3 (2018-19) LYCÉEMONTAIGNE- 7 -©Fradin Patrick -

Le raisonnement Chapitre 1 : Éléments de logiqueZExemple: Pour résoudre dansRl"inéquation1xÇ¡1, on écrit :1xÇ¡1()1xÅ1Ç0()xÅ1xÇ0()(xÅ1)xÇ0 etx6AE0()x2]¡1;0[L"ensemble des solutions réelles est donc ]¡1;0[.III LE RAISONNEMENT1) Raisonnement par l"absurdeSoitPune proposition dont on cherche à démontrer qu"elle est vraie. Raisonner par l"absurde c"est fairel"hypothèse quePest fausse, autrement dit, on suppose non(P), on cherche alors à obtenir une contradiction,c"est à dire une propositionQdont sait qu"elle est fausse, et telle que non(P)AE)Q. Si on n"y parvient, celaveut dire que "Qet non(Q)» est vraie, ce qui est impossible car une telle proposition est toujours fausse :c"est le principe de non contradiction. La conclusion est que P est vraie.ZExemple: montrons quep2 est un irrationnel par l"absurde :On suppose quep22Q, on peut écrirep2AEpqavecpetqentiers strictement positifs et premiers entreeux. En élevant au carré on a 2q2AEp2, ce qui entraîne quepest pair et doncpAE2aavecaentier, d"où2q2AE4a2i.e.q2AE2a2, doncqest pair lui aussi et par conséquentpetqne sont pas premiers entre eux :contradiction.2) Raisonnement par analyse-synthèseRaisonner par analyse-synthèse lorsque l"on cherche la ou les solutions à un problème, c"est raisonner endeux étapes qui sont :-l"analyse: on suppose que l"on a une solution du problème et on cherche à en déduire toutes lespropriétés possibles de cette solution, l"objectif étant d"essayer de l"identifier au mieux,-la synthèse: elle consiste à déterminer parmi tous les objets mathématiques ayant les propriétésrequises (obtenues lors de l"analyse), ceux qui sont effectivement solutions du problème.ZExemple: Montrons que toute fonctionf:[0;1]!Rest la somme d"une fonction affine et d"une fonctionqui s"annule en 0 et en 1.•Analyse: supposons qu"il existe une fonctiongqui s"annule en 0 et en 1, ainsi que deux réelsaetbtelsque8x2R,f(x)AEg(x)ÅaxÅb. En évaluant en 0 on doit avoirf(0)AEb, en évaluant en 1 on doit avoirf(1)AEaÅb, d"oùaAEf(1)¡bAEf(1)¡f(0). Maintenant queaetbsont connus, on en déduit quegest lafonctionx7!f(x)¡ax¡b•Synthèse: posonsbAEf(0),aAEf(1)¡f(0) etg:x7!f(x)¡ax¡b. Il est clair quef(x)AEg(x)ÅaxÅb,d"autre partg(0)AEf(0)¡bAE0 etg(1)AEf(1)¡a¡bAEf(1)¡f(1)Åf(0)¡f(0)AE0. Donca,betgsont biensolution du problème et celle-ci est unique.3) Démontrer une implicationPar définition, l"implication "PAE)Q» est fausse lorsquePest vraie etQfausse, elle est vraie dans lesautres cas. En particulier, siPest fausse, l"implication est nécessairement vraie quelque soit la valeur de véritédeQ. Par contre lorsquePest vraie, tout dépend deQ. Nous savons également que l"implication "PAE)Q»est équivalente à sa contraposée ":QAE) :P », donc démontrer l"une c"est démontrer l"autre.•Méthode directe: on suppose que la propositionPest vraie (c"estl"hypothèse), on cherche alors àétablir que nécessairement la proposition Q est vraie elle aussi.•Par l"absurde: on suppose le contraire dePAE)Q, c"est à dire on suppose "P^:Q» (i.e.Pest vraieetQest fausse. On montre alors que ceci conduit à une contradiction, ce qui entraîne que l"hypothèsefaite est fausse et par conséquent PAE)Q.À retenir: pour démontrer une implication.MPSI3 (2018-19) LYCÉEMONTAIGNE- 8 -©Fradin Patrick -

Solution des exercices Chapitre 1 : Éléments de logique2/Même méthode.3/Même méthode.Solution1.6Comme la relation de récurrence est à deux pas, on procède à une récurrence forte avec une initialisationpournAE0etnAE1. NotonsaAE5Åp510,r1AE1Åp52,bAE5¡p510etr2AE1¡p52. On vérifie qu"au rangnAE0on aar01Åbr02AEaÅbAE1AEu0, et que au rangnAE1on aar11Åbr12AEar1Åbr2AE1AEu1. Pour un entiern>1, on suppose la formuleétablie pour tous les entiersk2J0;nK(hypothèse de récurrence forte), on aunÅ1AEunÅun¡1, commenetn¡1sont dansJ0;nK, l"hypothèse permet d"écrireunÅ1AEarn1Åbrn2Åarn¡11Åbrn¡12AEarn¡11[r1Å1]Åbrn¡12[r2Å1], or on peut vérifierquer1Å1AEr21(de même pourr2), on en déduit queunÅ1AEarnÅ11ÅbrnÅ12, c"est la formule au rangnÅ1. La formule estdonc établie pour tout entier n.MPSI3 (2018-19) LYCÉEMONTAIGNE- 11 -©Fradin Patrick -

quotesdbs_dbs9.pdfusesText_15

[PDF] Éléments de logique

Chapitre 4 Quelques types de raisonnement

Chapitre 2 : ensembles - CEREMADE

M1201 - Mathématiques discrètes Cours 2 - Ensemble

10 Ensembles et applications

Éléments de logique

page - 1 - NIVEAU : 1 SM LES ENSEMBLES

Chapitre 0: Logique et raisonnements cours / TD Ce document

MATHS BCPST 1 - Dunod

Dénombrement - Mathématiques en ECS1