Recherche:Théorie des matrices logiques/Application: simulation de logiques multivalentes

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

La formule de logique propositionnelle

${\mathsf {(P\implies Q)\Longleftrightarrow (\neg P\lor Q)}}$

n'est pas en forme normale conjonctive.

Pour la transcrire telle quelle dans une matrice logique, il faut tout d’abord la décomposer en sous-formules et associer des variables auxiliaires à ces sous-formules:

${\mathsf {\underbrace {\underbrace {(P\implies Q)} _{R}\Longleftrightarrow \underbrace {(\lnot P\lor Q)} _{S}} _{T}}}$

La variable auxiliaire T représente la formule dans son ensemble.

La méthode de transcription ressemble à celle qui a déjà été utilisée pour les portes logiques: deux variables d'entrée, une variable de sortie. Exemple, clé de transcription de la disjonction:

${\begin{array}{l}&{\begin{array}{c}&{\mathsf {P}}&{\mathsf {Q}}&{\mathsf {S}}\\&{\mathsf {FV}}&{\mathsf {FV}}&{\mathsf {FV}}\\\end{array}}&\\&\\&\left.\ \,{\begin{array}{c}&\cdot \ \bullet &\cdot \ \bullet &\cdot \ \bullet \\&\cdot \ \bullet &\bullet \ \cdot &\bullet \ \cdot \\&\bullet \ \cdot &\cdot \ \bullet &\bullet \ \cdot \\&\bullet \ \cdot &\bullet \ \cdot &\bullet \ \cdot \end{array}}\quad \right\rbrace {{\mathsf {P}}\ \lor \ {\mathsf {Q}}}\end{array}}$

${\begin{array}{l}&{\begin{array}{c}&{\mathsf {P}}&{\mathsf {Q}}&{\mathsf {S}}\\&{\mathsf {FV}}&{\mathsf {FV}}&{\mathsf {FV}}\\\end{array}}&\\&\\&\left.\ \,{\begin{array}{c}&\bullet \ \cdot &\cdot \ \bullet &\cdot \ \bullet \\&\bullet \ \cdot &\bullet \ \cdot &\bullet \ \cdot \\&\cdot \ \bullet &\cdot \ \bullet &\bullet \ \cdot \\&\cdot \ \bullet &\bullet \ \cdot &\bullet \ \cdot \end{array}}\quad \right\rbrace {\neg {\mathsf {P}}\ \lor \ {\mathsf {Q}}}\end{array}}$

La négation de P s'opère par permutation des deux vecteurs verticaux correspondants.

Une variante de cette clé, simplifiée par fusion, figurait dans la matrice du circuit logique traité précédemment (porte OR).

Matrice logique de la formule:

${\begin{array}{l}&{\begin{array}{c}&{\mathsf {P}}&{\mathsf {Q}}&{\mathsf {R}}&{\mathsf {S}}&{\mathsf {T}}\\&{\mathsf {FV}}&{\mathsf {FV}}&{\mathsf {FV}}&{\mathsf {FV}}&{\mathsf {FV}}\\\end{array}}&\\&\\&\left.{\begin{array}{c}&\,\cdot \ \bullet &\,\cdot \ \bullet &\,\bullet \ \cdot &\,\cdot \ \cdot &\,\cdot \ \cdot \\&\,\cdot \ \bullet &\,\bullet \ \cdot &\,\bullet \ \cdot &\,\cdot \ \cdot &\,\cdot \ \cdot \\&\,\bullet \ \cdot &\,\cdot \ \bullet &\,\cdot \ \bullet &\,\cdot \ \cdot &\,\cdot \ \cdot \\&\,\bullet \ \cdot &\,\bullet \ \cdot &\,\bullet \ \cdot &\,\cdot \ \cdot &\,\cdot \ \cdot \\\end{array}}\quad \right\rbrace {{\mathsf {P}}\implies {\mathsf {Q}},\ {\text{r}}{\acute {\text{e}}}{\text{sultat en }}{\mathsf {R}}}&\\&\\&\left.{\begin{array}{c}&\,\bullet \ \cdot &\,\cdot \ \bullet &\,\cdot \ \cdot &\,\cdot \ \bullet &\,\cdot \ \cdot \\&\,\bullet \ \cdot &\,\bullet \ \cdot &\,\cdot \ \cdot &\,\bullet \ \cdot &\,\cdot \ \cdot \\&\,\cdot \ \bullet &\,\cdot \ \bullet &\,\cdot \ \cdot &\,\bullet \ \cdot &\,\cdot \ \cdot \\&\,\cdot \ \bullet &\,\bullet \ \cdot &\,\cdot \ \cdot &\,\bullet \ \cdot &\,\cdot \ \cdot \\\end{array}}\quad \right\rbrace {\neg {\mathsf {P}}\lor {\mathsf {Q}},\ {\text{r}}{\acute {\text{e}}}{\text{sultat en }}{\mathsf {S}}}&\\&\\&\left.{\begin{array}{c}&\,\cdot \ \cdot &\,\cdot \ \cdot &\,\cdot \ \bullet &\,\cdot \ \bullet &\,\bullet \ \cdot \\&\,\cdot \ \cdot &\,\cdot \ \cdot &\,\cdot \ \bullet &\,\bullet \ \cdot &\,\cdot \ \bullet \\&\,\cdot \ \cdot &\,\cdot \ \cdot &\,\bullet \ \cdot &\,\cdot \ \bullet &\,\cdot \ \bullet \\&\,\cdot \ \cdot &\,\cdot \ \cdot &\,\bullet \ \cdot &\,\bullet \ \cdot &\,\bullet \ \cdot \end{array}}\quad \right\rbrace {{\mathsf {R}}\Longleftrightarrow {\mathsf {S}},\ {\text{r}}{\acute {\text{e}}}{\text{sultat en }}{\mathsf {T}}}\end{array}}$

Projection 1 de la table:

${\begin{array}{c}&&{\text{Valeurs prises par les variables}}&\\&&&\\&{\mathsf {P:}}&{\mathsf {F\,F\,F\,F\,F\,F\,F\,F\,F\,F\,F\,F\,F\,F\,F\,F\,V\,V\,V\,V\,V\,V\,V\,V\,V\,V\,V\,V\,V\,V\,V\,V}}&\\&{\mathsf {Q:}}&{\mathsf {F\,F\,F\,F\,F\,F\,F\,F\,V\,V\,V\,V\,V\,V\,V\,V\,F\,F\,F\,F\,F\,F\,F\,F\,V\,V\,V\,V\,V\,V\,V\,V}}&\\&{\mathsf {R:}}&{\mathsf {F\,F\,F\,F\,V\,V\,V\,V\,F\,F\,F\,F\,V\,V\,V\,V\,F\,F\,F\,F\,V\,V\,V\,V\,F\,F\,F\,F\,V\,V\,V\,V}}&\\&{\mathsf {S:}}&{\mathsf {F\,F\,V\,V\,F\,F\,V\,V\,F\,F\,V\,V\,F\,F\,V\,V\,F\,F\,V\,V\,F\,F\,V\,V\,F\,F\,V\,V\,F\,F\,V\,V}}&\\&{\mathsf {T:}}&{\mathsf {F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,F\,V\,V\,V}}&{\text{(}}{\mathsf {T}}{\text{ = formule dans son ensemble)}}\\&&&\\&&\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\cdot \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\cdot \,\bullet \,\cdot \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\bullet \,\cdot &\\&&{\text{projection 1}}&\end{array}}$

Les 1 de la projection définissent la table de vérité de la formule.

${\begin{array}{c}&{\mathsf {P:}}&{\mathsf {F\,F\,V\,V}}&\\&{\mathsf {Q:}}&{\mathsf {F\,V\,F\,V}}&\\&{\mathsf {T:}}&{\mathsf {V\,V\,V\,V}}&{\text{(table de v}}{\acute {\text{e}}}{\text{rit}}{\acute {\text{e}}}{\text{ de la formule)}}\\\\&&\dots &\end{array}}$

La table de vérité ne contient que des V: la formule est une tautologie.

${\mathsf {P\implies Q}}$ équivaut à ${\mathsf {\neg P\lor Q}}$.

Remarque: la projection 1 est une matrice logique, et le pavé 'Valeurs prises par les variables', son interface. La table de vérité de la formule se lit dans l'interface, selon les indications de la projection. En apparence unis par leur caractère binaire, les éléments {F, V} de la table de vérité et les éléments {fermé, ouvert} de la projection ne sont pas de même nature.

La table de vérité de la formule est étrangère à la TML, comme l'est, par définition, l'interface. Le fait d'exprimer la table de vérité sous forme booléenne 1111 n'y changerait rien.

La logique trivalente de Łukasiewicz, ou Ł3, est syntaxiquement identique à la logique propositionnelle (la formule évoquée plus haut ne change pas) mais s'en écarte sur le plan sémantique en faisant intervenir une nouvelle valeur, située entre le faux et le vrai:

{F, I, V}, avec I pour 'indéterminé' ou, plus précisément, 'inconnaissable'.

Clé de transcription de la disjonction:

${\begin{array}{l}&{\begin{array}{c}&\ {\mathsf {P}}&\ {\mathsf {Q}}&\ {\mathsf {S}}\\&\ \ {\mathsf {FIV}}&\ \ \,{\mathsf {FIV}}&\ \ \,{\mathsf {FIV}}\\\end{array}}&\\&\\&\left.{\begin{array}{c}&\cdot \ \bullet \ \bullet &\cdot \ \bullet \ \bullet &\cdot \bullet \ \bullet \\&\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet \\&\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot \\&\bullet \ \cdot \ \bullet &\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet \\&\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet \\&\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot \\&\bullet \ \bullet \ \cdot &\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot \\&\bullet \ \bullet \ \cdot &\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot \\&\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot \end{array}}\quad \right\rbrace {\mathsf {P\lor Q}}\end{array}}$

${\begin{array}{l}&{\begin{array}{c}&{\mathsf {P}}&{\mathsf {Q}}&{\mathsf {S}}\\&\ \ {\mathsf {FIV}}&\ \ \,{\mathsf {FIV}}&\ \ \,{\mathsf {FIV}}\\\end{array}}&\\&\\&\left.{\begin{array}{c}&\bullet \ \bullet \ \cdot &\cdot \ \bullet \ \bullet &\cdot \bullet \ \bullet \\&\bullet \ \bullet \ \cdot &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet \\&\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot \\&\bullet \ \cdot \ \bullet &\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet \\&\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet \\&\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot \\&\cdot \ \bullet \ \bullet &\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot \\&\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot \\&\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot \end{array}}\quad \right\rbrace {\mathsf {\neg P\lor Q}}\end{array}}$

La négation de P s'opère par permutation des deux vecteurs extrèmes dans la bande verticale correspondante, le vecteur central formant pivot (ce qui est indéterminé reste indéterminé).

Matrice logique de la formule:

${\begin{array}{l}&{\begin{array}{c}&\ {\mathsf {P}}&\ {\mathsf {Q}}&\ {\mathsf {R}}&\ {\mathsf {S}}&\ {\mathsf {T}}\\&\ \ {\mathsf {FIV}}&\ \ {\mathsf {FIV}}&\ \ {\mathsf {FIV}}&\ \ {\mathsf {FIV}}&\ \ {\mathsf {FIV}}\\\end{array}}&\\&\\&\left.{\begin{array}{c}&\cdot \ \bullet \ \bullet &\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\bullet \ \cdot \ \bullet &\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\bullet \ \bullet \ \cdot &\cdot \ \bullet \ \bullet &\cdot \ \bullet \ \bullet &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\bullet \ \bullet \ \cdot &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\&\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot \\\end{array}}\quad \right\rbrace {\mathsf {P\implies Q}}{\text{, r}}{\acute {\text{e}}}{\text{sultat en }}{\mathsf {R}}&\\&\\&\left.{\begin{array}{c}&\bullet \ \bullet \ \cdot &\cdot \ \bullet \ \bullet &\cdot \ \cdot \ \cdot &\cdot \ \bullet \ \bullet &\cdot \ \cdot \ \cdot \\&\bullet \ \bullet \ \cdot &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot \\&\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot \\&\bullet \ \cdot \ \bullet &\cdot \ \bullet \ \bullet &\cdot \ \cdot \ \cdot &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot \\&\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot \\&\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot \\&\cdot \ \bullet \ \bullet &\cdot \ \bullet \ \bullet &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot \\&\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot \\&\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \cdot \ \cdot \\\end{array}}\quad \right\rbrace {\mathsf {\neg P\lor Q}}{\text{, r}}{\acute {\text{e}}}{\text{sultat en }}{\mathsf {S}}&\\&\\&\left.{\begin{array}{c}&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \bullet \ \bullet &\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\cdot \ \bullet \ \bullet &\bullet \ \bullet \ \cdot &\cdot \ \bullet \ \bullet \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \cdot \ \bullet &\cdot \ \bullet \ \bullet &\bullet \ \cdot \ \bullet \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \cdot \ \bullet &\bullet \ \bullet \ \cdot &\bullet \ \cdot \ \bullet \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\cdot \ \bullet \ \bullet &\cdot \ \bullet \ \bullet \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\bullet \ \cdot \ \bullet &\bullet \ \cdot \ \bullet \\&\cdot \ \cdot \ \cdot &\cdot \ \cdot \ \cdot &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot &\bullet \ \bullet \ \cdot \\\end{array}}\quad \right\rbrace {\mathsf {R\Longleftrightarrow S}}{\text{, r}}{\acute {\text{e}}}{\text{sultat en }}{\mathsf {T}}\end{array}}$

La projection 1 de la table comporte 243 éléments. Ses 1 définissent la table de vérité trivalente de la formule:

${\begin{array}{c}&{\mathsf {P:}}&{\mathsf {F\ F\ F\ \ I\ \ I\ \ I\ V\,V\,V}}&\\&{\mathsf {Q:}}&{\mathsf {F\ \ I\ V\,F\ \ I\ V\,F\ \ I\ V}}&\\&{\mathsf {T:}}&{\mathsf {V\,V\,V\,V\,\ I\ V\,V\,V\,V}}&{\text{(table de v}}{\acute {\text{e}}}{\text{rit}}{\acute {\text{e}}}{\text{ de la formule)}}\\\\&&\dots \dots \dots &\end{array}}$

La table de vérité ne contient pas uniquement des V.

Dans la logique Ł3, ${\mathsf {P\implies Q}}$ n'équivaut pas à ${\mathsf {\neg P\lor Q}}$.

La logique trivalente de Kleene, K3, produirait la table de vérité VVVIIVVIV.