soddisfacibilita

soddisfacibilita

soddisfacibilità in logica matematica, proprietà di una formula così definibile: una formula di una teoria si dice soddisfacibile se esiste una struttura tale che, interpretando in essa opportunamente le variabili, la formula risulti vera; per esempio, la formula 3x − 1 = y risulta vera se si assegna a x il valore 1 e a y il valore 2 ed è quindi una formula soddisfacibile in R.

Nel linguaggio degli → enunciati una formula ben formata (detta anche enunciato o proposizione) è soddisfacibile se è possibile assegnare alle lettere proposizionali che in essa compaiono valori di verità che la rendano vera. Per esempio, l’enunciato (A ∨ B) ∧ ¬C (si legge «A o B, e non C») risulta vero se si assegnano alle tre lettere proposizionali A B e C rispettivamente i valori di verità V, V e F. Infatti se A e B sono entrambe vere allora la loro disgiunzione (A ∨ B) è un enunciato vero; d’altra parte se C è un enunciato falso allora la sua negazione (¬C) è un enunciato vero; la congiunzione dei due enunciati veri A ∨ B e ¬C (cioè l’enunciato (A ∨ B) ∧ ¬C) è un enunciato vero. Esistono tuttavia proposizioni non soddisfacibili, che non risultano vere per alcun valore di verità delle loro lettere proposizionali: per esempio, la proposizione (A ∨ (B ⇒ C)) ∧ (¬A ∧ (B ∧ ¬C)) risulta falsa per entrambi i valori di verità che si possono assegnare ad A, B e C.