Non-implicazione inversa

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

Definizione

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

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

La tavola di verità di $P\nleftarrow Q$ è la seguente:

$P$	$Q$	$P\nleftarrow Q$
Vero	Vero	(NO)
Vero	(NO)	(NO)
(NO)	Vero	Vero
(NO)	(NO)	(NO)

Notazione

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

Notazioni alternative includono:

• $p\not \subset q$, che combina l'implicazione inversa $\subset$ negata col simbolo /;
• $p{\tilde {\leftarrow }}q$, che combina la freccia sinistra dell'implicazione inversa $\leftarrow$ con la tilde $\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 $\sim$ come operatori complemento, $\vee$ come operatore di unione e $\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 $y_{\wedge }x$ 0 1 x	alora $\scriptstyle {y\nleftarrow x}\!$ significa	y 1 0 0 0 0 1 $\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 $\scriptstyle {^{c}}\!$ (codivisori di 6) come operatore complementare$\scriptstyle {_{\vee }}\!$ (minimo comune multiplo) come operatore di unione $\scriptstyle {_{\wedge }}\!$ (massimo comun divisore) come operatore di intersezione, elementi che vanno a costruire un'algebra booleana.

$\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 $\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 $\scriptstyle {y_{\wedge }x}$ 1 2 3 6 x	allora $\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 $\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à

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

Chiaramente, è associativa se e solo il termine $rp=0$.

Non-commutatività

• $q\nleftarrow p=p\nleftarrow q$ se e solo se $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é $0\nleftarrow p=p$) e l'elemento di assorbimento del membro a destra (${p\nleftarrow 0=0}$).
• $1\nleftarrow p=0$, $p\nleftarrow 1=p'$, e $p\nleftarrow p=0$.
• L'implicazione $q\rightarrow p$ è il duale della non-implicazione inversa$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.

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