M03 - Logique booléenne et Karnaugh

M03 - Logique booléenne, De Morgan et tableaux de Karnaugh

Objectif

Écrire une table de vérité, simplifier une expression par le calcul (lois) ou par un tableau de Karnaugh, et nier une expression avec De Morgan.

---

1. Les opérateurs

$a$	$b$	$a\cdot b$ (ET)	$a+b$ (OU)	$\bar{a}$ (NON)	$a\oplus b$ (OU exclusif)	$a\Rightarrow b=\bar{a}+b$
0	0	0	0	1	0	1
0	1	0	1	1	1	1
1	0	0	1	0	1	0
1	1	1	1	0	0	1

Priorité : NON puis ET puis OU → $a\cdot b+c=(a\cdot b)+c$.

En informatique : ET = and/&&/&, OU = or/||/|, NON = not/!, XOR = ^. Le ET binaire sert à calculer une adresse réseau (IP ET masque) → R03 - Adressage IPv4 et classes ; le XOR sert à la parité RAID → ST01 - RAID.

2. Les lois à connaître

Nom	Avec ET	Avec OU
Élément neutre	$a\cdot 1=a$	$a+0=a$
Élément absorbant	$a\cdot 0=0$	$a+1=1$
Idempotence	$a\cdot a=a$	$a+a=a$
Complément	$a\cdot \bar{a}=0$	$a+\bar{a}=1$
Double négation	$\overline{\stackrel{ˉ}{a}}=a$
Distributivité	$a(b+c)=ab+ac$	$a+bc=(a+b)(a+c)$
Absorption	$a(a+b)=a$	$a+ab=a$
Absorption 2		$a+\bar{a}b=a+b$

De Morgan ⭐

$\overline{a+b}=\bar{a}\cdot \bar{b}\overline{a\cdot b}=\bar{a}+\bar{b}$ Règle : on barre chaque terme et on échange + et ·.

Exemples :

• $\overline{a\cdot (b+\bar{c})}=\bar{a}+\bar{b}\cdot c$
• $\overline{\bar{a}+c\cdot \bar{b}}=a\cdot (\bar{c}+b)$
• Année bissextile : $C=P+Q\cdot \bar{R}$ → $\bar{C}=\bar{P}\cdot (\bar{Q}+R)$

3. Tableaux de Karnaugh

Méthode

1. Remplir le tableau à partir de la table de vérité (colonnes en code Gray : 00, 01, 11, 10 - un seul bit change à chaque fois).
2. Entourer les 1 par rectangles de 1, 2, 4 ou 8 cases, les plus grands possible, chevauchements autorisés, le tableau est cyclique (les bords se touchent).
3. Pour chaque groupe, garder les variables qui ne changent pas ; l’expression finale = somme (OU) des groupes.

Exemple 1 - $f=ab+\bar{a}bc$

$a$ \ $bc$	00	01	11	10
0	0	0	1	0
1	0	0	1	1

• Groupe vertical colonne $bc=11$ : $a$ varie → reste $bc$.
• Groupe horizontal ligne $a=1$, colonnes 11 et 10 : $c$ varie → reste $ab$.
• $f=ab+bc$ ✅ (vérifié par table_verite.py).

Exemple 2 (BTS) - bonus joueur : $F=ab+\bar{b}c+\bar{c}a$

Table : $F=\Sigma m(1,4,5,6,7)$.

$a$ \ $bc$	00	01	11	10
0	0	1	0	0
1	1	1	1	1

• Toute la ligne $a=1$ (4 cases) → $a$.
• Colonne $bc=01$ (m1 et m5) → $b=0,c=1$ → $\bar{b}c$.
• $F=a+\bar{b}c$ (2 termes).

Simplification par le calcul (même résultat, plus long)

$F=ab+a\bar{c}+\bar{b}c$. Comme $\bar{b}c=\bar{b}c+a\bar{b}c$ (absorption), on peut écrire $F=ab+a\bar{c}+a\bar{b}c+\bar{b}c=a(b+\bar{b}c+\bar{c})+\bar{b}c$. Or $b+\bar{b}c=b+c$ (absorption 2), donc $b+\bar{b}c+\bar{c}=b+c+\bar{c}=1$. D’où $F=a+\bar{b}c$. Karnaugh y arrive en 10 secondes !

Karnaugh à 4 variables

Lignes $ab$ et colonnes $cd$ toutes deux en code Gray (00, 01, 11, 10). Les 4 coins forment un groupe.

4. Exercice

Simplifier $g=\bar{a}\bar{b}c+\bar{a}bc+abc+ab\bar{c}$.

Correction

Mintermes : $\bar{a}\bar{b}c$ = m1, $\bar{a}bc$ = m3, $abc$ = m7, $ab\bar{c}$ = m6.

$a$ \ $bc$	00	01	11	10
0	0	1	1	0
1	0	0	1	1

Groupes : (m1, m3) → $\bar{a}c$ ; (m7, m6) → $ab$. $g=\bar{a}c+ab$. Vérification : python3 table_verite.py "!a.!b.c + !a.b.c + a.b.c + a.b.!c" "!a.c + a.b"

5. Script : scripts/maths/table_verite.py

python3 table_verite.py "a.b + !a.b.c"                      # table de vérité
python3 table_verite.py "a.b + !a.b.c" "b.c + a.b"          # équivalentes ? ✅
python3 table_verite.py --mintermes "a.b + !b.c + !c.a"     # F = Σm(1, 4, 5, 6, 7)
python3 table_verite.py "!(a + b)" "!a.!b"                  # vérifier De Morgan

Notation : . ou * = ET, + = OU, ! = NON.

Voir aussi

• M02 - Numération (binaire, hexa) · M04 - Ensembles, fonctions et relations
• Retour : 00 - Index général