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

.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 !

Posted by niko_2307 on 28-03-2009 10:36:

Originally posted by Microke
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..

ma lo spezzamento non va usato quando non ci sono altre possibilità?

ovvero:
non si può applicare il letterale puro perchè abbiamo sia p che ¬p; sia q che ¬q; sia r che ¬r e sia s che ¬s

idem per l'asserzione

quindi penso che sia questo il caso il cui usare lo split

questo è quello che ho capito dalle slide.....ditemi se sbaglio

Posted by stenofa on 28-03-2009 11:02:

Prova parziale 31 - Marzo 2008.
es 3.

Determinare il valore di verità della formula seguente, se V è una interpretazione tale che V(p)= F, V(q)=F, V(r)=F

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

l'avete fatto?

__________________
..fortunato io...

Posted by carla86 on 28-03-2009 13:00:

Originally posted by stenofa
Prova parziale 31 - Marzo 2008.
es 3.

Determinare il valore di verità della formula seguente, se V è una interpretazione tale che V(p)= F, V(q)=F, V(r)=F

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

l'avete fatto?

è true!

Posted by stenofa on 28-03-2009 13:47:

okkeyy!

__________________
..fortunato io...

Posted by camno on 28-03-2009 15:54:

Originally posted by darkshadow
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.

..giusti entrambi.

Per quanto riguarda il primo, potresti arrivarci più semplicemente con:
p1=0 , p3=1 , p2=1 , p5=0

Posted by camno on 28-03-2009 17:04:

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

Originally posted by darkshadow
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. [/B]

confermo con Microke e:

1) non vi è nessuno split, e con "q=0 , p=1 , r=1 , s=0/1" viene UNSAT

2) corretto

3) semplicemente con "p3=0 , p2=1 , p1=0 , p4=1" viene "insieme vuoto", quindi SAT

4) corretto

5) corretto

6) corretto

7) con "p1=0 , p4=1" rimane la 'clausola vuota' di -p4, quindi risulta UNSAT

ps: non è per menarmela ma, rispetto agli appelli, posso garantire che queste DPLL (dei compitini) sono veramente semplici!
quindi, consiglio: approfittatene e FATE I COMPITINI!!

Posted by niko_2307 on 28-03-2009 18:36:

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

Originally posted by camno
confermo con Microke e:

1) non vi è nessuno split, e con "q=0 , p=1 , r=1 , s=0/1" viene UNSAT

2) corretto

3) semplicemente con "p3=0 , p2=1 , p1=0 , p4=1" viene "insieme vuoto", quindi SAT

4) corretto

5) corretto

6) corretto

7) con "p1=0 , p4=1" rimane la 'clausola vuota' di -p4, quindi risulta UNSAT

ps: non è per menarmela ma, rispetto agli appelli, posso garantire che queste DPLL (dei compitini) sono veramente semplici!
quindi, consiglio: approfittatene e FATE I COMPITINI!!

mi spiegi perchè non va applicato lo split??

Posted by camno on 28-03-2009 18:51:

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

Originally posted by niko_2307
mi spiegi perchè non va applicato lo split??

..immagino che ti riferisci all'es. 1, giusto?
cmq, prova ad eseguirlo nella sequenza che ho postato :"q=0 , p=1 , r=1 , s=0/1" e vedrai che non dovrai splittare.

l'errore di darkshadow sta nel fatto che doveva partire con "q=0" , visto che il letterale singolo ha la precedenza su tutto!

Posted by niko_2307 on 28-03-2009 18:57:

questa del letterale singolo non la sapevo...non ho trovato nessun riferimento sulle slide. grazie mille

Posted by niko_2307 on 28-03-2009 19:08:

Originally posted by Bennyk
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)

qualcuno riesce a postare lo svolgimento dell'8??

una volta trasformata in fnn non riesco a metterla in fnc

Posted by stenofa on 29-03-2009 14:13:

Originally posted by niko_2307
qualcuno riesce a postare lo svolgimento dell'8??

una volta trasformata in fnn non riesco a metterla in fnc

sai perchè non riesci, almeno credo, perchè è scritta male. l'ultimo connettivo tra q1 e q2 è un and non un or!

__________________
..fortunato io...

Posted by HatTrick86 on 29-03-2009 16:03:

ragazzi chiamatemi cretino ma io ad oggi non so dire se ho un SAT o un UNSAT ...riesco a fare la procedura fino ad arrivare ai vari assegnamenti, tipo p=0, t=0, r=1, s=0 ...ma poi come faccio a dire se è un SAT o UNSAT? So che è 1 scemenza e che è facile, ma io non ho capito in base a cosa lo dico...

diciamo che io mi baso su questo:

se mi rimane (p , -p) assegno p=1 avrò UNSAT
...cioè se mi rimane una clausola a cui non posso assegnare un valore coerente con quelli già assegnati rimango bloccato e sn unsat?

Ma il criterio "vero" qual'è?

__________________
"And there goes the Challenger, being chased by the blue, blue meanies on wheels. The vicious traffic squad cars are after our lone driver, the last American hero, the electric centaur, the, the demi-god, the super driver of the golden west!"

Posted by gab217 on 29-03-2009 18:28:

qualcuno di voi sa quanto dura il primo compitino?

Posted by niko_2307 on 29-03-2009 18:45:

Originally posted by stenofa
sai perchè non riesci, almeno credo, perchè è scritta male. l'ultimo connettivo tra q1 e q2 è un and non un or!

se è scritta male è un errore del prof, perkè è presa dal compitino....cmq non sono riuscito a svolgere nemmeno questa:

(p1 → q1) ^ (p2 → q2) → (p1 ^ p2 → q1 ^ q2)

che in pratica è la stessa cosa con i segni cambiati (ank'essa presa dal compitino)

ogni suggerimento è ben gradito :-D

Posted by gab217 on 30-03-2009 13:21:

Qualcuno di voi sa che tipo di valutazioni fa il professore ? Cioè se c'è un tot di es da fare ecc.

All times are GMT. The time now is 22:56.

Show all 30 posts from this thread on one page