Sistema connettivi adeguato logica trivalente

[40rob]

Il logica bivalente classica vero-funzionale esiste l'operatore di Sheffer $\uparrow$

$1, 1$
$1, 0$

tramite il quale si possono rappresentare tutti gli altri connettivi e tutte le altre funzioni di verità (di arietà finita) combinandolo insieme a delle variabili tramite formule del tipo $((x \uparrow y) \uparrow x)$.
In logiche a più valori finiti è possibile trovare qualcosa di analogo?
Cercando in rete ho trovato soltanto questo...
In logica trivalente supponendo che i valori sono ${0, 1, 2}$ la matrice di un operatore binario analogo a quello di Sheffer dovrebbe essere questa...

$1, 1, 1$
$1, 2, 1$
$1, 1, 0$

Se preferite potete scrivere l'operatore (che ho chiamato come l'analogo a 2 valori) anche così

$(x\uparrow y) = 1+ 2*(x^2*y+y*x^2)$

interpretando $+$ e $*$ come operazioni dell'aritmetica dell'orologio $\bmod(3)$

Ma non c'era la dimostrazione.
Non è difficile mostrare che si riescono a rappresentare le funzioni costanti, e la funzione successore $Mod(3)$ (uguale a $(x \uparrow x)$ ma le altre?

[40rob]

Riesco a mostrare che in generale se si hanno i connettivi binari $+$ e $*$ e quello "diagonale" o di "identità" $(j \setminus i)$ che tira fuori $1$ se il valore della variabile $j = i$ altrimenti $0$. A tre valori la matrice di $\setminus$ sarebbe questa...

$1, 0, 0$
$0, 1, 0$
$0, 0, 1$

Questo insieme è sempre adeguato.
Ad esempio se la funzione da rappresentare $f(x, y ,z)$ (di arietà 3 nel dominio logico trivalente) assume (in corrispondenza delle combinazioni di valori ordinate in modo canonico) i rispettivi valori $[v_1, ... , v_27]$ si può usare per rappresentarla la formula...

$v_1 * (0 \setminus x) * (0 \setminus y) * (0 \setminus z) + v_2 * (0 \setminus x) * (0 \setminus y) * (1 \setminus z) + v_3 * (0 \setminus x) * (0 \setminus y) * (2 \setminus z) + ... + v_27 * (2 \setminus x) * (2 \setminus y) * (2 \setminus z)$

Per i valori costanti presenti nella formula insieme a $v_1, ..., v_27$ si usano ovviamente le funzioni costanti unarie (facilmente definibili a partire da ${+, * , \setminus}$)
Questo sistema funziona ed è adeguato qualsiasi sia il numero di valori (per ipotesi finito).

[40rob]

Sono riuscito a capire che se il numero di valori è un numero primo $p$ la base di connettivi si può ridurre a ${+, *, 1}$ dove $1$ rappresenta il connettivo della funzione costante che dà sempre $1$.
Tramite $1$ e $+$ si possono rappresentare tutte le funzioni costanti... $2$ come $1+1$, $3$ come $1 + 1 + 1$ ecc.
La "diagonale" lo stesso è rappresentabile a pezzi, basta usare la formula

$[(x + -1) * (x + -2) * (x + -3) * ... * (x + -(p-1))] * [(-1)' * (-2)' * ... * (-(p-1))']$

$-1$, $-2$ ecc. sono le costanti degli elementi simmetrici rispetto alla somma, l'apice $'$ rappresenta l'operazione di simmetrico rispetto al prodotto. Se $p$ è primo ogni elemento diverso da $0$ è simmetrizzabile rispetto al prodotto.
se $x = 1$ oppure $x = 2$ oppure ... oppure $x = (p - 1)$ la formula assume valore $0$ altrimenti (se $x$ è $0$) il valore è $1$ perché i simmetrici della seconda parte della formula tra parentesi quadre si accoppiano con i non simmetrici (rispetto al prodotto) presenti nella prima parte tra parentesi quadre, dando un prodotto del tipo $1 * 1 * 1 *... * 1 = 1$.
Infine basta aggiungere $+1$, $+ 2$... alla formula precedente per spostare l'unità che non si azzera e così facendo

$[((x + 1) + -1) * ((x + 1) + -2) * ((x + 1) + -3) * ... * ((x + 1) + -(p-1))] * [(-1)' * (-2)' * ... * (-(p-1))']$

$[((x + 2) + -1) * ((x + 2) + -2) * ((x + 2) + -3) * ... * ((x + 2) - (p-1))] * [(-1)' * (-2)' * ... * (-(p-1))']$
...

si ottengono $p$ formule $F_v(x)$ che in corrispondenza di ogni valore $v$ in ${0,1, ... , p-1}$ danno valore $1$ se $x = v$ altrimenti $0$.
Usando un sistema analogo al precedente si possono rappresentare tutte le funzioni.

[40rob]

Risolto. Trovato in rete questo articolo con la dimostrazione...

http://www.revistasbolivianas.org.bo/sc ... ci_arttext

C'è qualche errore di battitura ma sembra funzioni.

[40rob]

Aggiungo una curiosità.
Dato un insieme di $n$ valori e dato un ordine $<$ a questi valori (ai quali ci riferiamo per comodità con ${0, ... , n-1}$), se si definiscono le operazioni binaria $(x \vee y)$ e unaria $\neg x$ come rispettivamente $\max({x, y})$ e $(x + 1) \bmod n$, la coppia di operazioni risulta adeguata per rappresentare tutte le funzioni a $n$ valori.

A titolo di esempio mostro perché è valido in $n = 3$ valori ${0, 1, 2}$, la dimostrazione per valori maggiori (e minori, è analoga).

In primo luogo tutti i valori sono rappresentabili tramite delle formule, infatti:

$2 = (x \vee \neg x \vee \neg (\neg x))$ ,
$0 = \neg (x \vee \neg x \vee \neg (\neg x))$,
$1 = \neg (\neg(x \vee \neg x \vee \neg (\neg x)))$

(fino a un numero di $\neg$ all'estrema destra uguali a $(n - 1) = (3 - 1) = 2$).

La penultima colonna di $\vee$

$0,1,2$
$1,1,2$
$2,2,2$

è uguale sempre al penultimo valore $1$ tranne che per l'ultimo posto in colonna dove c'è il massimo, $2$. Selezionandola con la formula

$(x \vee 1)$

e ponendo

$f_2(x) = \neg(\neg(x \vee 1))$

otteniamo la funzione unaria $0,0,1$ che dà $1$ se $x = 2$, $0$ altrimenti.
analogamente otteniamo la funzione

$f_0(x) = \neg(\neg(\neg x \vee 1))$

che dà $1$ se $x = 1$, $0$ altrimenti, e

$f_1(x) = \neg(\neg(\neg(\neg x \vee 1)))$

che dà $1$ se $x = 0$, $0$ altrimenti.
Infine "spostando" e "ribaltando" le righe di $\vee$ con $\neg$, $(\neg(\neg x \vee \neg (\neg y)))$...

$2,2,2$
$2,0,1$
$2,1,1$

e applicando $\neg$ otteniamo la funzione binaria

$(x \otimes y) = \neg(\neg(\neg x \vee \neg(\neg y)))$

$0,0,0$
$0,1,2$
$0,2,2$

che è una sorta di operazione di moltiplicazione perché ha le due righe e colonne uguali alla moltiplicazione ($0$ annulla tutti i termini e $1$ è neutro come nella moltiplicazione), d'altra parte siccome $\vee$ ha lo $0$ come elemento neutro, funziona in questa riga come l'operazione $+$ modulo $n$ di somma. Sfruttando queste funzioni, possiamo generare qualsiasi altra funzione $h(x, y)$ binaria (e non solo binaria) tramite questo stratagemma...

$h(x, y) =$
$((f_0(x) \otimes f_0(y)) \otimes h(0,0)) \vee ((f_0(x) \otimes f_1(y)) \otimes h(0,1)) \vee$
$((f_0(x) \otimes f_2(y)) \otimes h(0,2)) \vee ((f_1(x) \otimes f_0(y)) \otimes h(1,0)) \vee$
$((f_1(x) \otimes f_1(y)) \otimes h(1,1)) \vee ((f_1(x) \otimes f_2(y)) \otimes h(1,2)) \vee$
$((f_2(x) \otimes f_0(y)) \otimes h(2,0)) \vee ((f_2(x) \otimes f_1(y)) \otimes h(2,1)) \vee$
$((f_2(x) \otimes f_2(y)) \otimes h(2,2))$

in luogo di $h(0,0)$ ecc. ovviamente si sostituiranno le funzioni costanti $0$, $1$, $2$ ed avremo la formula cercata. Se $x = 1$ e $y = 2$ la formula assumerà il valore $h(1,2)$.

$((f_0(1) \otimes f_0(2)) \otimes h(0,0)) \vee ((f_0(1) \otimes f_1(2)) \otimes h(0,1)) \vee$
$((f_0(1) \otimes f_2(2)) \otimes h(0,2)) \vee ((f_1(1) \otimes f_0(2)) \otimes h(1,0)) \vee$
$((f_1(1) \otimes f_1(2)) \otimes h(1,1)) \vee ((f_1(1) \otimes f_2(2)) \otimes h(1,2)) \vee$
$((f_2(1) \otimes f_0(2)) \otimes h(2,0)) \vee ((f_2(1) \otimes f_1(2)) \otimes h(2,1)) \vee$
$((f_2(1) \otimes f_2(2)) \otimes h(2,2)) = $

$(0 \otimes h(0,0)) \vee (0 \otimes h(0,1)) \vee$
$(0 \otimes h(0,2)) \vee (0 \otimes h(1,0)) \vee$
$(0 \otimes h(1,1)) \vee (1 \otimes h(1,2)) \vee$
$(0 \otimes h(2,0)) \vee (0 \otimes h(2,1)) \vee$
$(0 \otimes h(2,2)) = $

$0 \vee 0 \vee$
$0 \vee 0 \vee$
$0 \vee h(1,2) \vee$
$0 \vee 0 \vee$
$0 = $

$h(1,2)$

In modo analogo si puòl mostrare che anche le funzioni di minimo (una sorta di congiunzione a più valori) e successore rappresentano un insieme adeguato di connettivi.


Infine con l'unico operatore $x|y = \neg(x \vee y)$ analogo a quello di Sheffer, si possono rappresentare tutte le funzioni perché la sua diagonale

$1,2,0$
$2,2,0$
$0,0,0$

è l'operatore $\neg x = (x | x)$ e siccome $\neg \neg(x | y) = x \vee y$ si ha che

$x | x = \neg x$
$((x | y)|(x | y)) | ((x | y)|(x | y)) = x \vee y$

siccome $\neg$ e $\vee$ sono adeguati lo è anche $|$.
A più valori di $3$ la dimostrazione è analoga bisogna solo iterare opportunamente $\neg$ nelle formule.