Appunti del Corso: Capitolo 1 - Linguaggio Matematico e Proposizioni
Linguaggio Oggetto e Metalinguaggio
In logica, distinguiamo tra:
- Linguaggio Oggetto: Il linguaggio formale che stiamo studiando (es. simboli come $x \in U$, $p, q, \wedge, \vee$).
- Metalinguaggio: Il linguaggio che usiamo per parlare del linguaggio oggetto (es. la lingua italiana con cui descriviamo le proprietà dei simboli logici).
Proposizioni
Una **proposizione** è una sentenza dichiarativa (una frase o asserzione) che può essere inequivocabilmente **VERA (V)** o **FALSA (F)**.
- Esempio $p$: "oggi piove". Può essere V o F.
- Esempio $q$: "4 è un numero dispari". È una proposizione FALSA.
- Esempio $r$: "4 è il quadrato di due". È una proposizione VERA.
Le proposizioni sono i "dati" elementari della logica. Combinandole, otteniamo informazioni.
Proposizioni Composte e Connettivi Logici
Le **proposizioni composte** sono costruite a partire da proposizioni semplici (o atomiche) o da altre proposizioni composte, mediante l'uso di **connettivi logici**. Il valore di verità di una proposizione composta dipende dai valori di verità delle sue sottoproposizioni.
Connettivi Logici Estensionali
I connettivi che usiamo sono **estensionali**, il che significa che il valore di verità della formula composta dipende *esclusivamente* dai valori di verità delle formule componenti.
1. Congiunzione (AND, $\wedge$)
È un connettivo binario. La proposizione $p \wedge q$ è VERA se e solo se sia $p$ che $q$ sono VERE.
| $p$ | $q$ | $p \wedge q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
2. Disgiunzione (OR, $\vee$, vel)
È un connettivo binario. La proposizione $p \vee q$ è VERA se e solo se almeno una tra $p$ e $q$ è VERA.
| $p$ | $q$ | $p \vee q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
3. Negazione (NOT, $\neg$)
È un connettivo unario. La proposizione $\neg p$ è VERA se e solo se $p$ è FALSA.
| $p$ | $\neg p$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
Vale la **doppia negazione**: $\neg (\neg p) \equiv p$.
Tavole di Verità per Formule Complesse
Per una formula con $n$ proposizioni atomiche distinte, la tavola di verità avrà $2^n$ righe, che rappresentano tutti i possibili casi (combinazioni di valori di verità).
Consideriamo la formula $(p \wedge q) \vee (\neg r)$. Le proposizioni atomiche sono $p, q, r$. Ci sono $2^3=8$ casi.
La **complessità** del metodo delle tavole di verità cresce esponenzialmente con il numero di proposizioni atomiche.
L'ordine di valutazione è determinato dal **connettivo principale**, che è quello alla radice dell'albero di parsing della formula. Le parentesi forzano la precedenza.
Valutazione in Corto Circuito (Lazy Evaluation)
Alcuni linguaggi di programmazione usano una valutazione "pigra" (lazy) o in corto circuito:
- Per $p \wedge q$: se $p$ è FALSO, non è necessario valutare $q$, perché $p \wedge q$ sarà sicuramente FALSO.
- Per $p \vee q$: se $p$ è VERO, non è necessario valutare $q$, perché $p \vee q$ sarà sicuramente VERO.
Proposizioni Logicamente Equivalenti ($\equiv$)
Due proposizioni $P$ e $Q$ sono **logicamente equivalenti** ($P \equiv Q$) se hanno lo stesso valore di verità in tutti i casi possibili (cioè, hanno la stessa tavola di verità).
- Commutatività:
- $p \wedge q \equiv q \wedge p$
- $p \vee q \equiv q \vee p$
- Doppia Negazione: $p \equiv \neg(\neg p)$
- Leggi di De Morgan:
- $\neg(p \wedge q) \equiv \neg p \vee \neg q$
- $\neg(p \vee q) \equiv \neg p \wedge \neg q$
Le proposizioni equivalenti sono **intercambiabili** e possono essere usate per semplificare espressioni o per escludere connettivi. Ad esempio, i set di connettivi $\{\neg, \wedge\}$ o $\{\neg, \vee\}$ sono funzionalmente completi.
- $p \vee q \equiv \neg(\neg p \wedge \neg q)$
- $p \wedge q \equiv \neg(\neg p \vee \neg q)$
Implicazione (Condizionale, $\Rightarrow$)
L'implicazione $p \Rightarrow q$ (si legge "$p$ implica $q$", o "se $p$ allora $q$") è definita come equivalente a $\neg p \vee q$.
È FALSA se e solo se la premessa $p$ è VERA e la conclusione $q$ è FALSA. In tutti gli altri casi è VERA.
| $p$ | $q$ | $\neg p$ | $\neg p \vee q \quad (p \Rightarrow q)$ |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 |
La **Regola di Deduzione (Modus Ponens)** afferma: se $p \Rightarrow q$ è VERA e $p$ è VERA, allora $q$ deve essere VERA.
Equivalenza importante: la **contronominale**: $p \Rightarrow q \equiv \neg q \Rightarrow \neg p$.
Tautologie, Contraddizioni e Dimostrazione per Assurdo
- Una **tautologia** è una proposizione che è sempre VERA (es. $p \Rightarrow (p \vee q)$).
- Una **contraddizione** è una proposizione che è sempre FALSA (es. $p \wedge \neg p$).
- La **dimostrazione per assurdo** di $p \Rightarrow q$ si basa sull'equivalenza $p \Rightarrow q \equiv \neg(p \wedge \neg q)$. Si nega la tesi ($p \wedge \neg q$) e si cerca di derivare una contraddizione.
Doppia Implicazione ($\Leftrightarrow$) e OR Esclusivo ($\oplus$)
Doppia Implicazione (Bicondizionale)
La proposizione $p \Leftrightarrow q$ ("$p$ se e solo se $q$") è VERA se e solo se $p$ e $q$ hanno lo stesso valore di verità.
È definita come: $p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)$.
| $p$ | $q$ | $p \Rightarrow q$ | $q \Rightarrow p$ | $(p \Rightarrow q) \wedge (q \Rightarrow p)$ |
|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 0 | 1 | 0 |
| 1 | 1 | 1 | 1 | 1 |
OR Esclusivo (XOR, $\oplus$)
La proposizione $p \oplus q$ è VERA se e solo se $p$ e $q$ hanno valori di verità diversi.
Si può definire come $p \oplus q \equiv (p \wedge \neg q) \vee (\neg p \wedge q)$, o anche $p \oplus q \equiv \neg(p \Leftrightarrow q)$.
| $p$ | $q$ | $p \oplus q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |