.dsy:it. (http://www.dsy.it/forum/)
- Logica matematica (http://www.dsy.it/forum/forumdisplay.php?forumid=246)
-- esercizi primo compito [31/03/08] (http://www.dsy.it/forum/showthread.php?threadid=34573)

esercizi primo compito [31/03/08]

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.

__________________
by Ð@rk§h@ÐØw

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.

__________________
by Ð@rk§h@ÐØw

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

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

__________________
by Ð@rk§h@ÐØw

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

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

__________________
by Ð@rk§h@ÐØw

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.

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

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

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

Re: esercizi primo compito [31/03/08]

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

--------------------------------------------------------------------------------------

__________________
..fortunato io...

Re: Re: esercizi primo compito [31/03/08]

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!

__________________
..fortunato io...