Université de Nice-Sophia Antipolis École Supérieure en Sciences Informatiques

2004–2005

Controle de Mathématiques Discrètes du 29 Septembre 2004

Aucun document autorisé

Note :

Nom : Prénom : Groupe:

Durée : 25 minutes

1 2 3 4

Toutes vos réponses doivent être justifiées par une démonstration ou un contre-exemple.

1 Récurrence simple

Soit k un entier naturel quelconque, montrer par récurrence, que (k + 1)^{n} − 1 est un multiple de k, pour tout n, entier naturel.

2 Ordre?

La relation d’égalité est elle une relation d’ordre?

3 Désordre?

Soit (E,≤) un ensemble ordonné. Soit R la relation sur P(E) \ {∅} définie par : ARB ⇔ ∀a ∈ A,∀b ∈ B,a ≤ b. La relation R est-elle une relation d’ordre? Si oui, est ce un ordre total ou partiel ?

4 Des ordres?

Soit E = {a,b,c,d}. On considère les relations binaires sur E, R_{1},R_{2} et R_{3} définies par xR_{i}y ⇔ (x,y) ∈ R_{i} avec R_{1} = {(a,b),(a,c),(a,d)}, R_{2} = {(a,b),(b,c),(d,d)},et R_{3} = {(a,b),(b,c),(b,d),(d,a)}.

– R_{1}, R_{2} et R_{3} sont-elles des relations d’ordre ?

– Est-il possible de compléter R_{1}, R_{2} et R_{3} pour que R_{1} , R_{2} et R_{3} deviennent des relations d’ordre? Si c’est possible, déterminer R′_{i} le plus petit ensemble contenant R_{i}, et tel que R′_{i} soit un ordre.