Logica Matematica: 11 Esercizi Risolti e Spiegati (da Facile a Difficile)

Esercizio 1 (Facile)

Testo:

Dimostra che se [math]n[/math] è un numero pari, allora [math]n^2[/math] è pari.

Soluzione

Definizione di numero pari:

Un numero intero [math]n[/math] è pari se può essere scritto come [math]n=2k[/math], dove [math]k[/math] è un intero.

Calcolo di [math]n^2[/math]:

[math]n^2=(2k)^2=4k^2=2(2k^2)[/math].

Conclusione:

Poiché [math]n^2[/math] è espresso come [math]2 \times \text{(intero)}[/math], è pari per definizione.

Esercizio 2 (Facile-Medio)

Testo:

Se [math]A=\{1,2,3\}[/math] e [math]B=\{3,4,5\}[/math], qual è l’insieme [math]A \cap B[/math]?

Soluzione

Definizione di intersezione:

[math]A \cap B[/math] è l’insieme degli elementi comuni ad [math]A[/math] e [math]B[/math].

Analisi degli elementi:

[math]3[/math] è presente in entrambi gli insiemi.

Gli altri elementi non sono condivisi.

Risultato:

[math]A \cap B = \{3\}[/math].

Esercizio 3 (Medio)

Testo:

Verifica se l’implicazione [math](p \lor q) \rightarrow \neg p[/math] è una tautologia.

Soluzione

Tavola di verità:

[math]p[/math]	[math]q[/math]	[math]p \lor q[/math]	[math]\neg p[/math]	[math](p \lor q) \rightarrow \neg p[/math]
V	V	V	F	F
V	F	V	F	F
F	V	V	V	V
F	F	F	V	V

Conclusione:

Non è una tautologia perché non sempre vera (es. quando [math]p[/math] è vero e [math]q[/math] è falso).

Esercizio 4 (Medio-Difficile)

Testo:

Dimostra per assurdo che [math]\sqrt{2}[/math] è irrazionale.

Soluzione

Assunzione iniziale:

Supponiamo che [math]\sqrt{2}[/math] sia razionale, quindi [math]\sqrt{2} = \frac{a}{b}[/math] con [math]a,b[/math] coprimi.

Quadrato di entrambi i lati:

[math]2 = \frac{a^2}{b^2} \implies a^2 = 2b^2[/math].

Quindi [math]a^2[/math] è pari, e per l’Esercizio 1, anche [math]a[/math] è pari ([math]a=2k[/math]).

Sostituzione:

[math](2k)^2 = 2b^2 \implies 4k^2 = 2b^2 \implies b^2 = 2k^2[/math].

Allora anche [math]b[/math] è pari, ma ciò contraddice l’ipotesi che [math]a[/math] e [math]b[/math] siano coprimi.

Conclusione:

L’assunzione è falsa, quindi [math]\sqrt{2}[/math] è irrazionale.

Esercizio 5 (Difficile)

Testo:

Risolvi il seguente problema di logica proposizionale: “Se piove, allora Marco prende l’ombrello. Marco non ha preso l’ombrello. Piove?”

Soluzione

Formalizzazione:

[math]P[/math]: “Piove”.

[math]Q[/math]: “Marco prende l’ombrello”.

Le premesse sono: [math]P \rightarrow Q[/math] e [math]\neg Q[/math].

Modus Tollens:

Da [math]P \rightarrow Q[/math] e [math]\neg Q[/math], si deduce [math]\neg P[/math].

Risposta:

No, non piove.

Esercizio 6 (Molto Difficile)

Testo:

Dimostra che ogni numero intero [math]n \ge 2[/math] ha un divisore primo.

Soluzione

Principio del buon ordinamento:

Ogni sottoinsieme non vuoto di [math]N[/math] ha un elemento minimo.

Costruzione dell’insieme:

Sia [math]S[/math] l’insieme dei divisori di [math]n[/math] maggiori di 1. [math]S[/math] è non vuoto perché [math]n \in S[/math].

Minimo di [math]S[/math]:

Sia [math]p[/math] il minimo di [math]S[/math].

Se [math]p[/math] non fosse primo, avrebbe un divisore [math]d[/math] con [math]1 < d < p[/math], ma [math]d[/math] sarebbe in [math]S[/math], contro la minimalità di [math]p[/math].

Conclusione:

[math]p[/math] è un divisore primo di [math]n[/math].

Ogni esercizio illustra un concetto chiave della logica matematica, dalla dimostrazione diretta all’assurdo, dalla logica proposizionale alla teoria dei numeri.

---

👉 Logica: Negazione e quantificatori . Esercizi svolti

Ecco altri 5 problemi di logica proposizionale a difficoltà crescente:

Esercizio 1 (Facile)

Testo:

Se [math]p[/math] è vera e [math]q[/math] è falsa, qual è il valore di verità di [math]\neg p \lor q[/math]?

Soluzione

Valori assegnati:

[math]p = \text{Vero}[/math] (V)

[math]q = \text{Falso}[/math] (F)

Calcolo delle sottoespressioni:

[math]\neg p = \text{Falso}[/math] (negazione di Vero)

[math]\neg p \lor q = \text{Falso} \lor \text{Falso} = \text{Falso}[/math]

Risposta:

L’espressione [math]\neg p \lor q[/math] è falsa.

Teoria:

• Negazione ([math]\neg[/math]): Inverte il valore di verità.
• OR ([math]\lor[/math]): È falso solo se entrambi gli operandi sono falsi.

Esercizio 2 (Facile-Medio)

Testo:

Costruisci la tavola di verità per [math]p \rightarrow (q \land \neg p)[/math].

Soluzione

Colonne necessarie:

[math]p[/math]	[math]q[/math]	[math]\neg p[/math]	[math]q \land \neg p[/math]	[math]p \rightarrow (q \land \neg p)[/math]
V	V	F	F	F
V	F	F	F	F
F	V	V	V	V
F	F	V	F	V

Interpretazione:

L’implicazione è falsa solo quando [math]p[/math] è vero e [math]q \land \neg p[/math] è falso (prime due righe). Negli altri casi, essendo [math]p[/math] falso, l’implicazione è vera.

Teoria:

Implicazione ([math]\rightarrow[/math]): [math]a \rightarrow b[/math] è falsa solo se [math]a[/math] è vero e [math]b[/math] è falso.

Esercizio 3 (Medio)

Testo:

Dimostra che [math](p \rightarrow q) \lor (q \rightarrow p)[/math] è una tautologia.

Soluzione

Tavola di verità:

[math]p[/math]	[math]q[/math]	[math]p \rightarrow q[/math]	[math]q \rightarrow p[/math]	[math](p \rightarrow q) \lor (q \rightarrow p)[/math]
V	V	V	V	V
V	F	F	V	V
F	V	V	F	V
F	F	V	V	V

Conclusione:

L’espressione è sempre vera, quindi è una tautologia.

Teoria:

Una tautologia è un’espressione sempre vera, indipendentemente dai valori di verità delle variabili.

Esercizio 4 (Medio-Difficile)

Testo:

Usa le leggi di De Morgan per semplificare [math]\neg (p \land \neg q)[/math].

Soluzione

Applicazione di De Morgan:

[math]\neg (p \land \neg q) \equiv \neg p \lor \neg (\neg q) \equiv \neg p \lor q[/math].

Risultato:

L’espressione semplificata è [math]\neg p \lor q[/math].

Teoria:

Leggi di De Morgan:

• [math]\neg (a \land b) \equiv \neg a \lor \neg b[/math]
• [math]\neg (a \lor b) \equiv \neg a \land \neg b[/math]

Esercizio 5 (Difficile)

Testo:

Dimostra che [math]\{p \rightarrow q, \neg q\} \vdash \neg p[/math] usando le regole di inferenza.

Soluzione

Premesse:

1. [math]p \rightarrow q[/math] (Se [math]p[/math], allora [math]q[/math])
2. [math]\neg q[/math] ([math]q[/math] è falso)

Applicazione del Modus Tollens:

[math]p \rightarrow q[/math] equivale a [math]\neg q \rightarrow \neg p[/math] (contronominale).

Da [math]\neg q[/math] (premessa 2) e [math]\neg q \rightarrow \neg p[/math] (dalla premessa 1 per contronominale), segue [math]\neg p[/math].

Conclusione:

[math]\neg p[/math] è logicamente derivabile dalle premesse.

Teoria:

Modus Tollens: Se [math]a \rightarrow b[/math] e [math]\neg b[/math], allora [math]\neg a[/math].

Bonus: Esercizio 6 (Molto Difficile)

Testo:

Mostra che [math](p \land q) \rightarrow r[/math] è logicamente equivalente a [math]p \rightarrow (q \rightarrow r)[/math].

Soluzione

Utilizzo dell’implicazione materiale:

Prima espressione: [math](p \land q) \rightarrow r \equiv \neg (p \land q) \lor r[/math].

Seconda espressione: [math]p \rightarrow (q \rightarrow r) \equiv \neg p \lor (q \rightarrow r) \equiv \neg p \lor (\neg q \lor r)[/math].

Applicazione della legge di De Morgan e proprietà associativa:

Sviluppiamo la prima espressione:
[math]\neg (p \land q) \lor r \equiv (\neg p \lor \neg q) \lor r[/math] (Legge di De Morgan).

Sviluppiamo la seconda espressione (già semplificata per implicazione materiale):
[math]\neg p \lor (\neg q \lor r)[/math].

Poiché l’operatore [math]\lor[/math] è associativo, abbiamo:
[math](\neg p \lor \neg q) \lor r \equiv \neg p \lor (\neg q \lor r)[/math].

Conclusione:

Le due forme sono logicamente equivalenti.

Teoria:

• Implicazione materiale: [math]a \rightarrow b \equiv \neg a \lor b[/math].
• Leggi di De Morgan: [math]\neg (a \land b) \equiv \neg a \lor \neg b[/math].
• Associatività di OR: [math](X \lor Y) \lor Z \equiv X \lor (Y \lor Z)[/math].

---

Ogni esercizio copre un aspetto diverso della logica proposizionale, dalle tavole di verità alle regole di inferenza.

(993)

PubblicitàPubblicità