Logica proposizionale

La logica proposizionale (o enunciativa) è un linguaggio formale con una semplice struttura sintattica, basata fondamentalmente su proposizioni elementari (atomi) e su connettivi logici di tipo vero-funzionale, che restituiscono il valore di verità di una proposizione in base al valore di verità delle proposizioni connesse (solitamente noti come AND, OR, NOT...). La semantica della logica proposizionale definisce il significato dei simboli e di qualsiasi proposizione che rispetti le regole sintattiche del linguaggio, basandosi sui valori di verità associati agli atomi. Data una interpretazione (o modello) di una proposizione (in generale di un insieme di proposizioni), e cioè una associazione tra le proposizioni elementari e le realtà rappresentate, possiamo generare un insieme infinito di proposizioni con significato definito che riguardino quella realtà. Ciascuna proposizione si riferisce quindi a uno o più oggetti della realtà rappresentata (anche astratta) e permette di descrivere o ragionare su quell'oggetto, utilizzando i due soli valori "vero" e "falso".

La definizione della struttura delle frasi (o sintassi) della logica proposizionale si fonda su due componenti:

• un alfabeto di simboli
• un insieme di sequenze di simboli (un linguaggio) definito tramite una grammatica generativa

L'alfabeto della logica proposizionale è costituito da:

• Un insieme numerabile di simboli di proposizione: p, q, r, ...
• I simboli dei connettivi logici: ${\displaystyle \neg }$ (NOT), ${\displaystyle \wedge }$ (AND), ${\displaystyle \vee }$ (OR), → (implicazione), ↔ (doppia implicazione)
• Le parentesi: (,) (hanno per lo più lo scopo di rendere il linguaggio più chiaro ed evitare ambiguità)

Le espressioni "sintatticamente corrette" della logica proposizionale (quelle che dovrebbero rappresentare degli enunciati dotati di senso in modo non ambiguo) sono chiamate formule ben formate, brevemente fbf (spesso in letteratura si trova anche wff, dall'inglese "well-formed formulas"), e sono definite mediante la seguente definizione ricorsiva:

Sono esempi di formule ben formate:

• p (dalla regola 1)
• (¬p) (dalla regola 2 applicata alla fbf precedente)
• (p${\displaystyle \wedge }$(¬p)) (dalla regola 3 applicata alle due fbf precedenti)
• ((p${\displaystyle \wedge }$(¬p))${\displaystyle \vee }$(¬p)) (dalla regola 3 applicata alle due fbf precedenti)

Sono esempi di non formule (p e q sono simboli di proposizione):

• p ${\displaystyle \wedge }$ (( q
• p ${\displaystyle \wedge }$${\displaystyle \vee }$ q

Stabilire il seguente ordine di precedenza dei connettivi logici, come accade per la moltiplicazione rispetto all'addizione, permette un utilizzo minore delle parentesi:

• ${\displaystyle \neg }$, ${\displaystyle \wedge }$, ${\displaystyle \vee }$, →, ↔

Per esempio p ${\displaystyle \wedge }$ ${\displaystyle \neg }$ q è la formula (p ${\displaystyle \wedge }$ (${\displaystyle \neg }$ q)).

Inoltre, si considerano i connettivi logici associativi a sinistra [ p ${\displaystyle \wedge }$ q ${\displaystyle \wedge }$ r viene reinterpretato come ((p ${\displaystyle \wedge }$ q) ${\displaystyle \wedge }$ r) ].

Le regole sopra esposte definiscono il linguaggio della logica proposizionale attraverso una grammatica generativa.

La grammatica della logica proposizionale scritta in BNF è la seguente:

f := l e L | (NOT f) | (f1 AND f2) | (f1 OR f2) | (f1 -> f2) | (f1 <-> f2)

Alle formule della logica proposizionale possono essere associati dei valori di verità mediante una funzione di valutazione:

Tali condizioni rispecchiano il significato che si vuole attribuire ai simboli associati ai connettivi logici e si possono riassumere mediante la seguente tavola di verità:

${\displaystyle P}$	${\displaystyle Q}$	${\displaystyle \neg }$${\displaystyle P}$	${\displaystyle P}$ ${\displaystyle \wedge }$ ${\displaystyle Q}$	${\displaystyle P}$ ${\displaystyle \vee }$ ${\displaystyle Q}$	${\displaystyle P}$ → ${\displaystyle Q}$	${\displaystyle P}$ ↔ ${\displaystyle Q}$
V	V	F	V	V	V	V
V	F	F	F	V	F	F
F	V	V	F	V	V	F
F	F	V	F	F	V	V

Si dimostra che una valutazione è univocamente individuata dai valori che assume sui simboli di proposizione: i valori sulle formule più complesse in cui compaiono simboli di operatori logici possono essere dedotti a partire dalle condizioni sopra esposte che definiscono una valutazione.

Sono importanti le seguenti definizioni:

Un banale esempio di formula soddisfacibile è p, un esempio di formula contraddittoria è (p${\displaystyle \wedge }$¬p), un esempio di tautologia è (p${\displaystyle \vee }$¬p).

Il problema di stabilire se una formula è soddisfacibile - noto anche come Problema di soddisfacibilità booleana - è un problema decidibile: si può risolvere considerando tutte le possibili combinazioni di valutazioni sui simboli proposizionali e calcolando il corrispondente valore di verità della formula composta sfruttando le proprietà della funzione di valutazione. Il teorema di Cook-Levin stabilisce che tale problema appartiene alla classe dei problemi NP-completi.

La definizione di soddisfacibilità si può estendere a insiemi (eventualmente infiniti) di formule ben formate:

Il teorema di compattezza stabilisce che un insieme di fbf S è soddisfacibile se e solo se ogni suo sottoinsieme finito è soddisfacibile.

Con altri termini è possibile dare le seguenti definizioni. Una formula ben formata A è:

• soddisfacibile se esiste una interpretazione I di A in cui A è vera; in questo caso I si dice modello di A.

• falsificabile se esiste una interpretazione I tale che A è falsa; I si chiama contromodello di A.

• valida se A è vera in ogni interpretazione.

• Dirk van Dalen, Propositional Logic, in Logic and Structure, Berlin, Springer, 2013, ISBN 978-3-540-20879-2.
• Sergio Galvan, Logica dei predicati, EDUCatt, Milano, 2004.

• Logica matematica
• Sistema formale
• Linguaggio del primo ordine
• STRIPS

• Wikibooks contiene testi o manuali sulla logica proposizionale
• Wikiversità contiene risorse sulla logica proposizionale
• Wikimedia Commons contiene immagini o altri file sulla logica proposizionale

• proposizionale, calcolo, in Dizionario di filosofia, Istituto dell'Enciclopedia Italiana, 2009.
• (EN) logic of propositions / propositional calculus, su Enciclopedia Britannica, Encyclopædia Britannica, Inc.
• (EN) Kevin C. Klement, Propositional Logic, su Internet Encyclopedia of Philosophy.
• (EN) Curtis Franks, Propositional Logic, su Stanford Encyclopedia of Philosophy.
• (EN) Eric W. Weisstein, Propositional Calculus, su MathWorld, Wolfram Research.
• (EN) Propositional calculus(2) / Propositional calculus, su Encyclopaedia of Mathematics, Springer e European Mathematical Society.
• (EN) Denis Howe, propositional logic, in Free On-line Dictionary of Computing. Disponibile con licenza GFDL

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