Esercizi di Logica matematica svolti

Soluzione: Poiché la tavola di verità è

↔ ∨ ↔

P Q R (Q (P R)) R

0 0 0 1

0

0 0 1

0 1 0 1

0 1 1 1

0

1 0 0

1 0 1 1

0

1 1 0

1 1 1 1

la è

FND

∧ ¬Q ∧ ¬R) ∨ ∧ ∧ ¬R)

(¬P (¬P Q

∨ ∧ ∧ ∨ ∧ ¬Q ∧ ∨ ∧ ∧

(¬P Q R) (P R) (P Q R)

e la è

FNC ∨ ∨ ¬R) ∧ ∨ ∨ ∧ ∨ ¬Q ∨

(P Q (¬P Q R) (¬P R).

4. Dimostrare che il seguente insieme di formule è insoddisfacibile:

{A ∨ ¬D, ¬B ∨ ¬C, ¬A ∨ ∨ ¬C, ∨ ¬D}

B D, C

Soluzione: Per assurdo, sia V una valutazione che soddisfa l’insieme di

formule cioè ∨ ¬D)

V (A = 1 (1)

∨ ¬C)

V (¬B = 1 (2)

∨ ∨ ¬C)

V (¬A B = 1 (3)

V (D) = 1 (4)

∨ ¬D)

V (C = 1 (5)

Da (4) e (1) otteniamo V (A) = 1 e da (4) e (5) otteniamo V (C) = 1.

∨ ¬C)

Quindi V (B) = 1 dalla (3). Ma allora V (¬B = 0, contro la (2).

5. Verificare se → ∨ ∧ ∨ → ∧ → |=

(Q (P R)) ((¬Q P ) R) (R P ) Q

Soluzione: Vediamo se c’è una valutazione (o interpretazione) V tale

→ ∨ ∧ ∨ → ∧ →

che V (Q) = 0 e V (Q (P R)) ((¬Q P ) R) (R P ) = 1.

Quest’ultima condizione si traduce nelle tre equazioni

→ ∨

V Q (P R) = 1

∨ →

V (¬Q P ) R = 1

→

V R P = 1.

La prima equazione è sempre soddisfatta, dato che V (Q) = 0. Poiché

∨

V (¬Q P ) = 1, la seconda implica che V (R) = 1. Di conseguenza la

terza implica che V (P ) = 1. Quindi: la valutazione V tale che V (P ) = 1,

V (Q) = 0 e V (R) = 1 testimonia che

→ ∨ ∧ ∨ → ∧ → 6|

(Q (P R)) ((¬Q P ) R) (R P ) = Q.

2

Esercizi svolti di Logica matematica del prof. Vitale su sequenti derivabili, albero di derivazione, come formalizzare una frase, come mettere in forma normale congiuntiva (CNF) e disgiuntiva (DNF) una formula, come dimostrare che una formula è insoddisfacibile, mettere un enunciato in forma prenessa, linguaggio con simbolo di predicato binario.