 | |
Il progetto dsy.it è l'unofficial support site dei corsi di laurea del Dipartimento di Scienze dell'Informazione e del Dipartimento di Informatica e Comunicazione della Statale di Milano. E' un servizio degli studenti per gli studenti, curato in modo no-profit da un gruppo di essi. I nostri servizi comprendono aree di discussione per ogni Corso di Laurea, un'area download per lo scambio file, una raccolta di link e un motore di ricerca, il supporto agli studenti lavoratori, il forum hosting per Professori e studenti, i blog, e molto altro...
In questa sezione è indicizzato in textonly il contenuto del nostro forum |
Esercizi di Preparazione per il 1° compito del 30/03/09
Clicca QUI per vedere il messaggio nel forum |
| darkshadow |
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. |
| Johnny88 |
| Non si puo applicare la regola del letterale puro? e quindi trovare che p2 = 1 e p3 = 1 ?? |
| Johnny88 |
Per caso sei riuscito a fare il 5 del 31 marzo 2008?
io mi sono incartato in un punto... |
| darkshadow |
Nessun altro a niente da dire sugli esercizi?? sono giusti o sbagliati??
@johnny88
non ho ancora fatto quelli dei compitini dell'anno scorso. |
| Microke |
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.. |
| 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.. |
| 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 |
| garfa84 |
| come dice Microke per la seconda parte sono d'accordo!! |
| garfa84 |
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 |
| Microke |
| Secondo me così (¬(p → q) V q) |
| darkshadow |
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. |
| 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) |
| Microke |
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 |
| darkshadow |
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. |
| Microke |
Ok,è chiaro anche se la bucalo aveva detto una cosa opposta !
Gli esercizi nel file allegato mi vengono uguali ! |
| niko_2307 |
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 :?:? |
| 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? |
| carla86 |
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! |
| camno |
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 |
| camno |
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!! ;)
|
| niko_2307 |
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?? |
| camno |
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! |
| niko_2307 |
| questa del letterale singolo non la sapevo...non ho trovato nessun riferimento sulle slide. grazie mille |
| niko_2307 |
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 |
| stenofa |
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! |
| HatTrick86 |
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'è? |
| gab217 |
| qualcuno di voi sa quanto dura il primo compitino? |
| niko_2307 |
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 |
| gab217 |
| Qualcuno di voi sa che tipo di valutazioni fa il professore ? Cioè se c'è un tot di es da fare ecc. |
|
|
|
|
