Soddisfacibilità logica

La soddisfacibilità logica è un problema decisionale, la cui istanza viene soddisfatta almeno una volta nell'assegnazione dei valori alle variabili del problema. È anche conosciuta come soddisfacibilità booleana, soddisfacibilità proposizionale o problema SAT. Nella logica proposizional una formula booleana è soddisfacibile quando è vera in almeno un modello. E', invece, una formula insoddisfacibile se è identicamente falsa per tutti i modelli.

SODDISFACIBILITA LOGICA

Ad esempio, la formula booleana ( A ∨ B ) è soddisfacibile in quanto è vera in tre modelli su quattro. Si distingue dalla formula ( A ∨ ¬A ) che, invece, è valida ( validità logica ) in quanto è vera in tutti i modelli.

Algoritmi di ricerca. Gran parte dei problemi risolvibili dagli algoritmi informatici sono caratterizzati da soddisfacibilità logica. Il problema è risolvibile in alcuni modelli ma non in tutti. L'algoritmo enumera i modelli fin quando non ne trova uno in grado di risolvere il problema.

Validità logica. Il concetto di soddisfacibilità logica è strettamente collegato a quello di validità logica. Data una formula A, per essere una formula valida è necessario che ¬A sia una formula insoddisfacibile. Data una formula A, per essere una formula soddisfacibile è necessario che ¬A sia una formula non valida.

https://www.okpedia.it/soddisfacibilita_logica


Segnala un errore o invia un suggerimento per migliorare la pagina


Logica proposizionale


FacebookTwitterLinkedinLinkedin