Insoddisfacibile

Insoddisfacibile è un aggettivo italiano usato principalmente nei campi della logica, della matematica e della filosofia per descrivere una proposizione, un insieme di proposizioni o un insieme di vincoli che non può essere soddisfatto in alcuna interpretazione.

Deriva dal prefisso in- (negazione) e dal verbo soddisfare; il sostantivo correlato è soddisfazione. L’aggettivo indica l’impossibilità di trovare un modello o una assegnazione che renda vera la proposizione.

In logica si parla di formula insoddisfacibile o teoria insoddisfacibile quando non esiste nessuna assegnazione di valori che renda vera la formula. Un esempio comune è la congiunzione di una proposizione e del suo negato, p ∧ ¬p, che non può essere vera. In informatica e nella matematica si parla anche di insoddisfacibilità di insiemi di clausole o di vincoli, cioè di situazioni prive di modelli. Al contrario, una formula soddisfacibile ammette almeno una interpretazione che la renda vera.

Nella pratica, i problemi di satisfiability (SAT) distinguono tra istanze soddisfacibili e insoddisfacibili e sono centrali in campi come la verifica di progettazioni e l’ottimizzazione.

Voci correlate: soddisfacibile, logica proposizionale, teoria dei modelli, problemi SAT.