Visualizza wikitesto di Non-implicazione inversa

Nella [[logica]], la '''non-implicazione inversa'''<ref>Lehtonen, Eero, e Poikonen, J.H.</ref>  è un [[connettivo logico]] che è la [[Negazione (matematica)|negazione]] dell'[[implicazione inversa]] (o, equivalentemente, la negazione dell'inverso dell'[[Implicazione logica|implicazione]]).

==Definizione==
[[File:Venn0010.svg|thumb|[[Diagramma di Venn]] di <math>A \not\leftarrow B</math> <br/> (l'area di colore bianco mostra dove la proposizione è falsa)]]
La non-implicazione inversa si denota con <math>P \nleftarrow Q</math> oppure con <math>P \not \subset Q</math>, ed è [[equivalenza logica|logicamente equivalente]]ad affermare che <math>\neg (P \leftarrow Q)</math>.

La [[tavola di verità]] di <math> P \nleftarrow Q </math> è la seguente<ref name="Knuth">{{cita|Knuth (2011)|p. 49}}.</ref>:

{| class="wikitable" style="text-align:center"
|- bgcolor="#ddeeff"
| <math> P </math> || <math> Q </math> || <math> P \nleftarrow Q </math>
|-
| {{Si2|Vero}} || {{Si2|Vero}} || {{no|Falso}}
|-
| {{Si2|Vero}} || {{no|Falso}} || {{no|Falso}}
|-
| {{no|Falso}} || {{Si2|Vero}} || {{Si2|Vero}}
|-
| {{no|Falso}} || {{no|Falso}} || {{no|Falso}}
|}

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

Notazioni alternative includono:
* <math>p \not\subset q</math>, che combina l'implicazione inversa <math>\subset</math> negata col simbolo /;
* <math>p \tilde{\leftarrow} q</math>, che combina la freccia sinistra dell'implicazione inversa <math>\leftarrow</math> con la tilde <math>\sim</math> della negazione.
* * M''pq'',, nella notazione di [[Józef Maria Bocheński|Bocheński]].

==Proprietà==
* Conservazione del valore falso: l'[[interpretazione (logica)|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 <math display="inline">q \nleftarrow p=q'p</math>.

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 <math>\sim</math> come operatori complemento, <math>\vee</math> come operatore di unione e <math>\wedge</math> come operatore di [[Intersezione (insiemistica)|intersezione]], fattori che unitamente costruiscono l'algebra booleana di una [[logica proposizionale]].

{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;"
| <math display="inline">{}\sim x</math>
| style="background-color:#DDFFDD"| 1
| style="background-color:#DDFFDD"| 0
|-
| x
! 0
! 1
|}
| style="border:none;" |and
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|y
|style="border:none;" |
|-
!1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
|-
!0
| style="background-color:#DDFFDD"|0
| style="background-color:#DDFFDD"|1
|-
| style="text-align:center;" |<math display="inline">y_\vee x</math>
!0
!1
|x
|}
| style="border:none;" |and
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|y
|style="border:none;" |
|-
!1
| style="background-color:#DDFFDD"|0
| style="background-color:#DDFFDD"|1
|-
!0
| style="background-color:#DDFFDD"|0
| style="background-color:#DDFFDD"|0
|-
| style="text-align:center;" |<math>y_\wedge x</math>
!0
!1
|x
|}
| style="border:none;" |alora <math>\scriptstyle{y \nleftarrow x}\!</math> significa
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|y
|style="border:none;" |
|-
!1
| style="background-color:#DDFFDD"|0
| style="background-color:#DDFFDD"|0
|-
!0
| style="background-color:#DDFFDD"|0
| style="background-color:#DDFFDD"|1
|-
| style="text-align:center;" |<math>\scriptstyle{y \nleftarrow x}\!</math>
!0
!1
|x
|}
|-
| style="border:none;" |''(Negazione)''
| style="border:none;" |
| style="border:none;" |''(or inclusivo)''
| style="border:none;" |
| style="border:none;" |''(And)''
| style="border:none;" |
| style="border:none;" |''(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 <math>\scriptstyle{ ^{c}}\!</math> (codivisori di 6) come operatore complementare<math>\scriptstyle{_\vee}\!</math> ([[minimo comune multiplo]]) come operatore di unione <math>\scriptstyle{_\wedge}\!</math> ([[massimo comun divisore]]) come operatore di intersezione, elementi che vanno a costruire un'algebra booleana.

{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;"
| <math>\scriptstyle{x^c}\!</math>
| style="background-color:#DDFFDD"|6
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|1
|-
| x
! 1
! 2
! 3
! 6
|}
| style="border:none;" |and
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|y
|style="border:none;" |
|-
!6
| style="background-color:#DDFFDD"|6
| style="background-color:#DDFFDD"|6
| style="background-color:#DDFFDD"|6
| style="background-color:#DDFFDD"|6
|-
!3
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|6
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|6
|-
!2
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|6
| style="background-color:#DDFFDD"|6
|-
!1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|6
|-
| style="text-align:center;" |<math>\scriptstyle{y_\vee x}\!</math>
!1
!2
!3
!6
|x
|}
| style="border:none;" |and
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|y
|style="border:none;" |
|-
!6
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|6
|-
!3
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|3
|-
!2
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|2
|-
!1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
|-
| style="text-align:center;" |<math>\scriptstyle{y_\wedge x}</math>
!1
!2
!3
!6
|x
|}
| style="border:none;" |allora <math>\scriptstyle{y \nleftarrow x}\!</math> significa
|style="border:none;" |
{| class="wikitable" style="border:none; background:transparent;text-align:center;"
|y
|style="border:none;" |
|-
!6
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
|-
!3
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|2
|-
!2
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|3
|-
!1
| style="background-color:#DDFFDD"|1
| style="background-color:#DDFFDD"|2
| style="background-color:#DDFFDD"|3
| style="background-color:#DDFFDD"|6
|-
| style="text-align:center;" |<math>\scriptstyle{y \nleftarrow x}\!</math>
!1
!2
!3
!6
|x
|}
|-
| style="border:none;" |''(Codivisore di 6)''
| style="border:none;" |
| style="border:none;" |''(Minimo comune multiplo)''
| style="border:none;" |
| style="border:none;" |''(Massimo comune divisore)''
| style="border:none;" |
| style="border:none;" |''(x è il massimo comune divisore [[coprimo]] con y)''
|}

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

Chiaramente, è associativa se e solo il termine <math>rp=0</math>.

====Non-commutatività====
* <math>q \nleftarrow p=p \nleftarrow q</math> se e solo se <math>q = p</math> . Quindi, la non-implicazione inversa non gode della proprietà commutativa.

====Elemento neutro e di assorbimento====
* 0 è l'[[elemento neutro]] del membro a sinistra (poiché <math>0 \nleftarrow p=p</math>) e l'[[elemento di assorbimento]] del membro a destra (<math>{p \nleftarrow 0=0}</math>).
* <math>1 \nleftarrow p=0</math>, <math>p \nleftarrow 1=p'</math>, e <math>p \nleftarrow p=0</math>.
* L'implicazione <math>q \rightarrow p</math> è il [[dualità (matematica)|duale]] della non-implicazione inversa<math>q \nleftarrow p</math> .

==Nell'informatica==
Un esempio di non implicazione inversa in informatica può essere trovato quando si esegue un [[Join (SQL)#Right outer join|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.<ref>{{Cita web|url=http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html|titolo=A Visual Explanation of SQL Joins|data=11 ottobre 2007|accesso=24 ottobre 2022|dataarchivio=15 febbraio 2014|urlarchivio=https://web.archive.org/web/20140215193839/http://www.codinghorror.com/blog/2007/10/a-visual-explanation-of-sql-joins.html|urlmorto=sì}}</ref>

==Note==
<references/>

==Bibliografia==
*{{Cita libro|cognome=Knuth|nome=Donald E.|wkautore=Donald Knuth|anno=2011|titolo=[[The Art of Computer Programming]], Volume 4A: Combinatorial Algorithms, Part 1|edizione=1a| editore=Addison-Wesley Professional| isbn=978-0-201-03804-0}}

== Altri progetti ==
{{interprogetto|preposizione=sulla}}

{{Connettivi logici}}

{{controllo di autorità}}
{{portale|matematica}}

[[Categoria:Connettivi logici]]