Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Curiosita':

Nel compito il secondo esercizio di DPLL richiedeva di portare in forma normale congiuntiva una certa formula. Ho provato e riprovato, e alla fine mi veniva un pezzo della formula che era :

(p1 /\ p2) /\ (¬q1 \/ ¬q2)

che non riuscivo a risolvere (poi l'ho risolto, male, per non lasciare in bianco. ma ho sicuramente sbagliato).

Siccome uscendo dall'aula m'e' sembrato di sentire qualcun altro che aveva avuto lo stesso problema vi chiedo: e' capitato anche a voi?

EDIT: corretta formula

Last edited by Simeon on 31-03-2008 at 14:49

marcooo

User info:

Registered: Sep 2007
Posts: 30 (0.00 al dì)
Location:
Corso: TLC
Anno: indefinito
Time Online: 20:38:41 [...]
Status: Offline

Post actions:

Mi è capitata la stessa cosa...
c'ho provato in tutti i modi ma alla fine ho lasciato in bianco...
qualcuno sa dirci come si risolveva???

francescoo

User info:

Registered: Feb 2008
Posts: 75 (0.01 al dì)
Location: novara
Corso: informatica
Anno: secondo
Time Online: 20:29:29 [...]
Status: Offline

Post actions:

io non avevo questo esercizio comunque si dovrebbe risolvere cosi:
abbiamo
(p1 /\ p2) \/ (¬q1 \/ ¬q2)

prendo
(p1 /\ p2) come (D1 /\ D2)
(¬q1 \/ ¬q2) come C
e applico la formula (D1 /\ D2) V C = (D1 \/ C) /\ (D2 \/ C)

quindi mi ritrovo con

(p1 V (¬q1 \/ ¬q2)) /\ (p2 \/ (¬q1 \/ ¬q2))
quindi:
(p1 V ¬q1 \/ ¬q2) /\ (p2 \/ ¬q1 \/ ¬q2)
cosi dovrebbe essere corretto
ditemi se avete capito..

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

No no aspetta, mi sono sbagliato. E' giusto quello che hai scritto, ma il pezzo di formula che veniva e' :

(p1 /\ p2) /\ (¬q1 \/ ¬q2)

Io l'ho risolta esattamente come hai detto tu, ma in questo caso e' sbagliato perche tra le due parentesi abbiamo una congiunzione, non una disgiunzione.

Comunque credo d'aver capito, anche se mi suona strano.

Il pezzo di partenza era

¬( (p1 /\ p2) -> (q1 /\ q2) )

risolvendola considerando ¬(a -> b) = a /\ ¬b veniva

(p1 /\ p2) /\ (¬q1 \/ ¬q2) (che e' quella che non so risolvere in nessun modo)

invece considerando soltanto (p1 /\ p2) -> (q1 /\ q2) (ignorando la negazione esterna) mi viene

¬((¬p1 \/ ¬p2) \/ (¬q1 /\ ¬q2))

e questa si potrebbe risolvere come dici tu.

Non mi torna che in un modo funzioni e nell'altro no ma boh, tanto non penso che basti un esercizio per l'insufficienza.

Last edited by Simeon on 31-03-2008 at 14:57

francescoo

User info:

Registered: Feb 2008
Posts: 75 (0.01 al dì)
Location: novara
Corso: informatica
Anno: secondo
Time Online: 20:29:29 [...]
Status: Offline

Post actions:

(p1 /\ p2) /\ (¬q1 \/ ¬q2)
quindi è ancora piu semplice
poiche hai /\ allo stesso livello quindi:

p1 /\ p2 /\ (¬q1 \/ ¬q2)
quindi hai l'insime di clausole C=p1,p2,¬q1 \/ ¬q2
e puoi applicare a queste la dpll
o no?
dimmi se è corretto..

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by francescoo
(p1 /\ p2) /\ (¬q1 \/ ¬q2)
quindi è ancora piu semplice
poiche hai /\ allo stesso livello quindi:

p1 /\ p2 /\ (¬q1 \/ ¬q2)
quindi hai l'insime di clausole C=p1,p2,¬q1 \/ ¬q2
e puoi applicare a queste la dpll
o no?
dimmi se è corretto..

francescoo

User info:

Registered: Feb 2008
Posts: 75 (0.01 al dì)
Location: novara
Corso: informatica
Anno: secondo
Time Online: 20:29:29 [...]
Status: Offline

Post actions:

non mi hai capito..
p1 è una clusola,p2 è un altra clusola,¬q1 \/ ¬q2 è un altra clusola ancora
hai tre clausole in totale
ok?

Simeon

User info:

Registered: Aug 2004
Posts: 984 (0.13 al dì)
Location: Milano
Corso: Informatica
Anno: IT IS OVER!
Time Online: 14 Days, 19:29:42 [...]
Status: Offline

Post actions:

Originally posted by francescoo
non mi hai capito..
p1 è una clusola,p2 è un altra clusola,¬q1 \/ ¬q2 è un altra clusola ancora
hai tre clausole in totale
ok?

Ora ho capito

Cavolo a pensarci bene... pero' non mi torna con quelle parentesi, boh. Magari hai ragione.