Tabella della verità

Le tabelle della verità (o tabelle logiche) sono tabelle usate nella logica per determinare se, attribuiti i valori di verità alle proposizioni che la compongono, una determinata proposizione è vera o falsa. La tabella di verità quindi si applica 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.

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 tabella 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 tabelle 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 tabelle di verità.

Le tabelle 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 tabelle 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 tabelle 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 tabella rappresenta la funzione booleana V = XY + XZ + YZ = X AND Y OR X AND Z OR Y AND Z esprimibile anche come ${\displaystyle v=(x\wedge y)\vee (x\wedge z)\vee (y\wedge z)}$

${\displaystyle x}$	${\displaystyle y}$	${\displaystyle z}$	${\displaystyle (x\wedge y)\vee (x\wedge z)\vee (y\wedge z)}$
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

La relazione di negazione NOT (  ) è un connettivo logico, attraverso il quale, a partire da una proposizione A si forma una nuova proposizione chiamata negazione di A ${\displaystyle {\overline {A}}}$ la quale è vera quando A è falsa, ed è falsa quando A è vera. La relazione è così definita:

${\displaystyle A}$	${\displaystyle {\overline {A}}}$
F	V
V	F

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

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\wedge B}$
F	F	F
F	V	F
V	F	F
V	V	V

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

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A\vee B}$
F	F	F
F	V	V
V	F	V
V	V	V

Espressioni composte possono essere costruite usando le parentesi per indicare la precedenza negli operatori.

La negazione della congiunzione ${\displaystyle {\overline {A\wedge B}}=A{\overline {\wedge }}B}$, e la disgiunzione della negazione ¬${\displaystyle A}$ ∨ ¬ ${\displaystyle B}$ risultano nella seguente:

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A}$ ∧ ${\displaystyle B}$	${\displaystyle A}$ ∧ ${\displaystyle B}$	¬ ${\displaystyle A}$	¬ ${\displaystyle B}$	¬ ${\displaystyle A}$ ∨ ¬ ${\displaystyle B}$
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

Le tabelle di verità possono essere usate per verificare equivalenze logiche.

La negazione della disgiunzione ¬ (${\displaystyle A}$ ∨ ${\displaystyle B}$) ≡ ${\displaystyle A}$∨ ${\displaystyle B}$, e l'unione delle congiunzioni ¬ ${\displaystyle A}$ ∧ ¬ ${\displaystyle B}$ risultano così di seguito equivalenti:

${\displaystyle A}$	${\displaystyle B}$	${\displaystyle A}$ ∨ ${\displaystyle B}$	${\displaystyle A}$ ∨ ${\displaystyle B}$	¬ ${\displaystyle A}$	¬ ${\displaystyle B}$	¬ ${\displaystyle A}$ ∧ ¬ ${\displaystyle B}$
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 tabelle di verità, dal momento che tutti i valori di stato possibili per ${\displaystyle A}$ e ${\displaystyle B}$ portano allo stesso stato per pari condizioni di ${\displaystyle A}$ ∧ ${\displaystyle B}$ e ¬ ${\displaystyle A}$ ∨ ¬ ${\displaystyle B}$; e per ${\displaystyle A}$ ∨ ${\displaystyle B}$ e ¬ ${\displaystyle A}$ ∧ ¬ ${\displaystyle B}$, risultando uguali tra loro e alternativamente utilizzabili. Questa equivalenza è conosciuta come legge di De Morgan.

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

${\displaystyle P}$	${\displaystyle Q}$	${\displaystyle P}$ ∧ ${\displaystyle Q}$	${\displaystyle P}$ ∨ ${\displaystyle Q}$	${\displaystyle P}$ ∧ ${\displaystyle Q}$	${\displaystyle P}$ ∨ ${\displaystyle Q}$	${\displaystyle P}$ → ${\displaystyle Q}$	${\displaystyle P}$ ← ${\displaystyle Q}$
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)

∧ = NAND (NAND esclusivo)

∨ = NOR (NOR esclusivo)

→ = "se-allora" (implicazione logica)

← = "(allora)-se" (controimplicazione logica)

<↔>: se e soltanto se è logicamente equivalente a <∨>: XNOR (NOR esclusivo).

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

Una forma condensata della tabella 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 tabella della verità:

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 tabella, permettendo al lettore una più rapida comprensione.

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 (+1 se vera; -1 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 sub-spazio 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, ovvero 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 (p= +1;q= +1)^[1].

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

• Calcolo proposizionale
• Mappa di Karnaugh
• Algebra di Boole

• Wikimedia Commons contiene immagini o altri file sulla tabella della verità

• verita, tavola di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
• (EN) truth table, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Opere riguardanti truth table, su Open Library, Internet Archive.
• (EN) Eric W. Weisstein, Truth Table, su MathWorld, Wolfram Research.
• (EN) Truth table, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Denis Howe, truth table, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL
• Generatore di tabelle di verità, su turner.faculty.swau.edu. URL consultato il 13 luglio 2010 (archiviato dall'url originale il 17 giugno 2010).
• Logisim - circuiti e tavole di verità, su sourceforge.net.
• Logisim Fork Italiano, su logisim.altervista.org. URL consultato il 19 maggio 2017 (archiviato dall'url originale il 6 ottobre 2017).

V · D · M Connettivi logici
Tautologia ( ${\displaystyle \top }$ )
Non-congiunzione ( ${\displaystyle \uparrow }$ ) · Implicazione inversa ( ${\displaystyle \leftarrow }$ ) · Implicazione ( ${\displaystyle \rightarrow }$ ) · Disgiunzione inclusiva ( ${\displaystyle \lor }$ )
Negazione ( ${\displaystyle \neg }$ ) · Disgiunzione esclusiva ( ${\displaystyle {\dot {\lor }}}$ ) · Doppia implicazione ( ${\displaystyle \leftrightarrow }$ ) · Proposizione
Non-disgiunzione inclusiva ( ${\displaystyle \downarrow }$ ) · Non-implicazione ( ${\displaystyle \nrightarrow }$ ) · Non-implicazione inversa ( ${\displaystyle \nleftarrow }$ ) · Congiunzione ( ${\displaystyle \land }$ )
Contraddizione ( ${\displaystyle \bot }$ )

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