Représenter deux ensembles dans un diagramme de Venn
Distinguer ∩, ∪, \ et complémentaire
Table de vérité P⟹Q
P=V,Q=V → V | P=V,Q=F → F P=F,Q=V → V | P=F,Q=F → V
De Morgan
¬(A∧B) = ¬A∨¬B ¬(A∨B) = ¬A∧¬B
Cardinal de l'union
Card(A∪B) = Card(A) + Card(B) − Card(A∩B)
📝 Exemple type CCF
120 personnes aiment A, 80 aiment B, 30 les deux.
① Calculer Card(A∪B). (120+80−30 = 170)
② Écrire la contraposée de "x pair ⟹ x divisible par 4" et construire sa table de vérité.
Schéma — Diagramme de Venn
→ A\B (bleu) : dans A mais pas B | A∩B (violet) : éléments communs | B\A (vert) : dans B mais pas A → Ā∩B̄ (extérieur pointillé) : n'appartient ni à A ni à B | Ex : 120+80−30 = 170
CH 02
Utilisation des matrices
⚠ Au CCF chaque année
Vocabulaire
Matrice (m×n) – tableau m lignes × n colonnes
aᵢⱼ – élément à la ligne i, colonne j
Matrice carrée – autant de lignes que de colonnes
Identité I – 1 sur la diagonale, 0 ailleurs
Transposée ᵗA – lignes et colonnes échangées
Puissance Aⁿ – A multiplié n fois par lui-même
Matrice d'adjacence – représente un graphe (0 ou 1)
Notions à maîtriser
Additionner deux matrices (même taille)
Multiplier par un scalaire
Calculer le produit A×B
Calculer A² = A×A
Lire une matrice d'adjacence
Interpréter M²[i][j] : chemins de longueur 2
⚠ A×B ≠ B×A (non commutatif)
Produit C = A×B
C[i][j] = somme des (A[i][k] × B[k][j]) pour k de 1 à p
Règle de taille
(m×p) × (p×n) → résultat (m×n) Colonnes de A = lignes de B
Matrice d'adjacence
M[i][j]=1 si arc i→j, sinon 0 M²[i][j] = nb chemins de longueur 2
📝 Exemple type CCF
A = [[1,2],[0,1]] et B = [[3,1],[1,0]].
① Calculer A×B et B×A. Conclure sur la commutativité. ② Calculer A².
③ Donner la matrice d'adjacence de A→B, B→C et interpréter M²[A][C].
Schéma — Produit matriciel A×B = C
→ C[i][j] = (ligne i de A) · (colonne j de B) — les cases jaunes se croisent pour donner la case orange → C[1][1] = 1×5 + 2×7 = 19 | Règle de taille : (m×p)×(p×n) → résultat (m×n) | ⚠ A×B ≠ B×A
CH 03
Graphes
⚠ Au CCF chaque année
Vocabulaire
Graphe orienté – arcs avec direction (flèches)
Graphe non orienté – arêtes sans direction
Sommet / Nœud – point du graphe
Arc – lien orienté entre deux sommets
Prédécesseur – sommet qui pointe vers S
Successeur – sommet vers lequel S pointe
Niveau 0 – aucun prédécesseur
Niveau k – max(niveaux prédéc.) + 1
Circuit – chemin qui revient à son départ
Notions à maîtriser
Dessiner un graphe depuis une liste d'arcs
Construire la matrice d'adjacence M
Lire les prédécesseurs / successeurs dans M
Calculer le niveau de chaque sommet
Identifier les circuits
Trouver tous les chemins entre deux sommets
Calculer M² et interpréter ses entrées
Matrice d'adjacence
M[i][j] = 1 si arc de i vers j M[i][j] = 0 sinon
Niveau d'un sommet
Niveau 0 : aucun prédécesseur Niveau k : max(niveaux prédéc.) + 1
Puissance M²
M²[i][j] = nombre de chemins de longueur 2 de i vers j
📝 Exemple type CCF
Arcs : A→B, A→C, B→D, C→D.
① Dessiner le graphe. ② Écrire la matrice M. ③ Calculer M² et interpréter M²[A][D].
④ Donner le niveau de chaque sommet. (A=0, B=1, C=1, D=2)
Schéma — Graphe orienté avec niveaux
→ Niveaux (bandes vertes) : A=0 | B=1, C=1 | D=2 (prédécesseurs : B et C) → M[A][B]=1 car A→B | M²[A][D]=2 → 2 chemins de longueur 2 : A→B→D et A→C→D
CH 04
Calcul booléen
⚠ Au CCF chaque année
Vocabulaire
Variable booléenne – valeur 0 ou 1
NON / ā – inverse la valeur
ET / a·b – vaut 1 si les deux valent 1
OU / a+b – vaut 1 si au moins un vaut 1
XOR – OU exclusif : 1 si exactement un vaut 1
FND – somme de produits (mintermes)
Minterme – produit vrai pour une seule ligne
Tableau de Karnaugh – simplification graphique
Notions à maîtriser
Construire la table de vérité de f(a,b,c)
Extraire la FND (lignes où f=1)
Simplifier avec les lois algébriques
Remplir et lire un tableau de Karnaugh
Regrouper les 1 par groupes de puissance de 2
Reconnaître les portes logiques (AND, OR, NOT…)
Idempotence & Absorption
a+a = a | a·a = a a+a·b = a | a·(a+b) = a
De Morgan
NOT(a AND b) = ā+b̄ NOT(a OR b) = ā·b̄
Complémentation
a+ā = 1 | a·ā = 0 ā̄ = a | 1̄ = 0 | 0̄ = 1
📝 Exemple type CCF
f(a,b,c) vaut 1 pour (0,1,0), (0,1,1), (1,1,0), (1,1,1).
① FND : f = ā·b·c̄ + ā·b·c + a·b·c̄ + a·b·c
② Simplifier : f = b·(ā+a)·(c̄+c) = b | ③ Vérifier avec un tableau de Karnaugh.
Schéma — Tableau de Karnaugh (3 variables)
→ Code de Gray : 00, 01, 11, 10 (1 seul bit change à chaque colonne — obligatoire) → Groupe de 4 (colonnes 11 et 10, 2 lignes) : a et c varient → ils s'éliminent → reste b=1 → f = b
CH 05
Compléments sur les graphes — PERT / MPM
⚠ Au CCF chaque année
Vocabulaire
Tâche – action à réaliser avec une durée
Antécédents – tâches à terminer avant
Date au plus tôt – début au plus tôt possible
Date au plus tard – début au plus tard sans retard
Marge totale – retard possible sans impact projet
Chemin critique – chemin le plus long, marge = 0
Durée minimale – longueur du chemin critique
Fermeture transitive – accessibilité entre sommets
Notions à maîtriser
Construire le graphe depuis un tableau de tâches
Calculer les dates au plus tôt (gauche → droite)
Calculer les dates au plus tard (droite → gauche)
Calculer la marge de chaque tâche
Identifier le chemin critique (marges nulles)
Donner la durée minimale du projet
Analyser l'impact d'un retard
Date au plus tôt (→)
DPT⁺(S) = max( DPT⁺(prédéc.) + durée arc )
Date au plus tard (←)
DPT⁻(S) = min( DPT⁻(success.) − durée arc )
Marge & chemin critique
Marge = DPT⁻ − DPT⁺ Chemin critique ↔ Marge = 0
📝 Exemple type CCF (sujet officiel)
Tâches : A(7j,−), B(2j,−), C(2j,B), D(3j,C), E(5j,−), F(1j,B+D+E).
① Construire le graphe MPM. ② Calculer toutes les dates tôt/tard. ③ Donner la durée minimale et le chemin critique.
④ Si E prend 2j de retard, le projet est-il impacté ?
Schéma — Ordonnancement PERT & chemin critique
→ Tôt (→) : max(tôt prédécesseur + durée) | Tard (←) : min(tard successeur − durée) → Marge = Tard − Tôt. Marge = 0 → chemin critique (orange). Durée minimale = 7 jours (A+C) → B (marge=4) et D (marge=4) peuvent prendre 4 jours de retard sans impacter le projet
CH 06
Éléments de la théorie des ensembles
⚠ Présent au CCF
Vocabulaire
Relation binaire – lien entre 2 éléments
Réflexivité – a R a pour tout a
Symétrie – a R b ⟹ b R a
Antisymétrie – a R b et b R a ⟹ a=b
Transitivité – a R b et b R c ⟹ a R c
Équivalence – réflexive + symétrique + transitive
Ordre – réflexive + antisymétrique + transitive
Classe d'équivalence – groupe d'éléments équivalents
Application – une seule image par élément
Injection – images toutes distinctes
Surjection – tout élément d'arrivée est atteint
Bijection – injection ET surjection
Notions à maîtriser
Vérifier les 4 propriétés d'une relation
Conclure : équivalence, ordre, ou aucune
Représenter par un graphe ou une matrice
Identifier les classes d'équivalence
Distinguer injection, surjection, bijection
Vérifier qu'une correspondance est une application
Calculer le cardinal de l'ensemble quotient
Exemple équivalence
a R b ⟺ a≡b [3] Classes : {0,3,…} | {1,4,…} | {2,5,…}
Application f : A→B
✓ Tout élément de A a une image ✓ Chaque élément a une seule image
Sur E={1,2,3,4,5,6} : a R b ⟺ même reste dans la division par 3.
① Vérifier que R est une relation d'équivalence. ② Donner les 3 classes d'équivalence.
③ f(x) = x mod 3 : f est-elle injective ? surjective ?
Schéma — Application f(x) = x mod 3
→ f est une APPLICATION : chaque élément de E a exactement une flèche sortante → f est SURJECTIVE : 0, 1 et 2 sont tous atteints (tout F est couvert) → f N'EST PAS INJECTIVE : 1 et 4 arrivent à la même image (1), 2 et 5 → (2), 3 et 6 → (0) → Classes d'équivalence associées : {1,4}, {2,5}, {3,6}