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\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\subset ̸Q$, ed è logicamente equivalentead affermare che $\mathrm{\neg }(P\leftarrow Q)$.

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

$P$	$Q$	$P\nleftarrow Q$
Template:Si2	Template:Si2	Template:No
Template:Si2	Template:No	Template:No
Template:No	Template:Si2	Template:Si2
Template:No	Template:No	Template: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\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 $q\nleftarrow p=q^{\prime }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.

$\sim x$ 1 0 x 0 1	and	y 1 1 1 0 0 1 $y_{\vee }x$ 0 1 x	and	y 1 0 1 0 0 0 $y_{\wedge }x$ 0 1 x	alora $y\nleftarrow x$ significa	y 1 0 0 0 0 1 $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 ${}^c$ (codivisori di 6) come operatore complementare${}_{\vee }$ (minimo comune multiplo) come operatore di unione ${}_{\wedge }$ (massimo comun divisore) come operatore di intersezione, elementi che vanno a costruire un'algebra booleana.

$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 $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 $y_{\wedge }x$ 1 2 3 6 x	allora $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 $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^{\prime }$, e $p\nleftarrow p=0$.
• L'implicazione $q\to 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

• Template:Cita libro