Funktionale Vollständigkeit der 3-wertigen Logik

Im Zusammenhang mit einigen neueren Arbeiten haben wir eine Sprache definiert, die auf einer dreiwertigen Logik à la Kleene basiert, wobei für wahr, für falsch und für Fehler oder . Um zu zeigen, dass unsere Sprache ausdrucksstark ist, wollten wir beweisen, dass wir eine Reihe von Operatoren erstellen können, die funktional vollständig sind. $1$ $0$ $\bot$

Es war ziemlich schwierig, vorhandene Ergebnisse in der Literatur zu finden. Wir haben ein 1962 von Jobe geschriebenes Papier gefunden, das den folgenden Satz enthält:

Jobe 1962 Satz Papier (eingeschränkter Zugang).

Die dreiwertige Logik die über die Menge ausgedrückt und durch die unten angegebenen Operatoren und definiert wird , ist funktional vollständig. $E$ $\{1, 2, 3\}$ $\bullet, E_1$ $E_2$

$\begin{array}{cccccc} ∙ & 3 & 2 & 1 & {E.}_{1} & {E.}_{2} \\ 3 & 3 & 2 & 1 & 3 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 3 \end{array}$ $\begin{array}{c|ccc|c|c} ~\bullet~ & ~3~ & ~2~ & ~1~ & ~E_1~ & ~E_2~ \\ \hline 3 & 3 & 2 & 1 & 3 & 1 \\ 2 & 2 & 2 & 1 & 1 & 2 \\ 1 & 1 & 1 & 1 & 2 & 3 \end{array}$

In unserer Arbeit haben wir dieses Ergebnis verwendet, indem wir eine Entsprechung zwischen unseren Operatoren und den von Jobe definierten Operatoren gezeigt haben (grob gesagt verwenden wir die starke Konjunktion, die Negation und einen Operator, der Unbekanntes in Falsch transformiert).

Mein Hauptanliegen ist, dass ich den Beweis der funktionalen Vollständigkeit von Jobe tatsächlich nicht verstehen kann und wir nach diesem Datum kein anderes Ergebnis (positiv oder negativ) finden konnten, was irgendwie etwas überraschend ist.

Meine Frage lautet also: Gibt es bekanntere Ergebnisse zur funktionalen Vollständigkeit von 3-wertigen Logiken? Alle Informationen in diese Richtung wären hilfreich.

reference-request lo.logic Charles
quelle

3

$3$

3

$3$

@ EmilJeřábek Danke, ich habe gerade über die Ternary Post Logic gelesen, und das scheint zu entsprechen (obwohl ich zu diesem Thema auch nicht viel finden kann). Hätten Sie einen Hinweis auf das 3-Elemente-Feld? Google ist etwas zu vage.

Charles

1 + 1 + \dots + 1

$1+1+\cdots+1$

{+, \cdot, 1}

$\{+,\cdot,1\}$

Die Kapitel 5 und 6 des Buches [Funktionsalgebren auf endlichen Mengen, Dietlinde Lau, 2006] enthalten eine eingehende Behandlung der funktionalen Vollständigkeit in einer vielwertigen Logik (einschließlich Beweisen). Zusammenfassend: Rosenbergs [1965, 1970] Charakterisierung maximaler Klone (auch als unvollständige Klone bezeichnet) liefert ein Kriterium für die funktionale Vollständigkeit der k-wertigen Logik für jedes k.

Für den Sonderfall der 3-wertigen Logik wurde eine solche Charakterisierung (bestehend aus 18 maximalen / unvollständigen Klassen) bereits 1954 von Jablonskij gegeben. Um zu überprüfen, ob Ihr Satz von 3-wertigen "Operatoren" funktional vollständig ist, ist sie vorhanden reicht aus, um zu überprüfen, ob sie in keine der 18 unvollständigen Klassen fallen.

Gustav Nordh
quelle

Funktionale Vollständigkeit der 3-wertigen Logik

Antworten: