.dsy:it. - DPLL - Regola spezzamento

Calendar

Members

Faq

Logout

.dsy:it. : Powered by vBulletin version 2.3.1

.dsy:it. > Didattica > Corsi G - M > Logica matematica > DPLL - Regola spezzamento

Last Thread Next Thread

Author

Thread Expand all | Contract all

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:

Edit | Report | IP: Logged

DPLL - Regola spezzamento

Ciao a tutti, volevo sapere se qualcuno poteva chiarirmi la regola dello spezzamento.

Mi ritrovo in un esercizio sul DPLL ad avere una situazione del genere:

p1=0, p4=1 |- {p2 V p3, p2 V ¬p3}

Ora, se applico lo spezzamento su p3 e' tutto ok, se lo applico su p2 invece qualcosa non quadra.

Il mio dubbio era: ma per applicare la regola dello spezzamento su un p bisogna avere sia p che ¬p nell'insieme delle clausole? Non riesco a trovare una conferma sulle slide :\

10-02-2008 22:48

Click here to Send Simeon a Private Message

yeah

.grande:maestro.

User info:

Registered: Nov 2003
Posts: 1644 (0.20 al dì)
Location: Cologno Monzese
Corso: Informatica Magistrale
Anno: II
Time Online: 12 Days, 21:36:41 [...]
Status: Offline

Post actions:

Edit | Report | IP: Logged

Lo spezzamento produce un bivio, da una parte aggiungi p = 1 nell'interpretazione, dall'altra hai p=0. L'insieme delle clausole resta il medesimo. Ecco perché lo spezzamento è una sorta di ultima spiaggia.

Nella situazione che esemplifichi io applicherei il letterale puro (non c'è ¬p2):
p1=0, p4=1, p2=1 |- C

__________________
?

11-02-2008 20:01

Click here to Send yeah a Private Message

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:

Edit | Report | IP: Logged

Originally posted by yeah
Lo spezzamento produce un bivio, da una parte aggiungi p = 1 nell'interpretazione, dall'altra hai p=0. L'insieme delle clausole resta il medesimo. Ecco perché lo spezzamento è una sorta di ultima spiaggia.

Nella situazione che esemplifichi io applicherei il letterale puro (non c'è ¬p2):
p1=0, p4=1, p2=1 |- C

Scusa eh, ma se applichi il letterale puro poi rimane

p1=0, p4=1, p2=1 |- {p2 V p3, p2 V ¬p3}

A sto punto se si usa la sussunzione (su p2) le due clausole spariscono e non si puo' assegnare un valore a p3, o sbaglio?

Inoltre non ho capito bene come funziona la regola del letterale puro, avevo capito che si potesse applicare solo se era presente p e basta come l'asserzione, non con p V C (in questo caso p2 V p3 e p2 V ¬p3)

Ti ringrazio per la risposta comunque.

EDIT:

Comunque nella situazione che ho proposto, se si applica lo spezzamento su p3 si trovano due assegnamenti.

Last edited by Simeon on 11-02-2008 at 20:23

11-02-2008 20:14

yeah

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

A sto punto se si usa la sussunzione (su p2) le due clausole spariscono e non si puo' assegnare un valore a p3, o sbaglio?

Non sbagli e ottieni un'interpretazione parziale che però soddisfa l'insieme di clausole.

L'asserzione ti fa aggiungere p=1 all'interpretazione se hai p da solo in una delle clausole (ma puoi avere ¬p in una clausola composta), mentre con il letterale puro "imponi" p=1 perché comunque devi trovare un'assegnazione che soddisfi l'insieme delle clausole e se non c'è ¬p puoi farlo.

e basta come l'asserzione, non con p V C (in questo caso p2 V p3 e p2 V ¬p3)

Leggendo le dispense non mi è sembrato così.

Questo è ovviamente quello che sembra a me

Comunque nella situazione che ho proposto, se si applica lo spezzamento su p3 si trovano due assegnamenti.

Ok, ma la DPLL mira a verificare se un insieme di clausole è soddisfacibile, quindi basta trovare un assegnamento (ecco uno dei motivi per cui lo spezzamento si applica alla fine, è meglio contenere l'esplosione dei percorsi da esplorare).

__________________
?

11-02-2008 20:33

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:

Edit | Report | IP: Logged

Ok, ma la DPLL mira a verificare se un insieme di clausole è soddisfacibile, quindi basta trovare un assegnamento (ecco uno dei motivi per cui lo spezzamento si applica alla fine, è meglio contenere l'esplosione dei percorsi da esplorare).

Voglio esser sicuro d'aver capito bene.

Riassumendo, trovandomi nella situazione che ho proposto, spezzando su p2 trovo un assegnamento parziale (p1=0, p4=1, p2=1) mentre se spezzo su p3 trovo due assegnamenti veri e propri (p1=0, p4=1, p3=0,p2=1) e (p1=0,p4=1,p3=1,p2=1).

Ed entrambe le soluzioni sono valide?

Mica per sfiducia, e' che non avevo mai trovato un assegnamento parziale in tutti gli esercizi/esempi che ho visto.

11-02-2008 20:49

yeah

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

Mica per sfiducia

Figurati, non sono mica io il docente

La DPLL serve a stabilire la soddisfacibilità di un insieme di clausole, cioè se trovi un assegnamento che rende vero l'insieme, allora detto insieme è soddisfacibile. Quindi anche un assegnamento parziale va bene, infatti (se è corretto), tale assegnamento dovrebbe bastare a rendere vero l'insieme delle clausole.

__________________
?

11-02-2008 21:33

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:

Edit | Report | IP: Logged

Scusa ancora ma stavo pensando: non e' che il fatto di non assegnare valori a p3 (nel caso di spezzamento su p2) si puo' interpretare come validita' sia di p3=0 che p3=1?

Infatti spezzando su p2 si ottiene il parziale (p1=0, p4=1, p2=1), e creando due assegnamenti completi sia con p3=1 che con p3=0 si trovano i due assegnamenti che vengon fuori con lo spezzamento su p3.

Sta cosa mi manda ai matti, potevano fare un esempio sulle slide di sto assegnamento parziale

11-02-2008 21:46

yeah

.grande:maestro.

Post actions:

Edit | Report | IP: Logged

Dovrei riflettere per bene su quanto hai scritto perché non sono sicuro di afferrare appieno o_O

La DPLL è deterministica, le regole si applicano meccanicamente, non c'è da interpretare Puoi usare un po' di occhio nella scelta della regola da applicare, ma spesso la libertà è poca se tieni lo spezzamento come ultima spiaggia.

Un assegnamento parziale è semplicemente un assegnamento che, pur non attribuendo un valore ad ogni lettera proposizionale, soddisfa l'insieme di clausole (di conseguenza qualsiasi sia il valore assegnato alle restanti lettere proposizionali la soddisfacibilità resta inalterata).

__________________
?

11-02-2008 22:08

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:

Edit | Report | IP: Logged

Non sono convinto al 100% (ma solo perche, ripeto, non trovo esempi/esercizi con questo tipo di situazione) ma almeno non brancolo piu' nel buio.

Cioe', la cosa che non mi convince del tutto e' che se spezzo su uno ho un risultato, se spezzo sull'altro ne ho uno diverso. Fosse stato come dicevo io (=non applichi spezzamento se non ci son p e p negato) sarei stato piu' contento. Certo uno puo' provare tutti gli spezzamenti, ma una cosa cosi' durante l'esame mi incasinerebbe un po' :asd:

Comunque grazie per le informazioni.

Last edited by Simeon on 12-02-2008 at 00:00

11-02-2008 23:53

All times are GMT. The time now is 13:11.

Last Thread Next Thread

Show Printable Version |

Email this Page |

Subscribe to this Thread |

Add to Bookmarks

Forum Jump:

Rate This Thread:

Forum Rules:

You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

HTML code is OFF
vB code is ON
Smilies are ON
[IMG] code is ON

Pagina generata in 0.071 seconds (65.67% PHP - 34.33% MySQL) con 25 query.