Logique ternaire

Cet article est une ébauche concernant les mathématiques et la logique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

La logique ternaire, ou logique 3 états (parfois abrégée 3VL), également appelé logique trinaire , trivalente , ou triléenne ) (en anglais three-valued logic, trinary logic, trivalent, ternary, or trilean^[1]), est une branche du calcul des propositions qui étend l'algèbre de Boole, en considérant, en plus des états VRAI (en anglais TRUE→ T), et FAUX (en anglais FALSE→ F), l'état INCONNU (en anglais UNKNOW→ U). Cela la différencie des logiques bivalentes plus connues (telles que la logique classique ou la logique booléenne ) qui ne fournissent que vrai et faux.

Si ce bandeau n'est plus pertinent, retirez-le. Cliquez ici pour en savoir plus.

Cet article ne cite pas suffisamment ses sources (février 2017).

Si vous disposez d'ouvrages ou d'articles de référence ou si vous connaissez des sites web de qualité traitant du thème abordé ici, merci de compléter l'article en donnant les références utiles à sa vérifiabilité et en les liant à la section « Notes et références ».

En pratique : Quelles sources sont attendues ? Comment ajouter mes sources ?

Emil Leon Post est reconnu pour avoir introduit pour la première fois des degrés de vérité logique supplémentaires dans sa théorie des propositions élémentaires de 1921 ^[2]. La forme conceptuelle et les idées de base de la logique à trois valeurs ont été initialement publiées par Jan Łukasiewicz et Clarence Irving Lewis . Celles-ci ont ensuite été reformulées par Grigore Moisil sous une forme algébrique axiomatique, et également étendues à la logique à n valeurs en 1945.

Pré-découverte modifier

Vers 1910, Charles Sanders Peirce a défini un système logique à valeurs multiples. Il ne l'a jamais publié. En fait, il n'a même pas numéroté les trois pages de notes où il définissait ses opérateurs à trois valeurs^[3]. Peirce a fermement rejeté l'idée que toutes les propositions doivent être vraies ou fausses, les propositions limites, écrit-il, sont « à la limite entre P et non P »^[4]. Cependant, aussi confiant qu'il était que « la logique triadique est universellement vraie »^[5], il a également noté que « tout cela est très proche du non-sens »^[6]. Ce n'est qu'en 1966, lorsque Max Fisch et Atwell Turquette commencèrent à publier ce qu'ils avaient redécouvert dans ses manuscrits inédits, que les idées triadiques de Peirce devinrent largement connues^[4].

Les différentes Logiques modifier

Tables de vérité Kleene et Priest modifier

Article connexe : Algèbre de De Morgan.

Ci-dessous, un ensemble de tables de vérité montrant les opérations logiques de la « logique forte de l'indétermination » de Stephen Cole Kleene et de la « logique du paradoxe » de Graham Priest.

(F, faux; U, unconnu; T, vrai)

NON A
NOT(A)
A	¬A
F	T
U	U
T	F

A ET B
AND(A, B)
A ∧ B		B
A ∧ B		F	U	T
A	F	F	F	F
	U	F	U	U
	T	F	U	T

A OU B
OR(A, B)
A ∨ B		B
A ∨ B		F	U	T
A	F	F	U	T
	U	U	U	T
	T	T	T	T

OU exclusif(A, B)
XOR(A, B)
A ⊕ B		B
A ⊕ B		F	U	T
A	F	F	U	T
	U	U	U	U
	T	T	U	F

D'une certaine manière, ces propriétés correspondent à l'intuition : par exemple, si on ignore si A est vrai ou faux, son inverse est tout aussi incertain.

Dans ces tables de vérité, l' état inconnu peut être considéré comme ni vrai ni faux dans la logique de Kleene, ou comme à la fois vrai et faux dans la logique de Priest. La différence réside dans la définition des tautologies. Là où la seule valeur de vérité désignée par la logique de Kleene est vrai, les valeurs de vérité désignées par la logique de Priest sont à la fois vrai et inconnu. Dans la logique de Kleene, il n'est pas possible de savoir si un état inconnu particulier représente secrètement vrai ou faux à tout moment. Cependant, certaines opérations logiques peuvent donner un résultat sans ambiguïté, même si elles impliquent un opérande inconnu . Par exemple, parce que vrai OU vrai est égal à vrai et que vrai OU faux est également égal à vrai , alors vrai OU inconnu est également égal à vrai. Dans cet exemple, étant donné que l’un ou l’autre état bivalent pourrait être sous-jacent à l’état inconnu et que l’un ou l’autre état donne également le même résultat, les résultats sont vrais dans les trois cas.

Si des valeurs numériques, par exemple des valeurs ternaires équilibrées (en), sont affectées à faux , inconnu et vrai de telle sorte que faux soit inférieur à inconnu et inconnu inférieur à vrai (F < U < T) , alors A ET B ET C... = MIN(A, B, C .. .) et A OU B OU C ... = MAX(A, B, C...).

en notation ternaire équilibré (−1, false; 0, unknown; +1, true)

NEG(A)
A	¬A
−1	+1
0	0
+1	−1

MIN(A, B)
A ∧ B		B
A ∧ B		−1	0	+1
A	−1	−1	−1	−1
	0	−1	0	0
	+1	−1	0	+1

MAX(A, B)
A ∨ B		B
A ∨ B		−1	0	+1
A	−1	−1	0	+1
	0	0	0	+1
	+1	+1	+1	+1

MIN(MAX(A, B), NEG(MIN(A, B)))
A ⊕ B		B
A ⊕ B		−1	+1
A	−1	−1	+1
	0	0	0
	+1	+1	−1

L'implication matérielle pour la logique de Kleene peut être définie comme :

$A\rightarrow B\ {\overset {\underset {\mathrm {def} }{}}{=}}\ {\mbox{OR}}(\ {\mbox{NOT}}(A),\ B)$ , et la table de vérité de « A implique B » est:

IMP_K(A, B), OR(¬A, B)
A $\Rightarrow$ B		B
A $\Rightarrow$ B		F	U	T
A	F	T	T	T
	U	U	U	T
	T	F	U	T

qui diffère de celle de la logique de Łukasiewicz (décrite dans ce sous-chapitre).

La logique de Kleene n'a pas de tautologies (formules valides) car chaque fois que tous les composants atomiques d'une formule bien formée se voient attribuer la valeur Inconnu, la formule elle-même doit également avoir la valeur Inconnu. (Et la seule valeur de vérité désignée pour la logique de Kleene est Vrai.) Cependant, le manque de formules valides ne signifie pas qu’elle manque d’arguments et/ou de règles d’inférence valides. Un argument est sémantiquement valide dans la logique de Kleene si, chaque fois (pour n'importe quelle interprétation/modèle) toutes ses prémisses sont vraies, la conclusion doit également être vraie. (La Logique du Paradoxe (LP) a les mêmes tables de vérité que la logique de Kleene, mais elle a deux valeurs de vérité désignées au lieu d'une ; ce sont : Vrai et Les deux (l'analogue d'Inconnu), de sorte que LP a des tautologies mais elle a moins de règles d'inférence valides)^[7].

Logique de Łukasiewicz modifier

Article détaillé : Logique de Łukasiewicz.

La logique de Łukasiewicz (noté Ł3) a les mêmes tables pour ET, OU et NON que la logique de Kleene donnée ci-dessus, mais diffère dans sa définition de l'implication en ce sens que « inconnu implique inconnu » est vrai . Cette section fait suite à la présentation du chapitre de Malinowski du Handbook of the History of Logic , vol 8 ^[8].

La table de vérité d'implication matèrielle pour la logique de Łukasiewicz est :

IMP_Ł(A, B)
A → B		B
A → B		F	U	T
A	F	T	T	T
	U	U	T	T
	T	F	U	T

IMP_Ł(A, B), MIN(1, 1−A+B)
A → B		B
A → B		−1	0	+1
A	−1	+1	+1	+1
	0	0	+1	+1
	+1	−1	0	+1

⇔

En utilisant l'implication et la négation de Łukasiewicz, les autres poortes logiques habituelles peuvent être dérivés comme suit :

${\begin{matrix}A\lor B=(A\rightarrow B)\rightarrow B\end{matrix}}$
${\begin{matrix}A\land B=\lnot (\lnot A\lor \lnot B)\end{matrix}}$
${\begin{matrix}A\leftrightarrow B=(A\rightarrow B)\land (B\rightarrow A)\end{matrix}}$ ( $\leftrightarrow$ = équivalence logique )

Il est également possible de dériver quelques autres opérateurs unaires utiles (dérivés pour la première fois par Tarski en 1921) ^{[réf. nécessaire]}:

$M A = \neg A \to A$
$L A = \neg M \neg A$
$I A = M A \land \neg L A$

Qui ont les tables de vérités suivantes:

$A$	$M A$
F	F
U	T
T	T

$A$	$L A$
F	F
U	F
T	T

$A$	$I A$
F	F
U	T
T	F

Ces opérateurs signifient:

$M$ se lit comme "il n'est pas faux que..." ou dans la tentative (infructueuse) de Tarski-Łukasiewicz d'axiomatiser la logique modale en utilisant une logique à trois valeurs "il est possible que...",
$L$ se lit "c'est vrai que... ou "il faut que...",
$I$ se lit "on ne sait pas que..." ou "il est contingent que...".

Dans le Ł3 de Łukasiewicz, la valeur désignée est Vrai, ce qui signifie que seule une proposition ayant cette valeur partout est considérée comme une tautologie . Par exemple, $A\rightarrow A$ et $A\leftrightarrow A$ sont des tautologies en Ł3 et aussi en logique classique. Toutes les tautologies de la logique classique ne s'applique pas "tel quel" en Ł3. Par exemple, la loi du tiers exclu , $A\lor \lnot A$ , et la loi de non-contradiction , $\lnot (A\land \lnot A)$ ne sont pas des tautologies dans Ł3. Cependant, en utilisant l'opérateur $I$ défini ci-dessus, il est possible d'énoncer des tautologies qui sont leurs analogues :

$A \lor (I A) \lor \neg A$ (équivalent à la loi du tiers exclu)
$\neg(A \land \neg(I A) \land \neg A)$ (équivalent à la loi de non-contradiction).

Logique RM3 modifier

La table de vérité pour l’implication matérielle de R-Mingle 3 (RM3) est:

IMP_RM3(A, B)
A → B		B
A → B		F	U	T
A	F	T	T	T
	U	F	U	T
	T	F	F	T

Une caractéristique déterminante du RM3 est l’absence de l’axiome d’affaiblissement :

$(A \to (B \to A))$

ce qui, par adjoint, équivaut à la projection du produit (XOR):

$(A \otimes B) \to A$

RM3 est une catégorie fermée monoïdale symétrique non cartésienne; le produit, qui est adjoint à gauche à l'implication, manque de projections valides et a $U$ comme identité monoïde. Cette logique équivaut à une logique paraconsistante « idéale » qui obéit également à la contrapositive.

Logique HT modifier

Article connexe : [[:Logique Intermédiaire (en)]].

La logique d'ici et là ( HT , également appelée logique de Smetanov SmT ou logique de Gödel G3), introduite par Heyting en 1930 ^[9] comme modèle pour l'étude de la logique intuitionniste , est une logique intermédiaire à trois valeurs où la troisième valeur de vérité NF (pas faux) a la sémantique d'une proposition dont on peut prouver intuitivement qu'elle n'est pas fausse, mais n'a pas de preuve intuitionniste de son exactitude.

(F, false; NF, not false; T, true)

NOT_HT(A)
A	¬A
F	T
NF	F
T	F

IMP_HT(A, B)
A → B		B
A → B		F	NF	T
A	F	T	T	T
	NF	F	T	T
	T	F	NF	T

Il peut être défini soit en ajoutant l'un des deux axiomes équivalents (¬ q → p ) → ((( p → q ) → p ) → p ) ou de manière équivalente p ∨(¬ q )∨( p → q ) aux axiomes de logique intuitionniste , ou par des tables de vérité explicites pour ses opérations. En particulier, la conjonction et la disjonction sont les mêmes que dans la logique de Kleene et Łukasiewicz, tandis que la négation est différente.

La logique HT est l'unique couche dans le réseau des logiques intermédiaires. En ce sens, elle peut être considérée comme la « deuxième logique intermédiaire la plus forte » après la logique classique.

Logique Post Ternaire modifier

not(a) = (a + 1) mod 3, ou not(a) = (a + 1) mod (n), où (n) est une valeur logique.

Algèbres modulaires modifier

Certaines arithmétiques modulaires 3VL ont été introduites plus récemment, motivées par des problèmes de circuit plutôt que par des problèmes philosophiques ^[10]:

Algèbre de Cohn,
Algèbre de Pradhan Dubrova^[11],
algèbre de Muzio.

En électronique modifier

En informatique modifier

En SQL, les variables de type booléen peuvent prendre, en plus des valeurs vrai et faux, la valeur NULL. Une variable booléenne non initialisée, ou une opération avec une variable numérique elle-même non initialisée (dont la valeur est aussi appelée NULL) renvoient le booléen NULL. L'évaluation des prédicats admet donc trois valeurs possibles : true, false et unknown.

Exemples d'évaluation d'une formule en informatique (équation ou inéquation mathématique) :

Équation	Typage de données	Résultat	Typage de résultat
4 < NULL	NULL est ici le NULL des nombres	renvoie la valeur NULL	NULL est ici le NULL des booléens

Quand on manipule un NULL booléen dans les opérations logiques, la logique ternaire s'applique. L'alternative « IF A THEN [instructions] » conduit à ne pas exécuter les instructions si A est NULL.

Notes et références modifier

Notes modifier

(en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Three-valued logic » (voir la liste des auteurs).

Références modifier

↑ https://nlp.stanford.edu/nlp/javadoc/javanlp/edu/stanford/nlp/util/Trilean.html
↑ (en) Emil L. Post, « Introduction to a General Theory of Elementary Propositions », American Journal of Mathematics, vol. 43, n^o 3,‎ 1921, p. 163–185 (ISSN 0002-9327, DOI 10.2307/2370324, lire en ligne, consulté le 15 mai 2024)
↑ (en) « Peirce’s Deductive Logic > Peirce's Three-Valued Logic (Stanford Encyclopedia of Philosophy/Summer 2020 Edition) » (consulté le 15 mai 2024)
↑ ^{a et b} (en) Robert Lane, « Commens : Triadic Logic », 2001 (consulté le 15 mai 2024)
↑ (en) « Peirce Logic Notebook, Charles Sanders Peirce Papers MS Am 1632 (339). Houghton Library, Harvard University », sur Harvard Library Viewer, p. 645
↑ (en) « Peirce Logic Notebook, Charles Sanders Peirce Papers MS Am 1632 (339). Houghton Library, Harvard University », sur Harvard Library Viewer, p. 638
↑ https://www.uky.edu/~look/Phi520-Lecture7.pdf
↑ (en) Dov M. Gabbay et John Woods, The Many Valued and Nonmonotonic Turn in Logic, Elsevier, 13 août 2007 (ISBN 978-0-08-054939-2, lire en ligne)
↑ (de) Arend Heyting, Die formalen Regeln der intuitionistischen Logik, Deütsche Akademie der Wissenschaften zu Berlin, Mathematisch-Naturwissenschaftliche Klasse, 1930 (lire en ligne), p. 42-56
↑ (en) Multiple-Valued Logic (DOI 10.1007/978-3-031-79779-8, lire en ligne)
↑ Elena Dubrova, « Multiple-valued logic synthesis and optimization », dans Logic Synthesis and Verification, Kluwer Academic Publishers, 1^er novembre 2001, 89–114 p. (ISBN 978-0-7923-7606-4, DOI 10.5555/566845.566849, lire en ligne)

Voir aussi modifier

Articles connexes modifier

Ordinateurs ternaires:
- le Setun (URSS, 1958)
- le Ternac (en) (États-Unis, 1973)
Logique polyvalente
Système ternaire
Algèbre de Post, Algèbre de De Morgan
Table de Karnaugh
Sortie à trois états
Tampon trois états

Liens externes modifier

(en) Development of ternary computers at Moscow State University
(en) Hackaday.io : Série d'articles accompagnant du projet Ternary Computing Menagerie (2019):

[1] ttps://nlp.stanford.edu/nlp/javadoc/javanlp/edu/stanford/nlp/util/Trilean.html

[2] (en) Emil L. Post, « Introduction to a General Theory of Elementary Propositions », American Journal of Mathematics, vol. 43, n^o 3,‎ 1921, p. 163–185 (ISSN 0002-9327, DOI 10.2307/2370324, lire en ligne, consulté le 15 mai 2024)

[3] (en) « Peirce’s Deductive Logic > Peirce's Three-Valued Logic (Stanford Encyclopedia of Philosophy/Summer 2020 Edition) » (consulté le 15 mai 2024)

[:0-4] {a et b} (en) Robert Lane, « Commens : Triadic Logic », 2001 (consulté le 15 mai 2024)

[5] (en) « Peirce Logic Notebook, Charles Sanders Peirce Papers MS Am 1632 (339). Houghton Library, Harvard University », sur Harvard Library Viewer, p. 645

[6] (en) « Peirce Logic Notebook, Charles Sanders Peirce Papers MS Am 1632 (339). Houghton Library, Harvard University », sur Harvard Library Viewer, p. 638

[7] ttps://www.uky.edu/~look/Phi520-Lecture7.pdf

[8] (en) Dov M. Gabbay et John Woods, The Many Valued and Nonmonotonic Turn in Logic, Elsevier, 13 août 2007 (ISBN 978-0-08-054939-2, lire en ligne)

[9] (de) Arend Heyting, Die formalen Regeln der intuitionistischen Logik, Deütsche Akademie der Wissenschaften zu Berlin, Mathematisch-Naturwissenschaftliche Klasse, 1930 (lire en ligne), p. 42-56

[10] (en) Multiple-Valued Logic (DOI 10.1007/978-3-031-79779-8, lire en ligne)

[11] Elena Dubrova, « Multiple-valued logic synthesis and optimization », dans Logic Synthesis and Verification, Kluwer Academic Publishers, 1^er novembre 2001, 89–114 p. (ISBN 978-0-7923-7606-4, DOI 10.5555/566845.566849, lire en ligne)

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]