Questo sito utilizza cookies, anche di terze parti, per mostrare pubblicità e servizi in linea con il tuo account. Leggi l'informativa sui cookies.
Username: Password: oppure
C/C++ - Formule logiche
Forum - C/C++ - Formule logiche

Avatar
Dice (Normal User)
Expert


Messaggi: 238
Iscritto: 26/11/2011

Segnala al moderatore
Postato alle 16:58
Giovedì, 15/12/2011
Mentre stavo leggendo un po di logica proposizionale, mi è venuta voglia di creare un programma in linguaggio C che poteva essere interessante:
acquisire da tastiera un formula logica (esempio: a or b and c implica d), e verificare se esiste un assegnamento di verità che la soddisfi.
Allora... io mi ci sono messo giù a pensare e ripensare su come fare ma....
l'unica cosa che so è che è necessario creare un array di caratteri (per poter acquisire le lettere e i numeri (i numeri, per semplicità, sostituiscono i connettivi logici); però non riesco proprio a capire come fare verificare l'assegnamento di verità della formula.
Io ci ho pensato per molto tempo e per il momento non mi è venuto in mente praticamente niente.
Volevo chiedervi se potevate aiutarmi, fatemi sapere.
Ciao.


La vita è un biscotto ma se piove si scioglie !!!
PM
Avatar
Il Totem (Admin)
Guru^2


Messaggi: 3635
Iscritto: 24/01/2006

Up
1
Down
V
Segnala al moderatore
Postato alle 10:11
Venerdì, 16/12/2011
Direi che hai un buon gusto per i problemi difficili. Quello che hai scelto è il problema della soddisfacibilità booleana ed è un problema NP-completo, ossia è risolvibile in tempo polinomiale solo da un algoritmo non deterministico.
La difficoltà, quindi, non è tanto eseguire un parsing, ma piuttosto risolvere il problema in tempo ridotto, il che non è possibile dato che lo spazio delle soluzioni cresce esponenzialmente.

Una cosa leggermente più semplice è verificare se un insieme di formule logiche è consistente mediante risoluzione logica. Per la logica proposizionale, la risoluzione è corretta e completa per refutazione. Perciò se non trovi un risolvente puoi star sicuro che non esiste.

Ok, mi sono andato a trovare una cosa un po troppo complessa, però ... - Dice - 17/12/11 18:47
se decidessi di limitarmi ? Cioè: io voglio verificare se esiste un assegnamento di verità che soddisfa una formula con questi limiti: al massimo 4 proposizioni e al massimo 3 connettivi. Dice che è possibile riuscirci ? - Dice - 17/12/11 18:50
3-SAT è ancora NP-Completo. L'istanza più facile del problema è 2-SAT e i suoi sottocasi. http://en.wikipedia.org/wiki/Boolean_satisfiability_problem#3-satisfiability - Il Totem - 18/12/11 11:44


"Infelici sono quelli che hanno tanto cervello da vedere la loro stupidità."
(Fligende Blatter)

"Dubitare di se stessi è il primo segno d'intelligenza."
(Ugo Ojetti)
PM