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

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^[2]:

$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.^[3]

Note

^ Lehtonen, Eero, e Poikonen, J.H.
^ Knuth (2011), p. 49.
^ 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

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

Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica

[1] Lehtonen, Eero, e Poikonen, J.H.

[Knuth-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).

[1]

[2]

[3]