LogicaUniPR - Guida Interattiva

7.1 Sintassi della Logica Proposizionale: Le Regole del Gioco

La sintassi stabilisce quali sequenze di simboli sono considerate "frasi" valide nel nostro linguaggio logico. È come la grammatica per una lingua naturale.

7.1.1 L'Alfabeto del Linguaggio Proposizionale ($\mathcal{L}_P$)

Ogni linguaggio formale inizia con un alfabeto, cioè un insieme di simboli base. Per la logica proposizionale, l'alfabeto $\mathcal{L}_P$ è tipicamente composto da:

• Un insieme numerabile di variabili proposizionali (o atomi): $Prop = \{p, q, r, p_0, p_1, p_2, \dots\}$. Queste rappresentano le affermazioni elementari che non possono essere ulteriormente scomposte all'interno della logica proposizionale.
• I connettivi logici:
  • $\neg$ (negazione, unario)
  • $\wedge$ (congiunzione, binario)
  • $\vee$ (disgiunzione, binario)
  • $\Rightarrow$ (implicazione, binario)
  • $\Leftrightarrow$ (doppia implicazione o bicondizionale, binario)
  (A volte si includono altri connettivi, come $\oplus$ per l'OR esclusivo, ma questi cinque sono i più comuni).
• Costanti logiche (opzionali, ma utili):
  • $\perp$ (falsum o assurdo), rappresenta una proposizione sempre falsa.
  • $\top$ (verum), rappresenta una proposizione sempre vera. (Se non si include $\top$, può essere definito come $\neg \perp$).
• Simboli ausiliari: Le parentesi $( \text{ e } )$ per raggruppare le sottoformule e garantire una lettura univoca.

7.1.2 Formule Ben Formate (FBF): Costruire Frasi Corrette

Non tutte le sequenze di simboli del nostro alfabeto formano una frase sensata. Ad esempio, "$p \wedge (\neg q \Rightarrow$" non è una formula completa. Le Formule Ben Formate (FBF) sono le "frasi grammaticalmente corrette" del nostro linguaggio. L'insieme delle FBF (spesso indicato con $FORM$ o $\mathcal{F}$) è il più piccolo insieme di stringhe sull'alfabeto $\mathcal{L}_P$ definito induttivamente dalle seguenti regole:

1. Base:
   • Ogni variabile proposizionale $p \in Prop$ è una FBF.
   • La costante $\perp$ è una FBF. (E $\top$, se inclusa nell'alfabeto).
2. Passo Induttivo:
   • Se $A$ è una FBF, allora $(\neg A)$ è una FBF.
   • Se $A$ e $B$ sono FBF, allora $(A \wedge B)$, $(A \vee B)$, $(A \Rightarrow B)$, e $(A \Leftrightarrow B)$ sono FBF.
3. Chiusura: Nient'altro è una FBF se non per applicazione delle regole precedenti.

Esempi di FBF: $p$, $\perp$, $(\neg q)$, $(p \wedge (\neg q))$, $( (r \Rightarrow p) \Leftrightarrow \perp )$.
Esempi di NON FBF: $p q \wedge$, $(\Rightarrow p)$, $p \neg q$.

Uso delle Parentesi e Precedenza: Le parentesi sono cruciali per evitare ambiguità. Per migliorare la leggibilità, si adottano convenzioni:

• Le parentesi più esterne di una formula possono essere omesse. Es: $(p \wedge q)$ può essere scritto $p \wedge q$.
• Esiste una gerarchia di precedenza tra i connettivi (come per le operazioni aritmetiche): $\neg$ ha la precedenza più alta, seguito da $\wedge$, poi $\vee$, e infine $\Rightarrow$ e $\Leftrightarrow$ (che spesso hanno la stessa precedenza e si valutano da sinistra a destra, o si usano parentesi per chiarire).
  Esempio: $\neg p \wedge q \Rightarrow r \vee s$ si interpreta come $(((\neg p) \wedge q) \Rightarrow (r \vee s))$. È sempre buona norma usare parentesi per evitare dubbi.

7.1.3 Alberi Sintattici e Connettivo Principale

Ogni FBF può essere rappresentata in modo univoco da un albero sintattico (o albero di parsing). Le foglie dell'albero sono le variabili proposizionali o le costanti ($\perp, \top$). I nodi interni sono etichettati con i connettivi logici. La radice dell'albero corrisponde al **connettivo principale** della formula, ovvero l'ultimo connettivo applicato nella sua costruzione secondo le regole induttive.

Per la FBF $F = ((\neg p) \vee (q \Rightarrow p))$:
Il connettivo principale è $\vee$.
Il sottoalbero sinistro è $(\neg p)$, il cui connettivo principale è $\neg$.
Il sottoalbero destro è $(q \Rightarrow p)$, il cui connettivo principale è $\Rightarrow$.

7.1.4 Sottoformule

Le sottoformule di una FBF $A$ sono tutte le FBF che compaiono come nodi nell'albero sintattico di $A$ (inclusa $A$ stessa).

7.1.5 Principio di Induzione Strutturale

Per dimostrare che una certa proprietà $P(F)$ vale per tutte le FBF $F$, si utilizza il Principio di Induzione Strutturale, che ricalca la definizione induttiva delle FBF:

1. Passo Base: Dimostrare che $P(F)$ vale per tutte le FBF atomiche (cioè per ogni variabile proposizionale $p$ e per $\perp$ (e $\top$ se presente)).
2. Passo Induttivo:
   • Assumere che $P(A)$ valga (Ipotesi Induttiva) e dimostrare che $P((\neg A))$ vale.
   • Assumere che $P(A)$ e $P(B)$ valgano (Ipotesi Induttive) e dimostrare che $P((A \bullet B))$ vale, per ogni connettivo binario $\bullet \in \{\wedge, \vee, \Rightarrow, \Leftrightarrow\}$.

Se entrambi i passi sono dimostrati, si conclude che la proprietà $P(F)$ vale per ogni FBF $F$.

Un esempio di utilizzo è dimostrare che ogni FBF contiene un numero uguale di parentesi aperte e chiuse (se le parentesi sono usate in modo stretto come nella definizione induttiva).

7.2 Semantica della Logica Proposizionale: Dare un Significato

La semantica si occupa di assegnare un significato alle FBF, e nella logica proposizionale classica, questo significato è un **valore di verità**: Vero (1) o Falso (0).

7.2.1 Valutazioni (o Assegnazioni di Verità)

Una valutazione (o assegnazione booleana) $v$ è una funzione che assegna un valore di verità (0 o 1) a ciascuna variabile proposizionale nell'alfabeto.

$v: Prop \to \{0, 1\}$.

Ad esempio, una valutazione potrebbe essere $v(p)=1, v(q)=0, v(r)=1, \dots$

7.2.2 Interpretazioni: Estendere le Valutazioni alle FBF

Un'interpretazione (spesso indicata anch'essa con $v$, o con la notazione $[[ \cdot ]]_v$) è una funzione che estende una data valutazione $v$ (definita sugli atomi) a *tutte* le FBF, specificando come calcolare il valore di verità di una formula composta. Le regole sono definite in modo ricorsivo, seguendo la struttura della formula e il significato intuitivo dei connettivi (come visto nelle tavole di verità del Capitolo 1):

• $v(\perp) = 0$ (Il falso è sempre falso).
• $v(\top) = 1$ (Il vero è sempre vero, se $\top$ è nell'alfabeto).
• $v(p)$ è dato dalla valutazione iniziale per ogni $p \in Prop$.
• $v((\neg A)) = 1 - v(A)$. (Se $v(A)=1$, $v((\neg A))=0$; se $v(A)=0$, $v((\neg A))=1$).
• $v((A \wedge B)) = \min(v(A), v(B))$. (È 1 se e solo se $v(A)=1$ e $v(B)=1$).
• $v((A \vee B)) = \max(v(A), v(B))$. (È 0 se e solo se $v(A)=0$ e $v(B)=0$).
• $v((A \Rightarrow B)) = 1$ se e solo se $v(A) \le v(B)$ (cioè, non accade che $v(A)=1$ e $v(B)=0$).
  Equivalentemente, $v((A \Rightarrow B)) = \max(1-v(A), v(B))$ oppure $v((A \Rightarrow B)) = 1 - v(A) + v(A)v(B)$ (usando l'aritmetica 0/1).
• $v((A \Leftrightarrow B)) = 1$ se e solo se $v(A) = v(B)$.

Il valore di verità di una FBF $F$ sotto una certa interpretazione $v$, $v(F)$, dipende unicamente dai valori di verità che $v$ assegna alle variabili proposizionali che compaiono in $F$. Se $F$ contiene $n$ variabili proposizionali distinte, ci sono $2^n$ possibili valutazioni iniziali da considerare, corrispondenti alle righe di una tavola di verità.

7.2.3 Modelli, Soddisfacibilità, Validità (Tautologie), Contraddizioni

• Se per una data interpretazione $v$, si ha $v(F)=1$, allora diciamo che $F$ è soddisfatta da $v$, oppure che $v$ è un modello per $F$. Si scrive $v \models F$.
• Una FBF $F$ è **soddisfacibile** se esiste almeno un'interpretazione $v$ che la soddisfa (cioè, $F$ ha almeno un modello). Questo significa che la sua tavola di verità contiene almeno un '1' nella colonna finale.
• Una FBF $F$ è **contraddittoria** (o insoddisfacibile) se non ha alcun modello, cioè se $v(F)=0$ per ogni possibile interpretazione $v$. La sua tavola di verità ha solo '0' nella colonna finale. Una formula è contraddittoria se e solo se è equivalente a $\perp$.
• Una FBF $F$ è valida (o è una tautologia) se è soddisfatta da ogni possibile interpretazione $v$, cioè se $v(F)=1$ per ogni $v$. La sua tavola di verità ha solo '1' nella colonna finale. Si scrive $\models F$. Una formula è una tautologia se e solo se è equivalente a $\top$ (o a $\neg \perp$).

$p \vee \neg p$ è una tautologia ($\models p \vee \neg p$).
$p \wedge q$ è soddisfacibile (ad esempio, $v(p)=1, v(q)=1$ è un modello), ma non è una tautologia.
$p \wedge \neg p$ è una contraddizione.

7.2.4 Conseguenza Logica (o Semantica)

Sia $\Gamma$ un insieme di FBF (chiamate premesse) e $F$ una singola FBF (chiamata conclusione). Diciamo che $F$ è una conseguenza logica (o **conseguenza semantica**) di $\Gamma$, e scriviamo $\Gamma \models F$, se e solo se ogni interpretazione $v$ che rende vere *tutte* le formule in $\Gamma$ rende vera anche $F$.

Formalmente: $\Gamma \models F \iff \text{per ogni interpretazione } v, \text{ se } (\forall G \in \Gamma, v(G)=1), \text{ allora } v(F)=1$.

In altre parole, non è possibile che tutte le premesse in $\Gamma$ siano vere e la conclusione $F$ sia falsa.

• Se $\Gamma = \{G_1, G_2, \dots, G_n\}$, si scrive $G_1, G_2, \dots, G_n \models F$.
• Se $\Gamma = \emptyset$ (insieme vuoto delle premesse), allora $\emptyset \models F$ (o semplicemente $\models F$) significa che $F$ è una tautologia (è vera in ogni interpretazione, senza bisogno di premesse).

Teorema di Deduzione Semantica (forma base): Per FBF $A$ e $B$, si ha che $A \models B$ se e solo se $\models (A \Rightarrow B)$. Cioè, $B$ è conseguenza logica di $A$ se e solo se l'implicazione $A \Rightarrow B$ è una tautologia.

Principio di Rifutazione: $\Gamma \models F$ se e solo se l'insieme $\Gamma \cup \{\neg F\}$ è insoddisfacibile (cioè è una contraddizione).

7.2.5 Equivalenza Logica (o Semantica)

Due FBF $A$ e $B$ sono logicamente equivalenti (o semanticamente equivalenti), scritto $A \equiv B$, se e solo se hanno lo stesso valore di verità per ogni possibile interpretazione $v$. Cioè, $v(A) = v(B)$ per ogni $v$. Questo è lo stesso concetto di equivalenza che abbiamo visto con le tavole di verità nel Capitolo 1.

Si può dimostrare che $A \equiv B$ se e solo se $\models (A \Leftrightarrow B)$ (cioè, la formula $A \Leftrightarrow B$ è una tautologia).

7.2.6 Forme Normali: FNC e FND

Ogni formula proposizionale può essere trasformata in una formula equivalente che ha una struttura standard, detta **forma normale**. Le due forme normali principali sono:

• Un letterale è una variabile proposizionale (es. $p$) o la sua negazione (es. $\neg p$).
• Una clausola disgiuntiva è una disgiunzione di uno o più letterali (es. $p \vee \neg q \vee r$).
• Una formula è in Forma Normale Congiuntiva (FNC) se è una congiunzione di una o più clausole disgiuntive.
  Esempio: $(p \vee \neg q \vee r) \wedge (\neg p \vee s) \wedge q$.
• Una clausola congiuntiva è una congiunzione di uno o più letterali (es. $p \wedge \neg q \wedge r$).
• Una formula è in Forma Normale Disgiuntiva (FND) se è una disgiunzione di una o più clausole congiuntive.
  Esempio: $(p \wedge \neg q \wedge r) \vee (\neg p \wedge s) \vee q$.

Teorema Fondamentale: Per ogni FBF $F$, esistono una FBF $F_{CNF}$ in FNC e una FBF $F_{DNF}$ in FND tali che $F \equiv F_{CNF}$ e $F \equiv F_{DNF}$.

Le forme normali si possono ottenere:

1. Dalla tavola di verità della formula.
2. Applicando una serie di trasformazioni basate su equivalenze logiche (eliminare $\Leftrightarrow$ e $\Rightarrow$, spingere le negazioni verso l'interno usando De Morgan e la doppia negazione, e infine usare le leggi distributive per ottenere la forma desiderata).

7.3 Esercizi del Capitolo 7