Implicazione logica

Da Wikipedia, l'enciclopedia libera.

L'implicazione logica è un concetto matematico che stabilisce che, data un'affermazione, se ne può ricavare un'altra.

[modifica] Implicazione Logica

L' ”implicazione logica” è una operazione binaria tra proposizioni (o asserzioni ), viene generalmente rappresentata con il simbolo (o connettivo logico) $\Rightarrow$ o ( $\Rightarrow$ ), date quindi 2 proposizioni $\mathcal A$ e $\mathcal B$ il valore della nuova proposizione $\mathcal A \Rightarrow \mathcal B$ che si legge “a implica b”, si può definire sulla base dei valori delle proposizioni di partenza secondo la seguente tabella di verità:

$\mathcal A$	$\mathcal B$	$\mathcal A \Rightarrow \mathcal B$
falsa	falsa	vera
falsa	vera	vera
vera	falsa	falsa
vera	vera	vera

Può essere vista anche come una relazione, due coppie di proposizioni sono in relazione se il risultato dell'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:

$\mathcal A$ è condizione sufficiente per $\mathcal B$ ;
$\mathcal B$ è condizione necessaria per $\mathcal A$ ;

applicando tali modi all'esempio precedente rispetto al linguaggio comune possiamo affermare che condizione sufficiente perché in cielo ci siano nuvole e 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 $\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 $\mathcal A \Rightarrow \mathcal B$ è sempre vera, va quindi posta particolare attenzione alle ipotesi, se sono false la dimostrazione riuscirà, ma le deduzioni che ne trarremo potrebbero essere errate. 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 \mathcal B \right )$ così come $\left [ \left ( \mathcal A \lor \mathcal B \right ) \land \neg \mathcal B \right ] = \left ( \mathcal A \land \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 e dimostrata.

[modifica] Equivalenza logica

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 equivalenza logica: $\mathcal B \Leftrightarrow \mathcal A$ , potremo anche esprimerla dicendo che:

$\mathcal A$ è condizione necessaria e sufficiente per $\mathcal B$ .

La tabella di verità per tale relazione è:

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

Come ogni relazione di equivalenza che si rispetti 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 )$