Funkcjonalna kompletność 3-wartościowej logiki

W kontekście niektórych ostatnich prac zdefiniowaliśmy język oparty na trójwartościowej logice à la Kleene, gdzie $1$ oznacza prawdę, $0$ za fałsz i $\bot$ za błąd lub nie wiem. Aby pokazać, że nasz język jest ekspresyjny, chcieliśmy udowodnić, że możemy zbudować zestaw funkcjonalnie kompletnych operatorów.

Trudno było znaleźć istniejące wyniki w literaturze. Znaleźliśmy jeden artykuł napisany w 1962 r. Przez Jobe, który stwierdza następujące twierdzenie:

Jobe Theorem Paper 1962 (ograniczony dostęp).

Logika trójwartościowa $E$ wyrażone w zestawie $\{1, 2, 3\}$ i zdefiniowane przez operatorów $\bullet, E_1$ i $E_2$ podana poniżej jest funkcjonalnie kompletna.

$\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}$

W naszym artykule wykorzystaliśmy ten wynik, pokazując zgodność między naszymi operatorami a operatorami zdefiniowanymi przez Jobe (z grubsza mówiąc, używamy silnej koniunkcji, negacji i operatora, który przekształca niewiedzę w fałsz).

Moją główną troską jest to, że właściwie nie jestem w stanie zrozumieć dowodu funkcjonalnej kompletności Jobe i nie byliśmy w stanie znaleźć żadnego innego wyniku (pozytywnego lub negatywnego) po tej dacie, co jest nieco zaskakujące.

Moje pytanie brzmi więc: czy są jakieś bardziej znane wyniki dotyczące funkcjonalnej kompletności logiki trójwartościowej? Wszelkie informacje w tym kierunku byłyby pomocne.

reference-request lo.logic Charles
źródło

The

3

$3$ -element pola jest funkcjonalnie kompletny. The

3

$3$ -element Algebra słupkowa jest funkcjonalnie ukończona.

Emil Jeřábek

@ EmilJeřábek Dzięki, właśnie przeczytałem o Ternary Post Logic, i wydaje się, że to odpowiada (chociaż nie mogę znaleźć dużo na ten temat). Czy miałbyś jakieś odniesienia do pola 3-elementowego? Google jest trochę zbyt niejasne.

Charles

Nie mogę podać referencji, ale jest to prosty fakt: standardowa interpolacja (wielowymiarowa) oznacza, że dowolną operację na polu skończonym można wyrazić wielomianem. Ponadto, jeśli pole jest liczbą pierwszą (taką jak tutaj), wówczas współczynniki wielomianu można zdefiniować stałymi składnikami (

1 + 1 + \dots + 1

$1+1+\cdots+1$ ). Zatem pierwsze pola w języku

{+, \cdot, 1}

$\{+,\cdot,1\}$ są funkcjonalnie kompletne.

Emil Jeřábek

Rozdziały 5 i 6 książki [Algebry funkcji na zbiorach skończonych, Dietlinde Lau, 2006] zawierają dogłębne podejście do funkcjonalnej kompletności w logice o wielu wartościach (w tym dowodach). Podsumowując: charakterystyka maksymalnych klonów przez Rosenberga [1965, 1970] (zwana także klonami niepełnymi) daje kryterium kompletności funkcjonalnej w logice wartości k dla dowolnego k.

Dla szczególnego przypadku logiki 3-wartościowej taką charakterystykę (składającą się z 18 maksymalnych / niepełnych klas) podał Jablonskij już w 1954 roku. Stąd, aby zweryfikować, czy twój zestaw 3-wartościowych „operatorów” jest funkcjonalnie kompletny, to wystarczy sprawdzić, czy nie należą one do żadnej z 18 niedokończonych klas.

Gustav Nordh
źródło

Funkcjonalna kompletność 3-wartościowej logiki

Odpowiedzi: