marcoguillermaz

User info:

Registered: Oct 2009
Posts: 12 (0.00 al dì)
Location: Milano
Corso: Informartica per le telecomunicazioni
Anno: 3
Time Online: 6:32:07: [...]
Status: Offline

Post actions:

Ciao a tutti sto facendo i temi d'esame per il compitino e mi è balzato all'occhio un problema con la dpll su un esercizio.
Mi date una mano??

allora nei due temi d'esame c'è questa espressione :

((q->p)->p)->q

l'altra è molto simile

((q->p)->q)->q

In entrambe chiede di verificare se siano tautologie, io come da procedura le nego, arrivando in fondo mi trovo una situzione di soddisfacibilità in entrambe le espressioni.

Potete verificare anche voi???


GRazie

s4lv0

User info:

Registered: Jun 2009
Posts: 20 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: III
Time Online: 13:35:18 [...]
Status: Offline

Post actions:

Ciao,
la prima:

¬[((q->p)->p)->q]

mi viene:

C={q v p, ¬p v p, ¬q}

ed è SAT


la seconda:

¬[((q->p)->q)->q]

mi da:

C={q v q, ¬p v q, ¬q}

ed è UNSAT

Last edited by s4lv0 on 26-03-2010 at 20:31

marcoguillermaz

User info:

Registered: Oct 2009
Posts: 12 (0.00 al dì)
Location: Milano
Corso: Informartica per le telecomunicazioni
Anno: 3
Time Online: 6:32:07: [...]
Status: Offline

Post actions:

Grazie mille per la risposta, il mio solo dubbio era come trattare i due casi in cui mi trovo :

p V p e p V not P, per il fatto che in entrambe sicuramente q = 0, visto il not q, ma in queste due come funziona ....???

s4lv0

User info:

Registered: Jun 2009
Posts: 20 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: III
Time Online: 13:35:18 [...]
Status: Offline

Post actions:

Figurati,
quando poni q=0, devi cancellare tt le clausole in cui compare ¬q, mentre cancelli solo il letterale da qll in cui compare q e viceversa se poni q=1

marcoguillermaz

User info:

Registered: Oct 2009
Posts: 12 (0.00 al dì)
Location: Milano
Corso: Informartica per le telecomunicazioni
Anno: 3
Time Online: 6:32:07: [...]
Status: Offline

Post actions:

Questo è chiarissimo, ma se noti quando ho la prima espressione in fnc, mi trovo p V p in questo caso ho capito, ma se mi trovo :

p V p, not q V p , not p

come mi devo comportare ???

s4lv0

User info:

Registered: Jun 2009
Posts: 20 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: III
Time Online: 13:35:18 [...]
Status: Offline

Post actions:

ti viene così:
p=0 |-{clausola vuota, ¬q}
quindi UNSAT

Last edited by s4lv0 on 26-03-2010 at 20:57

marcoguillermaz

User info:

Registered: Oct 2009
Posts: 12 (0.00 al dì)
Location: Milano
Corso: Informartica per le telecomunicazioni
Anno: 3
Time Online: 6:32:07: [...]
Status: Offline

Post actions:

Ti ringrazio, se mi dici solo come funziona quando devo per forza porre p = 0 e mi ritrovo p V p ? lo devo considerare come clausola vuota??

s4lv0

User info:

Registered: Jun 2009
Posts: 20 (0.00 al dì)
Location: Milano
Corso: Informatica
Anno: III
Time Online: 13:35:18 [...]
Status: Offline

Post actions:

certo, visto che ogni clausola la puoi considerare in "or" con la clausola vuota
quindi nel tuo esempio: p v p v clausola vuota ....xciò quando cancelli i due letterali ti rimane la clausola vuota

franky_fs

User info:

Registered: May 2008
Posts: 52 (0.01 al dì)
Location: Milano
Corso: Informatica Magistrale
Anno: 2
Time Online: 2 Days, 13:42:14 [...]
Status: Offline

Post actions:

Eventualmente per poter verificare se hai sbagliato o meno potresti applicare i valori SAT trovati con la DPLL alla formula di partenza, se il suo valore è FALSE, allora l'esercizio è corretto: hai trovato dei valori che dimostrano che la formula non è una tautologia. Se esce TRUE c'è qualcosa che non va.

__________________
Volere è potere
Memento audere semper
Sia che tu creda di farcela, o che tu creda di non farcela, hai comunque ragione!