Cours de Mathématique Discrète

Bac 2 Informatique
Introduction du cours
Chers étudiants, lorsque vous utilisez internet, envoyez un message sur WhatsApp, sécurisez
un mot de passe ou développez un programme informatique, vous manipulez des informations
qui sont discrètes : des bits (0 et 1), des graphes de réseaux, des ensembles, des relations et
des algorithmes. Les mathématiques discrètes, parfois appelées mathématiques finies, sont
précisément la branche des mathématiques qui étudie ces objets. Elles constituent le langage
fondamental de l’informatique et des réseaux.

Ce cours vous permettra de comprendre les bases théoriques qui se cachent derrière les
algorithmes, les bases de données, la cryptographie, les réseaux informatiques et l’intelligence
artificielle.

1) Pourquoi les mots de passe sont-ils difficiles à casser ?

Réponse : Les mots de passe sont protégés grâce à la cryptographie. Plus un mot de passe
est long et varié (majuscules, minuscules, chiffres, caractères spéciaux), plus le nombre des
combinaisons possibles augmente. Les mathématiques discrètes, notamment la combinatoire
et la théorie des nombres, permettent d’évaluer cette complexité et constituent la base des
méthodes de chiffrement.
2) Comment Google trouve-t-il le meilleur chemin entre des milliards de pages Web ?
Réponse : Google modélise le Web sous forme d’un graphe : chaque page est un sommet
(nœud) et chaque lien hypertexte est une arête. Des algorithmes sur les graphes (comme le
célèbre algorithme de classement des pages et d’autres techniques de recherche) permettent
d’identifier les pages les plus pertinentes et d’organiser les résultats de recherche.
3) Comment un GPS calcule-t-il l’itinéraire le plus court ?
Réponse : Le réseau routier est représenté par un graphe où les intersections sont des
sommets et les routes des arêtes. Chaque route possède un coût (distance, temps, trafic, etc.).
Le GPS utilise ensuite un algorithme de plus court chemin pour déterminer l’itinéraire optimal
entre le point de départ et la destination.
4) Comment Internet achemine-t-il les données d’un ordinateur à un autre ?
Réponse : Internet est un immense réseau de graphes composé de routeurs et de liaisons. Les
routeurs utilisent des algorithmes de routage pour choisir le meilleur chemin que doivent
emprunter les paquets de données afin qu’ils arrivent rapidement et correctement à leur
destination.
Vous voyez que derrière un moteur de recherche, un GPS, un mot de passe ou Internet se
cachent des notions de logique, de graphe, de combinatoire et d’algorithmes. Ce sont
précisément les outils que nous allons étudier dans le cours de mathématiques discrètes.

Plan du cours
CHAP 1 : Théorie des ensembles
CHAP 2 : Analyse combinatoire
CHAP 3 : Logique
CHAP 4 : Algèbre de Boole
CHAP 5 : Graphes
CHAP 6 : Illustration des exercices corrigés
CHAP I : THEORIE DES ENSEMBLES

a) Définition
On désigne sous le nom d’ensemble toute liste ou toute collection d’objet bien définie.
Ex : Bac 2 Informatique.
On appelle élément ou membre de l’ensemble les objets appartenant à l’ensemble.
Ex : Le promotionnel
On note par les lettres minuscules les éléments par les lettres majuscules les ensembles.
Ex : 𝐴 = {1,2,3,4} où A est l’ensemble et 1,2,3 et 4 sont respectivement élément de
l’ensemble
Le symbole ∈ est le signe d’appartenance d’un élément à un ensemble et ∉ est sa négation.
b) Ecriture d’un ensemble
Un ensemble A est défini en extension si on connait la liste de ses éléments.
Ex : 𝐴 = {1,2,3,4}
Si l’ensemble A ne contient que deux éléments on dit que A est un ensemble « paire », s’il
contient un élément, il est un ensemble « singleton » et s’il n’a aucun élément il est ensemble
« vide » et est noté par ∅ 𝑜𝑢 { }.
Soit A un ensemble et 𝑝(𝑥) une forme propositionnelle définie dans A. il existe un sous ensemble
de A formé des éléments de A vérifiant 𝑝(𝑥).
Soit B ce sous ensemble de 𝑝
Alors 𝐵 = {𝑥 ∈ 𝐴: 𝑝(𝑥)}on dit alors que 𝐵 est défini en compréhension.
Ex : 𝐵 = {𝑥 ∈ ℕ: 2/𝑥} en compréhension
𝐵 = {0,2,4, … }
c) Egalité de deux ensembles
Deux ensembles A et B sont égaux s’ils ont les mêmes éléments et on note « A = B ». A =
B : ∀x ∈ A ⟺ x ∈ B. La négation de l’égalité de A et B se note ℸ(A = B)
d) Sous-ensemble-inclusion
Tout ensemble A composé d’élément ∈ à l’ensemble B constitue un sous-ensemble de B. on dit
que A est inclus dans B et on écrit A⊂ B.
Parmi ls sous-ensemble de B figure B lui-même. Si A est un sous-ensemble de B et différent de
B. on dit que A est strictement inclus dans B. A⊂ B
Ex : ℕ ⊂ ℤ ⊂ ℚ ⊂ ℝ ⊂ ℂ.
e) Complémentaire
Soient A et E deux ensembles tels que A est une partie de E. on appelle complémentaire de A
par rapport à E qu’on note 𝐶𝐸𝐴 l’ensemble des éléments de E ∉ A.
Ex : 𝐴 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}, 𝐸 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒}. 𝑎𝑙𝑜𝑟𝑠 𝐶𝐸𝐴 = ∅
On écrit parfois E moins A (E-A). 𝐶𝐸𝐴 = {𝑥 ∈ E, x ∉ 𝐴 } Avec A⊂ E.
Si B=𝐶𝐸𝐴 ⟺ 𝐴 = 𝐶𝐸𝐵 est quand A =B
𝐶𝐴
𝐶𝐸 𝐸 = 𝐴 𝐶𝐸𝐸 = ∅ 𝐶𝐸∅ = 𝐸
Ex : les complémentaires de {0 } par rapport à ℕ, ℤ, ℚ, ℝ, ℂ sont ℕ∗ , ℤ∗ , ℚ∗ , ℝ∗ , ℂ∗
f) Ensemble des parties de E
Soit E un ensemble fini, les sous-ensembles de E sont les éléments d’un nouvel ensemble
appelé ensemble des parties de E que l’on note 𝓅(𝐸).
Ex : E= {𝑎, 𝑏, 𝑐, }, 𝓅(𝐸)= {∅, {𝑎}, {𝑏}, {𝑐}, {𝑎, 𝑏, }, {𝑎, 𝑐, }, {𝑏, 𝑐, }, {𝑎, 𝑏, 𝑐, }}, E ∈ 𝓅(𝐸) ⇒ 𝐴 ⊑ 𝐸
Si E= ∅, 𝓅(𝐸) ≠ ∅ car 𝓅(𝐸) = {∅}
g) Opérations sur les ensembles
 Intersection (∩) de 2 ensembles
Soient A et B deux en ensembles. On appelle intersection de A et B, l’ensemble noté A∩ B
constitué des éléments appartenant à la fois à A et à B.
Ainsi si A ⊂ 𝐸 et B ⊂ 𝐸 alors A∩ B = {x ∈ E: x ∈ A ⋀ 𝑥 ∈ 𝐵}
Propriétés :
𝑉𝐴,𝐵,𝐶 ∈ 𝐸
1. 𝐴 ∩ ∅ = ∅ si 𝑥 ∈ 𝐴 ∩ ∅ ⟹ 𝑥 ∈ 𝐴 ⋀ 𝑥 ∈ ∅, 𝑥 ∈ 𝐴 ⋀ 𝑥 ∉ ∅.
2. 𝐴 ∩ 𝐴 = 𝐴
3. 𝐴 ∩ 𝐵 = 𝐵 ∩ 𝐴
4. 𝐴 ∩ (𝐵 ∩ 𝐶) = (𝐴 ∩ 𝐵) ∩ 𝐶
 Réunion (∪) de 2 ensembles
Soient A et B deux ensembles. On appelle réunion de A et B l’ensemble A∪ 𝐵 constitué des
éléments appartenant à l’un au moins des ensembles.
A ⊂ 𝐸 et B ⊂ 𝐸 alors A∪ B = {x ∈ E: x ∈ A V 𝑥 ∈ 𝐵}
Propriétés :
1. 𝑉𝐴,𝐵,𝐶 ∈ 𝐸
2. 𝐴 ∪ ∅ = 𝐴 Si 𝑥 ∈ 𝐴 𝑉 𝑥 ∈ 𝐴 ∅, 𝑥 ∈ 𝐴 𝑉 𝑥 ∉ E.
3. 𝐴 ∪ 𝐵 = 𝐵 ∪ 𝐴
4. 𝐴 ∪ (𝐵 ∪ 𝐶) = (𝐴 ∪ 𝐵) ∪ 𝐶
 Relation entre l’intersection et la réunion
𝑉𝐴,𝐵,𝐶 ∈ 𝐸
1. 𝐴 ∩ (𝐵 ∪ 𝐶) = (𝐴 ∩ 𝐵) ∪ (𝐴 ∩ 𝐶)
2. 𝐴 ∪ (𝐵 ∩ 𝐶) =(𝐴 ∪ 𝐵) ∩ (𝐴 ∪ 𝐶)
3. 𝐶𝐸𝐴∩𝐵 = 𝐶𝐸𝐴 ∪ 𝐶𝐸𝐵
4. 𝐶𝐸𝐴∪𝐵 = 𝐶𝐸𝐴 ∩ 𝐶𝐸𝐵
𝐴 ∪ (𝐴 ∩ 𝐵) = 𝐴
5. { Lois d’absorption
𝐴 ∩ (𝐴 ∪ 𝐵) = 𝐴
 La différence
La différence de deux ensembles A et B est l’ensemble A moins B noté A∖ 𝐵 et définit comme
suite : A∖ 𝐵 = {𝑥 ∈ 𝐴 𝑒𝑡 𝑥 ∉ 𝐵}
 la différence symétrique
la différence symétrique de 2 ensembles A et B est l’ensemble noté A ∆ B et est définit comme
suite 𝐴∆𝐵 = (𝐴\𝐵) ∪ (𝐵\𝐴) = (𝐴 ∪ 𝐵)\(𝐴 ∩ 𝐵).
 Les quantificateur
soit p, une propriété définie sur l’ensemble E et A la partie de E dont les éléments ont pour
propriété caractéristique p. examinons les 3 cas suivants :
1er cas : A est non vide (A≠ ∅) il existe au moins un élément de E possédant p. nous écrivons
(∃𝑥 𝜖 𝐸 ) 𝑝(𝑥)
2ème Cas : A est vide (A≠ ∅). Aucun élément de E ne possède la propriété p. on écrira ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
(∃𝑥𝜖 𝐸 )𝑝(𝑥)
3ème Cas : est la partie pleine de E (A≡ 𝐸). Tout élément de E possède la propriété p. on écrira
(∀𝑥𝜖 𝐸 )𝜖 𝑝(𝑥).
Les symboles ∃ et ∀ s’appellent des quantificateurs.
Applications
1. Lequel des ensembles ci-dessous est différent de l’ensemble vide ?
𝑥
a) 𝐴 = {𝑥 ≠ 𝑥}
𝑥
b) B = {𝑥 2 −9 , 2𝑥 = 4}
𝑥
c) 𝐶 = {𝑥+8 = 8}
d) D= { }
2. Quels sont les éléments appartenant aux ensembles :
𝑥𝜖𝑅
a) 𝐴 = {𝑥 2 +𝑥−12 = 0}
b) 𝐵 = {(𝑥, 𝑦)𝜖𝑅 2 : 𝑦 = 𝑥, 𝑥 2 = 9}
3. La formule (∀𝑥 )(∀𝑦 ) 𝑅 (𝑥, 𝑦) a pour négation
a) ∀𝑥, ∃𝑦 𝑅̅(𝑥, 𝑦)
b) ∀𝑥, ∃𝑦 𝑅(𝑥, 𝑦)
c) ∃𝑥 ̅̅̅̅̅̅̅̅̅̅̅̅̅
∃𝑦 𝑅(𝑥, 𝑦)
̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
d) ∀𝑥 ∃𝑦 𝑅̅(𝑥, 𝑦)
e) ∃𝑥 ∀𝑦, 𝑅(𝑥, 𝑦)
f) Aucune des réponses n’est ci-haut n’est bonne.
4. La formule (∀𝑥 )(∃𝑦 ) 𝑅 (𝑥, 𝑦) a pour négation
𝑎) ∀𝑦, ∃𝑥 𝑅̅ (𝑥, 𝑦)
𝑏) ∃𝑥 ∀𝑦, 𝑅(𝑥, 𝑦)
𝑐) ∃𝑥 ̅̅̅̅̅̅̅̅̅̅̅̅̅
∃𝑦 𝑅(𝑥, 𝑦)
𝑑) ̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅̅
∀𝑥 ∃𝑦 𝑅̅(𝑥, 𝑦)
𝑒) ∃𝑥 ∀𝑦, 𝑅(𝑥, 𝑦)
Solution
1. Assertion C
2. 𝐴 = { −4,3} et 𝐵 = { −3,3}
3. Non (∀𝑥 ) 𝑝(𝑥) ⟺ ∃𝑥 𝑝̅ (𝑥)
Non (∀𝑦 ) 𝑝(𝑥) ⟺ ∃𝑥 𝑝̅ (𝑥)
Non [(∀𝑥 )(∀𝑦 )𝑅(𝑥, 𝑦)] ⇔ (∃𝑥 )(∃𝑦 ) 𝑅̅(𝑥, 𝑦)
Aucune réponse n’est bonne.
4. Assertion C
CHAP II : ANALYSE COMBINATOIRE
A. Introduction
L’analyse combinatoire est l’étude des problèmes de dénombrements dans les ensembles finis.
Le dénombrement consiste en une énumération des différentes manières de grouper les
éléments des ensembles finis en divers sous-ensembles, ordonnés ou non, selon diverses lois.
Un groupement est dit simple ou sans répétition s’il ne renferme que des objets distincts. Dans
le cas contraire, il est dit multiple ou avec répétition, c’est-à-dire qu’il renferme au moins deux
éléments égaux.
L’analyse combinatoire s’occupe donc de la détermination du nombre de chacun de ces
groupements.
Parmi ces groupements, on retrouve : les arrangements, les permutations et les combinaisons.
B. Notion de factorielle
Définition : Soit n un entier naturel non nul. On appelle factorielle n, et on note n !, le produit
des n premiers nombres entiers naturels non nuls. n ! = 𝑛. (𝑛 − 1). (𝑛 − 2). (𝑛 − 3) … . . 2. 1
1! 1
NB : 1 ! = 1. (1-1) ! = 1.0! ; d’où et 0 ! = 1 = 1 = 1
C. Arrangement sans répétition
Notion
Considérons le mot NORD formé de 4 lettres différentes.
 Déterminons les mots différents de 2 lettres que nous pouvons former avec les lettres N, O,
R et D du mot NORD, sachant qu’une lettre ne peut être prise qu’une fois. Nous ne nous
demandons pas si oui ou non ces mots existent. Deux mots sont différents ou bien s’ils
contiennent les mêmes lettres dans des ordres différents.
Nous avons : NO, NR, ND, ON, OR, OD, RN, RO, RD, DN, DO, DR.
Nous obtenons 1é mots différents de 2 lettres.
 Déterminons à présent les mots différents de 3 lettres. Nous avons : NOR, NOD, NRO,
NRD, NDO, NDR, ONR, OND, ORN, ORD, ODN, ODR, RNO, RND, RON, ROD, RDN, RDO,
DNO, DNR, DON, DOR, DRN, DRO. Nous obtenons 24 mots différents de 3 lettres.
Conclusion
Dans le premier cas, chaque mot formé constitue un arrangement de 4 éléments pris 2 à 2.
Dans le second, il constitue un arrangement de 4 éléments pris 3 à 3. C’est-à-dire une
disposition ordonnée de 2 ou 3 éléments parmi les 4 éléments présents.
NB :
 Un élément ne peut pas figurer plusieurs fois dans un même groupe
 Deux arrangements sont distincts
On appelle arrangement sans répétition de n éléments pris p à p (avec p ≤ 𝒏), tout groupe
de p éléments distincts choisis parmi les n éléments et placés dans un ordre déterminé.
𝐩 𝐧!
𝐀𝐧 = (𝒏−𝒑)!

Exemple : Combien existe-t-il de mots de trois lettres différentes formées à partir de 5 lettres
différentes ?
5!
A35 = (5−3)! = 60 𝑚𝑜𝑡𝑠

D. Permutations sans répétition

Notion
Déterminons les différentes façons de placer quelques personnes différentes sur un banc dont
le nombre de place est égal à celui des personnes. Ces personnes seront désignées par les
lettres de l’alphabet français, les places par des chiffres. Une personne ne peut être placée
qu’une fois à une place donnée. Considérons le mot NORD formé de 4 lettres différentes.
 Si elles sont deux, soient A et B, nous avons un banc à deux places
1 2 1 2
A B B A donc 2 façons différents
 Si elles sont trois, soient A, B et C, nous avons un banc à trois places.
1 123 123 123 123 123 123
2 ABC ACB BAC BCA CAB CBA donc 6 façons différents

Conclusion
Dans le premier cas, chaque façon de placer constitue une permutation de 2 éléments, dans le
second une permutation de 3 éléments ;
NB :
 Deux permutations sont distinctes si elles contiennent des éléments dans des ordres
différents.
 Une permutation est un arrangement de n éléments pris n à n.
On appelle permutation sans répétition de n éléments tout groupe de ces n éléments
placés dans un ordre déterminé.
𝑷𝒏 = 𝒏!

Exemple : De combien de manières 6 personnes peuvent-elles se placer :

a) En une rangée ? Rép : P6 =6 != 720

b) Autour d’une table ronde à 6 places ? Rép : P5 =5 != 120
E. Combinaison sans répétition
Notion
Déterminons les différentes façons de former des groupes différents d’un nombre donné de
personnes à partir d’un ensemble donné. Ces personnes seront désignées par les lettres de
l’alphabet français et une personne ne peut figurer qu’une seule fois dans un groupe donné.
Une personne ne peut figurer qu’une seule fois dans un groupe donné.
 Considérons un ensemble de 4 personnes : A, B, C et D, et formons des groupes renfermant
chacun 2 personnes choisies parmi les 4. Nous avons : AB, AC, AD, BC, BD, CD. Donc 6
groupes différents.
 En formant des groupes de 3 personnes choisies parmi les 4, nous avons : ABC, ABD, ACD,
BCD ; donc 4 groupes différents.
Conclusion
Dans le premier cas, chaque groupe constitue une combinaison de 4 éléments pris 2 à 2 ; dans
le second, il constitue une combinaison de 4 éléments pris 3 à 3.
 Un élément ne peut pas figurer plusieurs fois dans un même groupe
 Dans les combinaisons, l’ordre dans lequel se présentent les éléments ne compte pas. BC
et CB représente la même combinaison.
 Deux combinaisons sont distinctes si l’une contient au moins un élément que ne contient
pas l’autre. AC et AD, AB et CD ; ABC, ABD, BCD et ABE sont 2 à 2 des combinaisons distinctes.
 Etant donné un ensemble fini E formé de n éléments distincts, chaque groupe de p éléments
( p ≤ n ) choisis parmi les n éléments de E constitue une partie ou un sous-ensemble de E.
On appelle combinaison sans répétition de n éléments pris p à p (avec p ≤ 𝒏), tout groupe
de p éléments distincts choisis parmi les n éléments sans tenir compte de l’ordre.
𝐩 𝐧!
𝐂𝐧 = 𝒑!(𝒏−𝒑)!

Exemple : Une équipe de Basket-ball comprend 10 joueurs. De combien de façons le président

de l’équipe peut-il les recevoir :
a) En groupe de 6 ?
b) Si les joueurs Paul et Antoine ne peuvent pas être reçus ensemble ?
Réponse :
 6
a) C10 = 210
b) 1er cas : Paul et Antoine ne sont pas reçus, il faut choisir 6 joueurs parmi les 8 restants. C86 =
28
2ème cas : Paul est reçu, Antoine ne l’est pas. Il y a 6 joueurs à choisir parmi les 9 restants. Paul
doit nécessairement être reçu, il faut choisir 5 joueurs parmi les 8 restants C85 = 56.
3ème cas : Antoine est reçu, Paul ne l’est pas. Même raisonnement que pour le 2ème cas, C85 =
56.
Donc, il y a C86 + C85 + C85 = 140
a) Propriétés
p n−p
1. Cn = Cn (p ≤ n)
n−p n
En effet : Cn = (n − p)! (n−n+p)!
n! n! p
= (n − p)! p! = p! (n−p)! = Cn
2. CnP −1
−1 P
+ Cn−1
(n −1) ! (n −1)
En effet : CnP −− 11 + CnP −1 = (P − 1)!(n −1−p+1)! = P! (n − 1)!
(n −1) ! (n −1) ! P (n −1)! +(n − 1)!(n − p)
= (P − 1)!(n −p)! + P! (n −p − 1)! = P! (n − p)!
(n −1)! (P + n−p) (n −1)! n
= = P! !(n −p)! = CnP
P! (n −p)!
b) Triangle de pascal
La propriété 2 conduit à la construction d’un tableau triangulaire appelé triangle de pascal. Le
chiffre 1 qui sont à gauche et à droite du triangle sont les valeurs de Cn0 et Cnn . Sur la première
ligne le seul élément 1 et la valeur de C00 . Tout terme autre que les termes extrêmes s’obtiennent
en additionnant les termes au-dessus et les termes à gauche de ce dernier. Ainsi le terme de
rang p s’obtient en additionnant les termes de rang (n – 1) -ème ,d’où le tableau triangulaire

𝑛⁄𝑝 0 1 2 3 4 5 6
0 1
1 1 1
2 1 2 1
3 1 3 3 1
4 1 4 6 4 1
5 1 5 10 10 5 1
6 1 6 15 20 15 6 1
c) Binôme de newton
1. Généralités
Dans tout anneau commutatif (A, +, .) sont définis les expressions suivantes
∀a, b ∈ A (a + b) (a +b) = (a + b)² = a² + 2ab + b²
(a +b) (a + b) (a + b) = (a + b)3 = a3 + 3a²b + 3ab² + b3
On remarque les coefficients 1, 2, 1 (1er développement) et 1, 3, 3 1 (2ème développement)
interviennent respectivement dans le développement de (a + b)² et (a + b)3 sont les termes de
la 2ème et 3ème ligne du ∆ de pascal. Nous nous proposons de développer (a + b)n ∀a, b ∈ A avec
n∈ℕ
(a + b)n = ∑𝑛𝑝=0 CnP an−p b p 𝑒𝑡 (a − b)n = ∑𝑛𝑝=0 CnP (−1)𝑝 an−p b p formules du binôme de Newton
CnP Sont les coefficients du Binôme. Il faut savoir que les coefficients du binôme de
développement (a + b)n sont les termes de la nième ligne du triangle de pascal.
2. Propriétés
P1 : Le nombre des termes du développement (a + b)n est n + 1
P2 : La somme des exposants des termes a et b est n
P3 : Les coefficients des termes équidistances des extrêmes dans (a +b)n sont égaux.
F. Arrangement avec répétition
On appelle arrangement avec répétition de n éléments pris p à p, tout groupe de p éléments
choisis parmi les n éléments et placés dans un ordre déterminé, chaque élément pouvant figurer
plusieurs fois dans un même groupe. ̅̅̅̅
𝒑
𝑨𝒏 = 𝒏𝒑
Exemple : combien des mots de 2 lettres peut-on former avec 3 lettres ? ̅̅̅𝐴23 = 32 = 9
Combien des mots de 2 lettres peut-on former avec 2 lettres ? ̅̅̅
𝐴22 = 22 = 4
G. Permutation avec répétition
On appelle permutation avec répétition de n éléments tout groupe de ces n éléments placés
dans un ordre déterminé. 𝑷̅ 𝒌𝒏 = 𝒏! et 𝑷
̅ 𝒌𝒏𝟏 𝒌𝟐 𝒌𝟑 …𝒌𝒎 = 𝒏!
𝒌! 𝟏 𝒌 ! 𝒌 !𝒌 !…𝒌 !
𝟐 𝟑 𝒎

Exemple :
1) Déterminer le nombre des permutations des lettres ABABBCCDBC.
Nous au total 10 lettres dont 2A, 4B, 3C et 1D. ainsi n=10 ; 𝒌𝟏 = 𝟐; 𝒌𝟐 = 𝟒; 𝒌𝟑 = 𝟒
10!
̅ 2431
P10 = 2!4!3!1! = 12600
2) Calculer le nombre d’anagrammes des mots MISSISSIPPI
11!
̅11
P 4421
= 4!4!2!1! = 34650
H. Combinaison avec répétition
On appelle combinaison avec répétition de n éléments pris p à p, tout groupe de p éléments
choisis parmi les n éléments, sans tenir compte de l’ordre, chaque élément pouvant figurer
plusieurs fois dans un même groupe. 𝑪 ̅ 𝒑𝒏 = 𝑪
̅𝒑
𝒏+𝒑−𝟏
Tableau résumé : groupements multiples

Groupement Nombre Conditions

Arrangements de n ̅̅̅̅
𝒑
𝑨𝒏 = 𝒏𝒑 Ordre compte
éléments pris p à p
𝒏!
Permutations de n ̅ 𝒌𝒏𝟏 𝒌𝟐 𝒌𝟑 …𝒌𝒎 =
𝑷 Ordre compte
𝒌 𝟏 ! 𝒌𝟐 !𝒌𝟑 !…𝒌𝒎 !
éléments
Combinaisons de n ̅ 𝒑𝒏 = 𝑪
𝑪 ̅𝒑 Ordre ne compte pas
𝒏+𝒑−𝟏
éléments pris p à p

Applications
1. On considère les chiffres 1,2,3,4,5,6,7,8,9.
a) Combien de nombres de 3 chiffres peut-on former avec ces chiffres ? aucun chiffre ne peut
être repris deux fois.
b) Combien de ces nombres sont impairs ?
c) Combien de ces nombres sont pairs ?
d) Combien sont supérieur à 500 ?
e) Combien sont supérieurs à 300 si seulement les chiffres 1,2,3,4,5 et 6 sont utilisés ?
2. Combien existe-t-il des nombres compris entre 3000 et 4000 et ne renferment que les
chiffres 2, 3, 4 et 5 ? déterminez-le.
3. On considère les chiffres 1,2,3,4,5,6,7,8,9.
a) Combien de nombres de 5 chiffres différents peut-on former avec ces 9 chiffres ?
Parmi ces nombres
b) Combien se terminent par le chiffre 4 ?
c) Combien commencent par 23 ?
d) Combien renferment le chiffre 8 ?
e) Combien renferment les chiffres 5 et 7 ?
f) Combien ne connaissent ni 2 ni 9 ?
g) Combien renferment 1 et pas 6 ?
Solutions
1. .
a) 𝐀𝟑𝟗 =504
b) Ces nombres se terminent par 1,3,5,7 ou 9.
On doit commencer par la dernière place : il y a 𝐀𝟏𝟓 = 𝟓
La troisième place étant occupée, il reste 8 chiffres à placer à la 1 er place : il y a 𝐀𝟏𝟖 = 𝟖
Deux places étant occupées, il reste 1 chiffre à choisir parmi les 7 restants : 𝐀𝟏𝟕 = 𝟕
Donc, il y a 𝐀𝟏𝟓 𝒙𝐀𝟏𝟖 𝒙𝐀𝟏𝟕 = 𝟐𝟖𝟎
c) Ces nombres se terminent par 2, 4, 6 ou 8
Il y a 𝐀𝟏𝟒 = 𝟒 façons d’occuper la troisième place.
La troisième place étant occupée, il reste 2 chiffres à choisir parmi les 8 autres. Il y a 𝐀𝟐𝟖 =56
D’où 4x56= 224
d) Ces nombres commencent par 5, 6, 7, 8 ou 9
Il y’a 𝐀𝟏𝟓
La première place étant occupée, il reste 2 chiffres à choisir parmi les 8 autres. Il y a 𝐀𝟐𝟖 =56
D’où 𝐀𝟏𝟓 𝒙𝐀𝟐𝟖 = 𝟐𝟖𝟎
e) Ces nombres commencent par 3, 4, 5 ou 6
Il y a 𝐀𝟏𝟒 = 𝟒 façons d’occuper la première place.
La première place étant occupée, il reste 2 chiffres à choisir parmi les 5 autres. Il y a 𝐀𝟐𝟓 =20
D’où 𝐀𝟏𝟒 𝒙𝐀𝟐𝟓 = 𝟒𝒙𝟐𝟎 = 𝟖𝟎 nombres
2. Ces sont des nombres de 4 chiffres commençant par 3. Il reste 3 chiffres pour occuper les
3 dernières places. On a P3 =6 nombres ;
CHAP III : LOGIQUE
1. Définition et notation
Une proposition logique est un énoncé pour lequel on peut affirmer sans ambiguïté qu’il est vrai
ou qu’il est faux. Elle est notée par des lettres :P, Q, p, q, r, s, …
Exemple et contre-exemple :
 R:3>6
 s : 6 divise 3
 S : demain, il pleuvra
 q : le carré est un rectangle
 P : le Congo est un Etat sud-Américain
 Q : existe-t ’il un entier x tel que x-5 = 6
 p : les étudiants de Bac 2 Info sont méchants
Les énoncés R, s, q, P, Q sont des propositions logiques tandis que S et p ne le sont pas.
Valeur de vérité
La valeur de vérité d’une proposition est :
1 ou V si la proposition est vraie
0 ou F si la proposition est fausse
Exemples :
R : 5 + 6 =11 P : Kinshasa est la capitale de la RDC
Q : la poule est une herbivore S : la France est un Etat de l’Union Africaine
P et R ont pour valeur de vérité 1 ou V
Q et S ont pour valeur de vérité 0 ou F
Table de vérité
Cas d’une proposition p : il y a deux possibilités 21=2
P
1
0

Cas de deux proportions p et q : il y a quatre possibilités 22=4

p q
1 1
1 0
0 1
0 0

Cas de trois proportions p, q et s: il y a huit possibilités 23=8

P Q R
1 1 1
1 1 0
1 0 1
1 0 0
0 1 1
0 1 0
0 0 1
0 0 0
Négation d’une proposition
Soit P une proposition. La négation de la proposition P est la proposition « non P » qui est vraie
si P est fausse et fausse si P est vraie.
La négation de P se note 𝑃̅
Principes logiques
Une proposition logique doit respecter les deux principes logiques suivants
a) Principe du tiers-exclu : une proposition logique est soit vraie soit fausse
b) Principe de non-contradiction : une proposition logique ne peut pas être à la fois vraie et
fausse.
Exemple : a) une porte est ouverte et fermée
b) il n’est pas vrai qu’un être existe et n’existe pas
2. Quantificateur
Quantificateur universel
Considérons dans R, l’équation 0x=0. Quel que soit x appartenant à R, x vérifie l’égalité,
autrement dit tout entier x de R vérifie l’équation.
On écrit ∀𝑥𝜖𝑅: 0𝑥 = 0
Le symbole « ∀ » est le quantificateur universel qui signifie que tout élément d’un ensemble,
d’une théorie, considérée vérifie une propriété donnée, définie sur cet ensemble.
Quantificateur existentiel
Soit l’égalité x+3> 7, il existe au moins un réel x vérifiant l’inégalité ( 8 par exemple)
On écrit ∃𝑥𝜖𝑅: 𝑥 + 3 > 7
Le symbole « ∃ » est le quantificateur existentiel qui signifie : « on peut trouver au moins un
élément d’un ensemble ( d’une théorie) considéré vérifiant une propriété donnée, définie sur
l’ensemble.
Remarque : en considérant l’égalité x + 3 = 7, on remarque qu’il existe un et un seul entier qui
vérifie l’équation.
On écrit ∃! 𝑥𝜖𝑁: 𝑥 + 3 = 7 et on lit : il existe un et un seul x appartenant à N tel que x + 3 = 5.
Les quantificateurs universel et existentiel peuvent être utilisés dans une même proposition à
condition de bien respecter l’ordre dans lequel on les place.
Exemple : ∃𝑥𝑒𝜖𝑁: ∀𝑥𝜖𝑁, 𝑥 + 𝑒 = 𝑥
∀𝑥𝜖𝑁: ∃𝑒𝜖𝑁: 𝑥 + 𝑒 = 𝑥
3. Connecteurs et opérateurs logiques
A partir de 2 propositions P et Q on peut déterminer une nouvelle proposition posée 2 autres
que nous noterons P 𝜃 Q.
La valeur de vérité de P 𝜃 Q est déterminée en fonction valeurs de vérité de P et Q. Ainsi le
symbole 𝜃 s’appelle connecteurs logiques.
P Q P𝜽Q
1 1
1 0
0 1
0 0
Il suffit de trouver une suite de 4 valeurs correspondantes pour fixer exactement le sens du
connecteur logique. Cette suite de valeur s’appelle une évaluation. Ainsi toute évaluation
détermine un connecteur logique remarquera qu’une évaluation peut se définir comme
application qui va d’un ensemble 𝐵 {1,2,3,4} à 4 éléments un en3s V {1,0} à 2 éléments.
On peut définir 16 connecteurs logiques entre positions mais dans ce qui suit on étudiera que
les principaux connecteurs usuels.
a) Connecteurs usuels
A. CONJONCTION LOGIQUE : le connecteur « et » : Ʌ
La conjonction de P et Q est la proposition notée « PɅQ » est vraie si P et Q sont simultanément
vraie et fausse dans les autres cas.
P Q PɅQ
1 1 1
1 0 0
0 1 0
0 0 0
EX : P (x) : x est divisible par 3
Q (x) x est divisible par 5
P (x) et Q (x) : x est divisible par 3 et par 5 (V)
- 15 est divisible par 3 et par 5 (V)
- 18 est divisible par 5 (F).
Propriétés
C1 : La conjonction est commutative (P et Q) ; P Ʌ Q = Q Ʌ P
C2 : la conjonction est associative, ∀ P, Q, R, : P Ʌ (Q Ʌ R) = (P Ʌ Q) ɅR
C3 : La conjonction est Idempotente ∀ P, P Ʌ P=P
C4 : Pour tout P proposition on a P Ʌ (𝑃̅) = Faux
Ex : 2 est paire et 2 n’est pas paire
B. LA DISJONCTION INCLUSIVE : le connecteur « ou » : V
La disjonction est un connecteur logique qui à un couple de proposition (P, Q) associe « P OU
Q » vraie si l’une au moins de 2 propositions est vraie et fausse dans tous les autres cas.

a) Notation PVQ
P Q PVQ
1 1 1
1 0 1
0 1 1
0 0 0
Ex : 15 est divisible par 3 ou 5 : V
- 6 est divisible par 3 ou 5 : V
- 17 est divisible par 3 ou 5 : F
b) Proprétés
C1 : la disjonction est commutative
C2 : la disjonction est associative
C3 : la disjonction est Idempotente
C4 : pour tout P proposition on a P V (𝑃̅) = Vrai
C. DISJONCTION EXCLUSIVE le connecteur « … ou bien … » : 𝑽
Définition : La disjonction exclusive est un connecteur logique qui a un couple de proposition
(P, Q) associe la proposition pour exclure Q vraie si P et Q ont des valeurs de vérité et fausse
dans tous les autres cas.

P Q P𝑽Q
1 1 0
1 0 1
0 1 1
0 0 0

Notation :
P𝑽Q et on lit : soit P soit Q.
Exemple :
P : Le professeur de Math promet dix points ou un livre de Math à l’étudiant qui répond
correctement à la question posée.
Q : une exclusion temporaire sera infligée à l’étudiant qui arrive en retard à la FAC ou qui
bavarde en salle de cours.
Dans la proposition P, le Professeur promet un de deux objets tout en excluant l’octroi de deux
à la fois.
D. IMPLICATION le connecteur « si … alors… » : ⟹
Définition
L’implication est un connecteur logique qui à un couple de proposition (P, Q) associe la
proposition « P implication Q » fausse si P est vraie et Q est fausse. Elle est vraie dans tous les
autres cas.
Notation
P ⟹ Q qui se lit P implique ou entraine Q
P ⟹ Q la proposition P ⟹ Q peut se lire aussi « (non P) ou Q.
 P Q P⟹Q
1 1 1
1 0 0
0 1 1
0 0 1
Exemple :
P : DIMERCIA paie les frais académiques
Q : DIMERCIA suit les cours
E. BI-IMPLICATION (équivalence) le connecteur « si et seulement si alors » : ⟺
Définition :
La Bi-implication est un connecteur logique qui a un couple de proposition (P, Q) associe la
proposition « P Bi-implication Q » vraie P et Q ont les mêmes valeurs de vérité, fausse dans les
autres cas.
P Q P⟹Q
1 1 1
1 0 0
0 1 0
0 0 1

Notation :
P ⇔ Q qui se lit P est équivalent à Q
F. AUTRES CONNECTEURS UTILISES
 LA TAUTOLOGIE
Définition
La tautologie est un connecteur logique dont l’évaluation est 1111
Notation
Elle se note P ‫ ݼ‬Q qui se lit tau Q. Cette proposition est toujours vraie
P Q P‫ݼ‬Q
1 1 1
1 0 1
0 1 1
0 0 1

 L’ANTILOGIE
Définition
L’antilogie est un connecteur logique dont l’évaluation est 0000
P&Q=F
Table de vérité
P Q P&Q
1 1 0
1 0 0
0 1 0
0 0 0
 PRINCIPES ET LES LOIS DE LA LOGIQUE
a) PRINCIPE DE LA NON-CONTRADICTION
Pour tout P proposition on a P Ʌ 𝑃̅est une antilogie
P et 𝑃̅ est toujours fausse
P 𝑃̅ PɅ𝑃̅
1 0 0
0 1 0
Ex1 : Deux est pair et 2 est impair P est pair et 𝑃̅ est non pair
b) PRINCIPE DU TIERS-EXCLUS
Définition
Pour tout P proposition on a PV 𝑃̅ est tautologie
P 𝑃̅ P V 𝑃̅
1 0 1
0 1 1
Ex : P :3 est premier ou
𝑃̅ : 3 n’est pas premier
c) LOI DE CONTRAPOSITION
Pour tout P et Q deux propositions on a : (𝑃 ⇒ 𝑄) ⟺ (𝑄̅ ⟹ 𝑃̅ )
P Q 𝑃⇒𝑄 𝑃̅ 𝑄̅ (𝑄̅ ⟹ 𝑃̅)
1 1 1 0 0 1
1 0 0 0 1 0
0 1 1 1 0 1
0 0 1 1 1 1

d) LOIS DE DEMORGAN
Ces lois concernent la négation de la conjonction et de la disposition. Pour tout P,Q deux
proposition on a les équivalences logiques suivantes.
̅̅̅̅̅̅̅
C1 : (𝑃 ∧ 𝑄) ≡ 𝑃̅V 𝑄̅
P Q 𝑃∧Q ̅̅̅̅̅̅̅
(𝑃 ∧ 𝑄) 𝑃̅ 𝑄̅ 𝑃̅V 𝑄̅
1 1 1 0 0 0 0
1 0 0 1 0 1 1
0 1 0 1 1 0 1
0 0 0 1 1 1 1

̅̅̅̅̅̅̅
C2 :𝑃 ∨ 𝑄 ≡ 𝑃̅ ∧ 𝑄̅
P Q 𝑃∨Q ̅̅̅̅̅̅̅
(𝑃 ∨ 𝑄) 𝑃̅ 𝑄̅ 𝑃̅ ∧ 𝑄̅
1 1 1 0 0 0 0
1 0 1 0 0 1 0
0 1 1 0 1 0 0F
0 0 0 1 1 1 1

G. RAISONNEMENTS MATHEMATIQUES
 Raisonnement par implication
Raisonner par implication c’est remplacé l’implication proposée par un certain nombre
d’implications successives dont la vérité est facile à établir ou elle est déjà établie.
 Raisonnement par contraposition
Pour démontrer que la proposition si 𝑃 ⟹ 𝑄 est vraie dans un référentiel E, il suffit de démontrer
dans le référentiel E, il suffit de démontrer dans le même référentiel que la proposition (𝑄̅ ⇒ 𝑃̅)
Exemple : Soit n un naturel, si 𝑛2 est pair alors n est pair
Hypothèses : 𝑛2 pair n ∈ ℕ
Thèse : 𝑛 est pair
Démonstration : par contraposition on démontre que n impair implique que 𝑛2 est impair.
(n impair) ⇒ (∃𝑘𝜖𝑁: 𝑛 = 2𝑘 + 1
⇒ (𝑛2 = 4𝑘 2 + 4𝑘 + 1)
⇒ (𝑛2 = 2(2𝑘 2 + 2𝑘) + 1
⇒ (𝑛2 = 2𝑘 ′ + 1) si 𝑘 ′ = (2𝑘 2 + 2𝑘)
⇒ (𝑛2 𝑒𝑠𝑡 𝑖𝑚𝑝𝑎𝑖𝑟)
 Raisonnement par absurde
Dans une théorie ‫ح‬, si une proposition P est contradictoire alors tout énoncé Q est contradictoire
dans cette même théorie.
Principe : Si dans une théorie ‫ح‬on veut demander que P est vrai, on forme la théorie ‫ ح‬obtenue
en adjoignant et résulte du principe de non contradiction que non P ( 𝑃̅ ) ne peut être vraie.
 Raisonnement par contre-exemple
On considère un énoncé P donnant une propriété universelle de certains éléments d’une théorie
‫ ح‬et on se propose de demander que P soit faux. Pour cela il suffit d’exhiber un élément de la
théorie ‫ ح‬vérifiant 1P.
∀𝑥 𝑃(𝑥)
̅
𝑃 ∃𝑥
Ex : Tout naturel qui est à la fois divisible par 4 et par 6 est aussi divisible par 24
4 6 24
∀𝑛𝜀 ℕ∗ ∶ 𝑛 𝑒𝑡 𝑛 ⟹ 𝑛
∃36
 Raisonnement par récurrence
Le principe consiste à établir une forme propositionnelle où intervient une variable n avec n
entier naturel est vrai pour tout n.
Principe : P (n) n𝜖ℕ
Démontrer que n=0, n=1, n=2 les propositions obtenues démontrer que la proposition est vraie
jusqu’à l’ordre R + 1
Ex : la somme de n premiers nombres naturels
𝑛 (𝑛+1)(𝑛+2)
1.2+2.3+3.4 + …. +n(𝑛 + 1) = Démontrer par récurrence que cette proposition est
3
vraie.
1 (1+1)(1+2)
a) Vérifions que p(1) est vraie : 1.2 = 3
b) Soit k est un entier naturel et supposons que p(k) est vraie : 1.2+2.3+3.4 + …. +k(𝑘 + 1) =
𝑘 (𝑘+1)(𝑘+2)
3
(𝑘+1) (𝑘+2)(𝑘+3)
c) Montrons que p(k+1) est vraie : 1.2+2.3+3.4 + …. +(k+1)[(𝑘 + 1) + 1] = 3
𝑘 (𝑘+1)(𝑘+2)
1.2+2.3+3.4 + …. +k(k+1)+(𝑘 + 1)[(𝑘 + 1) + 1] = + (𝑘 + 1)[(𝑘 + 1) + 1]
3
𝑘(𝑘+1) (𝑘+2)+3(𝑘+1)[(𝑘+1)+1]
= 3
(𝑘+1) (𝑘+2)(𝑘+3)
= 3
APPLICATION
1) Si tous les chiens affectueux sont fidèles et si les chiens fidèles sont dociles, quelle
affirmation est certainement fausse ?
a) Tous les chiens affectueux sont dociles
b) Certains chiens affectueux sont dociles
c) Aucun chien affectueux n’est docile
2) Dans les phrases suivantes, indiquez si le « ou » est employé dans un sens inclusif ou
exclusif :
a) Ce sport est déconseillé aux personnes cardiaques ou asthmatiques ; R/ ou est inclusif
b) Au deuxième tour, le candidat sera élu ou battu ; R/ ou est exclusif
c) Demain à seize heures, je ferai du sport ou j’irai au cinéma ; R/ ou est exclusif
d) La clôture devra être réparée ou remplacée ; R/ ou est exclusif
e) Le moineau se nourrit des graines ou d’insectes ; R/ ou est inclusif
f) Je vivrai sans reproche ou périrai sans honte ; R/ ou est inclusif
g) Engageons un vendeur parlant KISANGA ou KIYEKE. R/ ou est inclusif
3) Préciser à l’aide d’un quantificateur le sens de « un » dans les phrases suivantes :
a) Un sot trouve toujours un plus sot qui l’admire ;
b) Un congolais doit être fier de son pays ;
c) Un congolais a été champion du monde en boxe ;
d) Dans un triangle isocèle, une médiane est également hauteur ;
e) Un homme a besoin d’avoir un idéal ;
f) Un enseignant a toujours un nouveau sujet à étudier.
4) Trois personne de trois nationalités différentes habitent les trois premières maisons
d’une rue. Chaque maison a une couleur différente et chaque personne a un métier différent.
On sait que :
a) L’angolais habite la maison rouge ;
b) Le congolais est musicien ;
c) Le gabonais habite la maison du milieu ;
d) La maison rouge est à côté de la verte ;
e) L’écrivain habite la première maison à gauche.
Quelle est la nationalité de l’écrivain ? Qui habite la maison jaune ?
5) Montrer que la conjonction et la disjonction sont distributives l’une par rapport à l’autre
a) P Ʌ (𝑄 𝑉 𝑅) ⇔ ( 𝑃 Ʌ 𝑄) 𝑉 (𝑃 Ʌ 𝑅)
b) P V (Q Ʌ 𝑅) ⇔ (𝑃 𝑉 𝑄) Ʌ ( 𝑃 𝑉 𝑅)
6) Construire la table de vérité de
(P ⇒ 𝑅) Ʌ (𝑄 ⇒ 𝑅)] ⟹ [(𝑃 Ʌ 𝑄) ⟹ 𝑅]
7) Trouver la valeur de vérité de la proposition suivante :
(P V R) ⇔ 𝑄] ⟹ [ 𝑃 Ʌ 𝑄]
Si P ≡ 0, 𝑄 ≡ 1 𝑒𝑡 𝑅 ≡ 1
8) Déterminer la valeur de vérité de la proposition suivante
a) ∀𝑥 ∈ 𝐴 ∶ 2 ≤ 𝑥 < 8 𝐴 = {2, 4, 6, 8}
b) ∃𝑥 ∈ 𝐸 ∶ 3 < 𝑥 < 7 ⟹ 𝑥 𝑑𝑖𝑣𝑖𝑠𝑒 5 𝐸 = {0,3,5,7}
9) Peut-on dire dans ℝ que 𝑥 >3 ⇒ 𝑥 >1?
𝑥 ≤3 ⟹𝑥 >1?
Donner la classe de ces 2 implications
Solution
1)
2)
3)
4) .

Rouge Verte Jaune

Angolais Gabonais Congolais
Ecrivain Musicien
L’Angolais est écrivain, Le Congolais habite la maison jaune.
5) a) P Q R PɅ𝑄 𝑃 Ʌ 𝑅 𝑄 Ʌ (𝑄 𝑉) (𝑃 Ʌ 𝑄) 𝑉 (𝑃 Ʌ 𝑅)
b) P Q R Q Ʌ 𝑅 𝑃 𝑉 (𝑄 Ʌ 𝑅) 𝑃 𝑉 𝑄 (𝑃 𝑉 𝑅 ) (𝑃 𝑉 𝑄) Ʌ (𝑃 𝑉 𝑅)
6) a) ∀𝑥 ∈ 𝐴 ∶ 2 ≤ 𝑥 < 8 𝐴 = {2, 4, 6, 8}. 𝑖𝑙 𝑓𝑎𝑢𝑡 𝑣é𝑟𝑖𝑓𝑖𝑒𝑟 𝑐𝑒𝑡𝑡𝑒 𝑓𝑜𝑟𝑚 ∀ {𝑥 𝜖𝐴 ∶
𝑃 (𝑥)} 𝐴
{x/2 ≤ 𝑥 < 8} ≠ 𝐴
Car 8 y est exclus
b) ∃𝑥𝜖 ∶ 3 < 𝑥 < 7 ⟹ 𝑥 𝑑𝑖𝑣𝑖𝑠𝑒 5
{∃𝑥|3 < 𝑥 < 7} = {5} 𝜖 = {0, 3, 5, 7}
{x∈ ∈∶ 𝑃 (𝑥)} ∅ 𝐿𝑎 𝑝𝑟𝑜𝑝𝑜𝑠𝑖𝑡𝑖𝑜𝑛 𝑒𝑠𝑡 𝑣𝑟𝑎𝑖𝑒
P (x) ⇒ 𝑄 (𝑥)
7) x>3 ⟹𝑥 >1 𝐷𝑎𝑛𝑠 ℝ
P (x) = x > 3
Q (x) = x > 1
Il faut trouver d’abord la classe de condition de chaque proposition
P (x) = x > 3 = ] 3, ∞ [ = 𝐴
Q (x) = x > 1 = ]1, +∞ [ = 𝐵
Pour trouver la classe de condition de toute la proposition (avec le signe implications) il faut
appliquer la formule (ĀՈḂ) U B
P(x) ⟹ 𝑄 (𝑥)
A CB
(ĀՈḂ) U B ⟹ ] − ∞, 3] Ո] − ∞, 1] U]1, +∞ = ℝ
En math : Ո = 1 on aura (TA Ʌ TB) VB ⇔ 𝐴 ⟹ 𝐵
Ո=V
c) x ≤ 3 ⟹ 𝑥 > 1 ; 𝑃 (𝑥) = 𝑥 ≤ 3 ⟹ 𝑍] − ∞, 3]
𝑄 (𝑥) = 𝑥 > 1 ⟹ 𝑛]1, + ∞[
Comme Z n’est pas inclus dans M
x≤3 ⟹𝑥 >1 ≡𝐹
(ŻՈṀ) U M
Trouver la valeur de vérité de ce qui précède.
Solution
n (n+1)(2𝑛+1)
Démontrer sur N que 1² + 2² + 3² + ………. + n² = avec n ≥ 1 n ∈ N
6
1 (1 + 1)(2.1 + 1)
n = 1 P (1) = =1=1
6
2 (2 + 1)(2.2 + 1)
n = 2 P (2) = =5=1
6
K (k + 1)(2K + N)
n = K P(K) = 6
(𝐾 + 1)(K + 1 + 1)[(2 (K+1)+1 )] (K + 1 )(2K + 3)
jusqu’à l’ordre K + 1 = P (K + 1) = =
6 6
P (K + 1) = 1² + 2² + 3² + ………. + K² + (K + 1)²
K (K + 1 )(2K + 1)
= + (K + 1)²
6
K (K + 1 )(2K + 1) + 6 (K+1 )²
= 6
(K + 1 )[K (2K + 1) +6 (K + 1)]
= 6
(K + 1 )(2K2 +K + 6K + 6)
= 6
(K + 1 )(2K² + K + 6) (K + 1 )(K + 2)(2K +3)
= =
6 6

T.P à (remettre Lundi)

1) Dans ℝ on considère les condites
a) P (X) : X ≤ 3 ; Q (X) : X ˃ 2
b) P (X) : X ˂ 4 ; Q (X) : X ˂ 5
c) P (X) : X ˂ 4 ; Q (X) : X ˃ 6
Pour chacun des cas, exprimer les conditions P et Q ; Pour Q ainsi que leur négation T (P 1 Q) ;
1 (P V Q) et trouver leurs classes.
2) Démontrer que tout prédécesseur d’une puissance et 10 un multiple de 9 (par récurrences)
3) Etudier de raisonnement suivant dû au logicien et mathématicien ALFRED "Supposons que
tout ensemble en de cardinal n, nous ayons démontré l’implication (P∈ En et Q∈ En) ⇒ (P = Q).
cet implication est vraie pour n = 1. Si elle est vraie pour tout n nos éléments de l’ensemble
En + 1 = {X1, X2, ……Xn + 1}. Les ensembles En = {X1, X2, Xn} et E’n = {X1,
X2, ……Xn + 1} sont chacun de cardinal
(a + b) R (c, d) ⇔ a = c et b ≤ d est une relation d’ordre (1, 4) R (1, 2) ⇔ 1 = 1 et 4 ≤ 2 : F la
relation est d’ordre partiel
CHAP IV : ALGEBRE DE BOOLE

L'algèbre de Boole est une structure algébrique qui ne contient que deux éléments, que l'on
appelle couramment variables logiques. Ces variables ne peuvent avoir que deux états :
- 0 : Faux (False)
- 1 : Vrai (True) ou : ouvert ou fermé, arrêt ou marche, inactif ou actif, relâché ou enfoncé.
Comme n'importe quelle autre algèbre, il existe dans l'Algèbre de BOOLE, des opérations, des
variables, et des fonctions. Celles-ci prennent le nom de :
- Opérations logiques
- Variables logiques
- Fonctions logiques
Alors on peut dire que l'algèbre de Boole est une algèbre qui opère sur des variables logiques
à l'aide des opérateurs logiques pour réaliser une fonction logique.
1. Les opérateurs logiques
On définit six opérations logiques :
- Trois opérations principales.
- Trois opérations secondaires.

1.1 Les opérateurs principaux

a) NON (NOT) :
- Appelé couramment inverseur a une seule entrée et une seule sortie, c'est un opérateur qui
réalise le complément d'une variable logique A, noté :
-
- Porte NON (NOT) Son fonctionnement est défini par la
table de vérité suivante :

-
- NON (NOT)
b) ET (AND):
C'est le produit logique de deux ou plusieurs variables logiques, le résultat de l'opération est 1,
lorsque toutes les variables sont à 1. Si A et B représentent deux variables logiques, le résultat
de l'opération ET entre ces deux variables est noté :

ET (AND)
c) OU (OR):
C'est la somme logique de deux ou plusieurs variables logiques, le résultat de
l'opération est 1, lorsque au moins une des variables est égale à 1. Si A et B
représentent deux variables logiques, le résultat de l'opération OU entre ces deux
variables A et B est noté :

La fonction OR, notée +, est définie par la table de vérité suivante :

OU (OR)
1.2 Les opérateurs secondaires
a) NON ET (NAND) :
C'est le complément de produit logique de deux variables logiques A et B noté :

Le symbole graphique d'une porte logique NAND est représenté comme suit :
Une opération logique NAND fonctionne selon la table de vérité suivante :

NON ET (NAND)
b) NON OU (NOR) :
C'est l'équivalent d'une opération OU suivie d'une opération NON de la somme logique de deux
variables logiques A et B notée :

L'opération logique NOR a pour symbole :

Porte NON OU (NOR) L'opération logique NOR a pour table de vérité
suivante

NON OU (NOR)
c) OU exclusif (XOR):
Cette opération donne comme résultat 1, si et seulement si une des deux variables est
égale à 1, elle est définie par :

Elle a pour représentation symbolique :

Sa table de vérité est la suivante :

OU Exclusif (XOR)
XOR est égal à 1 si et seulement si A = 1 ou B = 1 mais pas simultanément
Une opération XOR fournit un comparateur d'inégalité : XOR ne vaut 1 que si A et B sont
différents. Le complément du XOR correspond à un détecteur d'égalité.
2. Théorème de De-Morgan

Deux des plus importants théorèmes de l'algèbre booléenne nous ont été légués par le
mathématicien De Morgan. Les théorèmes de De Morgan se révèlent d'une grande utilité pour
simplifier des expressions comprenant des sommes ou des produits de variables
complémentés. Voici ces deux théorèmes :
Théorème :
- Le complément d'un produit logique égal à la somme des compléments
- Le complément d'une somme logique égal au produit des compléments
̅̅̅̅̅
𝑨. 𝑩 = ̅+𝑩
𝑨 ̅ ̅̅̅̅̅̅̅̅̅̅
∏𝒏𝒊=𝟏 𝑨𝒊 = ∑𝒏𝒊=𝟏 ̅̅̅
𝑨𝒊
{ ou { 𝒏
̅̅̅̅̅̅̅̅
𝑨+𝑩=𝑨 . 𝑩 ̅ ̅ ̅̅̅̅̅̅̅
∑𝒊 𝑨𝒊 = ∏𝒊=𝟏 ̅̅̅
𝒏
𝑨𝒊
Les théorèmes de De Morgan permettent de transformer les ET en OU et vice-versa. Le couple
(ET, NON) ou le couple (OU, NON) suffisent donc à exprimer n'importe quelle formule algébrique
combinatoire.

3. Propriétés des opérateurs logiques

Les opérateurs vus ci-dessus respectent les lois suivantes, qu'il est facile de vérifier par
induction parfaite, c'est à dire en vérifiant tous les cas possibles à partir des tables de vérité.

3.1. Propriétés des opérateurs AND et OR

a) Associativité

b) Commutativité

c) Distributivité

d) L'élément neutre

e) Complémentarité

f) Involution de la négation
g) L'invariance

h) L'idempotence

3.2. Propriétés des opérateurs NAND et NOR

a) Associativité

b) Commutativité

c) Distributivité

NAND :

NOR :
CHAP VI : GRAPHES

1. Définition : Un graphe est un ensemble de liens qui relient des éléments entre eux.
Les liens sont représentés par des lignes appelées arêtes ou par des arcs.

Les éléments sont représentés par des points qu'on appelle sommets. Les éléments peuvent
être des lieux, des personnes, des tâches, etc.
Dans la représentation graphique d'un graphe:

 Les sommets sont généralement identifiés par une lettre minuscule, une lettre majuscule,
un nombre ou un mot.
 Les arêtes sont généralement nommées à l'aide des lettres désignant ses extrémités dans
n'importe quel ordre.
 Voici un exemple de graphe qui traduit une situation bien précise. Les sommets représentent
des îles et les arêtes représentent des ponts.

Situation réelle

2. Types de graphes (Graphe complet graphe connexe)

Un graphe complet est un graphe dont chaque sommet est relié directement à tous les autres
sommets.
Graphe complet graphe non complet

Un graphe est connexe quand tout sommet peut être relié à tout autre sommet par une arête
ou une suite d’arêtes. Le graphe connexe est un graphe en un seul morceau.
3. Ordre d’un graphe
L'ordre d'un graphe correspond au nombre de sommets contenus dans un graphe.

L’ordre du graphe est de 5 L’ordre du graphe est de 4

4. Degré d’un sommet
Le nombre de fois qu’un sommet est touché par une arête est le degré de ce sommet.
Si plus d’une arête relient deux sommets, ces arêtes sont dites parallèles.
Une boucle est une arête qui lie un sommet à lui-même. Celle-ci compte pour une arête, mais
pour 2 degrés.

Le degré du sommet C = 4
Le degré du sommet B = 2
Le degré du sommet A = 2
Le degré du sommet E = 2
Le degré du sommet D = 2

Le nombre d’arêtes du graphe est 6.

La somme des degrés de tous les sommets d'un graphe est toujours le double du nombre
d'arêtes du graphe. Dans l'exemple précédent, il y a 6 arêtes et la somme des degrés de tous
ses sommets est 12.
5. Optimisation à l’aide de graphes
Les graphes sont une façon utile de représenter certaines situations. À l'aide de ces graphes, il
est possible d'optimiser ou de résoudre des situations qui, à première vue, peuvent nous
apparaitre très complexes. Voici quelques méthodes d'optimisation à l'aide des graphes.
6. Chemin critique
Dans certains types de situation, il est possible de représenter les différentes étapes à l'aide
d'un graphe value et orienté. Ainsi, il sera visuellement possible de voir différents chemins
partant tous du même point d'origine et se rendant au même point final. Certains de ces chemins
peuvent être parallèles, ce qui signifie que les étapes qui les composent peuvent se dérouler en
même temps. Parmi tous ces chemins, celui ayant le plus grand poids est le chemin critique. Le
poids ici représente le temps minimal qu'il faut considérer pour réaliser le projet au complet.
Etapes de résolution d’un problème avec l’utilisation du chemin critique
1. Représenter la situation à l'aide d'un graphe valué et orienté en tenant compte des étapes
préalables.
2. Déterminer le poids de chacun des chemins qui relient le sommet du début et le sommet de
la fin.
3. Le chemin critique du graphe correspond au chemin qui a le plus grand poids. Il suffit
d'interpréter la réponse selon la situation.

Produire un album de finissant

Le comité des finissants d'une école secondaire se prépare à la production d'un album de
finissants. La directrice de l'école leur demande d'estimer le temps requis pour la production
de leur album. Voici un tableau qui présente les étapes à faire pour la réalisation de l'album de
finissants.
Tâches Temps (jours) Préalables
A : Acheter les films 1 Aucun
B : Charger les caméras 1 A
C : Prendre les photos du
3 B
conseil étudiant
D : Prendre les photos des
2 B
enseignants
E : Prendre les photos des
1 B
clubs sportifs
F : Faire développer les
2 C-D-E
photos
G : Faire la mise en page 5 F
H : Faire signer par le
3 G
comité de l’album
I : Faire signer par la
2 G
directrice
J : Imprimer les albums 5 H-I
Exemple : Déterminer le nombre minimum de jours requis pour la production de l'album de
finissants.
Solution
Etape 1 :

Étape 2

Début - A - B - C - F - G -H –J - Fin = 20
Début - A - B - C - F - G - I - J - Fin = 19
Début - A - B - D - F - G - H - J - Fin = 19
Début - A - B - D - F - G - I - J - Fin = 18
Début - A - B - E - F - F - H - J - Fin = 18
Début - A - B - E - F - G - I - J - Fin = 17

Étape 3

Dans cet exemple, le chemin critique est Début - A - B - C - F - G - H - J - Fin puisque son
poids est le plus élevé, soit 20 jours. On peut donc affirmer que la production de l'album
prendra au minimum 20 jours.
7. Arbre de valeur minimale ou maximale
Dans le type de problème présentant, par exemple, des situations impliquant des réseaux, il est
souvent demandé de minimiser ou de maximiser les couts ou les distances. Il faut donc trouver
l'arbre de la valeur minimale ou maximale qui relie entre eux tous les sommets d'un graphe.
Étapes de résolution d'un problème avec l'utilisation de l'arbre de valeur minimale:

1. Réécrire les sommets du graphe à côté du graphe de départ.

2. Tracer l'arête ayant le plus petit poids.
3. Parmi les arêtes restantes, répéter la deuxième étape jusqu'à ce que tous les sommets du
graphe soient reliés sans cycle simple.
4. Calculer le poids de l'arbre obtenu si nécessaire.

Étapes de résolution d'un problème avec l'utilisation de l'arbre de valeur maximale:

1. Réécrire les sommets du graphe à côté du graphe de départ.
2. Tracer l'arête ayant le plus gros poids.
3. Parmi les arêtes restantes répéter la deuxième étape jusqu'à ce que tous les sommets du
graphe soient reliés sans cycle simple.
 4. Calculer le poids de l'arbre obtenu si nécessaire.

Exemple

Construction de trottoirs

Un entrepreneur doit relier 5 immeubles par des trottoirs

de béton. Il soumet une première estimation du cout de
l'opération, représenté par le graphe valué ci-contre. Les
couts notés sont en milliers de dollars.

On veut minimiser le cout total de la construction de ces

trottoirs en s'assurant que tous les immeubles soient
reliés.

Solution
Comme on veut minimiser les couts, il faut donc déterminer l'arbre de valeur minimale.
Étape 1
Réécrire les sommets du graphe à côté du graphe de départ.
Étape 1 Étape 2
Réécrire les sommets du graphe à côté du Tracer l'arête ayant le plus petit poids.
graphe de départ.

Étape 3
Parmi les arêtes restantes, répéter la deuxième étape jusqu'à ce que tous les sommets du
graphe soient reliés sans cycle simple.
Puisque deux arêtes ont la même valeur, on les sélectionne tous les deux successivement s'ils
ne créent pas de cycle simple. Puis, on continue avec la valeur suivante.

Puisque l'arête ED créerait un cycle simple, on passe à la suivante.

Après avoir sélectionné le segment AB, tous les sommets sont maintenant reliés. On a donc
l'arbre de valeur minimale.

Étape 4
Calculer le poids de l'arbre obtenu.

Il suffit d'additionner la valeur de toutes les arêtes sélectionnées pour connaitre le cout total des
travaux.

Cout=7+8+8+10=33 milliers de dollars=33 000Cout=7+8+8+10=33 milliers de dollars=33 000 $

8. La chaine de poids minimal

Dans certaines situations, il sera question de trouver la chaine de poids minimal reliant deux
points en particulier dans un graphe valué. Cette chaine de poids minimal porte aussi le nom de
chaine optimale.

Étapes pour la recherche de la chaine optimale entre deux sommets dans un graphe valué
:

1. Assigner à chaque sommet adjacent à celui de départ une lettre et un nombre représentant
respectivement le sommet de provenance et le poids de la plus petite chaine qui les relie.
2. Répéter la première étape jusqu'au sommet d'arrivée.
3. Procéder à rebours pour reconstituer la chaine optimale en partant du dernier sommet
jusqu'au sommet de départ.
Le chemin le plus court

Voici le plan d'un quartier regroupant 7 immeubles. Laurie réside dans l'immeuble A et elle
veut se rendre chez son amie Jessica, qui habite dans l'immeuble G, en empruntant le chemin
le plus court. Par où doit-elle passer et combien de temps est-ce que ça devrait lui prendre si
les valeurs indiquées sur le graphe suivant sont les durées de déplacement (en minutes)?

Solution

1. Assigner, à chaque sommet adjacent à celui de départ, une lettre et un nombre

représentant respectivement le sommet de provenance et le poids de la plus petite chaine
qui les relie.

Le sommet A est le sommet de départ. Les sommets adjacents sont B, C, D et E. On recherche

donc la chaine ayant la plus petite valeur reliant chacun de ces sommets au sommet de départ.

Pour le sommet B, la chaine ayant la plus petite valeur, 7, est celle provenant directement de A.
On inscrit donc 7(A) juste à côté du sommet B. Pour C, la chaine ayant la plus petite valeur, 6,
provient directement de A. On inscrit donc 6(A) juste à côté du sommet C. Pour D, la chaine
provenant directement du sommet A a une valeur de 9, mais celle passant par le sommet C a
une valeur plus petite, soit 6+1=7. On choisit donc cette dernière en inscrivant 7(C). Pour E, la
chaine ayant la plus petite valeur est celle passant par C puis par D, avec une valeur
de 6+1+3=10. On y inscrit 10(D).
2. Répéter la première étape jusqu'au sommet d'arrivée.

Comme nous avons évalué les sommets B, C, D, E, nous devons maintenant appliquer la
même procédure aux sommets adjacents, soit F et G.

Pour F, la chaine provenant de D a une valeur de 7+8=15 et celle provenant de E a une valeur
de 10+4=[Link] choisit donc la chaine issue du sommet E en inscrivant 14(E) à côté de
F. Pour G, en procédant de la même façon, on trouve que la chaine de poids minimal est celle
provenant du sommet F, avec une valeur de 14+5=19. On y inscrit donc 19(F).

3. Procéder à rebours pour reconstituer la chaine optimal en partant du dernier sommet

jusqu'au sommet de départ.

En partant du dernier sommet G, on suit les indications que nous avons inscrites à côté de
chaque sommet pour reconstituer la chaine de poids minimal jusqu'au sommet de départ.

La chaine optimale recherchée est donc la chaine A-C-D-E-F-G. C'est alors le trajet que Laurie
devra emprunter pour se rendre le plus rapidement possible chez Jessica. Elle devrait y être
en 19 minutes.
En regardant l'exemple précédent, on remarque que ce n'est pas nécessairement la ligne droite
qui est la plus courte. En effet, le trajet A-C-E-G a une valeur totale de 20 minutes
comparativement au trajet de 19 minutes que nous avions trouvé. Ce n'est pas non plus le trajet
qui compte le moins d'étapes qui est le plus court, car A-E-G n'a que 2 étapes et est d'une durée
de 24 minutes.

Un algorithme semblable à la démarche employée pour résoudre le problème précédent est

programmé dans les applications de GPS de nos téléphones intelligents.
9. Le nombre Chromatique
Le nombre chromatique est le nombre minimal de couleurs qu'on doit utiliser pour colorer tous
les sommets d'un graphe en s'assurant que deux sommets adjacents ne soient pas de la même
couleur.
On utilise les concepts de graphe coloré et de nombre chromatique pour résoudre les problèmes
de planification pour lesquels on doit tenir compte de certaines incompatibilités.

Les situations suivantes sont des exemples de cas où il peut être utile de trouver le nombre
chromatique : la planification d'horaire, le regroupement d'espèces d'animaux ou de plantes, la
coloration des États sur une carte du monde, etc.
Étapes de résolution d'un problème avec l'utilisation du nombre chromatique :

a) Tracer le graphe représentant la situation où les sommets sont les éléments à considérer
et où les arêtes illustrent les incompatibilités entre les éléments.
b) Dresser la liste des sommets du graphe en ordre décroissant de degré (l'ordre n'a pas
d'importance pour deux sommets ayant le même degré).
c) Colorier le premier sommet de la liste (celui dont le degré est le plus élevé) d'une couleur
de son choix.
d) En suivant la liste, attribuer la même couleur aux autres sommets qui ne sont pas reliés au
premier sommet ni entre eux.
e) Répéter les étapes 3 et 4 avec une nouvelle couleur chaque fois jusqu'à ce que les sommets
soient tous colorés.
f) Calculer le nombre de couleurs utilisées pour donner le nombre chromatique et répondre à
la question.

Exemple : le festival de musique

Les organisateurs d’un festival de musique doivent planifier l’horaire des représentations des
différents groupes à l’affiche, mais ils ont plusieurs contraintes à respecter.

 Le groupe Les Amateurs ne peut pas jouer en même temps que Les Bons à rien parce
que les 2 groupes ont le même batteur.
 Le chanteur Calvin Harry ne peut pas faire sa prestation en même temps que Dany
Lavoto puisque les deux utilisent le même équipement de scène.
 Calvin Harry et Janis Jackson ne veulent pas se produire sur scène en même temps
puisqu’ils partagent sensiblement le même public.
 Les artistes suivants : Calvin Harry, Janis Jackson, Éléonore Rugby et Dany
Lavoto refusent de faire leur spectacle en même temps que Les Valeureux Pingouins parce
qu’ils jugent que ceux-ci sont trop populaires et qu’il n’y aurait donc plus assez de spectateurs
pour leur propre spectacle.
 Finalement, Janis Jackson ne veut pas jouer en même temps que Les Bons à rien parce
qu’elle veut absolument assister à leur spectacle.

À la lumière de toutes ces contraintes, quel est le nombre minimal de scènes et de soirs qui
seront nécessaires pour présenter tous ces spectacles lors de ce festival?

Solution
1. Tracer le graphe représentant la situation où les sommets sont les éléments à considérer et
où les arêtes illustrent les incompatibilités entre les éléments
 Légende

A : Les Amateurs
B : Les Bons à rien
CH : Calvin Harry
DL : Dany Lavoto
ER : Éléonore Rugby
JJ : Janis Jackson
VP : Les Valeureux Pingouins

2. Dresser la liste des sommets du graphe en ordre décroissant de degré

VP (4), CH (3), JJ (3), DL (2), B (2), A (1), ER (1)

3. Colorier le premier sommet de la liste d'une couleur de son choix

Le sommet VP est le sommet ayant le plus grand degré, soit 4. On le colore en bleu.

4. En suivant la liste, attribuer la même couleur aux autres sommets qui ne sont pas
reliés au premier sommet ni entre eux

Les seuls sommets qui ne sont pas reliés à VP et qui sont reliés entre eux sont A et
B. On colore alors B puisqu'il est le prochain sur la liste.

5. Répéter les étapes 3 et 4 avec une nouvelle couleur chaque fois jusqu'à ce que les
sommets soient tous colorés

Les prochains sommets de plus haut degré sont CH et JJ. On choisit CH qu'on colore en vert.
On peut également attribuer la couleur verte aux sommets A et ER, qui ne sont pas reliés
entre eux ni à CH.

Finalement, les 2 derniers sommets qui ne sont pas encore colorés ne sont pas reliés entre
eux. On peut donc leur attribuer la même couleur sans problème. On choisit arbitrairement le
rouge.

Voici donc le graphe représentant la situation :

Légende

A : Les Amateurs
B : Les Bons à rien
CH : Calvin Harry
DL : Dany Lavoto
ER : Éléonore Rugby
JJ : Janis Jackson
VP : Les Valeureux
Pingouins
6. Calculer le nombre de couleurs utilisées pour donner le nombre chromatique et
répondre à la question

Nous avons utilisé 3 couleurs différentes. Le nombre chromatique de ce graphe est donc 3.
Mais qu'est-ce que cela signifie dans la mise en situation?

Les groupes qui ont été colorés d'une même couleur vont pouvoir présenter leur spectacle lors
du même soir. Comme le nombre chromatique est 3, cela signifie qu'il faudra 3 soirs pour
présenter tous les spectacles. Comme il y a 3 sommets verts (et seulement 2 en bleu et 2 en
rouge), cela signifie qu'il faudra 3 scènes pour présenter simultanément les spectacles
des Amateurs, de Calvin Harry et d'Éléonore Rugby.

Remarque : À l'étape 5, si on avait choisi le sommet JJ au lieu du sommet CH, on aurait obtenu
le même nombre de soirs, mais un nombre différent de scènes.
Bibliographie

 Kenneth H. Rosen, Discrète Mathematics and Its Applications.

 Susanna S. Epp, Mathematics with Applications.
 Norman L. Biggs, Discrete Mathematics.
 Thomas H. Cormen et collaborateurs, Introduction to Algorithms (pour les applications
aux algorithmes).