Logique Propositionnelle - Aide Mémoire

Voir aussi : Algo

1. Propositions

• Proposition : phrase vraie ou fausse.
• Notation : $P,Q,R...$
• Littéral : une proposition ($P$) ou sa négation ($\neg P$).

---

2. Connecteurs logiques

• Négation : $\neg P$
• Conjonction (ET) : $P\wedge Q$
• Disjonction (OU) : $P\vee Q$
• Implication : $P\Rightarrow Q$ (équivaut à $\neg P\vee Q$)
• Équivalence : $P\iff Q$

---

3. Table de vérité de l’implication

P	Q	P $\Rightarrow$ Q
V	V	V
V	F	F
F	V	V
F	F	V

---

4. Réciproque, Contraposée, Négation

Pour $P\Rightarrow Q$ :

• Réciproque : $Q\Rightarrow P$ (pas équivalente à l’originale).
• Contraposée : $\neg Q\Rightarrow \neg P$ (équivalente à l’originale).
• Négation : $P\wedge \neg Q$.

---

5. Lois de De Morgan

• $\neg (P\wedge Q)\equiv \neg P\vee \neg Q$
• $\neg (P\vee Q)\equiv \neg P\wedge \neg Q$

---

6. Formes normales

Forme Normale Conjonctive (FNC / CNF)

• Conjonction de disjonctions de littéraux.
• Schéma : $({\ell }_1\vee {\ell }_2\vee \dots )\wedge ({\ell }_3\vee {\ell }_4\vee \dots )\wedge \dots$
• Exemple : $(P\vee Q)\wedge (\neg P\vee R)$

Forme Normale Disjonctive (FND / DNF)

• Disjonction de conjonctions de littéraux.
• Schéma : $({\ell }_1\wedge {\ell }_2\wedge \dots )\vee ({\ell }_3\wedge {\ell }_4\wedge \dots )\vee \dots$
• Exemple : $(P\wedge \neg Q)\vee (Q\wedge R)$

---

7. Méthode pour passer en CNF ou DNF

1. Éliminer $\Rightarrow$ et $\iff$ (remplacer par $\neg ,\vee ,\wedge$).
2. Pousser les négations à l’intérieur (De Morgan).
3. Distribuer :
   • Pour CNF : distribuer $\vee$ sur $\wedge$ $\to$ obtenir $\wedge$ de $\vee$.
   • Pour DNF : distribuer $\wedge$ sur $\vee$ $\to$ obtenir $\vee$ de $\wedge$.

---

8. Exemple

Formule : $(P\Rightarrow Q)\vee R$

1. Remplacer $\Rightarrow$ : $(\neg P\vee Q)\vee R$
2. Simplifier : $\neg P\vee Q\vee R$

• CNF : $(\neg P\vee Q\vee R)$
• DNF : $(\neg P\wedge \top )\vee (Q\wedge \top )\vee (R\wedge \top )$ (peut se simplifier à la formule elle-même)

---

---

9. Tableaux de Karnaugh

Objectif

• Simplifier des expressions booléennes (ou propositions logiques).
• Outil visuel basé sur la table de vérité.
• Évite les longues manipulations algébriques.

---

Construction

• Colonnes et lignes labellées avec combinaisons de variables (codées en Gray code).
• Chaque case correspond à une affectation des variables.
• On place dans la case le résultat de la fonction (Vrai = 1, Faux = 0).

Exemples :

• 2 variables (P, Q) $\to$ tableau $2\times 2$.
• 3 variables (P, Q, R) $\to$ tableau $2\times 4$.
• 4 variables (P, Q, R, S) $\to$ tableau $4\times 4$.

---

Exemple Karnaugh à 2 variables

Q=0	Q=1
P=0	f(0,0)
P=1	f(1,0)

---

Règles de simplification

1. Regrouper les 1 contigus (puissances de 2 : 1, 2, 4, 8…).
2. Groupes possibles :
   • 1 case (min terme complet)
   • 2 cases, 4 cases, 8 cases… (plus la zone est grande, plus la formule est simplifiée)
3. Chaque groupe donne un produit (conjonction) de littéraux.
   • Variables qui changent à l’intérieur du regroupement sont éliminées.
   • Celles qui restent identiques sont conservées.
4. La fonction finale est la somme (disjonction) de tous les groupes.

---

Exemple de simplification (cas 3 variables)

Formule initiale : $f(P,Q,R)=\sum m(1,2,3,5,7)$ (où $m(i)=\text{minterme }i$ de la table de vérité)

Tableau de Karnaugh (3 variables) :

PQ \ R	0	1
00	0	1
01	1	1
11	0	1
10	0	0

Groupes :

• Regroupe (001, 011) $\to Q=0\wedge R=1$
• Regroupe (010,011) $\to P=0\wedge Q=1$
• Regroupe (111) (isolé) $\to P=1\wedge Q=1\wedge R=1$

Fonction simplifiée :

$f(P,Q,R)=(\neg Q\wedge R)\vee (\neg P\wedge Q)\vee (P\wedge Q\wedge R)$

9.1. Cas 2 variables (P, Q)

Tableau :

Q=0	Q=1
P=0	f(0,0)
P=1	f(1,0)

Exemple :

Soit $f(P,Q)=P\vee Q$

Q=0	Q=1
P=0	0
P=1	1

Groupes :

• Colonne Q=1 donne $Q$
• Ligne P=1 donne $P$

Formule simplifiée :

$f=P\vee Q$

(ce qui confirme la forme originale)

---

9.2. Cas 3 variables (P, Q, R)

Tableau (ordre Gray pour Q,R) :

P \ QR	00	01	11	10
0	f(0,0,0)	f(0,0,1)	f(0,1,1)	f(0,1,0)
1	f(1,0,0)	f(1,0,1)	f(1,1,1)	f(1,1,0)

Exemple :

Soit $f(P,Q,R)=\sum m(1,2,3,5,7)$ (mintermes 001,010,011,101,111)

Remplissage :

P \ QR	00	01	11	10
0	0	1	1	1
1	0	1	1	0

Groupes :

• Regroupe (001,011) $\to \neg Q\wedge R$
• Regroupe (010,011) $\to \neg P\wedge Q$
• Regroupe (111 seul) $\to P\wedge Q\wedge R$

Formule simplifiée :

$f=(\neg Q\wedge R)\vee (\neg P\wedge Q)\vee (P\wedge Q\wedge R)$

---

9.3. Cas 4 variables (P, Q, R, S)

Tableau (PQ en ligne, RS en colonne, codés en Gray) :

PQ \ RS	00	01	11	10
00	f(0,0,0,0)	f(0,0,0,1)	f(0,0,1,1)	f(0,0,1,0)
01	f(0,1,0,0)	f(0,1,0,1)	f(0,1,1,1)	f(0,1,1,0)
11	f(1,1,0,0)	f(1,1,0,1)	f(1,1,1,1)	f(1,1,1,0)
10	f(1,0,0,0)	f(1,0,0,1)	f(1,0,1,1)	f(1,0,1,0)

Exemple :

Soit $f(P,Q,R,S)=\sum m(0,2,8,10,13,15)$

Tableau complété (1 aux mintermes, 0 ailleurs) :

PQ \ RS	00	01	11	10
00	1	0	0	1
01	0	0	0	0
11	0	0	1	0
10	1	0	0	1

Groupes :

• (0000,0010,1000,1010) $\to$ rectangle 4 cases $\to \neg Q\wedge \neg R$
• (1111,1101,1011,1001) réduit $\to$ combinaison qui garde $P\wedge Q\wedge R$…

Formule simplifiée (exemple illustratif) :

$f=(\neg Q\wedge \neg R)\vee (P\wedge Q\wedge R)$

Remarque

Ceci est un test d’admonition pour Quartz.