3 Formes normales
Considérons l'ensemble d'atomes fini : Vp={p1,...,pn}.
-
une formule est une fonction de Vp dans {v,f} ;
- deux formules équivalentes représentent la même fonction.
Donc card(F/º)£ 22n.
En fait card(F/º)= 22n : soit une fonction f donnée
| p1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
| p2 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
| p3 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
| f |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
On peut construire la formule F représentant f:
F=(p1 Ù ¬ p2 Ù ¬ p3) Ú
(¬ p1 Ù p2 Ù ¬ p3) Ú
(p1 Ù ¬ p2 Ù p3) ...
Définition 11
Forme normale conjonctive (resp. disjonctive) : conjonction (resp. disjonction)
de disjonctions (resp. conjonctions) de littéraux.
Propriété 8
Toute formule est logiquement équivalente à une formule sous forme normale.
Algorithme de mise sous forme normale ;
-
-
A « Bº(A ® B) Ù (B ® A)
- A ® Bº¬ A Ú B
-
-
¬ ¬ Aº A
- ¬ (A Ú B)º¬ A Ù ¬ B
- ¬ (A Ù B)º¬ A Ú ¬ B
-
-
A Ú (B Ù C)º(A Ú B) Ù (A Ú C)
- A Ù (B Ú C)º(A Ù B) Ú (A Ù C)
Exemple : (A Ù (A ® C)) ® Cº...