da bub » 31/07/2021, 15:36
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 $massimo({x, y})$ e $(x + 1) mod 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 \negx)$ ,
$0 = \neg(x \vee \negx \vee \neg\negx)$,
$1 = \neg\neg(x \vee \negx \vee \neg\negx)$
(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(\negx \vee 1)$
che dà $1$ se $x = 1$, $0$ altrimenti, e
$f_1(x) = \neg\neg(\neg\negx \vee 1)$
che dà che $1$ se $x = 1$, $0$ altrimenti.
Infine "spostando" e "ribaltando" le righe di $\vee$ con $\neg$, $(\neg\negx \vee \neg\negy)$...
$2,2,2$
$2,0,1$
$2,1,1$
e applicando $\neg$ otteniamo la funzione binaria
$(x \otimes y) = \neg(\neg\negx \vee \neg\negy)$
$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 $\negx = 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.