Esercizio 1 Si assuma di avere i seguenti simboli proposizionali: B, R, O, C. (a) Quale è il numero totale dei possibili mondi ? RISPOSTA: poiché ad ogni simbolo si possono assegnare 2 valori (vero o falso), ci sono 2^4 = 16 possibili mondi. (b) Quanti sono i mondi in cui la seguente sentenza (R AND C) => (¬O AND ¬B) è falsa ? RISPOSTA: Una implicazione è falsa se la premessa è vera e la conclusione è falsa. Esistono 4 mondi in cui (R AND C) è vera. Infatti, fissato il valore vero per R e C, sia O che B possono assumere un qualunque valore di verità. La conclusione negata è ¬(¬O AND ¬B), che è equivalente a (O OR B), ed è vera (e quindi la conclusione è falsa) in 3 dei 4 mondi su citati. Quindi la sentenza è falsa in 3 mondi. Un modo alternativo per rispondere alla domanda era quello di produrre la tabella di verità per i possibili mondi: R C O B (R AND C) => (¬O AND ¬B) --------------------------------------------- f f f f v f f f v v f f v f v f f v v v f v f f v f v f v v f v v f v f v v v v v f f f v v f f v v v f v f v v f v v v v v f f v v v f v f v v v f f v v v v f e contare le righe della tabella con valore falso (f) per la sentenza considerata. (c) Si dica, motivando la risposta, se la sentenza di sopra è equivalente ad un insieme di clausole di Horn. RISPOSTA: Si. E' equivalente all'insieme: {R AND C => ¬O, R AND C => ¬B}. Infatti, se si elimina l'implicazione, si ottengono le clausole ¬R OR ¬C OR ¬O e ¬R OR ¬C OR ¬B, che hanno 0 letterali positivi e quindi sono clausole di Horn. (d) Provare che la sentenza di sopra non è conseguenza logica della sentenza R => ¬B RISPOSTA: Per provare che B non è conseguenza logica di B, basta esibire un mondo dove A è vero e B è falso. In questo caso ciò accade per R, C, ¬B, O. Esercizio 2 (a) Vero o Falso? A <=> B |= A OR B. RISPOSTA: Falso. {A= f, B= f} soddisfa A <=> B ma non A OR B. (b) Vero o Falso? A <=> B |= ¬A OR B. RISPOSTA: Vero. ¬A OR B è equivalente a A => B, che è conseguenza logica di A <=> B. (c) Vero o Falso? (A <=> B) AND (¬A OR B) è soddisfacibile RISPOSTA: Vero. M(A <=> B) non è vuoto e implica (¬A OR B) (d) Vero o Falso? (A <=> B) <=> C possiede lo stesso numero di modelli di (A <=> B) per ogni insieme fissato di simboli proposizionali che includono A, B, C. RISPOSTA: Vero. Entrambi hanno 4 modelli in A, B, C. Esercizio 3 Provare le seguenti asserzioni: (a) la sentenza A è valida se e solo se Vero |= A RISPOSTA: Ricordiamo che A |= B se e solo se M(A) è incluso in M(B), e che una sentenza valida è vera in tutti i mondi. La sentenza Vero è vera in tutti i mondi, così come A se è valida. Quindi Vero |= A. Viceversa, se Vero |= A, poiché deve valere che M(Vero) è incluso in M(A), allora A deve essere valida, altrimenti esisterebbe un mondo in cui Vero è falso. (b) Per ogni sentenza A, Falso |= A RISPOSTA: poiché M(Falso) è l'insieme vuoto, è vero che per ogni sentenza A abbiamo M(Falso) è incluso in M(A). (c) A |= B se e solo se ( A => B ) è valida RISPOSTA: Se A |= B, allora M(A) è incluso in M(B) e quindi per i modelli in cui A è vera, lo è anche B, quindi A => B è vera. Per i modelli restanti, A è falsa e quindi A => B è vera. Quindi A => B è valida. Viceversa, se A => B è valida, tutte le volte che A è vera, lo è anche B e quindi M(A) è incluso in M(B), cioè A |= B. (d) A equivale B se e solo se ( A <=> B ) è valida RISPOSTA: deriva dalla risposta (c) applicata ad entrambe le direzioni. (e) A |= B se e solo se ( A AND ¬B ) è insoddisfacibile RISPOSTA: la domanda si riduce a (c) in quanto A AND ¬B è insoddisfacibile se e solo se A => B è valida. Esercizio 4 Si consideri una base di conoscenza proposizionale con solo 4 simboli proposizionali, A, B, C, D. Quanti modelli possiedono le seguenti sentenze ? (a) ( A AND B ) OR ( B AND C ) RISPOSTA: 6. Si giustifica la risposta contando il numero di righe della tabella di verità con valore vero. Nel fare questo conto ricordarsi sempre di considerare i simboli proposizionali che non compaiono nella sentenza. Ad esempio, in questo caso D non compare e quindi può assumere sia valore vero che falso. In generale, se n sono i simboli che non compaiono nella sentenza, allora il numero di righe della tabella di verità che hanno valore vero deve essere moiltiplicato per 2^n (perchè tali sono i possibili assegnamenti di valori di verità agli n simboli che non compaiono nella sentenza). (b) A OR B RISPOSTA: 12. (c) (A <=> B) AND (B <=> C) RISPOSTA: 4. Esercizio 5 Dire se le seguenti sentenze sono valide, insoddisfacibili, o solo soddisfacibili. Giustificare la risposta usando la tabella di verità o le regole di equivalenza viste a lezione. (a) S => S RISPOSTA: valida, perché sia Vero => Vero che Falso => Falso sono vere. (b) S => F RISPOSTA: soddisfacibile. Non valida perchè con S vero e F falso, la sentenza è falsa. Però con S vero e F vero o con S falso e qualunque valore per F, la sentenza è vera. (c) (S => F) => (¬S => ¬F) RISPOSTA: soddisfacibile. Vera se sia S che F assumono valore vero, ma falsa quando S è falso e F vero. (d) S OR F OR ¬F RISPOSTA: valida, poiché (F OR ¬F) è sempre vera. (e) ((S AND H) => F) <=> ((S => F) OR (H => F)) RISPOSTA: valida. Per dimostrarlo bisogna applicare le regole di equivalenza: ((S AND H) => F) <=> ((S => F) OR (H => F)) ¬(S AND H) OR F <=> (¬S OR F) OR (¬H OR F) (¬S OR ¬H) OR F <=> ¬S OR F OR ¬H OR F ¬S OR ¬H OR F <=> ¬S OR ¬H OR F (f) (S => F) => ((S AND H) => F)) RISPOSTA: valida. Se S vale falso, le due sottoespressioni sono false; se S è vero allora o (S => F) è falsa (e quindi l'intera sentenza è vera) o F è vero, e quindi tutte e due le sottoespressioni sono vere. (g) (S AND F) OR ¬F RISPOSTA: soddisfacibile. Se F è falso, la sentenza è vera, ma se F è vero e S è falso, la sentenza è falsa. (h) S OR F OR (S => F) RISPOSTA: valida. Infatti, eliminando l'implicazione, la sentenza è equivalente a (S OR F OR ¬S), e poiché (S OR ¬S) è vero, la sentenza è sempre vera. Esercizio 6 Spiegare come utilizzando la risoluzione si possa dimostrare che due sentenze A e B sono logicamente equivalenti. RISPOSTA: Ci sono almeno due metodi. Il primo metodo mostra che la sentenza A <=> B è valida, negandola, poi convertendola in forma normale congiuntiva (CNF) e quindi raggiungendo una contraddizione tramite la risoluzione. Il secondo metodo utilizza la risoluzione per provare che A |= B e B|= A.