[PDF] Fondamentaux pour les Mathématiques et lInformatique

View - Download Fondamentaux pour les Mathématiques et lInformatique

Previous PDF

Next PDF

Universite Bordeaux 1

Licence de Sciences, Technologies, Sante

Mathematiques, Informatique, Sciences de la Matiere et Ingenierie M1MI1002 Fondamentaux pour les Mathematiques et l'Informatique

Fondamentaux pour les Mathematiques et

l'Informatique

FASCICULE D'EXERCICES

Table des matieres

Avant-propos 5

1 Rudiments de logique 7

1.1 Operations logiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

1.2 Quanticateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

1.3 Raisonnement par l'absurde . . . . . . . . . . . . . . . . . . . . . . . . .

1 1

1.4 Raisonnement par la contraposee . . . . . . . . . . . . . . . . . . . . . .

1 2

1.5 Raisonnement par recurrence . . . . . . . . . . . . . . . . . . . . . . . .

12

2 Ensembles et applications 15

2.1 Ensembles . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 5

2.2 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1 7

2.2.1 Images, antecedents . . . . . . . . . . . . . . . . . . . . . . . . . .

17

2.2.2 Image directe et image reciproque . . . . . . . . . . . . . . . . . .

18

2.2.3 Composition des applications . . . . . . . . . . . . . . . . . . . .

18

2.2.4 Injection, surjection, bijection . . . . . . . . . . . . . . . . . . . .

19

2.2.5 Autres exercices . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 2

2.3 Relations binaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

24

3 Denombrement 29

3.1 Ensembles nis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2 9

3.2 Problemes de denombrement . . . . . . . . . . . . . . . . . . . . . . . . .

3 0

3.3 Proprietes des coecients binomiaux . . . . . . . . . . . . . . . . . . . .

33

3.4 Manipulation de sommes . . . . . . . . . . . . . . . . . . . . . . . . . . .

3 4

4 Devoirs surveilles des annees anterieures 35

3 4

Avant-propos

Ce fascicule rassemble un choix d'exercices couvrant le programme de l'UEM1MI1002 "Fondements pour les Mathematiques et l'Informatique". Il s'agit a la fois d'une base dans laquelle on pourra puiser les exercices a developper en travaux diriges, et d'un outil de travail personnel pour les etudiants. Il va de soi que l'on ne pourra traiter l'integralite de ces exercices pendant les 21 seances de cours/travaux diriges. Les exercices proposes sont de diculte assez variable : les enonces juges un peu plus diciles sont signales par des etoilesF. Le contr^ole des connaissances consiste, pour cette UE, en : deux devoirs surveilles d'une duree d'1h30, aectes chacun d'un coecient 0:4, de tests, pendant les seances de cours, et de devoirs en temps libre dont la moyenne des notes est aectee d'un coecient 0:2. Le style et le niveau des exercices (sans etoile) de ce recueil donnent une indication de ce qui est attendu des etudiants pour les devoirs surveilles. 5 6

Chapitre 1

Rudiments de logique

1.1 Operations logiques

Exercice 1.1.P,QetRdesignent trois propositions logiques. 1. Co nstruirel est ablesd ev erited esp ropositionss uivantes: (a)P)(Q)P) (b)P)(Q)(P^Q)) (c) ( P^Q),(:(P) :Q)) 2.

Ex primersa ns)ni,:

(a):(P,Q) (b):((P_Q))Q) (c):(P)(Q)R)).

Exercice 1.2.

1. L aquelled esfo rmulessu ivantesest equivalente a: P et(P ou Q) ? (a)P et Q (b)P ou Q (c)P (d)Q 2. L aquelled esfo rmulessu ivantesest equivalente a: ( P et Q)ou P? (a)P et Q (b)P ou Q (c)P (d)Q 7

Exercice 1.3.

1.

Q uelleest l an egationd e: ( non P)et Q?

(a)P et(non Q) (b)P ou(non Q) (c) ( non P)ou Q 2.

Q uelleest l an egationd e: P ou(non Q) ?

(a) ( non P)ou Q (b) ( non P)et Q (c) ( non P)et(non Q) (d)P et(non Q) 3.

Q uelleest l an egationd e: ( non P)ou(non Q) ?

(a)P et Q (b)P ou Q (c) ( non P)et(non Q) Exercice 1.4.Dans un journal est annoncee la nouvelle suivante : L'armee ne quittera pas le pays tant que le calme n'est pas revenu. En considerant l'annonce ocielle precedente comme vraie, dire si les argumentations suivantes sont correctes : 1. " Lecal meest r evenu,d oncl 'armeeq uittel ep ays." 2. " L'armeeq uittel ep ays,d oncl ec almee stre venu." 3. " L'armeen 'ap asq uittel ep ays,d oncl ec almen 'estp asr evenu." Exercice 1.5.On suppose queaetbsont des nombres reels. Representer par une formule logique la valeur de chacune des expressions suivantes en langagePython:

1.if a > b :

a < 2*b else: True

2.if a > b :

a < 2*b else: False

3.if a > b :

a < 2*b else: b < 3*a 8

1.2 Quanticateurs

Exercice 1.6.

Ecrire les negations logiques des propositions suivantes : 1. ( x21^x3<2)_(x29^x <0).

2.8x2R;x <1)x2<1.

3.8p2N;8n2Z; pn.

4. " Touti ntervalled eRcontient un element de l'intervalle [0;1]." Exercice 1.7.SoitEun ensemble etAetBdeux parties deE. La denition de ABest \tout element deAest element deB".A quelle(s) proposition(s) ci-dessous cela correspond-il? {8x2A;x2B {8x2E;(x2B)x2A) {8y2E;(y2A)y2B) ( 8x2E;x2A))(8x2E;x2B) Exercice 1.8.Sifest une application deRdansR, la denition de\f est bornee"est \9M2R;8x2R;jf(x)j M". Donner la denition de \f n'est pas bornee". La denition de \fest croissante" est \8(x;y)2R2;xy)f(x)f(y)". Donner la denition de \f n'est pas croissante". Exercice 1.9.Pour chacune des propositions suivantes, donner sa negation, et dire si elle est vraie ou fausse (en justiant la reponse)

1.8x2R;x2>0

2.8x2R;x2>0

3.9x2R;x2>0

4.8x2R;px

2=x 5. ( 8x2R)(9y2R)(x+y= 0) 6. ( 9y2R)(8x2R)(x+y= 0).

Exercice 1.10.

Ecrire sous la forme d'une formule avec quanticateurs les enonces suivants : 1. T outen tiern aturelp ossedeu ner acineca rreer eelle. 2. T outen tiern aturelp ossedeu nr eelp ositifp lusg randq uel ui. 3. Il ex isteu nr eelp lusp etitq uet ousl ese ntiersn aturels. 4.

L 'intervalleIest inclus dans [1;2].

9

Exercice 1.11.

1. S oienta;bdeux entiers naturels et soitn=ab. Completer les phrases suivantes an qu'elles soient vraies (il peut y avoir plusieurs solutions possibles) : (a) . ..etu nm ultipled ea. (b)bet un diviseur de .... (c)nest divisible par .... 2. Ecrire sous forme d'une formule quantiee et demontrer. (a) La so mme( lad ierence)d ed euxen tiersp airsest p aire. (b) L as omme(l ad ierence)d 'unen tierp airet u nen tieri mpaires ti mpaire. (c) L asom me( lad ierence)d ed euxen tiersi mpairse stp aire. 3. Est -ilp ossibled eg eneraliserl es enoncesd el am anieresu ivante? (a) S oitkun entier naturel. La somme (la dierence) de deux multiples dekest toujours un multiple dek. (b) S oitkun entier naturel. La somme (la dierence) de deux entiers divisibles parkest toujours aussi divisible park. (c) S oitkun entier naturel. La somme d'un entier divisible parket un entier non divisible parkn'est jamais divisible park. (d) S oitkun entier naturel. La somme (la dierence) de deux entiers non divisible parkest toujours divisible park. 4. Ecrire sous forme d'une formule quantiee et demontrer. (a)

T outen tierd ivisiblep ar6 est p air.

5. Co mpleterl esp hrasesp ourfor merl esp ropositionq uel 'onp eutd eduired el 'enonce precedent : (a) Il n 'existep asd 'entier. ........q uiso itd ivisiblep ar6 . (b) S iu nen tieres ti mpair,al orsi l. ...........^ etred ivisiblep ar6 . (c) S iu nen tieres tp air,a lorsi l. ...........^ etred ivisiblep ar6. (d) Et re. .....est u neco nditionn ecessairep ourq u'unen tiers oitd ivisiblep ar6. (e) Et re. .....est u neco nditionsu santep ourqu 'unen tiern es oitp asd ivisible par 6. 6. Ecr ireso usfo rmed 'unef ormuleq uantieee td emontrer. (a) S oientkun entier naturel etdun diviseur dek. Montrer que tout entier divisible parkest divisible pard. Exercice 1.12.Traduire par une formule logique la valeur retournee par la fonction

Python

def f(p,q): for n in range(p): if n*n == q: return True return False en supposant que les parametrespetqsont des entiers naturels. 10

1.3 Raisonnement par l'absurde

Exercice 1.13.Montrer par l'absurde que 0 n'est pas racine dex4+ 12x1. Exercice 1.14.Montrer par l'absurde que le polyn^omex43x3+x2x+p2 n'admet pas de racine entiere. Exercice 1.15.Demontrer la propriete suivante par l'absurde : "Tout entier de carre impair est impair " Exercice 1.16.Principe des tiroirsDemontrer que lorsque l'on range (n+ 1) paires de chaussettes dansntiroirs distincts, alors au moins un des tiroirs contient au moins 2 paires de chaussettes. Exercice 1.17.Soitn1 un entier naturel. On se donnen+ 1 reels 0x0x1 xn1. On veut montrer la propriete (P) suivante : Au moins deux de ces reels sont distants de moins de 1n 1. Ecrire a l'aide de quanticateurs une formule logique portant sur les quantites x ixi1equivalente a la propriete (P). 2.

Ecrire la negation de cette formule logique.

3. En d eduireu ned emonstrationp arl 'absurded el ap ropriete( P). Exercice 1.18.Sur une ^le, on trouve deux sortes de personnes : les sinceres, qui disent toujours la verite, et les menteurs, qui mentent toujours. 1. Al icee tB obso ntd euxh abitantsd ecet te^le.Al iced eclare\L'und 'entren ousd eux au moins est un menteur". Montrer par l'absurde que Alice est sincere. Qu'en est-il de Bob? 2. Ch loeet De nisso ntd euxa utresh abitants.C hloed eclare\Je s uism enteuseo u Denis est sincere". Montrer par l'absurde que Chloe est sincere. Qu'en est-il de

Denis?

3. Ga spard,Me lchioret Ba lthazarso ntt roish abitants.Ga spardd eclare: \N ous sommes tous menteurs". Melchior dit : \Un et un seul d'entre nous est sincere". Montrer par l'absurde que Gaspard est un menteur, puis que Melchior est sincere.

Qu'en est-il de Balthazar?

Exercice 1.19.Le but de cet exercice est de montrer par l'absurde quep2est irra- tionnel. Supposons qu'il existe deux entiers naturels tels quep2= 2q2. 1. Mo ntrerq u'onp eutsu pposerq uepetqsont premiers entre eux. 2.

Mo ntrerq uepest pair.

3.

En d eduireq ueqest pair.

4.

En d eduireq uepetqn'existent pas.

11

1.4 Raisonnement par la contraposee

Exercice 1.20.

Ecrire les reciproques et les contraposees des implications suivantes :

1.x6=y)(x+ 1)(y1)6= (x1)(y+ 1).

2. ( 8" >0;jf(x)j< "))(f(x) = 0) Exercice 1.21.Soitnun entier.Enoncer et demontrer la contraposee de l'implication suivante : "Sin2est impair, alorsnest impair." Exercice 1.22.Le but de cet exercice est de demontrer par contraposition la propriete suivante, pourn2N: \ Si l'entier (n21) n'est pas divisible par 8, alors l'entiernest pair " 1. Ecrire la propriete ci-dessus sous la forme d'une formule mathematique. 2. Ecrire la contraposee de la formule donnee a la question 1). 3. En re marquantq u'unen tieri mpairns'ecrit sous la formen= 4k+r, aveck2N etr2 f1;3g(a justier), prouver que la formule de la question 2) est vraie. 4.

A-t -ond emontrel ap roprieted el 'enonce?

Exercice 1.23.Soitx2Run reel.

1.

Q uelleest l aco ntraposeeQ(x) de la proposition

P(x) : \x <0)x < x2"?

2.

D emontrezQ(x).

1.5 Raisonnement par recurrence

Exercice 1.24.Montrer que8n15,3nn!12

n

Exercice 1.25.Montrer que8n2N, on a 2n1n!nn.

Exercice 1.26.Pourn2N, on considere la propriete suivante P n: 2n> n2: 1. Mo ntrerq ue,p ourn3, l'implicationPn=)Pn+1est vraie. 2. Q uelsso ntl esen tiersnpour lesquels la proprietePnest vraie? 12

Exercice 1.27.

1.

Mo ntrerq ue8n2N, on a (n+ 1)!Pn

k=1k!. 2. Mo ntrerq uep ourt outen tiern aturelnet tout reelx >0, on a (1 +x)n1 +nx:

Exercice 1.28.Pourn2N, on pose

a n=nX k=1k; b n=nX k=1k

2;etcn=nX

k=1k 3:

Montrer quean=n(n+ 1)2

,bn=n(n+ 1)(2n+ 1)6 etcn=a2n. Exercice 1.29.Montrer, par recurrence surn, que pour tout couple (x;y) de nombres reels, on a x nyn= (xy)n1X k=0x kyn1k: Indication: remarquer quexn+1yn+1= (xnyn)y+ (xy)xn.

Exercice 1.30.Montrer que8n2Non a

n X k=1(1)kk=(1)n(2n+ 1)14

Exercice 1.31.

1. Mo ntrezq uel as ommed esnpremiers entiers impairs est egal an2. 2. Mo ntrezq uel as ommed escarresdesnpremiers entiers impairs estegal an(2n1)(2n+ 1)3 3. Mo ntrezq uel asom med escubesdesnpremiers entiers impairs est egal a 2n4n2. FExercice 1.32.On denit une suite (un)n2Npar le procede suivant •u0= 1, •un+1=( un2 sinest pair u n+ 1 sinon. Montrer par recurrence que, pour toutn2N, on a :un=(

2n+112

nsinest pair 2 n+112 n+1sinon. 13

Exercice 1.33.Soit (un)n2Nla suite denie par

•u0= 1, •8n2N; un+1=Pn k=0uk.

Montrer que, pour toutn2N, on aun= 2n1.

Exercice 1.34.Trouver l'erreur dans le raisonnement par recurrence suivant : Soit a prouver que si, dans une piece, il se trouvenpersonnes dont au moins une lle, les npersonnes sont des lles. La propriete est evidemment vraie pourn= 1. Supposons-la vraie pourn, et soit dans une piecen+1 personnes, dont une lleF. On fait sortir une personneP, qui n'est pasF. Restent npersonnes dontF: d'apres l'hypothese de recurrence, toutes ces personnes sont des lles. On fait alors sortirFet rentrerP: il se trouve dans la piecenpersonnes qui sont toutes des lles, sauf peut-^etreP; d'apres l'hypothese de recurrence, ce sont donc toutes des lles. On fait rentrerF: il y a bienn+ 1 lles dans la piece. Donc la propriete est vraie pourn+ 1. Exercice 1.35.SoientPnla propriete \9 divise 10n1" etQnla propriete \9 divise 10 n+ 1". 1. Mo ntrerq ues inest un entier,Pn)Pn+1etQn)Qn+1(on pourra utiliser 10 n+1= 10n:(9 + 1)) 2. \ 8n2N;Pn"est-elle vraie? Et\8n2N;Qn"? 14

Chapitre 2

Ensembles et applications

2.1 Ensembles

Exercice 2.1.

1.

S oientA=f2;3;4;5getB=f4;5;6g. Determiner :

A\B ; A[B ;{NA ;{RA ;{NB ;{A[BA

2. S oientl esi ntervalles( deR)I= [1;3] etJ= [2;4]. Determiner :

I\J ; I[J ;{RI ;{RJ ;{R(I[J):

Exercice 2.2.SoitA=f0;1;2;3g. Trouver deux partiesFetGdeAtelles que (FnG)[G=F; puis deux partiesF0etG0deAtelles que (F0nG0)[G06=F0:

A quelle condition surFetGa-t-on (FnG)[G=F?

Exercice 2.3.Montrer que siAetBsont deux parties d'un ensembleE, on a

AB=){EB{EA:

Exercice 2.4.SoientA,B,Ctrois parties d'un ensembleE. On suppose que l'on a les inclusions suivantes :A[BA[CetA\BA\C.

Montrer que l'on a l'inclusionBC.

15 Exercice 2.5.SoientEun ensemble, etF,Gdeux parties deE. Montrer que

FG()F[G=G(){EF[G=E:

Exercice 2.6.SoientA,BetCtrois parties d'un ensembleE. Montrer que

A[B[C= (AnB)[(BnC)[(CnA)[(A\B\C)

Exercice 2.7.SoientA1,A2etA3trois parties d'un ensembleE. Donner une ecriture plus simple des parties{E({EA1[({EA2\{EA3)) et (A1\A2)[(A1\{EA2). Exercice 2.8.Le planetant rapporte a un repere orthonorme, representer les ensembles suivants :

1.f1g f2;3;4g

2.f0;2g f1;3g

3.f1g R

4. [0 ;1][1;2] 5. [0 ;1]R+ 6.RR+ 7.NN 8.ZR Exercice 2.9.SoientAetBdeux parties deE, on appelle dierence symetrique de

AetB, l'ensemble

AB= (AnB)[(BnA)

1.

P ourt outep artieAdeE, determinerEA,AA,A{EAet;A.

2.

Mo ntrerqu e

AB= (A[B)n(A\B)

3.quotesdbs_dbs46.pdfusesText_46

[PDF] la somme de deux multiples de 3 est toujours un multiple de 3

[PDF] La somme de deux nb entiers est 24 L'un des nb est le double de l'autre Quels

[PDF] la somme de deux nombres décimaux est 24

[PDF] La somme de deux nombres entiers est 24 L'un des nombres est le double de l'autre Quels sont ces deux nombres

[PDF] la somme de deux nombres relatifs

[PDF] La somme de deux produits

[PDF] la somme de trois entiers consécutifs est divisible par 3

[PDF] la somme de trois entiers consécutifs est un multiple de 3

[PDF] la somme de trois nombres consécutifs est 24 trouver ces trois nombres

[PDF] la somme de trois nombres consécutifs est 75 quels sont ces trois nombres

[PDF] La somme des carré est egale a 15313

[PDF] La somme des mesures de l'angle

[PDF] la somme du produit

[PDF] la somme du produit de 16 par 4 et de 9

[PDF] La somme et le quotient