Funzione di verità

Nella logica, una funzione di verità è una funzione da valori di verità a un valore di verità univoco. Essa accetta come input e come output un valore di verità vero oppure falso. L'esempio tipico è nella logica proposizionale, in cui una proposizione composta è costruita a partire da proposizioni atomiche collegate mediante connettivi logici; se il valore di verità dell'enunciato composto è interamente determinato dal/i valore/i di verità dell'enunciato/i costituente/i, l'enunciato composto è chiamato funzione di verità (del valore di verità delle proposizioni componenti) e qualsiasi connettivo logico utilizzato è detto vero-funzionale.

La logica proposizionale classica è una logica vero-funzionale, dal momento che ogni affermazione possiede un valore di verità che è vero o falso, e ogni connettivo logico è vero-funzionale (che ha una tabella di verità corrispondente), quindi ogni affermazione composta è un funzione di verità. D'altra parte, la logica modale non è vero-funzionale.

Descrizione

Un connettivo logico è vero-funzionale se il valore di verità di un enunciato composto è funzione del valore di verità dei suoi enunciati componenti. Una classe di connettivi è vero-funzionale se ciascuno dei suoi membri lo è. Ad esempio, il connettivo "e" è vero-funzionale poiché una frase come " Le mele sono frutti e le carote sono verdure " è vera se e solo se ciascuna delle sue frasi componenti "le mele sono frutti " e " le carote sono verdure " è vera; altrimenti è falso.

I connettivi della forma "x crede che ..." sono esempi tipici di connettivi che non sono vero-funzionali. Se ad esempio Mary crede erroneamente che Al Gore sia stato Presidente degli USA il 20 aprile 2000, ma non crede che la luna sia fatta di formaggio fresco, allora la frase

" Mary crede che Al Gore sia stato Presidente degli USA il 20 aprile 2000 "

è vera, mentre

" May crede che la luna sia fatta di formaggio verde "

è falsa. In entrambi i casi, ogni frase componente (cioè " Al Gore era presidente degli USA il 20 aprile 2000 " e " la luna è fatta di formaggio verde ") è falsa, ma ogni frase composta formata anteponendo la frase " Mary crede che " differisce nel valore di verità. In altre parole, il valore di verità di una frase della forma " Maria crede che... " non è determinato unicamente dal valore di verità della sua frase componente, e quindi il connettivo (o semplicemente operatore poiché è unario) non è vero-funzionale.

La classe dei connettivi logici classici (come & , →) usati nella costruzione delle formule è vero-funzionale. Le tavole di verità stabiliscono i loro valori di verità in funzione del valore di verità variabile dei loro argomenti. Il calcolo proposizionale vero-funzionale è un sistema formale le cui formule possono essere interpretate come vere o false.

Tabella delle funzioni di verità binarie

Nella logica a due valori, ci sono sedici possibili funzioni di verità, dette anche funzioni booleane, di due ingressi P e Q. Ognuna di queste funzioni corrisponde a una tavola di verità di un certo connettivo logico nella logica classica, inclusi diversi casi degeneri come una funzione che non dipende da uno o da entrambi i suoi argomenti.

Completezza funzionale

Poiché una funzione può essere espressa come una composizione, un calcolo logico vero-funzionale non ha bisogno di simboli dedicati affinché tutte le funzioni sopra menzionate siano funzionalmente complete. Nel calcolo proposizionale l'equivalenza logica di alcune affermazioni composte fa sì che non siano necessari ulteriori simboli di calcolo specifici. Ad esempio, la logica classica ha ¬ P ∨ Q equivalente a P → Q: per un sistema logico a base classica, l'operatore condizionale "→" non è quindi necessario se "¬" (non) e "∨" (o) sono già in uso.

Un insieme minimo di operatori che possono esprimere ogni affermazione esprimibile nel calcolo proposizionale è chiamato insieme minimo funzionalmente completo. Un insieme minimamente completo di operatori è ottenuto dalla sola NAND {↑} e dalla sola NOR {↓}.

I seguenti sono gli insiemi minimi funzionalmente degli operatori le cui arietà è minore o uguale a 2:

Un elemento

{↑}, {↓}.

Due elementi

$\{\vee ,\neg \}$, $\{\wedge ,\neg \}$, $\{\to ,\neg \}$, $\{\gets ,\neg \}$, $\{\to ,\bot \}$, $\{\gets ,\bot \}$, $\{\to ,\nleftrightarrow \}$, $\{\gets ,\nleftrightarrow \}$, $\{\to ,\nrightarrow \}$, $\{\to ,\nleftarrow \}$, $\{\gets ,\nrightarrow \}$, $\{\gets ,\nleftarrow \}$, $\{\nrightarrow ,\neg \}$, $\{\nleftarrow ,\neg \}$, $\{\nrightarrow ,\top \}$, $\{\nleftarrow ,\top \}$, $\{\nrightarrow ,\leftrightarrow \}$, $\{\nleftarrow ,\leftrightarrow \}$.

Tre elementi

$\{\lor ,\leftrightarrow ,\bot \}$, $\{\lor ,\leftrightarrow ,\nleftrightarrow \}$, $\{\lor ,\nleftrightarrow ,\top \}$, $\{\land ,\leftrightarrow ,\bot \}$, $\{\land ,\leftrightarrow ,\nleftrightarrow \}$, $\{\land ,\nleftrightarrow ,\top \}$.

Proprietà algebriche

Alcune proprietà che una funzione di verità binaria (o un corrispondente connettivo logico) può avere sono:

• associatività: all'interno di un'espressione contenente due o più degli stessi connettivi associativi in una riga, l'ordine delle operazioni può essere modificato purché la sequenza degli operandi non lo sia.
• commutatività: gli operandi del connettivo possono essere scambiati senza mutare il valore di verità dell'espressione.
• distributività : Un connettivo indicato con · si distribuisce su un altro connettivo indicato con +, se a · ( b + c ) = ( a · b ) + ( a · c ) per tutti gli operandi a, b, c.
• idempotenza: ogni volta che gli operandi dell'operazione sono gli stessi, il connettivo fornisce l'operando come risultato. In altre parole, l'operazione preserva sia il valore vero che il valore falso (vedi sotto).
• legge di assorbimento: Una coppia di connettivi $\land ,\lor$ soddisfa la legge di assorbimento se $a\land (a\lor b)=a\lor (a\land b)=a$ per tutti gli operandi a , b.

Un insieme di funzioni di verità è funzionalmente completo se e solo se per ciascuna delle seguenti cinque proprietà contiene almeno un elemento che ne è privo:

• monotonia: Se f(a₁, ..., a_n) ≤ f(b₁, ..., b_n) per ogni a₁, ..., a_n, b₁, ..., b_n ∈ {0,1} tle che a₁ ≤ b₁, a₂ ≤ b₂, ..., a_n ≤ b_n. Ad esempio, $\vee ,\wedge ,\top ,\bot$.
• affinità: affine: Per ogni variabile, al variare del suo valore, il valore di verità dell'operazione varia o resta costante, a parità di valore delle altre variabili. Per esempio, gli operatori $\neg ,\leftrightarrow$, $\not \leftrightarrow ,\top ,\bot$.
• auto-dualità: leggere dall'alto verso il basso i valori di verità dell'operazione (nella tavola di verità) è identico a leggere il complemento a uno dei valori che si leggono dal basso verso l'alto. In altre parole, per l'operatore $\neg$, vale che: f(¬a₁, ..., ¬a_n) = ¬f(a₁, ..., a_n)
• preservazione del valore "vero": l'interpretazione in base alla quale a tutte le variabili viene assegnato un valore di verità di "vero" produce un valore di verità di "vero" come risultato di queste operazioni. Ciò vale per gli operatori $\vee ,\wedge ,\top ,\rightarrow ,\leftrightarrow ,\subset$ (cfr. validità).
• preservazione del valore "falso": l'interpretazione in base alla quale a tutte le variabili viene assegnato un valore di verità di "falso" produce un valore di verità di "vero" come risultato di queste operazioni. Ciò vale per gli operatori $\vee ,\wedge ,\nleftrightarrow ,\bot ,\not \subset ,\not \supset$ (cfr. validità).

Arietà

Una funzione concreta può anche essere definita operatore . Nella logica a due valori ci sono 2 operatori nullari (costanti), 4 operatori unari, 16 operatori binari, 256 operatori ternari e $2^{2^{n}}$ operatori n -ari. Nella logica a tre valori ci sono 3 operatori nullari (costanti), 27 operatori unari, 19683 operatori binari, 7625597484987 operatori ternari e $3^{3^{n}}$ operatori n -ari. Nella logica a k valori, ci sono k operatori nullari, $k^{k}$ operatori unari, $k^{k^{2}}$ operatori binari, $k^{k^{3}}$ operatori ternari e $k^{k^{n}}$ operatori n -ari. Un operatore n-ario della logica con valori k è una funzione da $\mathbb {Z} _{k}^{n}\to \mathbb {Z} _{k}$. Pertanto, il numero di tali operatori è $|\mathbb {Z} _{k}|^{|\mathbb {Z} _{k}^{n}|}=k^{k^{n}}$,che è il modo in cui sono stati derivati i numeri sopra.

Tuttavia, alcuni degli operatori di una particolare arietà sono in realtà forme degenerate che eseguono un'operazione di arietà inferiore su alcuni input e ignorano il resto degli input. Dei 256 operatori booleani ternari sopra citati, ${\binom {3}{2}}\cdot 16-{\binom {3}{1}}\cdot 4+{\binom {3}{0}}\cdot 2$ sono tali forme degenerate di operatori binari o di arietà inferiore, come evidenziato dal principio di inclusione-esclusione. L'operatore ternario $f(x,y,z)=\lnot x$ è uno di questi operatori degeneri che in realtà è un operatore unario applicato a un input x chee ignora gli altri due input y e z.

La negazione è un operatore unario, che assume un singolo argomento(es. ¬P). Gli altri operatori necessitano di almeno due argomenti per determinare una proposizione composta e si dicono quindi operatori binari: (P ∧ Q, P ∨ Q, P → Q, P ↔ Q).

L'insieme degli operatori logici Ω può essere suddiviso in sottoinsiemi disgiunti come segue:

$\Omega =\Omega _{0}\cup \Omega _{1}\cup \ldots \cup \Omega _{j}\cup \ldots \cup \Omega _{m}\,.$

In questa partizione, $\Omega _{j}$ è l'insieme dei simboli degli operatori di arietà j.

Nel più famigliare calcolo proposizionale, $\Omega$ è partizionato come segue:

operatori nullari: $\Omega _{0}=\{\bot ,\top \}$

operatori unari: $\Omega _{1}=\{\lnot \}$

operatori binari: $\Omega _{2}\supset \{\land ,\lor ,\rightarrow ,\leftrightarrow \}$

Principio di composizionalità

Il principio di composizionalità permette di interpretare i simboli dei connettivi logici senza ricorrere ale tavole di verità, per mezzo di una funzione di interpretazione di un insieme di funzioni di verità funzionalmente completo (Gamut, 1991). Sia 'I la funzione di interpretazione, Φ, Ψ due proposizioni qualsiasi, e f_nand la funzione di verità definita come:

• f_nand(T,T) = F; f_nand(T,F) = f_nand(F,T) = f_nand(F,F) = T

Allora, per opportunità, f_not, f_or f_and e così via con gli altri operatori, sono definiti per mezzo di f_nand:

• f_not(x) = f_nand(x,x)
• f_or(x,y) = f_nand(f_not(x), f_not(y))
• f_and(x,y) = f_not(f_nand(x,y))

oppure, in alternativa, f_not, f_or f_and e così via sono definiti direttamente:

• f_not(T) = F; f_not(F) = T;
• f_or(T,T) = f_or(T,F) = f_or(F,T) = T; f_or(F,F) = F
• f_and(T,T) = T; f_and(T,F) = f_and(F,T) = f_and(F,F) = F

allora:

I(~) = I(not) = f_not

I(&) = I(and) = f_and

I(v) = I(or-) = f_or

I(~Φ) = I(notΦ) = I(not)(I(Φ)) = f_not(I(Φ))

I(ΦandΨ) = I(and)(I(Φ), I(Ψ)) = f_and(I(Φ), I(Ψ))

etc.

Perciò, se S (abbreviazione di sentence) è una proposizione che è una stringa sia di simboli logici v₁...v_n che rappresentano altrettanti connettivi, che di simboli non logici c₁...c_n, quindi se e solo se I(v₁)...I(v_n) è stato elaborato interpretando v₁ a v_n per mezzo di f_nand (o di un altro insieme funzionalmente completo di funzioni di verità), allora il valore di verità I(s) è interamente determinato dai valori di verità c₁...c_n, cioè da I(c₁)...I(c_n). In altre parole, come è atteso e richiesto inizialmente, S è vera o falso solo rispetto a un'interpretazione di tutti i suoi simboli non logici.

Nell'informatica

Gli operatori logici sono implementati come porte logiche nei circuiti digitali. Praticamente tutti i circuiti digitali (con l'eccezione principale della DRAM) sono costruiti da NAND, NOR, NOT e porte di trasmissione. Le porte NAND e NOR con 3 o più ingressi anziché i soliti 2 ingressi sono abbastanza comuni, sebbene siano logicamente equivalenti a una cascata di porte a 2 ingressi. Tutti gli altri operatori vengono implementati scomponendoli in una combinazione logicamente equivalente di 2 o più delle porte logiche di cui sopra.

L'"equivalenza logica" di "NAND solo", "NOR solo" e "NOT e AND" è simile all'equivalenza di Touring. Il fatto che tutte le funzioni di verità possono essere espresse solo con NOR è dimostrato dall'Apollo Guidance Computer.

Bibliografia

• Józef Maria Bocheński (1959), A Précis of Mathematical Logic, translated from the French and German versions by Otto Bird, Dordrecht, South Holland: D. Reidel.
• Alonzo Church (1944), Introduction to Mathematical Logic, Princeton, NJ: Princeton University Press. See the Introduction for a history of the truth function concept.

Voci correlate

• Bertrand Russell e Alfred North Whitehead,

Principia Mathematica, 2ª edizione

• Ludwig Wittgenstein,

Tractatus Logico-Philosophicus, Proposizione 5.101

• Operazione bit a bit
• Funzione binaria
• Funzione booleana
• Logica booleana
• Elenco di argomenti di algebra booleana
• Connettivo logico
• Costante logica
• Operatore modale
• Calcolo proposizionale
• Funzione proposizionale
• Tavola della verità
• Valore di verità

Collegamenti esterni

• (EN) truth function, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.