 | |
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 |
DPLL - Regola spezzamento
Clicca QUI per vedere il messaggio nel forum |
| Simeon |
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 :\ |
| 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 |
| Simeon |
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. |
| yeah |
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 :D
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). |
| Simeon |
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. |
| yeah |
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. |
| Simeon |
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 :| |
| yeah |
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). |
| Simeon |
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. |
|
|
|
|
