Implicazione logica

Da Wikipedia, l'enciclopedia libera.
bussola Disambiguazione – "Conseguenza logica" rimanda qui. Se stai cercando l'omonimo album dei Matia Bazar, vedi Conseguenza logica (album).

In matematica, la implicazione logica (simbolo \Rightarrow ) è un connettivo logico attraverso il quale, a partire da due proposizioni A e B, si forma una nuova proposizione chiamata A implica B e scritta A \Rightarrow B la quale è vera se e solo se è verificata la seguente condizione: se è vero A allora è vero anche B. In particolare A implica B è vera se A è falsa qualunque sia il valore di verità di B.

Questa definizione si può riassumere mediante la seguente tabella di verità:

 \mathcal A  \mathcal B  \mathcal A \Rightarrow \mathcal B
F F V
F V V
V F F
V V V

L'implicazione logica può essere vista anche come una relazione, due coppie di proposizioni sono in relazione se il risultato dell'operatore logico implicazione è VERO, questo aspetto è particolarmente evidente nel linguaggio comune dove l'implicazione è espressa nella forma “se A allora B”, così ad esempio ci risulta naturale la comprensione di:

“se piove allora ci sono nuvole in cielo

e l'unica possibilità che tale affermazione sia falsa è quella di verificare che in un dato momento piova ma NON ci siano nuvole in cielo. Supponendo che sia vera  \mathcal A \Rightarrow \mathcal B questa può anche essere espressa nei seguenti modi:

applicando tali modi all'esempio precedente rispetto al linguaggio comune possiamo affermare che condizione sufficiente perché in cielo ci siano nuvole è che piova, così come condizione necessaria perché piova è che in cielo ci siano nuvole. Uno sguardo più approfondito alla tabella di verità ci suggerisce tuttavia un modo per esprimere l'implicazione come risultato di espressioni logiche basate sui connettivi logici di “congiunzione” \land, “disgiunzione”  \lor e “negazione”  \lnot:  \mathcal A \Rightarrow \mathcal B è equivalente a:

 \neg \mathcal A \lor \mathcal B (i) ovvero applicando i Teoremi di De Morgan  \neg \left ( \mathcal A \land \neg \mathcal B \right ) (ii)

da tali notazioni emerge immediatamente che  \mathcal A \Rightarrow \mathcal A è una proposizione sempre vera indipendentemente dal valore di  \mathcal A . La notazione  \Rightarrow quindi è di per sé superflua, ma giustificata tuttavia dall'uso frequente che ne deriva dall'attività di deduzione, in questo contesto le proposizioni coinvolte vengono chiamata ipotesi:  \mathcal A , tesi:  \mathcal B , e teorema:  \mathcal A \Rightarrow \mathcal B (si noti che il teorema può essere posto in altre forme si veda infatti la deduzione è un caso particolare di inferenza), provare la veridicità di quest'ultima significa verificare la veridicità della tesi (dimostrare il teorema), la formalizzazione dei teoremi in questo modo ha il nome in logica di “modus ponens”. Possiamo inoltre notare come si possa riscrivere la (i) così:

 \neg \left ( \mathcal A \right ) \lor \neg \left ( \neg \mathcal B \right ) (iii) ovvero  \neg \left ( \neg \mathcal B \right ) \lor \neg \left ( \mathcal A \right )

e quindi per la (i) a  \neg \mathcal B \Rightarrow \neg \mathcal A (iv), questa forma viene chiamata contronominale della  \mathcal A \Rightarrow \mathcal B ed è a questa equivalente, e può essere usata nella dimostrazione dei teoremi in vece di quest'ultima. Tornando all'esempio in linguaggio naturale potremo scrivere la forma contronominale come:

“se non ci sono nuvole in cielo allora non piove

Un'altra strada per la dimostrazione di  \mathcal A \Rightarrow \mathcal B consiste nel tentare di dedurre da  \neg \left( \mathcal A \Rightarrow \mathcal B \right)  una contraddizione, cioè una proposizione  \mathcal C sempre falsa del tipo  \mathcal P \land \neg \mathcal P , in tale caso si parla di dimostrazione per assurdo. Se infatti otteniamo la dimostrazione di  \neg \left( \mathcal A \Rightarrow \mathcal B \right) \Rightarrow \mathcal C con  \mathcal C sempre falsa e per la (iv) si ha anche  \neg \mathcal C \Rightarrow \left( \mathcal A \Rightarrow \mathcal B \right) dove  \neg \mathcal C è sempre vera perché negazione di una contraddizione, ed impone quindi la veridicità di  \mathcal A \Rightarrow \mathcal B . Riguardando la tabella di verità dell'implicazione notiamo che se  \mathcal C è sempre falsa allora  \mathcal A \Rightarrow \mathcal B è sempre vera e andrà, quindi, posta particolare attenzione alle ipotesi: se sono false la dimostrazione riuscirà ma le deduzioni che ne trarremo sulla tesi saranno vuote di significato (la stessa può essere vera o falsa). Fin dall'antichità infatti è noto come da premesse false si possa dedurre ciò che si vuole. L'operazione di Implicazione gode inoltre della seguente proprietà:

 \left [ \left ( \mathcal A \Rightarrow \mathcal B \right ) \land \left ( \mathcal B \Rightarrow \mathcal C \right ) \right ] \Rightarrow \left ( \mathcal A \Rightarrow \mathcal C \right ) (v)

per dimostrarla possiamo usare la regola deduttiva, assumere vera la  \left [ \left ( \mathcal A \Rightarrow \mathcal B \right ) \land \left ( \mathcal B \Rightarrow \mathcal C \right ) \right ] dimostrare la veridicità della (v) e quindi dedurre \mathcal A \Rightarrow \mathcal C . Abbiamo inoltre bisogno di sapere che:

 \left [ \left ( \mathcal A \land \mathcal B \right ) \lor \neg \mathcal B \right ] = \left ( \mathcal A \lor \neg \mathcal B \right ) così come  \left [ \left ( \mathcal A \lor \mathcal B \right ) \land \neg \mathcal B \right ] = \left ( \mathcal A \land \neg \mathcal B \right ) (vi)

per la dimostrazione delle quali possiamo valutare le rispettive tabelle di verità, o considerare la proprietà distributiva della congiunzione e disgiunzione logica e la dualità delle algebre di Boole rispetto a tali connettivi. Tornando alla (v) togliamo dall'espressione il segno di implicazione ed otteniamo:

 \left [ \left ( \neg \mathcal A \lor \mathcal B \right ) \land \left ( \neg \mathcal B \lor \mathcal C \right ) \right ] \Rightarrow \left ( \neg \mathcal A \lor \mathcal C \right ) e quindi:  \neg \left [ \left ( \neg \mathcal A \lor \mathcal B \right ) \land \left ( \neg \mathcal B \lor \mathcal C \right ) \right ] \lor \left ( \neg \mathcal A \lor \mathcal C \right ) ovvero  \neg \left ( \neg \mathcal A \lor \mathcal B \right ) \lor \neg \left ( \neg \mathcal B \lor \mathcal C \right ) \lor \left ( \neg \mathcal A \lor \mathcal C \right ) ed ancora  \left ( \mathcal A \land \neg \mathcal B \right ) \lor \left ( \mathcal B \land \neg \mathcal C \right ) \lor  \neg \mathcal A \lor \mathcal C

riordinando i termini e tenendo presente la (vi) arriviamo quindi a scrivere:

 \neg \mathcal B \lor \neg \mathcal A \lor \mathcal B \lor \mathcal C

dove la presenza di  \neg \mathcal B \lor \mathcal B ci dice che è sempre vera cioè è una tautologia e la nostra tesi è dimostrata.

Coimplicazione[modifica | modifica wikitesto]

Se accade che valgano contemporaneamente  \mathcal A \Rightarrow \mathcal B e  \mathcal B \Rightarrow \mathcal A cioè che sia vera la:

 \left ( \mathcal A \Rightarrow \mathcal B \right ) \land \left ( \mathcal B \Rightarrow \mathcal A \right ) (iv)

allora possiamo esprimere questo fatto con un nuovo connettivo che chiameremo coimplicazione (o doppia implicazione logica):  \mathcal A \Leftrightarrow \mathcal B , potremo anche esprimerla dicendo che:

o che

  •  \mathcal A e  \mathcal B sono logicamente equivalenti.

La tabella di verità per tale connettivo è:

 \mathcal A  \mathcal B  \mathcal A \Rightarrow \mathcal B  \mathcal B \Rightarrow \mathcal A  \mathcal A \Leftrightarrow \mathcal B
falsa falsa vera vera vera
falsa vera vera falsa falsa
vera falsa falsa vera falsa
vera vera vera vera vera

Come ogni relazione di equivalenza essa gode delle proprietà riflessiva commutativa, transitiva: riflessiva perché  \mathcal A \Rightarrow \mathcal A è sempre vera come abbiamo visto, commutativa per definizione, transitiva per la (v) al punto precedente. Spesso i teoremi sono impostati su equivalenze logiche per più di 2 proposizioni:

 \left ( \mathcal A_1 \Leftrightarrow \mathcal A_2 \right ) \land \left ( \mathcal A_2 \Leftrightarrow \mathcal A_3 \right ) \land
\ldots \land \left ( \mathcal A_{N-1} \Leftrightarrow \mathcal A_N \right )

per brevità (di dimostrazione), in tale caso si usa la seguente forma:

 \left ( \mathcal A_1 \Rightarrow \mathcal A_2 \right ) \land \left ( \mathcal A_2 \Rightarrow \mathcal A_3 \right ) \land
\ldots \land \left ( \mathcal A_{N-1} \Rightarrow \mathcal A_N \right ) \land \left ( \mathcal A_N \Rightarrow \mathcal A_1 \right )

(vii) che le due espressioni siano equivalenti lo si deduce anche in questo caso dalla proprietà (v) dell'implicazione.

L'implicazione dal punto di vista insiemistico[modifica | modifica wikitesto]

Può essere utile ai fini della piena comprensione dell'implicazione logica mettersi in un'ottica di tipo insiemistico. L'implicazione  \mathcal A \Rightarrow \mathcal B può essere letta anche come \mathcal A \subseteq \mathcal B. Notiamo, infatti, che la proposizione logica scritta significa che se vale la proprietà \mathcal A, allora deve necessariamente valere anche la proprietà \mathcal B; ciò equivale al fatto che l'insieme degli elementi che soddisfano la proprietà \mathcal A deve essere contenuto nell'insieme degli elementi che soddisfano la proprietà \mathcal B.

Abbiamo visto che  \mathcal A \Rightarrow \mathcal B equivale a dire \neg \mathcal B \Rightarrow \neg \mathcal A; questa ultima implicazione, equivale a dire che se un elemento non soddisfa la proprietà  \mathcal B , cioè non sta nell'insieme degli elementi soddisfacenti tale proprietà, allora non deve soddisfare neanche la proprietà \mathcal A: questo ha un immediato riscontro in quanto detto prima: se un elemento non sta in \mathcal B, poiché \mathcal A \subseteq \mathcal B, esso non potrà stare neppure in \mathcal A.

Vediamo adesso la nozione di equivalenza (o coimplicazione): abbiamo che  \mathcal A \Leftrightarrow \mathcal B , cioè che \left(\mathcal A \Rightarrow \mathcal B \right) \and \left( \mathcal B \Rightarrow \mathcal A \right): quindi \left( \mathcal A \subseteq \mathcal B \right) \and \left(\mathcal B \subseteq \mathcal A\right): l'ovvia conseguenza è \mathcal A = \mathcal B. Infatti, la prima implicazione significa che un elemento che soddisfa la proprietà \mathcal A deve soddisfare anche la \mathcal B, mentre la seconda dice che un elemento che soddisfa la proprietà \mathcal B, deve necessariamente soddisfare anche la \mathcal A. Ne segue che gli elementi che soddisfano la prima proprietà sono tutti e soli quelli che soddisfano anche la seconda.

Da questa lettura insiemistica dell'implicazione logica, possiamo anche ricavare le nozioni di condizioni necessarie e condizioni sufficienti: se  \mathcal A \Rightarrow \mathcal B , cioè se \mathcal A \subseteq \mathcal B, allora:

  • non è necessario che un elemento stia in \mathcal A affinché stia in \mathcal B: esistono infatti elementi di \mathcal B che non stanno in \mathcal A
  • è sufficiente che un elemento stia in \mathcal A, per poter concludere che sta anche in \mathcal B: ogni elemento di \mathcal A infatti è anche un elemento di \mathcal B
  • è necessario che un elemento stia in \mathcal B, affinché possa stare in \mathcal A: se infatti tale elemento fosse fuori da \mathcal B, non potrebbe in nessun caso essere dentro \mathcal A
  • non è sufficiente che un elemento stia in \mathcal B per poter concludere che sta anche in \mathcal A: come detto prima, esistono certamente elementi appartenenti a \mathcal B ma non ad \mathcal A.


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