.dsy:it. - Esercizi di Preparazione per il 1° compito del 30/03/09

Pages (2): [1] 2 »
Show 150 posts per page

.dsy:it. (http://www.dsy.it/forum/)
- Logica matematica (http://www.dsy.it/forum/forumdisplay.php?forumid=246)
-- Esercizi di Preparazione per il 1° compito del 30/03/09 (http://www.dsy.it/forum/showthread.php?threadid=38068)

Posted by darkshadow on 22-03-2009 20:19:

Esercizi di Preparazione per il 1° compito del 30/03/09

Ciao,
in vista del compito di logica del 30 che ne dite se mettiamo le soluzioni degli esercizi dei vecchi temi d'esame/compitini? Parlo della pate che riguarda l'algoritmo DPLL. Magari controllando anche che questi siano efettivamente giusti.

Ecco quelle che ho fatto io:

1) studiare mediante la procedura DPLL la soddisfacibilità del seguente insieme di clausole:

code:
    C = {p V q, ¬q, r V ¬p, ¬r V s, ¬p V ¬s}

    Ø ├ C
Spezzamento su p

Ramo p = 1 ├ C

p = 1 ├ {¬q, r, ¬r V s, ¬s}

p = 1, q = 0 ├ {r, ¬r V s, ¬s}

p = 1, q = 0, r = 1 ├ {s, ¬s}

p = 1, q = 0, r = 1, s = 1 ├ {□}

            UNSAT


Ramo p = 0 ├ C

p = 0 ├ {q, ¬q,¬r V s}

p = 0, q = 1 ├ {¬r V s}

p = 0, q = 1, r = 0 ├ {□}

            UNSAT

2) studiare mediante la procedura DPLL la soddisfacibilità del seguente insieme di clausole:

code:
    C = {¬p V q, ¬s V ¬t, ¬q, p V ¬r, r V s}

    Ø ├ C

q = 0 ├ {¬p, ¬s V ¬t,p V ¬r, r V s}

q = 0, p = 0 ├ {¬s V ¬t,¬r, r V s}

q = 0, p = 0, r = 0 ├ {¬s V ¬t, s}

q = 0, p = 0, r = 0, s = 1 ├ {¬t}

q = 0, p = 0, r = 0, s = 1, t = 0 ├ Ø

       SAT

3) Applicando l'algoritmo DPLL, determinare se il seguente insieme di clausole è o meno soddisfacibile:

code:
    C = {¬p1 V ¬p2, p2 V p3, ¬p1 V ¬p3 V p4, p2 V ¬p3 V ¬p4, p1 V p4}

    Ø ├ C

Spezzamento su p1

Ramo p1 = 1 ├ C

p1 = 1 ├ {¬p2, p2 V p3, ¬p3 V p4, p2 V ¬p3 V ¬p4}

p1 = 1, p2 = 0 ├ {p3, ¬p3 V p4, ¬p3 V ¬p4}

p1 = 1, p2 = 0, p3 = 1 ├ {p4, ¬p4}

p1 = 1, p2 = 0, p3 = 1, p4 = 1 ├ {□}

            UNSAT


Ramo p1 = 0 ├ C

p1 = 0  ├ {p2 V p3, p2 V ¬p3 V ¬p4, p4}

p1 = 0, p4 = 1  ├ {p2 V p3,p2 V ¬p3}

p1 = 0, p4 = 1, p2 = 1 ├ {□}

            UNSAT

4) dimostrare che la seguente formula è una tautologia negandola, trasformandola in FNC e applicando l'algoritmo DPLL

(((p → q) → q) Λ ¬q) → ((r → ¬p) → ¬r)

code:
¬((((p → q) → q) Λ ¬q) → ((r → ¬p) → ¬r))

(((p → q) → q) Λ ¬q) Λ ¬(((r → ¬p) → ¬r))

((¬(p → q) V q) Λ ¬q) Λ ¬((¬(r → ¬p) V ¬r))

(((p Λ ¬q) V q) Λ ¬q) Λ ¬((r Λ p) V ¬r)

(p V q) Λ (¬q V q) Λ ¬q Λ ¬(r Λ p) Λ r

(¬q V q) = 1, si semplifica.

(p V q) Λ ¬q Λ (¬r V ¬p) Λ r


    C = {p V q, ¬q, ¬r V ¬p, r}

    Ø ├ C

q = 0 ├ {p, ¬r V ¬p, r}

q = 0, p = 1 ├ {¬r, r}

q = 0, p = 1, r = 1 ├ {□}

            UNSAT  ----->  allora è una TAUTOLOGIA

5) Dimostrare che l'insieme formato dalle seguenti 5 clausole è insoddisfacibile applicando l'algoritmo DPLL

code:
    C = {p V q V r, p V ¬q, q V ¬r, r V ¬p, ¬p V ¬q V ¬r}

    Ø ├ C

Spezzamento su p

Ramo p = 1 ├ C

p = 1 ├ {q V ¬r, r, ¬q V ¬r}

p = 1, r = 1 ├ {q, ¬q}

p = 1, r = 1, q = 1 ├ {□}

            UNSAT

Ramo p = 0 ├ C

p = 0 ├ {q V r, ¬q, q V ¬r}

p = 0, q = 0 ├ {r, ¬r}

p = 0, q = 0, r = 1 ├ {□}

            UNSAT

6) Dimostrare che l'insieme formato dalle seguenti 5 clausole è insoddisfacibile applicando l'algoritmo DPLL

code:
    C = {p V ¬r, r V ¬q, q V p V r, q V ¬p, ¬p V ¬q V ¬r}

    Ø ├ C

Spezzamento su p

Ramo p = 1 ├ C

p = 1 ├ {r V ¬q, q, ¬q V ¬r}

p = 1, q = 1 ├ {r,¬r}

p = 1, q = 1, r = 1 ├ {□}

            UNSAT

Ramo p = 0 ├ C

p = 0 ├ {¬r, r V ¬q, q V r}

p = 0, r = 0 ├ {¬q, q}

p = 0, r = 0, q = 0 ├ {□}

            UNSAT

7) Applicando l'algoritmo DPLL, determinare se il seguente insieme di clausole è o meno soddisfacibile:

code:
    C = {p1 V ¬p4, ¬p1 V ¬p2, p2 V p3, ¬p1 V ¬p3 V p4, p2 V ¬p3 V ¬p4, p1 V p4}

    Ø ├ C

Spezzamento su p1

Ramo p1 = 1 ├ C

p1 = 1 ├ {¬p2, p2 V p3, ¬p3 V p4, p2 V ¬p3 V ¬p4}

p1 = 1, p2 = 0 ├ {p3, ¬p3 V p4, ¬p3 V ¬p4}

p1 = 1, p2 = 0, p3 = 1 ├ {p4, ¬p4}

p1 = 1, p2 = 0, p3 = 1, p4 = 1 ├ {□}

            UNSAT

Ramo p1 = 0 ├ C

p1 = 0 ├ {¬p4, p2 V p3, p2 V ¬p3 V ¬p4, p4}

p1 = 0, p4 = 0 ├ {p2 V p3}

QUI COSA DEVO APPLICARE???

Questi sono quelli che ho fatto per ora. Se qualcuno vuole controllare che siano giusti e se ci sono errori posti la soluzione giusta. Inoltre mi sapete dire cosa devo fare nella 7) che a un certo punto non so cosa applicare.

Ciao e grazie a chi vorrà partecipare!

Ds.

__________________
by Ð@rk§h@ÐØw

Posted by Johnny88 on 23-03-2009 14:47:

Non si puo applicare la regola del letterale puro? e quindi trovare che p2 = 1 e p3 = 1 ??

Posted by Johnny88 on 23-03-2009 14:48:

Per caso sei riuscito a fare il 5 del 31 marzo 2008?
io mi sono incartato in un punto...

Posted by darkshadow on 24-03-2009 12:33:

Nessun altro a niente da dire sugli esercizi?? sono giusti o sbagliati??

@johnny88
non ho ancora fatto quelli dei compitini dell'anno scorso.

__________________
by Ð@rk§h@ÐØw

Posted by Microke on 25-03-2009 11:33:

Originally posted by darkshadow

Nessun altro a niente da dire sugli esercizi?? sono giusti o sbagliati??

@johnny88
non ho ancora fatto quelli dei compitini dell'anno scorso.

Provo a farli oggi pomeriggio!
Appena fai i compitini posta i risultati,visto che ho alcuni dubbi sugli esercizi del tipo 6..

Posted by Microke on 25-03-2009 11:49:

Nel primo esercizio io non ho usato nessun spezzamento, e con q=s=0 e p=r=1 mi è venuto unsat

Il secondo esercizio mi viene come te

Il terzo mi viene sat :

p1 = 0, p4 = 1 ├ {p2 V p3,p2 V ¬p3}

p1 = 0, p4 = 1, p2 = 1 ├ {□}

Se metti p2=1 va via tutto,non resta nessuna clausola vuota..

Posted by Microke on 25-03-2009 13:09:

Il quattro mi viene diverso: nella seconda parte devi applicare prima la negazione dell'implicazione perchè hai un Not fuori dalla tonda

Il cinque e il sei mi vengono uguali
Nel sette , p4 va via ma ti resta la clausola vuota quindi è unsat

Posted by garfa84 on 25-03-2009 16:21:

come dice Microke per la seconda parte sono d'accordo!!

Posted by garfa84 on 25-03-2009 16:22:

ho il dubbio qui : (p → q) → q) se fare
così (¬(p → q) V q)
o così (¬p V q) → q
ma alla fine il risultato non cambia...

4) dimostrare che la seguente formula è una tautologia negandola, trasformandola in FNC e applicando l'algoritmo DPLL

(((p → q) → q) Λ ¬q) → ((r → ¬p) → ¬r)

code:
¬((((p → q) → q) Λ ¬q) → ((r → ¬p) → ¬r))

(((p → q) → q) Λ ¬q) Λ ¬(((r → ¬p) → ¬r))

((¬(p → q) V q) Λ ¬q) Λ ¬(((r → ¬p) Λ r))

(((p Λ ¬q) V q) Λ ¬q) Λ ((¬r V ¬p) Λ r)

(p V q) Λ (¬q V q) Λ ¬q Λ (¬r V ¬p) Λ r

(¬q V q) = 1, si semplifica.

(p V q) Λ ¬q Λ (¬r V ¬p) Λ r

C = {p V q, ¬q, ¬r V ¬p, r}

Ø ├ C

q = 0 ├ {p, ¬r V ¬p, r}

q = 0, p = 1 ├ {¬r, r}

q = 0, p = 1, r = 1 ├ {□}

UNSAT -----> allora è una TAUTOLOGIA

Posted by Microke on 25-03-2009 20:15:

Secondo me così (¬(p → q) V q)

Posted by darkshadow on 25-03-2009 22:08:

Nel primo esercizio io non ho usato nessun spezzamento, e con q=s=0 e p=r=1 mi è venuto unsat

Il secondo esercizio mi viene come te

Il terzo mi viene sat :

p1 = 0, p4 = 1 ├ {p2 V p3,p2 V ¬p3}

p1 = 0, p4 = 1, p2 = 1 ├ {□}

Se metti p2=1 va via tutto,non resta nessuna clausola vuota..

Hai ragione nel primo è inutile fare lo split visto che ho il lettarale ¬q.

e hai ragione pure nel terzo che viene SAT con p1 = 0, p4 = 1, p2 = 1, p3 = X (cioè il suo valore è indiferente).

Originally posted by Microke
Il quattro mi viene diverso: nella seconda parte devi applicare prima la negazione dell'implicazione perchè hai un Not fuori dalla tonda

Il cinque e il sei mi vengono uguali
Nel sette , p4 va via ma ti resta la clausola vuota quindi è unsat

Guarda ti dirò.... l'ordine in cui applichi una regola non cambia il risultato solo che a volte se applichi per prima una certa regola ci arrivi al risultato in meno passaggi pero il risultato non cambia; lo dice pure il prof nelle dispense.
Cmq nella seconda riga:
(((p → q) → q) Λ ¬q) Λ ¬(((r → ¬p) → ¬r))
c'è una parentesi in + che non serve però il risultato è giusto l'ho ricontrollato è ho pure applicato le regole in ordine diverso.

PS: metto in allegato l'esercizio 5 e 6 di una delle versioni del primo compitino del 2008, guardate il testo per capire di quale si tratta; cmq entrambi gli esercizi sono della stessa versione.
Se non si capisce qulacosa fatemi sapere.

DS.

__________________
by Ð@rk§h@ÐØw

Posted by Bennyk on 26-03-2009 11:25:

Qualcuno ha fatto quest'esercizio?

8) Applicando la procedua DPLL, determinare se la seguente formula è o meno una tautologia.

(p1 → q1) V (p2 → q2) → (p1 v p2 → q1 V q2)

Posted by Microke on 26-03-2009 13:34:

bennyk : a me viene Sat con q1=0 q2=0 p1=1 p2=0

Mentre questo quiz :

1. In base alle convenzioni adottate sulle parentesi, quali delle seguenti espressioni sono formule?

(q -> r) and ¬p and ¬(¬q <--> r)

Perchè non è una formula ?
Perchè non esiste la negazione della doppia implicazione ?
Oppure per il problema delle due and che rendono la formula ambigua ?
A proposito di questo dubbio,ghilardi ha detto che :
A and B and C è uguale a :

(A and B) and C ed a (A and C) and B

mentre la Bucalo ha detto che A and B and C è uguale a :

A and (B and C )

Che dite ? Non riesco a capire :S

Posted by darkshadow on 26-03-2009 13:43:

allora in base alla convensione sappiamo che not lega + strettamente di OR oppure AND che alloro volta legano streetamente + di -->

se hai A and B and C la cosa è ambigua perchè hai 2 possibilità:

(A and B) and C oppure A and (B and C)
quindi nel caso di + and si devono per forza mettere le parentesi.

quindi: (q -> r) and ¬p and ¬(¬q <--> r) non è una formula perchè ambigua

se invece fosse stata:
((q -> r) and ¬p) and ¬(¬q <--> r)

oppure

(q -> r) and (¬p and ¬(¬q <--> r))

allora queste sarebbero state delle fomule.

CMQ avete guardato il file in allegato con i 2 esercizi di una delle versioni del compitino 2008??

DS.

__________________
by Ð@rk§h@ÐØw

Posted by Microke on 26-03-2009 14:30:

Ok,è chiaro anche se la bucalo aveva detto una cosa opposta !
Gli esercizi nel file allegato mi vengono uguali !

All times are GMT. The time now is 09:47.

Pages (2): [1] 2 »
Show all 30 posts from this thread on one page