Non-implicazione inversa

Nella logica, la non-implicazione inversa[1] è un connettivo logico che è la negazione dell'implicazione inversa (o, equivalentemente, la negazione dell'inverso dell'implicazione).

Definizione

Diagramma di Venn di ${\displaystyle A\not \leftarrow B}$
(l'area di colore bianco mostra dove la proposizione è falsa)

La non-implicazione inversa si denota con ${\displaystyle P\nleftarrow Q}$ oppure con ${\displaystyle P\not \subset Q}$, ed è logicamente equivalentead affermare che ${\displaystyle \neg (P\leftarrow Q)}$.

La tavola di verità di ${\displaystyle P\nleftarrow Q}$ è la seguente[2]:

${\displaystyle P}$	${\displaystyle Q}$	${\displaystyle P\nleftarrow Q}$
Vero	Vero	(NO)
Vero	(NO)	(NO)
(NO)	Vero	Vero
(NO)	(NO)	(NO)

Notazione

La non-implicazione inversa è denotata col simbolo ${\displaystyle p\nleftarrow q}$, che rappresenta la freccia con verso sinistro propria dell'implicazione inversa con il simbolo della negazione /.

Notazioni alternative includono:

• ${\displaystyle p\not \subset q}$, che combina l'implicazione inversa ${\displaystyle \subset }$ negata col simbolo /;
• ${\displaystyle p{\tilde {\leftarrow }}q}$, che combina la freccia sinistra dell'implicazione inversa ${\displaystyle \leftarrow }$ con la tilde ${\displaystyle \sim }$ della negazione.
• * Mpq,, nella notazione di Bocheński.

Proprietà

• Conservazione del valore falso: l'interpretazione in base alla quale a tutte le variabili viene assegnato un valore di verità di "falso" produce un valore di verità di "falso" come risultato della non-implicazione inversa.

Espressioni linguistiche

Nel linguaggio naturale la non-implicazione inversa è resa da espressioni quali: Q non implica P.

Algebra booleana

Nell'algebra di Boole la non-implicazione inversa è definita come ${\textstyle q\nleftarrow p=q'p}$.

Ad esempio, in un'algebra booleana a due elementi si ha: la coppia di elementi {0,1} con 0 e 1 come elementi unitari, gli operatori ${\displaystyle \sim }$ come operatori complemento, ${\displaystyle \vee }$ come operatore di unione e ${\displaystyle \wedge }$ come operatore di intersezione, fattori che unitamente costruiscono l'algebra booleana di una logica proposizionale.

${\textstyle {}\sim x}$ 1 0 x 0 1	and	y 1 1 1 0 0 1 ${\textstyle y_{\vee }x}$ 0 1 x	and	y 1 0 1 0 0 0 ${\displaystyle y_{\wedge }x}$ 0 1 x	alora ${\displaystyle \scriptstyle {y\nleftarrow x}\!}$ significa	y 1 0 0 0 0 1 ${\displaystyle \scriptstyle {y\nleftarrow x}\!}$ 0 1 x
(Negazione)		(or inclusivo)		(And)		(non-implicazione inversa)

Esempio di algebra booleana a 4 elementi: i 4 divisori {1,2,3,6} di 6 con 1 come zero e 6 come elemento unitario, operatori ${\displaystyle \scriptstyle {^{c}}\!}$ (codivisori di 6) come operatore complementare${\displaystyle \scriptstyle {_{\vee }}\!}$ (minimo comune multiplo) come operatore di unione ${\displaystyle \scriptstyle {_{\wedge }}\!}$ (massimo comun divisore) come operatore di intersezione, elementi che vanno a costruire un'algebra booleana.

${\displaystyle \scriptstyle {x^{c}}\!}$ 6 3 2 1 x 1 2 3 6	and	y 6 6 6 6 6 3 3 6 3 6 2 2 2 6 6 1 1 2 3 6 ${\displaystyle \scriptstyle {y_{\vee }x}\!}$ 1 2 3 6 x	and	y 6 1 2 3 6 3 1 1 3 3 2 1 2 1 2 1 1 1 1 1 ${\displaystyle \scriptstyle {y_{\wedge }x}}$ 1 2 3 6 x	allora ${\displaystyle \scriptstyle {y\nleftarrow x}\!}$ significa	y 6 1 1 1 1 3 1 2 1 2 2 1 1 3 3 1 1 2 3 6 ${\displaystyle \scriptstyle {y\nleftarrow x}\!}$ 1 2 3 6 x
(Codivisore di 6)		(Minimo comune multiplo)		(Massimo comune divisore)		(x è il massimo comune divisore coprimo con y)

Proprietà

Non-associatività

${\displaystyle r\nleftarrow (q\nleftarrow p)=(r\nleftarrow q)\nleftarrow p}$ se e solo se ${\displaystyle rp=0}$. In un'algebra booleana a due elementi, l'ultima condizione è ridotta a ${\displaystyle r=0}$ oppure ${\displaystyle p=0}$. In un'algebra booleana non banale la non-implicazione inversa non è associativa.

Chiaramente, è associativa se e solo il termine ${\displaystyle rp=0}$.

Non-commutatività

• ${\displaystyle q\nleftarrow p=p\nleftarrow q}$ se e solo se ${\displaystyle q=p}$ . Quindi, la non-implicazione inversa non gode della proprietà commutativa.

Elemento neutro e di assorbimento

• 0 è l'elemento neutro del membro a sinistra (poiché ${\displaystyle 0\nleftarrow p=p}$) e l'elemento di assorbimento del membro a destra (${\displaystyle {p\nleftarrow 0=0}}$).
• ${\displaystyle 1\nleftarrow p=0}$, ${\displaystyle p\nleftarrow 1=p'}$, e ${\displaystyle p\nleftarrow p=0}$.
• L'implicazione ${\displaystyle q\rightarrow p}$ è il duale della non-implicazione inversa${\displaystyle q\nleftarrow p}$ .

Nell'informatica

Un esempio di non implicazione inversa in informatica può essere trovato quando si esegue un join esterno destro su un insieme di tabelle estratte da un database, se i record che non corrispondono alla condizione di join dalla tabella "sinistra" vengono esclusi.[3]

Note

1. Lehtonen, Eero, e Poikonen, J.H.
2. Knuth (2011), p. 49.
3. A Visual Explanation of SQL Joins, su codinghorror.com, 11 ottobre 2007. URL consultato il 24 ottobre 2022 (archiviato dall'url originale il 15 febbraio 2014).

Bibliografia

• Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms, Part 1, 1a, Addison-Wesley Professional, 2011, ISBN 978-0-201-03804-0.

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sulla non-implicazione inversa