Resume Math jan 2010 .pdf

---

À propos / Télécharger Aperçu

---

Ce document au format PDF 1.3 a été généré par Microsoft Word / Mac OS X 10.6.2 Quartz PDFContext, et a été envoyé sur fichier-pdf.fr le 23/12/2009 à 12:42, depuis l'adresse IP 90.42.x.x. La présente page de téléchargement du fichier a été vue 1542 fois.
Taille du document: 3.3 Mo (14 pages).
Confidentialité: fichier public

Aperçu du document

---

Mathématique  :  résumé  
 

Chapitre  1  :  introduction  
 
Addition  et  multiplication  :  
 
 
Binaires  :  opérations  sur  deux  opérandes  
 
Internes  et  partout  définies  :   ∀x, y ∈UnEnsemble : ∃( x ∗ y ) ∈UnEnsemble      
où   ∗  représente   +  ou   × .  
 
Commutatives  :   ∀x, y : x ∗ y = y ∗ x  
 
Associatives  :   ∀x, y,z : ( x ∗ y ) ∗ z = x ∗ ( y ∗ z)  
€
 
 
€
€ €
 
Disposent  
d
’un  
n
eutre  
:
 
€
+  :   0 : ∀x : x + 0 = x  
 
 
€
×  :   1: ∀x : x × 1 = x  
 
 
 
 
0  est  même  absorbant  pour   ×  :   ∀x : x × 0 = 0  
€ €
 
€
Grâce  à  l€
’associativité,  on  peut  même  définir  ces  opérations  comme  des  opérations    
n-­‐aires  :  opérations  sur  n  opérandes.  
€ €
 
 
Résultat  pour   +  
Résultat  pour   ×  
x1 + x 2 + ...+ x n  
x1 × x 2 × ... × x n  
n  opérandes   x n  
1  opérande   x  
x  
x  
0  opérande  
0  
1  
€
€
 
dans  le  cas  ou  n  =  0  le  résultat  est  le  neutre  de  l’opération  considérée  
€
€
  €€
€
€
 
Distributivité  :   ×  distribue   +  :   ∀x, y,z : ( x × y ) + ( x × y ) = x × ( y + z)  
 
(Le  contraire  n’est  pas  correct  :   +  NE  distribue  PAS   × )  
 
 
Symétrisable  
:  2  opérandes  
sont  dites  symétriques  si  leur  composée  par   +  ou   ×  
€
€ €
donne  le  neutre  de  l’opération.  
€
€
 
 
∀x∃y : ( x + y = 0)   opposé  OU   ( x × y = 1) inverse  
 
 
Dans  ,  tous  les  éléments  ont  un  opposé  et  seul  -­‐1  et  1  ont  un  
€inverse.  
 
 

 
€

€

⚠Vrai  dans    mais  pas  forcément  dans  tous  les  ensembles.  
€

Chapitre  2  :  arithmétique  
 
Division  Euclidienne  :  
 
Opération  sur  deux  opérandes  :  m  =  dividende,  d  =  diviseur  
 
m = q : quotient  
division  entière  
d

m ÷ d = r : reste  
modulo  :  reste  de  la  division  euclidienne  
 
  q  et  r  sont  les  seuls  entiers  qui  respectent  ces  trois  affirmations  :  
m = ( d × q) + r

€
€

 

r ≥0

 

r<d
 
Comment  faire  la  division  euclidienne,  visuellement  :  
On  place  la  valeur  de  m  sur  la  droite,  on  va  chercher  le  multiple  de  d  le  plus  proche  en  
€ direction  de   −∞ pour  la  division  euclidienne  (de  sorte  que  le  reste  soit  positif)  et  en  
direction  de  0  pour  les  langages  Java  et  Pascal  par  exemple  (de  sorte  que  le  reste  soit  du  
même  signe  que  m).  Le  multiple  auquel  on  arrive  est  q  et  l’écart  entre  ce  q  et  m  est  le  
reste  r  (non  signé  /  du  même  signe  que  m).  

€

 
La  relation  |  signifie  :  
b | a =  b  est  diviseur  de  a  
  Ex  :  5|15  =  VRAI  
Quelques  propriétés  :    
∀a : a | a

€

 
OU  
/  

a  est  multiple  de  b   OU  
5|12  =  FAUX  

€

∀a,b,c : ( a | b) ( a | c ) ⇒ ( a | b + c ) ( a | b − c )

 

∀a,b,c : ( a | b) ( a | c ) ⇒ ( a | b × c )
∀a,b,c : ( a | b) (b | c ) ⇒ ( a | c )
∀a,b ∈ Naturels : ( a | b) (b | a) ⇒ ( a = b)

€

 

r = a ÷ b = a  modulo   b = 0  

€

Lors  du  calcul  «  modulo  n  »,  chaque  entier  est  remplacé  par  le  reste  de  sa  division  par  n.  
Malheureusement,  si  n  n’est  pas  un  nombre  premier,  on  obtient  un  ensemble  dans  
lequel,  par  exemple,  un  produit  peut  s’annuler  sans  qu’aucun  des  facteurs  ne  soit  nul,  ou  
d’autres  incohérences  qui  peuvent  être  dérangeantes.  
 
Ex  :  modulo  8  :  3  x  4  =  0…  
 
C’est  pourquoi  on  se  cantine  souvent  au  calcul  «  modulo  n  »  avec  un  n  premier.  
Propriété  intéressante  :  (à  partir  d’ici,   ÷  signifiera  «  modulo  »)  
 
∀a,b,c,n : (( a + b) × c ) ÷ n = (( a ÷ n ) + (b ÷ n )) × (c ÷ n ) ÷ n  

[

€
€
€
€
€
€
€

€

]

 
  Ceci  peut  faciliter  considérablement  les  calculs  !!!  
Exemple  :  calcul  de   389 ÷1037€  
1°  :  décomposer  89  en  une  somme  de  puissances  de  2  :  
€
89 = 64 +16 + 8 +1 = (2 6 + 2 4 + 2 3 + 2 0 )  
 
= 364 × 316 × 38 × 31  
Donc  :   389 €
2°  :  calculer  toutes  les  puissances  de  3  successives,  modulo  1037  :  
31 ÷1037  
 
 
=  3  
€ 2
 
 
=  9  
€ 34 ÷1037  
3 ÷1037  
=  9 2 ÷1037   =  81  
38 ÷1037  
=  81 2 ÷1037   =  339  
16
3 ÷1037  
=  339 2 ÷1037   =  851  
2
332 ÷1037
€   =  851 2 ÷1037   =  375  
64
3 ÷1037€   =  375 ÷1037   =  630  
3°  :  effectuer  
€ le  calcul  trouvé  en  1  :  
89
3 ÷1037 €
= ( 364 ÷1037) × ( 316 ÷1037) × ( 38 ÷1037) × ( 31 ÷1037) ÷1037
€
 
389 ÷1037 = (630 × 851 × 339 × 3) ÷1037

[

]

389 ÷1037 = 1017
 
Les  nombres  premiers  :  
Un  nombre  premier  est  un  nombre  admettant  2  diviseurs  :  1  et  lui  même  (1  n’est  donc  
pas  premier  car  il  n’en  a  qu’un  seul).  
Les  nombres  premiers  sont  comme  les  «  atomes  »  de  l’arithmétique  :  tout  nombre  peut  
s’écrire  d’une  et  une  seule  manière  comme  produit  de  nombres  premiers.  
 
Ex  :  1802  =  2  x  2  x  5  x  7  x  13  
Factoriser  un  nombre  en  un  produit  de  nombre  premiers  est  un  «  problème  difficile  »  
càd  qu’il  peut  prendre  un  temps  énorme  car  cela  nécessite  un  nombre  d’opération  
immense  :  on  teste  la  divisibilité  par  d,  on  incrémente  éventuellement  d,  et  on  
recommence,  jusqu’à  atteindre  la  racine  carrée  du  nombre  souhaité…  
Par  contre,  vérifier  que  tel  produit  est  bien  la  factorisation  est  très  simple.  
 
Plus  grand  commun  diviseur  :  deux  nombres  naturels  ont  toujours  au  moins  1  diviseur  
en  commun  :  1,  le  plus  grand  des  diviseurs  commun  est  noté  :  
 
pgcd(a,b)  
Plus  petit  commun  multiple  :  deux  nombres  naturels  ont  toujours  un  multiple  en  
commun  :  leur  produit.  Le  plus  petit  commun  multiple  est  noté  :  
 
ppcm(a,b)  
 
Dans  tous  les  cas,  on  a  :  pgcd(a,b)  *  ppcm(a,b)  =  a  x  b  

Algorithme  d’Euclide  pour  trouver  le  pgcd  :  
Soient  a  et  b  deux  naturels   ≥  2  et  soit  r  le  reste  de  la  division  euclidienne  de  a  par  b  
 
On  a  donc,  de  par  la  théorie  :   a = (b × q) + r  
Si  r  =  0    pgcd(a,b)  
€ =  b  
Sinon,  pgcd(a,b)  =  pgcd(b,r)  
Ex  :  
€
a = 980 b = 378 pgc d (980,378) =
⇒ 980 = 378 × 2 + 224 ⇒ pgcd( 378,224 )
⇒ 378 = 224 × 1+154 ⇒ pgcd(224,154 )
⇒ 224 = 154 × 1+ 70 ⇒ pgcd(154,70)

 

⇒ 154 = 70 × 2 + [14 ] ⇒ pgcd( 70,14 )
⇒ 70 = 14 × 5 + 0 ⇒ [14 ]
Le  pgcd  est  donc  le  dernier  reste  non  nul.  
 
Théorème  de  Bézout  :  
∀a,b ∈ N 0 ,∃α , β ∈ Z : pgcd(a,b) = a × α + b × β  
 
En  français,  le  pgcd  de  deux  nombre  peut  toujours  s’écrire  
comme  une  combinaison  linéaire  de  ces  deux  nombres.  

€

Expriment  le  reste  actuel  en  
fonction  de  m  et  d  à  cette  
étape  

€ Comment  trouver  les  coefficients   α  et   β  ?  

Dresser  le  tableau  suivant  :  (⚠ l’étape  1  est  à  la  3ème  ligne)  
Ici  :  m  =  1330  et  d  =  602
€
€
N°  étape  
m  
d  
r  
q  
α  
/  
/  
1  
2  
3  
4  
5  
…  

€

 
 
1330  
602  
126  
96  
28  
 

 
 
602  
126  
96  
28  
14  
 

1330  
602  
126  
96  
28  
14  
0  
 

 
 
2  
€
=
4  
1  
3  
2  
€
  €

β  

1  
0  
0  
1  
€
1  
-­‐2  
−4
q
×
α
β
q
=
 
=
i−1
i−2 − i × βi−1 =  9  
− i
5  
-­‐11  
-­‐19  
42  
 
€  
€ €€
 
 

 
 
Coefficients  de  Bezout  
 
 pgcd(1330,602) = 14 = ( −19) × 1330 + 42 × 602  
 
Remarques  :    
le  pgcd  est  multiple  de  tous  les  autres  diviseurs  commun  de  a  et  b  :  
∀a,b,c : (c | a) (c | b) ⇒ (c | pgcd(a,b))  
 
parmi  les  diviseurs  de  a  et  b,  seul  le  pgcd  peut  s’écrire  sous  la  forme   a × α + b × β  :  
 
 
∀a,b,d : ( d | a) ( d | b) (∃α, β : d = a × α + b × β) ⇒ d = pgcd(a,b)  
 
€

€
€

€

€

Deux  nombres  sont  dits  «  premiers  entre  eux  »  si  leur  seul  diviseur  commun  est  1,  donc  
si  :   pgcd(a,b) = 1 ⇔ ∃α , β :1 = a × α + b × β ⇔  a(resp.  b)  est  inversible  modulo  b(resp.  a)  
 
Remarques  :  
 
Si  
 est  premier,  et  si  a  n’en  
€ p€
€ est  pas  un  multiple,  a  et  p  sont  premiers  entre  eux  
 
Si  a  divise   b × c ,  et  si  a  et  b  sont  premiers  entre  eux,  alors  a  divise  c  :  
 
 
∀a,b,c : ( a | b × c ) ( pgcd(a,b) = 1) ⇒ ( a | c )  
 
Si  m  est  multiple  de  a  et  b,  premiers  entre  eux,  alors  m  est  multiple  de   a × b  :  
 
  €
∀a,b,m : ( a | m) (b | m) ( pgcd(a,b) = 1) ⇒ ( a × b | m)  
 
€
Calculer  un  inverse  modulo  n  :  
€
 
Soient  n  =  910  et  a  =  291  :  l’inverse  de  291  modulo  910  se  calcule  en  dressant  le  
€
tableau  suivant  :  

 
 
On  a  donc   1 ÷ 910 = (910 × α ) ÷ 910 + (291 × ( −369)) ÷ 910  
  modulo  910  :   1 = 291 × ( −369)  
   ( −369) ÷ 910 = 541   a −1 = 541  
  €
Application  
€ :  résoudre  des  équations  en  modulo  n  :  
 
Ex  :  m€
odulo  97  :   57 × x = 24  
 
 
On  inverse  57  modulo  97  :   57 −1 = 80  
x = 24 × 80 = 77  
 
 
 
€
x = 74  
 
 
modulo  100  :   6 × €
 
 
On  inverse  6  modulo  100  :  ∄  (n’existe  pas)  
€  
 
On  cherche  par  tâtonnement  et  on  trouve  2  solutions  :   x = 29, x = 79  
  Encore  une  preuve  qu’il  vaut  mieux  calculer  modulo  un  nombre  premier  (tous  les  
€
nombres  sont  inversibles)  
€

Chapitre  3  :  cryptage  
 
Ce  chapitre  ne  sera  pas  résumé  ici,  cfr.  Notes  power  point.  
 

Chapitre  4  :  logique  des  propositions  

€

 
Ici  on  ne  se  préoccupera  que  de  savoir  si  une  proposition  a  une  valeur  de  vérité  VRAI  ou  
FAUSSE,  pas  de  savoir  si  elle  a  du  sens,  afin  d’éviter  les  paradoxes.  
 
En  logique,  on  se  dote  de  propositions  élémentaires,  notées   pi  et  de  connecteurs  (ex  :  
négation,  conjonction,  disjonction,  …).  
 
 
Négation  :   ¬p =! p = not ( p) =| p = ...  
¬  
€
On  peut  dresser  un  tableau  de  vérité  dans  lequel  1  vaut  vrai  et  0  faux  :    
0  
1  
 
1  
0  
 
0  
1  
∧  
€
€
 
Conjonction  :   p1 ∧ p2  =  p₁  and  p₂  =  …  
0  
0  
0  
 
1  
0  
1  
 
€
0  
1  
∨  
 
Disjonction  :   p1 ∨ p2  =  p₁  or  p₂  =  …    
€
0  
0  
1  
 
1  
1  
1  
 
 
€
Le  tableau  €
de  vérité  permet  d’établir  la  valeur  de  vérité  d’une  proposition  en  fonction  de  
ses  propositions  élémentaires.  Le  nombre  de  ligne  du  tableau  est  égal  à  2  exposant  le  
nombre  de  propositions  élémentaires.  
 
Propriétés  des  connecteurs  :  
 
Double  négation  :   ¬¬p = p  
p ∧ q = q ∧ p    
 
Commutativité  :  
ET  
        p ∨ q = q ∨ p  
 
Associativité  :  
( p ∧ q) ∧ r = p ∧ (q ∧ r)  
 
 
 
( p ∨ q) ∨ r = p ∨ (q ∨ r)  
€  
 
Distributivité:  
p ∧ (q ∨ r) = ( p ∧ q) ∨ (€p ∧ r)  
€
 
 
 
p ∨ (q ∧ r) = ( p ∨ q) ∧ ( p ∨ r)  
€  
p ∧ p = p  
 
Idempotence  
€ :  
p ∨ p = p  
 
 
 
€  
 
De  Morgan  :      
¬( p ∧ q) = ¬p ∨ ¬q  
€
 
 
 
 
¬( p ∨ q) = ¬p ∧ ¬q  
€
 
€
Remarques  :  
€
p ∧ ¬p = 0
 
  €
p ∨ ¬p = 1
 
 
 
Il  n’y  a  pas  de  priorité  naturelle  de   ∧  sur   ∨ ,  ni  l’inverse.  
 
0  est  absorbant  pour   ∧  et  1  est  absorbant  pour   ∨ .  
€
€

€
€

Les  propositions  suivantes  définissent  l’implication  :  
¬( p ∧ ¬q)
 

€

 
¬p ∨ q
p⇒q
p  est  l’antécédent,  q  est  le  conséquent.  
Le  seul  cas  ou  l’implication  est  fausse  est  si  q  est  faux  et  p  est  vrai.  

 
 
 
€ Si   p ⇒ q  est  vrai,  on  dit  :  
 
p  est  condition  suffisante  de  q  
 
q  est  condition  nécessaire  (ou  logique)  de  p  
 
Equivalence  :   p ⇔ q = ( p ⇒ q) ∧ (q ⇒ p)  
 
Disjonction  exclusive  :   p ⊕ q = ( p ∧ ¬q) ∨ (¬p ∧ q)  
 
€
Equivalence  et  disjonction  sont  négation  l’une  de  l’autre  :   ¬( p ⇔ q) = p ⊕ q  
 
€
Une  tautologie  est  une  proposition  dont  la  valeur  de  vérité  est  toujours  vraie.  
 
  très  utiles  pour  les  démonstrations,  elles  valident  le  raisonnement.  
€
 
Ex  :  la  règle  du  «  modus  ponens  »  :   p ∧ ( p ⇒ q) ⇒ q  
 
 
En  d’autre  termes  :  si  une  implication  est  vraie  et  si  son  antécédent  est  
vrai,  alors  le  conséquent  est  vrai  aussi  
 
€
Comment  s’en  servir  :  exemple  :  
 
Essayons  de  prouver  que  :   ( p ∧ q ⇒ r) ⇒ ( p ⇒ (q ⇒ r))  
 
p ∧ q ⇒ r  
Supposé  vrai  
1°  :    
p ⇒ (q ⇒ r)  
A  prouver  
 
€
 
 
€
p ∧ q ⇒ r  
Supposé  vrai  
2°  :    
€
p  
 
q
⇒
r  
A  prouver  
 
 
€
p ∧ q ⇒ r  
3°  :    
Supposé  vrai  
p  
 
€
q  
 
A  prouver  
r  
€
 
Il  ne  reste  alors  qu’à  appliquer  le  «  modus  ponens  »  et  la  démonstration  est  finie.  
 

€

€

Les  électriciens  utilisent  une  notation  spéciale  :   ¬p  devient   p ,   ∧    ×  et   ∨    +.  
Dans  ce  contexte  (SEULEMENT),   ×  est  prioritaire  sur  +.  
On  retrouve  les  priorités  classiques  :  
p × 1 = p  
p + 0 = p  
p × 0 = 0  
€
€ € €
€
p×q=q× p
€
p+q =q+ p
 
p × (q
€ × r) = ( p × q)€× r
p + (q + r) = ( p + q) + r
p × (q + r) = ( p × q) + ( p × r)
Et  on  en  ajoute  des  plus  spéciales  :  
p +1 = 1
p + (q × r) = ( p + q) × ( p + r)
p× p= p
p+ p = p

 

p= p
p× p=0
p + p =1
p+q = p ×q
p ×q = p+q

€

 
Les  électroniciens  s’intéressent  beaucoup  à  deux  connecteurs  :  nand  et  nor  :  
 
nand  
0  
1  
nor  
0  
1  
0  
1  
1  
0  
0  
0  
1  
1  
0  
1  
0  
1  
 
p  nand  q  =   p × q  
 
p  nor  q  =   p + q  
 
Pourquoi  s’y  intéresser  ?  Ces  deux  connecteurs  sont  dits  «  universels  »,  càd  qu’ils  
suffisent  chacun  pour  construire  n’importe  quel  autre  connecteur.  
€:     négation  :  p  nand  p  =€
 
Ex  
  p × p = p  
 

(

) (

)

conjonction  :  (p  nand  q)  nand  (p  nand  q)  =   p × q × p × q = p × q + p × q = p × q  

€
€

Chapitre  5  :  logique  des  prédicats  

€

 
Contrairement  au  chapitre  précédent  ou  l’on  s’intéressait  aux  proposition  seules(pᵢ),  
dans  ce  chapitre,  nous  nous  intéresserons  aux  prédicats,  càd  les  propositions  dépendant  
d’une  ou  de  plusieurs  variables  (appelons  les   pi ( x ) ).  
 
La  valeur  de  vérité  de   p( x )  dépend  donc  de  la  valeur  numérique  de  x.  
 
€
La  valeur  de  vérité  de ∀x : p( x )  n’est  vraie  que  si p( x ) est  vrai  pour  toutes  les  valeurs  de  
x.   ∀  est  appelé  
€ quantificateur  universel,  il  peut  être  lu  «  pour  tout  ».  
 
La  valeur  de  vérité  de   ∃x : p( x )  n’est  vrai  que  s’il  existe  au  moins  une  valeur  de  x  pour  
€
€
laquelle p( x )  existe.   ∃  est  appelé  quantificateur  existentiel,  il  peut  être  lu  «  il  existe  ».  
 
Un  prédicat  d€u  type  :   ∀x : (x × y = x)  dont  la  valeur  dépend  de  y  est  appelé  un  prédicat  
en  y  :  il  vaut  
€vrai  si  y  est  égal  à  1  et  faux  s’il  vaut  toute  autre  valeur.  
€
La  variable  y,  non  quantifiée,  est  dite  libre.  
La  variable  x,  quantifiée,  est  dite  liée.  
€
Le  prédicat  est  équivalent  à   ∀z : (z × y = z) .  

⚠  Les  quantificateurs   ∀  et   ∃  ne  sont  pas  commutatifs  :   ∀x∃y : p( x, y)  n’est  pas  
équivalente  à   ∃y∀x : p( x, y )  !  En  fait  on  a  une  implication  :   ∃y∀x : p( x, y ) ⇒ ∀x∃y : p( x, y ) .  
€
 
Les  quantificateurs  
€
€sont  commutatifs  ssi  ils  sont  
€de  même  nature  et  consécutifs.  
 
€
€
Comment  nier  un  quantificateur  ?  
¬(∀x : p( x )) ⇔ ∃x : (¬p( x ))
 
 
¬(∃x : p( x )) ⇔ ∀x : (¬p( x ))
 
Les  quantificateurs  sont  chacun  associés  aux  un  connecteurs  de  la  manière  suivante  :    
∀  et   ∧  :  
€
∀x : ( p( x ) ∧ q( x )) ⇔ (∀x : p( x )) ∧ (∀x : q( x ))  
 
∃  et     ∧  :  
∃x : ( p( x ) ∧ q( x )) ⇒ (∃x : p( x )) ∧ (∃x : q( x ))  
 
€
€€ ∀  et   ∨  :  
∃x : ( p( x ) ∨ q( x )) ⇔ (∃x : p( x )) ∨ (∃x : q( x ))  
 
€
€€ ∃  et     ∨  :  
€
€
∀x
:
p
x
 
(
)
( ∨ q( x )) ⇐ (∀x : p( x )) ∨ (∀x : q( x ))  
€
  €€
€ La  notation   ∃!x : p( x )  est  un  raccourci  pour   ∃x : p( x ) ∧ ∀y,z : ( p( y ) ∧ p( z) ⇒ ( y = z))  
€€cette  affirmation  €revient  
Nier  
à  écrire   ∀x : ¬p( x ) ∨ ∃y,z(( y ≠ z) ∧ p( y ) ∧ p( z))  
€
 
€
€

€

Chapitre  6  :  ensembles  
 
Un  ensemble  est  une  collection  non  structurée  d’objets,  à  priori  quelconques.  
Pour  signifier  l’appartenance  à  un  ensemble,  on  écrit  :   x ∈ E .  
Soit  l’objet  appartient  à  l’ensemble  soit  il  n’y  appartient  pas,  il  ne  peut  y  appartenir  
plusieurs  fois.  
Le  nombre  d’éléments  dans  l’ensemble  est  appelé  cardinal  (ou  puissance)  de  
€
l’ensemble  et  se  note  #E  ou   E .  
 
La  représentation  d’un  ensemble  sous  la  forme  d’une  courbe  fermée  (ou  patate),  est  
appelée  diagramme  de  Venn.  L’appartenance  d’un  objet  à  l’ensemble,  est  symbolisée  par  
€
un  point  dans  la  patate.  
 
On  peut  écrire  un  ensemble  en  extension  en  listant  tous  ses  éléments  :  
E = {3,Chaussette,Juliette,vert} (ici   E = 4 )  
Lorsqu’il  n’y  à  pas  d’ambigüité,  on  se  permet  souvent  de  suggérer  une  partie  des  
éléments  :  
 
E = {' a','b',...,' m'}   OU  
E = {1,2,3,...}  
€
€
 
On  peut  aussi  décrire  un  ensemble  en  compréhension  en  énonçant  un  critère  
d’appartenance  à  cet  ensemble  :  
€
€
 
E = x ( x ∈ Z ) ∧ ( x 2 < 4 )  

{

}

 
On  utilise  parfois  une  notation  mixte  :    
E = 2 p, p +1,3p + 7 ( p ∈ N 0 )  
€  
 
Parmi  les  ensembles,  il  en  est  un  qui  est  important  :  l’ensemble  vide,  seul  ensemble  sans  
aucun  éléments,  de  cardinal  0.  Il  s’écrit  de  différentes  façons  :  
€
V = { } = ∅  
 
 
Le  prédicat   x ∈ ∅  est  toujours  faux.  
Par  contre,   ∀x ∈ ∅ : p( x )  est  toujours  vrai.  
€
 
Remarques  
:  
€
 
Un  ensemble  ne  s’appartient  pas.   E ∈ E est  toujours  faux  !  
€
 
Donc,  l’affirmation  suivante,  signifiant  E  est  composé  d’un  élément  :  l’ensemble  E  
est  fausse  :   E = { E },  même  si   E = ∅,  en  effet,   {∅}  est  un  ensemble  de  cardinal  1,  un  
singleton.  
€
 

{

€

}

€

€

Inclusion  :  
 
On  raccourci  l’écriture   ∀x : (( x ∈ A) ⇒ ( x ∈ B))  par   A ⊆ B .  
 
La  négation  de  ceci  est   ∃x : (( x ∈ A) ∧ ( x ∉ B)) .  
Propriétés  de  l’inclusion  :  
∅ ∈ E  est  toujours  
vrai  :  le  vide  appartient  
€ à  chaque  ensemble.  
€
Tout  ensemble  est  inclus  à  lui  même  :   E ⊆ E  
€ égaux  sont  inclus  l’un  dans  l’autre  :    
 
Deux  ensembles  
∀A,B : (( A ⊆ B) ∧ ( B ⊆ A)) ⇔ ( A = B)  
€
: (( A ⊆ B) ∧ ( B ⊆ C )) ⇒ ( A ⊆ C )  
 
L’inclusion  est  transitive  :   ∀A,B,C
€

⚠

 
 L’appartenance  n’est  pas  transitive  !  
€
 
L’ensemble  de  tous  les  s€
ous  ensembles  de  E  s’appelle  le  power  set  de  E.  Il  se  note   P ( E ) .  
E = {1,2,3}
 
Ex  :  
  On  a  toujours P ( E ) = 2 E  
P ( E ) = {∅,{1},{2},{3},{1,2},{1,3},{2,3}, E }
€
 
On  peut  effectuer  des  opérations  sur  des  ensembles  :  
€
  € Intersection  :   A B = { x ( x ∈ A) ∧ ( x ∈ B)}  
 

Union  : A B = { x ( x ∈ A) ∨ ( x ∈ B)}  

 

Différence  :   A − B = { x ( x ∈ A) ∧ ( x ∉ B)}  
€
Différence  
symétrique  :  

 
€

A ⊕ B = { x ( x ∈ A) ⊕ ( x ∈ B)} = ( A B) − ( A B) = ( A − B) ( B − A)  

 
€
Si  l’on  travaille  dans  un  «  univers  de  référence  »  E  :  
 
€ Le  complémentaire  de  A  :   A = { x ( x ∈ E ) ∧ ( x ∉ A)} = E − A  

€

€
€

€
€
€
€
€
€

Ainsi  on  peut  écrire  :   A − B = A B  
 
Sur  le  power  set  de  l’univers,  on  a  les  propriétés  suivantes  :  
€
A B = B A    
A B = B A  
 
€
A( BC ) = ( A B) C
 
 
A( BC ) = ( A B) C
A∅ = A €
A E = A
   
 
A∅ = ∅
A E = E
A( BC ) = ( A B) ( AC )
 
A( BC ) = ( A B) ( AC )
A A = A   €  
A A = A  
A = A  
∅ = E    
E = ∅  
 
A A = ∅   €  
A A = E  
A B = A B    
A B = A B  
 
€
La  différence  symétrique  est  associative  :   A ⊕ ( B ⊕ C ) = ( A ⊕ B) ⊕ C = A ⊕ B ⊕ C  
€
A ⊕ B ⊕ C  est  l’ensemble  des  éléments  appartenant  à  1!  ensemble  ou  aux  trois.  
 
€
€

€

Un  ensemble  est  équipotent  à  un  autre  si  chacun  de  ses  élément  peut  être  mis  en  
correspondance  «  one  to  one  »  avec  ceux  de  l’autre  (il  faut  pour  cela  que  les  deux  
ensembles  aient  les  même  cardinal.  
Un  ensemble  est  dit  infini  s’il  est  équipotent  à  une  de  ses  parties  propres.  
Un  ensemble  est  dit  dénombrable  s’il  est  équipotent  à  une  partie  de  l’ensemble  N.  
Tout  sous  ensemble  d’un  ensemble  dénombrable  est  lui-­‐même  dénombrable.  
Une  union  de  deux  ensembles  dénombrable  est  dénombrable.  
 

Chapitre  7  :  combinatoires  
 
  De  combien  de  façon  peut-­‐on  ranger  4  éléments  distincts  ?    
 
On  a  4  choix  pour  le  premier,  3  pour  le  second,  …,  1  seul  choix  pour  le  dernier,  
donc  au  total  on  a  4.3.2.1  =  4!  choix.  
 
Il  s’agit  d’une  permutation  : Pn = n!  
 
  De  combien  de  façon  peut-­‐on  choisir  et  ranger  4  éléments  parmi  6  ?  
 
On  a  6  façon  de  choisir  le  premier,  5  pour  le  second,  …  3  pour  le  dernier,  donc  au  
total  on  à  6.5.4.3  =  6!/2!  c€
hoix  possibles.  
n!
 
Il  s’agit  ici  d’un  arrangement  de  k  éléments  pris  parmi  n  :   Ank =
 
(n − k )!
 
  De  combien  de  façon  peut-­‐on  choisir  sans  les  ranger  4  éléments  parmi  6  ?  
 
Appelons  T  le  travail  consistant  à  choisir  et  ranger  4  éléments  parmi  les  6.   α  
€
 
T  peut  être  décomposé  en  2  travaux  successifs  indépendants  
:    
β1  
 
 
Choisir  4  éléments  parmi  les  6  
β2  
 
 
Ranger  4  éléments    
 
€
 
 
 
On  a  donc   α = β1 × β2  
€
6!
 
Or  on  connaît   α  ( A46 )  et   β2  ( P4 )  €
:   β1  =   A46 / P4  =  
 
2!×4!
 
€
n!
Si  on  généralise  :  choisir  k  éléments  parmi  n  peut  se  faire  de   Cnk =
manières.  
€ €
k!× ( n − k )!
€ € € € € €

⚠  Ce  nombre  est  également  le  nombre  de  sous  ensemble  de  cardinal  k  dans  un  

ensemble  de  n  éléments.  
€
 
Propriété  :    
 
Cnk = Cnn −k  
 
 
 
  De  combien  de  façon  peut  on  ranger  7  objets  dont  3  sont  identiques  ?  
€
Il  faut  d’abord  choisir  3  places  parmi  7  pour  mettre  les  objets  identiques  :   C73  
Ensuite  il  faut  ranger  les  4  autres  :   P4  
7!
7!
 C73 × P4 =
× 4!=  
3!×4!
3!
€
Généralisons  :  rangement  de  n  éléments  dont   n1,n 2 ,...  sont  identiques  :  
€
n!
Pnn1 ,n 2 ,... =
 
n1!×n 2!×...
€
 
€
  De  combien  de  façon  peut  on  ranger  n  éléments  «  en  rond  »  ?  
 
Nbr  rangements  circulaires  de  n  éléments  =   ( n −1)!  
€

€

Chapitre  8  :  récurrence  et  récursivité  
 
Principe  :  pour  prouver   ∀n ≥ n 0 : p( n )  :  
 
On  prouve   p( n 0 )  
 
 
pas  initial  
 
On  prouve   p( k ) ⇒ p( k +1)    
pas  récurrent  
Donc,  on  suppose  
€ que   p( k )  est  vrai  et  on  essaye  de  prouver p( k +1) .  
 
€

Chapitre  €9  :  matrices  

€
 
Pas  dans  la  matière.  Non  résumé  ici.  
 

Chapitre  10  et  suivants  

€

 
Cfr.  Les  pdf  donnés  en  introduction  aux  séances  d’exercices  et  les  exercices  eux  même.  
Le  reste  est  de  l’entrainement.  
 
 
 
Bon  travail  !  



Sur le même sujet..

---