Chapitre 137 minDébutant
Aide-mémoire : les formules de logique et de Boole
Par Josselyn C., prof de BTS SIO. Mis à jour le .
À la fin de ce chapitre, tu sauras
- retrouver en un coup d'œil une table, une loi ou une notation ;
- relire les erreurs qui coûtent le plus de points.
Cet aide-mémoire rassemble sur une page les tables de vérité, les notations, les lois du calcul propositionnel et de l'algèbre de Boole, les règles des quantificateurs et des ensembles, et la méthode de Karnaugh. C'est la page à relire la veille de l'épreuve E3 ; chaque ligne renvoie au chapitre qui l'explique.
Les tables de vérité
| a | b | non a | a et b | a ou b | a ⊕ b | a ⇒ b | a ⇔ b | NAND | NOR |
|---|---|---|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 0 |
À retenir : le et ne vaut 1 que sur une ligne, le ou ne vaut 0 que sur une ligne, l'implication ne vaut 0 que pour 1 ⇒ 0 (chapitres 1 et 2).
Les notations
| Opération | Logique | Ensembles | Algèbre de Boole | Python | SQL |
|---|---|---|---|---|---|
| Non | ¬P | A̅ | a̅ | not | NOT |
| Et | P ∧ Q | A ∩ B | ab | and | AND |
| Ou | P ∨ Q | A ∪ B | a + b | or | OR |
| Faux / vrai | F / V | ∅ / E | 0 / 1 | False / True | FALSE / TRUE |
| Implication | P ⇒ Q | A ⊂ B (vraie pour tout x) | a̅ + b | not p or q | NOT p OR q |
Priorités : non, puis et, puis ou. Dans le doute, des parenthèses.
Implication et équivalence
| Formule | Équivalent | Remarque |
|---|---|---|
| P ⇒ Q | ¬P ∨ Q | Fausse seulement si P vraie et Q fausse |
| Contraposée | ¬Q ⇒ ¬P | Toujours équivalente à P ⇒ Q |
| Réciproque | Q ⇒ P | Pas équivalente en général |
| Négation de P ⇒ Q | P ∧ ¬Q | Ce n'est pas une implication |
| P ⇔ Q | (P ⇒ Q) ∧ (Q ⇒ P) | Vraie si P et Q ont la même valeur |
« P seulement si Q », « il faut Q pour P » : P ⇒ Q. « Il suffit de P pour Q », « Q dès que P » : P ⇒ Q aussi (langage courant).
Les lois de l'algèbre de Boole
| Loi | Forme produit | Forme somme |
|---|---|---|
| Neutre | a · 1 = a | a + 0 = a |
| Absorbant | a · 0 = 0 | a + 1 = 1 |
| Idempotence | aa = a | a + a = a |
| Complémentarité | aa̅ = 0 | a + a̅ = 1 |
| Distributivité | a(b + c) = ab + ac | a + bc = (a + b)(a + c) |
| Absorption | a(a + b) = a | a + ab = a |
| Absorption du complément | a(a̅ + b) = ab | a + a̅b = a + b |
| Adjacence | (a + b)(a + b̅) = a | ab + ab̅ = a |
| De Morgan | non(ab) = a̅ + b̅ | non(a + b) = a̅ b̅ |
Plus : commutativité, associativité, double complément (le complément de a̅ est a), et le consensus ab + a̅c + bc = ab + a̅c (chapitres 6 et 7).
Ce qui n'existe pas : 1 + 1 = 2, a + a = 2a, aa = a², la simplification de a + b = a + c en b = c.
Les quantificateurs
| Énoncé | Négation |
|---|---|
| ∀x ∈ E, p(x) | ∃x ∈ E, ¬p(x) |
| ∃x ∈ E, p(x) | ∀x ∈ E, ¬p(x) |
| ∀x ∈ E, p(x) ⇒ q(x) | ∃x ∈ E, p(x) ∧ ¬q(x) |
| ∀x, ∃y, p(x, y) | ∃x, ∀y, ¬p(x, y) |
Un contre-exemple suffit pour réfuter un « pour tout » ; un exemple suffit pour prouver un « il existe ». L'ordre de ∀ et ∃ change le sens ; deux quantificateurs du même type s'échangent (chapitre 3).
Les ensembles
- x ∈ A : un élément appartient à un ensemble ; A ⊂ B : un ensemble est inclus dans un autre.
- Si card(E) = n, alors card(P(E)) = 2ⁿ.
- A ∩ B (et), A ∪ B (ou), A̅ (non), A \ B = A ∩ B̅.
- De Morgan : complémentaire de A ∩ B = A̅ ∪ B̅ ; complémentaire de A ∪ B = A̅ ∩ B̅.
- card(A ∪ B) = card(A) + card(B) − card(A ∩ B) ; card(A̅) = card(E) − card(A).
- {x ∈ E | p(x)} : l'ensemble des éléments qui vérifient p (chapitre 5).
Forme canonique et Karnaugh
- Minterme d'une ligne : variable à 1 telle quelle, variable à 0 barrée (la ligne 101 donne ab̅c).
- Forme canonique disjonctive : somme des mintermes des lignes où la fonction vaut 1 (chapitre 8).
- Tableau de Karnaugh à 3 variables : a en ligne, bc en colonne dans l'ordre 00, 01, 11, 10 ; les colonnes 00 et 10 sont voisines.
- Regroupements : uniquement des 1, rectangles de 1, 2, 4 ou 8 cases, les plus grands possible, le moins possible, chevauchements permis.
- Lecture : on garde les variables constantes dans le groupe (1 → telle quelle, 0 → barrée) ; un groupe de 2 élimine une variable, un groupe de 4 en élimine deux (chapitre 9).
En informatique
- Adresse du réseau = adresse IP ET masque ; adresse de diffusion = adresse IP OU complément du masque.
- Masque de bits :
x & mgarde,x | mallume,x ^ minverse les bits où m vaut 1. - a ⊕ k ⊕ k = a : le XOR chiffre et déchiffre avec la même clé ; il calcule aussi la parité du RAID 5.
- NAND et NOR sont universelles : chacune suffit pour construire toutes les autres opérations (chapitre 10).
andetors'arrêtent dès que le résultat est connu (court-circuit) ;all()est un ∀ etany()un ∃ (chapitre 11).
Les erreurs qui coûtent le plus de points
| Erreur | Correction |
|---|---|
| non(a + b) = a̅ + b̅ | non(a + b) = a̅ b̅ : quand la barre se casse, le signe change |
| Négation de « tous » = « aucun » | Négation de « tous » = « au moins un ne… pas » |
| Négation de P ⇒ Q = ¬P ⇒ ¬Q | Négation de P ⇒ Q = P ∧ ¬Q |
| « P seulement si Q » = Q ⇒ P | « P seulement si Q » = P ⇒ Q |
| Colonnes de Karnaugh 00, 01, 10, 11 | Colonnes 00, 01, 11, 10 (code de Gray) |
| Oublier que les colonnes 00 et 10 sont voisines | Le tableau se referme comme un cylindre |
| Un groupe de 3 ou de 6 cases | Seulement 1, 2, 4 ou 8 cases |
| 1 + 1 = 2 ou 1 + 1 = 0 | 1 + 1 = 1 (c'est le XOR qui donne 1 ⊕ 1 = 0) |
| Confondre ∈ et ⊂ | Élément ∈ ensemble ; ensemble ⊂ ensemble |
| Une phrase finale qui recopie les lettres | Une phrase avec les mots de l'énoncé |