 | |
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 primo compito [31/03/08]
Clicca QUI per vedere il messaggio nel forum |
| darkshadow |
Ciao.
Qualcuno puo' controllare se questi esercizi che erano nel primo compitino di logica sono giusti??
esercizio 5:
controllare se l'insieme delle clausole è soddisfacibile applicando l'algoritmo DPLL.
C = {p3 V p1, ¬p3 V ¬p4, ¬p1 V p5 V p2, p3 V p2 V ¬p4, p3 V ¬p2 V ¬p5, ¬p3 V p4}
spezzo su p3:
p3 = 1 |--- {¬p4, ¬p1 V p5 V p2, p4}
asserzione su p4
p3 = 1, p4 = 1 |--- {¬p1 V p5 V p2}
asserzione su p1
p3 = 1, p4 = 1, p1 = 0 |--- {0}
l'insieme delle clausole è soddisfacibile
--------------------------------------------------------------------------------------
esercizio 6:
controllare se è una tautologia.
(p1 ----> q1) V (p2 ----> q2) ----> (p1 V p2 ----> q1 V q2)
¬((p1 ----> q1) V (p2 ----> q2) ----> (p1 V p2 ----> q1 V q2))
(p1 ----> q1) V (p2 ----> q2) Λ ¬(p1 V p2 ----> q1 V q2)
(¬p1 V q1 V ¬p2 V q2) Λ (p1 V p2) Λ ¬(q1 V q2)
(¬p1 V q1 V ¬p2 V q2) Λ (p1 V p2) Λ ¬q1 Λ ¬q2)
C = {¬p1 V q1 V ¬p2 V q2, p1 V p2, ¬q1, ¬q2}
asserzione su q1
q1 = 0 |--- {¬p1 V ¬p2 V q2, p1 V p2, ¬q2}
asserzione su q2
q1 = 0, q2 = 0 |--- {¬p1 V ¬p2, p1 V p2}
spezzamento su p1
q1 = 0, q2 = 0, p1 = 0 |--- {p2}
q1 = 0, q2 = 0, p1 = 0, p2 = 1 |--- {0}
l'insieme delle clausole è soddisfacibile quindi non è una tautologia.
--------------------------------------------------------------------------------------
esercizio 4:
trasformare la seguente formula in FNN:
¬(p ---> q) V ¬(¬q V r)
p Λ ¬q V (¬¬q Λ ¬r)
p Λ ¬q V (q Λ ¬r)
e dopo mi sa che ho sbagliato.
se potete postate la soluzione.
--------------------------------------------------------------------------------------
esercizio 3:
per quali valori è soddisfacibile.
¬(p Λ ¬q ---> r) V (q Λ ¬(r V p))
(p Λ ¬q Λ ¬r) V (q Λ ¬r Λ ¬p)
A = (p Λ ¬q Λ ¬r).
B = (q Λ ¬r Λ ¬p).
Y = A V B
faccio la tavola di verità
p q r | ¬p|¬q |¬r| A | B | Y |
0 0 0 | 1 | 1 | 1 | 0 | 0 | 0 |
0 0 1 | 1 | 1 | 0 | 0 | 0 | 0 |
0 1 0 | 1 | 0 | 1 | 0 | 1 | 1 |
0 1 1 | 1 | 0 | 0 | 0 | 0 | 0 |
1 0 0 | 0 | 1 | 1 | 1 | 0 | 1 |
1 0 1 | 0 | 1 | 0 | 0 | 0 | 0 |
1 1 0 | 0 | 0 | 1 | 0 | 0 | 0 |
1 1 1 | 0 | 0 | 0 | 0 | 0 | 0 |
soluzione:
p = 0, q = 1, r = 0.
p = 1, q = 0, r = 0.
--------------------------------------------------------------------------------------
Grazie anticipatamente. |
| Simeon |
Scusami se ti rispondo solo in parte, ma col voto che ho preso non mi sento di fare chissa' quali correzioni.
code:
(p1 ----> q1) V (p2 ----> q2) Λ ¬(p1 V p2 ----> q1 V q2)
(¬p1 V q1 V ¬p2 V q2) Λ (p1 V p2) Λ ¬(q1 V q2)
(¬p1 V q1 V ¬p2 V q2) Λ (p1 V p2) Λ ¬q1 Λ ¬q2)
C = {¬p1 V q1 V ¬p2 V q2, p1 V p2, ¬q1, ¬q2}
Forse qui hai risolto un mio grosso dubbio, pero' devo capire se e' giusto quel che hai fatto.
Tu hai preso "(p1 ----> q1) V (p2 ----> q2)", l'hai risolto e poi hai unito le due soluzioni (¬p1 V q1) e (¬p2 V q2) in un'unica clausola (¬p1 V q1 V ¬p2 V q2). Ma si puo' fare?
Lo stesso dicasi per ¬(q1 V q2) che diventa (¬q1 /\ ¬q2). Si possono contare due clausole q1 e q2 togliendo le parentesi (come qualcuno mi diceva in un altro thread)?
Se queste cose son giuste il resto dell'esercizio penso sia corretto.
Per l'esercizio 4 io sono arrivato a (p /\ ¬q) \/ (q /\ ¬r) e mi son fermato, mi sembra giusto cosi'...
La DPLL e l'altro esercizio non li ho controllati che devo scappare, ma tanto non sarei manco sicuro di quel che dico. |
| darkshadow |
Originally posted by Simeon
Scusami se ti rispondo solo in parte, ma col voto che ho preso non mi sento di fare chissa' quali correzioni.
code:
(p1 ----> q1) V (p2 ----> q2) Λ ¬(p1 V p2 ----> q1 V q2)
(¬p1 V q1 V ¬p2 V q2) Λ (p1 V p2) Λ ¬(q1 V q2)
(¬p1 V q1 V ¬p2 V q2) Λ (p1 V p2) Λ ¬q1 Λ ¬q2)
C = {¬p1 V q1 V ¬p2 V q2, p1 V p2, ¬q1, ¬q2}
Forse qui hai risolto un mio grosso dubbio, pero' devo capire se e' giusto quel che hai fatto.
Tu hai preso "(p1 ----> q1) V (p2 ----> q2)", l'hai risolto e poi hai unito le due soluzioni (¬p1 V q1) e (¬p2 V q2) in un'unica clausola (¬p1 V q1 V ¬p2 V q2). Ma si puo' fare?
Lo stesso dicasi per ¬(q1 V q2) che diventa (¬q1 /\ ¬q2). Si possono contare due clausole q1 e q2 togliendo le parentesi (come qualcuno mi diceva in un altro thread)?
Se queste cose son giuste il resto dell'esercizio penso sia corretto.
Penso di si visto che sono tutti degli or.
Per l'esercizio 4 io sono arrivato a (p /\ ¬q) \/ (q /\ ¬r) e mi son fermato, mi sembra giusto cosi'...
Già. mi hanno detto che cosi è gisuto, pero io ho fatto altre cose poi.
La DPLL e l'altro esercizio non li ho controllati che devo scappare, ma tanto non sarei manco sicuro di quel che dico.
Non importa grazie lo stesso. |
| Vincy07 |
ciao premetto che non ho passato il compitino (anche se ero sicuro di averlo fatto più che bene).
in ogni caso se ti interessa, l'esercizio 5 che hai fatto penso che sia sbagliato poichè mancano i valori di p5 e p2 quindi in pratica non realizzeresti una tabella di verità senza questi 2 valori.
dovrebbe essere così:
p5=0 {p3vp1; ¬p3v¬p4; ¬p1vp2; p3vp2v¬p4; ¬p3vp4}
p5=0, p2=0 {p3vp1; ¬p3v¬p4; ¬p1; p3v¬p4; ¬p3vp4}
p5=0, p2=0, p1=1 {¬p3v¬p4; p3v¬p4; ¬p3vp4}
p5=0, p2=0, p1=1, p4=0 {¬p3}
p5=0, p2=0, p1=1, p4=0, p3=0
cmq per esseri sicuri che sia giusto, basta provare con la tabella di verità: sarà un pò lunga ma alla fine è la dimostrazione che ciò che ti viene dall'algoritmo DPLL è corretto. in pratica saranno 32 righe 2alla5 (p1-->p5)
spero di esser stato utile
ciauz |
| darkshadow |
Originally posted by Vincy07
ciao premetto che non ho passato il compitino (anche se ero sicuro di averlo fatto più che bene).
in ogni caso se ti interessa, l'esercizio 5 che hai fatto penso che sia sbagliato poichè mancano i valori di p5 e p2 quindi in pratica non realizzeresti una tabella di verità senza questi 2 valori.
dovrebbe essere così:
p5=0 {p3vp1; ¬p3v¬p4; ¬p1vp2; p3vp2v¬p4; ¬p3vp4}
p5=0, p2=0 {p3vp1; ¬p3v¬p4; ¬p1; p3v¬p4; ¬p3vp4}
p5=0, p2=0, p1=1 {¬p3v¬p4; p3v¬p4; ¬p3vp4}
p5=0, p2=0, p1=1, p4=0 {¬p3}
p5=0, p2=0, p1=1, p4=0, p3=0
cmq per esseri sicuri che sia giusto, basta provare con la tabella di verità: sarà un pò lunga ma alla fine è la dimostrazione che ciò che ti viene dall'algoritmo DPLL è corretto. in pratica saranno 32 righe 2alla5 (p1-->p5)
spero di esser stato utile
ciauz
Da quello che è stato detto negli altri 3d dove sono stati fatti esercizi dpll, mi hanno detto che il fatto che alcuni letterali non siano presenti nella soluzione non significa che sia sbagliato ma che abbiamo ottenuto un risultato parziale, cioè i valori di quei letterali che non appargono nella soluzione sono indifferenti.
qualcuno puo' riconfermare sta cosa?? |
| Larios |
io ho fatto il 5 e il 6 esattmente come te, sicuro di aver passato anche se con un voto basso...., ma sorpresa non ho passato :)
non so davvero cosa possa essere sbagliato... |
| darkshadow |
Originally posted by Larios
io ho fatto il 5 e il 6 esattmente come te, sicuro di aver passato anche se con un voto basso...., ma sorpresa non ho passato :)
non so davvero cosa possa essere sbagliato...
beh... nemmeno io l'ho passato.
Non so dove abbiamo sbagliato nei 2 esercizi se dici che lo hai fatto come me. Adesso per saperlo dobbiamo aspettare venerdi (che palle :evil: ) se sapevo prima dei risultati ci andavo proprio ieri. |
| Simeon |
| A me sta cosa di non avere le soluzioni online mi manda ai matti, non ho spesso la possibilita' di muovermi di mattina e quindi non sapro' mai cos'ho sbagliato, almeno sta settimana. |
| sawind |
già..a chi lo dici..anche a me sta facendo diventare matta..tra l'altro ho mandato una mail alla bucalo per chiederle se avevo sbagliato l'esercizio e mi ha detto di aver fatto tutto in maniera corretta..
cmq a parte questo e rispondendo agli esercizi..io il primo l'avrei fatto in maniera differente..
dato che arrivi in un punto in cui hai questa situazione
p3 = 1 |--- {¬p4, ¬p1 V p5 V p2, p4}
non sono sicura che tu possa applicare l'assert su p4..hai sia il p4 che il ¬p4..
io sarei tornata indietro e avrei fatto altri passi..in modo di essere sicura delle cose..ti scrivo come avrei fatto io..
cominciando su p1
split
p1=1
{¬p3V¬p4,p5Vp2,p3Vp2V¬p4,p3V¬p2V¬p5,¬p3Vp4}
Split nuovamente su p2
p1=1,p2=1
{¬p3V¬p4,p3V¬p5,¬p3Vp4}
Split su p3
P1=1,p2=1,p3=0
{¬p5}
letterale puro
soddisfacibile con p1=1,p2=1,p3=0,p5=0
e' vero che ho applicato tutti split e sono quelli che il prof ha detto di evitare..ma andando avanti in questa maniera non potevo fare altro..e almeno..si è sicuri della riuscita..
per quanto riguarda l'esercizio 4 ti scrivo di seguito come risolverlo..
¬(p ---> q) V ¬(¬q V r)
(p Λ ¬q) V (q Λ ¬r)
(p V (qΛ¬r2) Λ (¬q V (q Λ ¬r))
(p V q) Λ (p V ¬r) Λ (¬q Vq)Λ(¬q V ¬r)
ciao ragazzi |
| valeriam. |
| sinceramente non sono stata a leggere tutto (lo confesso ho letto solo l'ultimo post) però il professore aveva detto che applicare lo split quando non serve lo conta come errore e dato che potevi benissimo fare a meno di applicarlo così tante volte penso che ti abbia dato come sbagliato l'esercizio |
| sawind |
| Beh..si applica lo split perchè con la scelta che ho deciso di seguire..è l'unica possibile scelta per continuare l'esercizio..premetto che io non avevo questo esercizio nel compito..si poteva fare anche in altro modo..ma ovviamente sarei dovuta tornare indietro e verificare tutte le possibilità..l'unico metodo che potevo scegliere mano a mano che svolgevo l'esercizio era lo split..comunque domani si vede..da come ho capito parecchie persone non riescono a capire il motivo per cui il compito non sia andato bene.. |
| stenofa |
Originally posted by darkshadow
Ciao.
Qualcuno puo' controllare se questi esercizi che erano nel primo compitino di logica sono giusti??
esercizio 5:
controllare se l'insieme delle clausole è soddisfacibile applicando l'algoritmo DPLL.
C = {p3 V p1, ¬p3 V ¬p4, ¬p1 V p5 V p2, p3 V p2 V ¬p4, p3 V ¬p2 V ¬p5, ¬p3 V p4}
spezzo su p3:
p3 = 1 |--- {¬p4, ¬p1 V p5 V p2, p4}
asserzione su p4
p3 = 1, p4 = 1 |--- {¬p1 V p5 V p2}
asserzione su p1
p3 = 1, p4 = 1, p1 = 0 |--- {0}
l'insieme delle clausole è soddisfacibile
--------------------------------------------------------------------------------------
secondo me l'asserzione, come già detto non è corretta. penso bisognerebbe spezzare su p4 ma il ramo p3=1 non ci porta alla soddisfacibilità. nel ramo p3=0 io ho fatto così:
p3=0, p1=1 ├ {p5 V p2, p2 V ¬p4, ¬p2 V ¬p5}
p3=0, p1=1, p4=0 ├ {p5 V p2, ¬p2 V ¬p5}
spezzo su p5 o p2 indifferentemente e soddisfo Co in due diversi assegnamenti.
Non so se è corretta ma io la risoverei così.
ciao! |
| stenofa |
Originally posted by stenofa
secondo me l'asserzione, come già detto non è corretta. penso bisognerebbe spezzare su p4 ma il ramo p3=1 non ci porta alla soddisfacibilità. nel ramo p3=0 io ho fatto così:
p3=0, p1=1 ├ {p5 V p2, p2 V ¬p4, ¬p2 V ¬p5}
p3=0, p1=1, p4=0 ├ {p5 V p2, ¬p2 V ¬p5}
spezzo su p5 o p2 indifferentemente e soddisfo Co in due diversi assegnamenti.
Non so se è corretta ma io la risoverei così.
ciao!
no è sbagliata! è giusta come l'hai scritta all'inizio ma alla fine è clausola vuota! |
|
|
|
|
