LOGICA MATEMATICA

Claudia Malvenuto e Roberto Maieli^{∗} Canale E-O - a.a 2002-2003 Scheda di esercizi n. 11

17 novembre 2003

Equivalenza logica, Validità, Conseguenza Logica

Notazione : Gli esercizi presentano una notazione leggermente differente a quella del testo di Ben-Ari, dove il simbolo ↔ indica l’equivalenza logica, da noi, invece, indicata con il simbolo “≡”. Riportiamo per comodità la notazione relativa ai connettivi della logica classica, caso proposizionale, da noi usati nelle dispense e negli esercizi :

¬, ∧, ∨, →, ←, ↔ .

Useremo, inoltre, il connettivo ⊕ per indicare la disgiunzione esclusiva A⊕B (si tenga presente che data una assegnazione v per gli atomi di A⊕B, diremo che v(A ⊕ B) = V se e solo se v(A) ≠ v(B)).

Esercizio 1 Dimostrare che A ⊕ B ≡ ¬(A ↔ B).

Esercizio 2 Formalizzare le due seguenti proposizioni:

1. “Se il tempo è bello, allora, se la macchina è pronta, vado al mare”;

2. “Se il tempo è bello e la macchina è pronta, allora vado al mare”.

Dimostrare che 1 ≡ 2.

∗Dipartimento di Informatica, Università di Roma “La Sapienza”, Via Salaria, 113.

E-mail: claudia, maieli@dsi.uniroma1.it.

Esercizio 3 Dimostrare che l’equivalenza logica è una relazione di equivalenza fra proposizioni, ossia è riflessiva, simmetrica e transitiva.

Esercizio 4 Dato l’enunciato F = ((A ↔ ¬B) ∧ (¬A ↔ B)), determinare :

1. un enunciato logicamente equivalente ad F che contenga solo i connettivi ¬, ∧, ∨,

2. l’enunciato equivalente ad F che contenga solo ¬ e ∧,

3. l’enunciato equivalente ad F che contenga solo i connettivi ¬, ∨.

Esercizio 5 Verificare l’equivalenze logiche

A ∧ B ≡ ¬(A → ¬B) A ∨ B ≡ ¬A → B,

e sfruttarle per dimostrare che ¬, → formano una base di connettivi.

Esercizio 6 Dimostrare i seguenti lemmi.

Lemma 1 Sia A una formula proposizionale, ed U un insieme di formule proposizionali {A_{1}, ..., A_{n}}, allora:

1. A è soddisfacibile se e solo se |̸= ¬A;

2. se U è soddisfacibile allora U − {A_{i}}, 1 ≤ i ≤ n, è soddisfacibile;

3. se U è soddisfacibile e ⊧ B allora U ∪ {B} è soddisfacibile;

4. se U è insoddisfacibile e B è una formula proposizionale, allora U ∪{B} è insoddisfacibile;

5. se U è insoddisfacibile ed esiste una A_{i}, con 1 ≤ i ≤ n, tale che ⊧ A_{i}, allora U − {A_{i}} è insoddisfacibile.

6. se U ⊧ A allora U ∪ {B} ⊧ A per qualsiasi B;

7. se U ⊧ A e ⊧ B allora U − {B} ⊧ A;

Lemma 2 Un letterale è un qualsiasi atomo p o la sua negazione ¬p (diremo ch e p e ¬p sono una coppia di letterali complementari. Si mostri che un insieme di letterali L è soddisfacibile se e solo L non contiene alcuna coppia di letterali complementari.

Esercizio 7 Dire quali delle seguenti formule o insiemi di formule proposizionali sono rispettivamente valide (o tautologie), falsificabili o insoddisfacibili. Dire altresì quali tra quelle indicate sono conseguenze logiche.

1. (p ∧ ¬p) → q;

2. {p, ¬q} ⊧ (p ∨ r) ∧ (¬q ∨ ¬r);

3. p ∧ (¬p ∨ q);

4. p → q → (¬p → ¬q);

5. p → q → (¬q → ¬p);

6. (p → q) ↔ (p ↔ (p ∧ q))

7. (p → q) ↔ (q ↔ (p ∨ q))

8. (p ∧ q) ↔ ((p ↔ q) ↔ (p ∨ q))

9. (p ↔ q) ↔ ((p ∨ q) → (p ∧ q)) Esercizio 8 Stabilire se l’enunciato di sinistra è o non è conseguenza logica del corrispettivo enunciato di destra, nella tabella di sotto:

\begin{matrix}¬(A ∧ B) & ¬(A ∨ B) \\ A ∨ B & A ⊕ B \\ A & B → A \\ B → A & A \\ B → (A ∧ B) & A \\ A ∧ B → ¬C & A ∧ ¬B → C \\ ¬C → (A → ¬B) & A → (B → C) \\ A ∨ B → C & B → C \\ ¬A & (A → B) ∧ (A → ¬B) \end{matrix}

Esercizio 9 Quali dei seguenti enunciati sono conseguenza logica delle premesse A ∨ B e A ∨ C?

1. A,

2. B ∨ C,

3. ¬A → B ∧ C, 4. B ∧ C → ¬A,

5. (¬C → A) ∧ (¬B → A). Esercizio 10 Verificare che:

1. {A → B, B → C, ¬C} ⊧ ¬A;

2. {A → ¬B, C → B} ⊧ A → ¬C;

3. {B ∨ C, A ↔ B} ⊧ A ∨ C;

4. {(A → B) → C, A → ¬B} |̸= A → C;

5. una qualsiasi tautologia A (enunciato valido) è conseguenza logica di un qualsiasi enunciato B;

6. un qualsiasi enunciato A è conseguenza logica di {B → C, B ∧ ¬C}.