La tavola di verità () o tavola logica è una tabella usata nella logica per determinare se, attribuiti i valori di verità alle proposizioni che la compongono, una determinata proposizione è vera o falsa. Si può associare una tavola di verità a qualsiasi operatore logico vero-funzionale, vale a dire in cui le condizioni di verità o falsità di qualunque enunciato che si ottiene applicando quell'operatore è determinato interamente ed esclusivamente da quelle degli enunciati più semplici a cui si applica.

Descrizione Utilizzate come principale rappresentazione di una funzione booleana, le espressioni possono essere costrutti formati da più espressioni, in cui all'inizio compare una premessa, ed alla fine una conclusione. La tavola di verità elenca sulle caselle delle righe corrispondenti alle colonne delle variabili della funzione tutte le possibili combinazioni di valori che possono assumere le variabili booleane ed il risultato della funzione nelle caselle delle righe corrispondenti all'ultima colonna a destra, per tale combinazione di valori.

Le tavole di verità furono introdotte da Gottlob Frege, Charles Peirce, Bertrand Russell e altri verso il 1880, ed assunsero la forma attuale nel 1922, con i lavori indipendenti di Emil Leon Post e Ludwig Wittgenstein. Nel suo Tractatus logico-philosophicus Wittgenstein le usa per inquadrare le funzioni della verità all'interno di una serie. La vasta influenza esercitata da questa opera ha portato ad una larga diffusione delle tavole di verità.

Le tavole di verità sono usate per calcolare il valore di espressioni logico-funzionali. Le espressioni logico-funzionali possono essere sia atomiche (ad esempio, variabili proposizionali o semplici "segnaposto") oppure funzioni proposizionali costituite da formule atomiche e operatori logici (come AND, OR e NOT). Le intestazioni di colonna delle tavole della verità mostrano (i) le funzioni e/o le variabili proposizionali, e (ii) le espressioni di verità risultanti dalle combinazioni di quelle funzioni e variabili proposizionali. Nelle righe sono riportati tutti i possibili valori calcolati di V = "vero" o F = "falso" assegnati a (i) e (ii). In altre parole: ogni riga è una diversa interpretazione di (i) e (ii).

Le tavole di verità applicate alla logica classica (cioè a quella binaria) sono limitate alla logica booleana, dove sono ammessi soltanto due valori: "vero" (indicato anche con "1") e "falso" (indicato con "0").

Ad esempio la seguente tavola rappresenta la funzione booleana AND OR AND OR AND esprimibile anche come

F F F F F F V F F V F F F V V V V F F F V F V V V V F V V V V V

Operatori logici Operatore logico negazione NOT La relazione di negazione NOT (  ) è un connettivo logico, attraverso il quale, a partire da una proposizione si forma una nuova proposizione chiamata negazione di la quale è vera quando è falsa, ed è falsa quando è vera. La relazione è così definita:

F V V F

Operatore logico congiunzione AND Prendiamo due variabili proposizionali, e , e l'operatore logico AND (∧), ottenendo la congiunzione logica " e " o, più correttamente, . In altre parole: se sia che sono vere, allora la congiunzione è vera; ogni diversa assegnazione di valori di verità rende falsa. La relazione è così definita:

F F F F V F V F F V V V

Operatore logico disgiunzione OR Prendiamo due variabili proposizionali, e , e l'operatore logico OR (∨), ottenendo la congiunzione logica " OR ", se sia che sono vere, allora la disgiunzione è vera; se sono entrambe false è falsa; se è falsa e è vera, o viceversa, allora è vera. La relazione è così definita:

F F F F V V V F V V V V

Operatore NAND (congiunzione negata) Espressioni composte possono essere costruite usando le parentesi per indicare la precedenza negli operatori.

La negazione della congiunzione , e la disgiunzione della negazione ¬ ∨ ¬ risultano nella seguente:

∧ ∧ ¬ ¬ ¬ ∨ ¬ F F F V V V V F V F V V F V V F F V F V V V V V F F F F

Operatore NOR Le tavole di verità possono essere usate per verificare equivalenze logiche.

La negazione della disgiunzione ¬ ( ∨ ) ≡ ∨ , e l'unione delle congiunzioni ¬ ∧ ¬ risultano così di seguito equivalenti:

∨ ∨ ¬ ¬ ¬ ∧ ¬ F F F V V V V F V V F V F F V F V F F V F V V V F F F F

Analizzando e confrontando le due tavole di verità, dal momento che tutti i valori di stato possibili per e portano allo stesso stato per pari condizioni di ∧ e ¬ ∨ ¬ ; e per ∨ e ¬ ∧ ¬ , risultando uguali tra loro e alternativamente utilizzabili. Questa equivalenza è conosciuta come legge di De Morgan.

Tavole di verità per gli operatori logici più comuni Ecco le tavole di verità per gli operatori logici più comuni:

↔ → ← F F F F F V V V F V F V V F V F V F F V V F F V V V V V F V V V

Legenda: V = "vero", F = "falso"; = AND (congiunzione logica); = OR (disgiunzione logica); = XOR (OR esclusivo); ↔ = "se e solo se", è logicamente equivalente a XNOR (NOR esclusivo); → = "se-allora" (implicazione logica); ← = "(allora)-se" (controimplicazione logica).

I diagrammi di Johnston, simili ai diagrammi di Eulero-Venn, forniscono un metodo di visualizzazione della tavola della verità.

Tavole di verità condensate per operatori binari Una forma condensata della tavola di verità è usata per gli operatori binari; in questa, i titoli delle righe e colonne indicano gli operandi, e gli elementi della matrice il risultato. L'algebra di Boole, ad esempio, usa questa notazione condensata della tavola della verità:

∧ F V F F F V F V ∨ F V F F V V V V

Questa notazione è utile specialmente se gli operatori sono commutativi, benché si possano specificare le righe come primo operando e le colonne come secondo. La notazione abbreviata è particolarmente utile quando si trattano valori logici multipli, dato che rallenta il vertiginoso aumento di righe che sarebbe altrimenti necessario usare. Fornisce anche una forma caratteristica e prontamente riconoscibile della distribuzione dei valori nella tavola, permettendo al lettore una più rapida comprensione.

Inferenza logica spaziale Wittgenstein (1921) e Pólya (1940) coi loro lavori posero le basi della nozione di spazio logico e di ipercubo. Ogni proposizione atomica (con la sua negazione) forma un asse di un sistema di coordinate cartesiane, in un punto del quale assume un valore booleano ( se vera; se falsa, essendo lo zero già usato per l'origine degli assi) a seconda del suo valore di verità. Per ogni punto di un ipercubo, può essere identificato un sottospazio logico fra questo punto e l'origine degli assi. Su ogni spazio logico possono operare gli operatori booleani di unione, intersezione e negazione.

Ad esempio per due proposizioni p e q (di cui si considerano anche le rispettive negazioni) avremo 2 assi divisi in quattro quadranti in grado di rappresentare tutte le possibili combinazioni dei valori di verità di p e q, ossia la loro tavola di verità con qualsiasi operatore booleano. Se consideriamo l'operatore di congiunzione, avremo un punto (indicante il valore di verità dell'operatore) soltanto nel primo quadrante alle coordinate Thierry Morineau. Hypercube algebra: a diagrammatic and sentential notation to support inferences in logic. Phil and Susan Turner. European Conference on Cognitive Ergonomics, Aug 2012, Edinburgh, United Kingdom. 2012. hal-00722696.

Per proposizioni connesse da molteplici operatori, si possono in questo modo stabilire inferenze logiche "per via grafica", notando le relazioni spaziali.

Note

Voci correlate Algebra di Boole Logica proposizionale Mappa di Karnaugh

Altri progetti

Collegamenti esterni

Categoria:Algebra di Boole Categoria:Elettronica digitale Categoria:Logica proposizionale