LogicaUniPR - Guida Interattiva

Appunti della Professoressa: Capitolo 7 - Logica Proposizionale (Sintassi e Semantica)

Appunti del Corso: Capitolo 7 - Logica Proposizionale: Sintassi e Semantica Formale

Introduzione alla Logica Proposizionale Formale

Nei capitoli precedenti abbiamo introdotto la logica proposizionale in modo intuitivo. Ora, la formalizzeremo definendo precisamente la sua sintassi (come si costruiscono le frasi corrette) e la sua semantica (come si attribuisce un significato, ovvero un valore di verità, a queste frasi).

Questo approccio formale è cruciale per evitare ambiguità e per poter sviluppare metodi di ragionamento automatico (calcolo logico).

Sintassi della Logica Proposizionale

La sintassi definisce le regole per costruire le "frasi" corrette del nostro linguaggio logico.

1. Alfabeto ($\mathcal{A}$)

L'alfabeto della logica proposizionale è un insieme finito di simboli, composto da:

  • Simboli di proposizione atomica (o variabili proposizionali): Un insieme numerabile di simboli, es. $p, q, r, a, b, c, p_1, p_2, \dots$. Rappresentano le affermazioni elementari.
  • Simboli di connettivo logico: $\neg$ (negazione), $\wedge$ (congiunzione), $\vee$ (disgiunzione), $\Rightarrow$ (implicazione), $\Leftrightarrow$ (doppia implicazione). A volte si include $\oplus$ (OR esclusivo).
  • Simbolo per la Falsità (costante logica): $\perp$ (si legge "falso" o "assurdo"). A volte si include anche $\top$ per la Verità.
  • Simboli ausiliari: Parentesi $(, )$ per raggruppare e disambiguare.

2. Stringhe e Formule Ben Formate (FBF)

Una stringa è una qualsiasi sequenza finita di simboli dell'alfabeto $\mathcal{A}$. L'insieme di tutte le stringhe è $\mathcal{A}^*$. Non tutte le stringhe hanno un senso logico (es. "$p \wedge (\neg q$)" non è completa).

Le **Formule Ben Formate (FBF)** sono quelle stringhe che rispettano le regole grammaticali del nostro linguaggio logico. L'insieme delle FBF è il più piccolo insieme definito induttivamente come segue:

  1. Ogni simbolo di proposizione atomica (es. $p$) è una FBF.
  2. Il simbolo $\perp$ è una FBF. (Se si usa $\top$, anche $\top$ è una FBF).
  3. Se $X$ è una FBF, allora $(\neg X)$ è una FBF.
  4. Se $X$ e $Y$ sono FBF, allora $(X \wedge Y)$, $(X \vee Y)$, $(X \Rightarrow Y)$, $(X \Leftrightarrow Y)$ sono FBF.

Nota sulle parentesi: Per migliorare la leggibilità, le parentesi più esterne possono essere omesse. Esiste anche una gerarchia di precedenza tra i connettivi (tipicamente $\neg$ lega più forte, poi $\wedge$, poi $\vee$, poi $\Rightarrow, \Leftrightarrow$) che permette di omettere alcune parentesi interne. Ad esempio, $p \wedge q \Rightarrow r$ si intende come $((p \wedge q) \Rightarrow r)$.

3. Alberi di Parsing e Connettivo Principale

Ogni FBF può essere rappresentata univocamente da un albero di parsing (o albero sintattico). Le foglie dell'albero sono le proposizioni atomiche o $\perp$. I nodi interni sono i connettivi. La radice dell'albero è il connettivo principale della formula, cioè l'ultimo connettivo applicato nella sua costruzione.

La formula $(\neg (a \wedge b)) \vee ((\neg c) \Rightarrow d)$ ha come connettivo principale $\vee$.
Il suo sottoalbero sinistro è $\neg (a \wedge b)$ (connettivo principale $\neg$).
Il suo sottoalbero destro è $((\neg c) \Rightarrow d)$ (connettivo principale $\Rightarrow$).

4. Principio di Induzione Strutturale sulle FBF

Per dimostrare che una proprietà $P(X)$ vale per tutte le FBF $X$, si usa il **Principio di Induzione Strutturale**. Bisogna dimostrare:

  • Casi Base:
    • $P(a)$ vale per ogni proposizione atomica $a$.
    • $P(\perp)$ vale.
  • Passi Induttivi:
    • Se $P(X)$ vale (Ipotesi Induttiva), allora $P((\neg X))$ vale.
    • Se $P(X)$ e $P(Y)$ valgono (Ipotesi Induttive), allora $P((X \bullet Y))$ vale, per ogni connettivo binario $\bullet \in \{\wedge, \vee, \Rightarrow, \Leftrightarrow\}$.

Semantica della Logica Proposizionale

La semantica si occupa di attribuire un significato alle FBF, in particolare un valore di verità (Vero o Falso).

1. Valutazioni e Interpretazioni

Una **valutazione** (o assegnazione di verità) è una funzione $v$ che assegna a ogni proposizione atomica un valore di verità, $0$ (Falso) o $1$ (Vero).
$v: \{\text{proposizioni atomiche}\} \to \{0,1\}$.

Un'interpretazione (spesso indicata anche con $v$ o $[[\cdot]]$) estende una valutazione a tutte le FBF, definendo come calcolare il valore di verità di una formula composta a partire dai valori delle sue componenti. Per la logica classica, un'interpretazione $v: FBF \to \{0,1\}$ deve soddisfare le seguenti condizioni:

  • $v(\perp) = 0$.
  • $v((\neg X)) = 1 - v(X)$. (Equivalentemente, $v((\neg X))=1$ se $v(X)=0$, e $v((\neg X))=0$ se $v(X)=1$).
  • $v((X \wedge Y)) = \min(v(X), v(Y))$. (Equivalentemente, $v((X \wedge Y))=1$ se $v(X)=1$ e $v(Y)=1$, altrimenti $0$).
  • $v((X \vee Y)) = \max(v(X), v(Y))$. (Equivalentemente, $v((X \vee Y))=0$ se $v(X)=0$ e $v(Y)=0$, altrimenti $1$).
  • $v((X \Rightarrow Y)) = 1$ se e solo se $v(X) \le v(Y)$. (Equivalentemente, $v((X \Rightarrow Y))=0$ se $v(X)=1$ e $v(Y)=0$, altrimenti $1$. Oppure $v((X \Rightarrow Y)) = \max(1-v(X), v(Y))$).
  • $v((X \Leftrightarrow Y)) = 1$ se e solo se $v(X) = v(Y)$. (Equivalentemente, $v((X \Leftrightarrow Y))=1$ se $v(X)=v(Y)$, altrimenti $0$).

Il valore di verità di una FBF $P$ è univocamente determinato dai valori di verità assegnati alle proposizioni atomiche che compaiono in $P$. Se $P$ contiene $n$ atomi distinti, ci sono $2^n$ possibili interpretazioni (valutazioni iniziali degli atomi) da considerare.

2. Modelli, Soddisfacibilità, Validità, Contraddizioni

  • Se per una data interpretazione $v$, $v(P)=1$, diciamo che $P$ è soddisfatta da $v$, o che $v$ è un modello per $P$. Si scrive $v \models P$.
  • Una FBF $P$ è soddisfacibile se esiste almeno un'interpretazione $v$ tale che $v \models P$ (cioè, se ha almeno un modello).
  • Una FBF $P$ è contraddittoria (o insoddisfacibile) se non ha modelli, cioè se $v(P)=0$ per ogni interpretazione $v$. Si scrive $\not\models P$ (anche se a volte $\perp \models P$ si usa per indicare che $P$ è una contraddizione, il che è un po' confuso). Più comunemente, $P$ è una contraddizione se $P \equiv \perp$.
  • Una FBF $P$ è valida (o una tautologia) se è soddisfatta da ogni interpretazione, cioè se $v(P)=1$ per ogni $v$. Si scrive $\models P$.

$p \vee \neg p$ è una tautologia.
$p \wedge \neg p$ è una contraddizione.
$p \wedge q$ è soddisfacibile (es. se $v(p)=1, v(q)=1$) ma non è una tautologia.

3. Conseguenza Semantica (o Logica)

Sia $\Gamma$ un insieme di FBF (le premesse) e $P$ una FBF (la conclusione). Diciamo che $P$ è una conseguenza semantica di $\Gamma$, scritto $\Gamma \models P$, se ogni interpretazione che rende vere tutte le formule in $\Gamma$ rende vera anche $P$.

Formalmente: $\Gamma \models P \iff \forall v, ((\forall Q \in \Gamma, v(Q)=1) \Rightarrow v(P)=1)$.

Se $\Gamma = \{Q_1, \dots, Q_n\}$, scriviamo $Q_1, \dots, Q_n \models P$.
Se $\Gamma = \emptyset$ (l'insieme vuoto), allora $\emptyset \models P$ significa che $P$ è vera in tutte le interpretazioni, cioè $P$ è una tautologia ($\models P$).

Lemmi importanti:

  • $\Gamma \models P \iff \Gamma \cup \{\neg P\}$ è insoddisfacibile. (Principio di Rifutazione)
  • Per FBF $P, Q$: $P \models Q \iff \models (P \Rightarrow Q)$. (Teorema di Deduzione Semantica, caso semplice)
  • Più in generale: $Q_1, \dots, Q_n \models P \iff \models (Q_1 \wedge \dots \wedge Q_n) \Rightarrow P$.

4. Equivalenza Semantica

Due FBF $P$ e $Q$ sono **semanticamente equivalenti**, scritto $P \equiv Q$, se hanno lo stesso valore di verità per ogni possibile interpretazione $v$. Cioè, $v(P) = v(Q)$ per ogni $v$. Questo è lo stesso concetto di equivalenza logica visto con le tavole di verità.

$P \equiv Q \iff \models (P \Leftrightarrow Q)$.

5. Forme Normali

Ogni FBF può essere trasformata in una FBF equivalente che ha una struttura standardizzata, chiamata **forma normale**.

  • Un letterale è una proposizione atomica o la sua negazione (es. $p$, $\neg q$).
  • Una clausola disgiuntiva è una disgiunzione di letterali (es. $p \vee \neg q \vee r$).
  • Una clausola congiuntiva è una congiunzione di letterali (es. $p \wedge \neg q \wedge r$).
  • Una FBF è in Forma Normale Congiuntiva (FNC) se è una congiunzione di clausole disgiuntive.
    Esempio: $(p \vee \neg q) \wedge (\neg p \vee r) \wedge q$.
  • Una FBF è in Forma Normale Disgiuntiva (FND) se è una disgiunzione di clausole congiuntive.
    Esempio: $(p \wedge \neg q) \vee (\neg p \wedge r) \vee q$.

Teorema: Per ogni FBF $P$, esistono una FBF $P_C$ in FNC e una FBF $P_D$ in FND tali che $P \equiv P_C$ e $P \equiv P_D$. Le forme normali si possono ottenere manipolando la formula con equivalenze logiche (eliminando $\Rightarrow, \Leftrightarrow$, portando $\neg$ sugli atomi con De Morgan, e usando la distributività).