Capitolo 1: Introduzione alla Logica Matematica e Linguaggio
Benvenuto al primo capitolo! Qui esploreremo le fondamenta del linguaggio logico, un passo cruciale per comprendere come strutturare ragionamenti precisi, cosa indispensabile in informatica.
1.1 Perché la Logica nell'Informatica?
Ti sei mai chiesto come fa un computer a "capire" cosa deve fare? Non possiede intelligenza propria, ma esegue istruzioni. Queste istruzioni devono essere formulate in un linguaggio privo di ambiguità, un linguaggio formale. La logica è la scienza che studia i principi del ragionamento valido e ci fornisce gli strumenti per creare e comprendere questi linguaggi formali. In informatica, la logica è ovunque: dalla progettazione dei circuiti elettronici (porte logiche) alla scrittura di programmi corretti, dalla creazione di database intelligenti alla base dell'intelligenza artificiale.
1.2 Proposizioni: Mattoni del Ragionamento
Il blocco costruttivo fondamentale della logica è la proposizione. Cos'è? È semplicemente una frase, un'affermazione, per cui possiamo decidere con certezza se è VERA (V) o FALSA (F). Questo suo essere "Vera" o "Falsa" è chiamato il suo valore di verità. Pensa a un interruttore: o è acceso (Vero) o è spento (Falso), non ci sono vie di mezzo.
- Esempio 1: "Roma è la capitale d'Italia." Questa è una proposizione, e il suo valore di verità è VERO.
- Esempio 2: "I gatti possono volare." Questa è una proposizione, e il suo valore di verità è FALSO.
- Esempio 3: "5 è un numero pari." Proposizione FALSA.
- Non-Esempio 1: "Che bella giornata!" Questa è un'esclamazione, non possiamo dire se sia vera o falsa in senso logico.
- Non-Esempio 2: "x + 5 = 10". Questa frase contiene una variabile ($x$). Il suo valore di verità dipende da cosa sia $x$. Se $x=5$, è vera. Se $x=3$, è falsa. Frasi come questa, il cui valore di verità dipende da variabili, sono chiamate predicati e le studieremo più avanti. Per ora, ci concentriamo su affermazioni complete.
Per semplicità, indichiamo le proposizioni "atomiche" (cioè quelle più semplici, non scomponibili) con lettere minuscole come $p, q, r, \dots$. Spesso, per convenzione, si usa 1 per rappresentare il VERO e 0 per rappresentare il FALSO.
1.3 Connettivi Logici: Costruire Frasi Complesse
Proprio come in italiano usiamo "e", "o", "non" per legare frasi semplici, in logica usiamo i connettivi logici per combinare proposizioni atomiche e formarne di più complesse. Il bello è che il valore di verità della frase complessa dipenderà in modo preciso dai valori di verità delle parti e dal connettivo usato.
1.3.1 Negazione (NOT, $\neg$) - "Non è vero che..."
La negazione, indicata con $\neg p$, inverte semplicemente il valore di verità di $p$. Se $p$ è vera, $\neg p$ è falsa. Se $p$ è falsa, $\neg p$ è vera.
| $p$ | $\neg p$ |
|---|---|
| 0 (Falso) | 1 (Vero) |
| 1 (Vero) | 0 (Falso) |
Esempio: Se $p$: "Il sole è una stella" (VERO), allora $\neg p$: "Non è vero che il sole è una stella" (FALSO).
1.3.2 Congiunzione (AND, $\wedge$) - "Sia... sia..."
La congiunzione $p \wedge q$ (leggi "$p$ e $q$") è VERA soltanto se $p$ è VERA e $q$ è VERA. In tutti gli altri casi è FALSA.
| $p$ | $q$ | $p \wedge q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Esempio: $p$: "Parma è in Emilia" (VERO), $q$: "Milano è in Emilia" (FALSO). Allora $p \wedge q$ è FALSA.
1.3.3 Disgiunzione Inclusiva (OR, $\vee$) - "Almeno uno dei due..."
La disgiunzione $p \vee q$ (leggi "$p$ o $q$") è VERA se almeno una tra $p$ e $q$ è VERA. È FALSA solo se entrambe sono FALSE. Attenzione: questo "o" è inclusivo, significa "$p$ o $q$ o entrambi".
| $p$ | $q$ | $p \vee q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Esempio: $p$: "Studio logica" (sperabilmente VERO!), $q$: "Ascolto musica". $p \vee q$ è vera se studio, se ascolto musica, o se faccio entrambe le cose.
1.4 Tavole di Verità per Proposizioni Composte
Per analizzare proposizioni complesse, usiamo le tavole di verità. Se una formula contiene $n$ proposizioni atomiche distinte, ci sono $2^n$ possibili combinazioni dei loro valori di verità. Ogni riga della tavola rappresenta una di queste combinazioni. Calcoliamo il valore della formula passo-passo, partendo dalle sotto-formule più interne fino al connettivo principale (quello che lega le parti più grandi della formula).
Esempio: Tavola di verità per $ (p \Rightarrow q) \wedge (\neg q \Rightarrow \neg p) $
Questa formula esprime l'equivalenza tra un'implicazione e la sua contronominale.
| $p$ | $q$ | $\neg p$ | $\neg q$ | $p \Rightarrow q$ (A) | $\neg q \Rightarrow \neg p$ (B) | (A) $\wedge$ (B) |
|---|---|---|---|---|---|---|
| 0 | 0 | 1 | 1 | 1 | 1 | 1 |
| 0 | 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 | 1 | 1 | 1 |
Nota: Per vedere la tavola di verità dell'implicazione ($\Rightarrow$), consulta la sezione 1.6.
1.5 Equivalenza Logica ($\equiv$)
Due formule proposizionali $F_1$ e $F_2$ sono logicamente equivalenti, scritto $F_1 \equiv F_2$, se e solo se hanno la stessa tavola di verità. Ciò significa che per qualsiasi assegnazione di valori di verità alle proposizioni atomiche che le compongono, $F_1$ e $F_2$ assumono lo stesso valore di verità.
Alcune equivalenze fondamentali (molte altre sono elencate nel `formulario.pdf` e in `tutorato-01.pdf`):
- Doppia Negazione: $p \equiv \neg(\neg p)$
- Commutatività: $p \wedge q \equiv q \wedge p$; $p \vee q \equiv q \vee p$
- Associatività: $(p \wedge q) \wedge r \equiv p \wedge (q \wedge r)$; $(p \vee q) \vee r \equiv p \vee (q \vee r)$
- Leggi di De Morgan:
- $\neg(p \wedge q) \equiv \neg p \vee \neg q$
- $\neg(p \vee q) \equiv \neg p \wedge \neg q$
- Distributività:
- $p \wedge (q \vee r) \equiv (p \wedge q) \vee (p \wedge r)$
- $p \vee (q \wedge r) \equiv (p \vee q) \wedge (p \vee r)$
- Implicazione: $p \Rightarrow q \equiv \neg p \vee q$
1.6 Implicazione Materiale ($\Rightarrow$)
L'implicazione $p \Rightarrow q$ (si legge "$p$ implica $q$", o "se $p$ allora $q$") è un connettivo cruciale. $p$ è l'antecedente (o ipotesi/premessa) e $q$ è il conseguente (o tesi/conclusione).
È FALSA unicamente quando l'antecedente $p$ è VERO e il conseguente $q$ è FALSO. In tutti gli altri casi è VERA. Questo include il caso "paradossale" in cui $p$ è FALSO: da una premessa falsa, l'implicazione è sempre vera, indipendentemente dalla conclusione ("Ex falso quodlibet").
| $p$ | $q$ | $p \Rightarrow q$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Equivalenze importanti:
- $p \Rightarrow q \equiv \neg p \vee q$ (Questa è spesso usata come definizione).
- Contronominale: $p \Rightarrow q \equiv \neg q \Rightarrow \neg p$. Utile nelle dimostrazioni: per provare $p \Rightarrow q$, a volte è più facile provare che se non vale $q$, allora non può valere $p$.
1.7 Doppia Implicazione (Bicondizionale, $\Leftrightarrow$)
La doppia implicazione $p \Leftrightarrow q$ (si legge "$p$ se e solo se $q$", a volte abbreviato "p sse q") è VERA se e solo se $p$ e $q$ hanno lo stesso valore di verità (entrambe vere o entrambe false). Indica che $p$ è condizione necessaria e sufficiente per $q$, e viceversa.
| $p$ | $q$ | $p \Leftrightarrow q$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Equivalenza: $p \Leftrightarrow q \equiv (p \Rightarrow q) \wedge (q \Rightarrow p)$.
1.8 OR Esclusivo (XOR, $\oplus$)
L'OR esclusivo $p \oplus q$ è VERO se e solo se $p$ e $q$ hanno valori di verità diversi (uno è vero e l'altro è falso).
| $p$ | $q$ | $p \oplus q$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
Equivalenze:
- $p \oplus q \equiv (p \wedge \neg q) \vee (\neg p \wedge q)$
- $p \oplus q \equiv \neg (p \Leftrightarrow q)$
1.9 Tautologie, Contraddizioni e Formule Soddisfacibili
- Una formula è una **tautologia** se è sempre VERA per qualsiasi assegnazione di valori di verità alle sue proposizioni atomiche.
Esempio: $p \vee \neg p$ (Principio del Terzo Escluso).
Esempio: $(p \wedge (p \Rightarrow q)) \Rightarrow q$ (Modus Ponens). - Una formula è una contraddizione se è sempre FALSA per qualsiasi assegnazione di valori di verità.
Esempio: $p \wedge \neg p$ (Principio di Non Contraddizione). - Una formula è soddisfacibile se esiste almeno un'assegnazione di valori di verità che la rende VERA.
Tutte le tautologie sono soddisfacibili. Le contraddizioni non sono soddisfacibili. Esistono formule soddisfacibili che non sono tautologie (es. $p \wedge q$).
1.10 Esercizi del Capitolo 1
Esercizio 1.1: Identificare Proposizioni
Per ciascuna delle seguenti frasi, indica se è una proposizione logica. Se lo è, e se possibile, indica il suo valore di verità.
- "La luna è fatta di formaggio verde."
- "Che ore sono?"
- "$2 + 3 = 5$."
- "Studia per l'esame!"
- "Questa frase è falsa." (Attenzione: paradosso!)
Esercizio 1.2: Costruzione Tavole di Verità
Costruisci la tavola di verità completa per la formula: $(p \Rightarrow q) \wedge \neg q$. Cosa puoi dire del risultato in relazione a $\neg p$?
Esercizio 1.3: Leggi di De Morgan
Dimostra una delle leggi di De Morgan, ad esempio $\neg (p \vee q) \equiv \neg p \wedge \neg q$, usando una tavola di verità.
Esercizio 1.4: Tautologia del Modus Ponens
Verifica che la formula $(p \wedge (p \Rightarrow q)) \Rightarrow q$ è una tautologia costruendo la sua tavola di verità.
Commenti e Domande sul Capitolo 1
(Questa sezione è un placeholder. In un sito web reale, qui potrebbe esserci un sistema di commenti integrato per discussioni e domande.)