Satisfatibilidade: diferenças entre revisões

Na [[lógica matemática]], '''satisfatibilidade''' e '''validade''' são conceitos elementares da [[semântica]]. Uma fórmula é ''satisfatívelsatisfazível'' se é possível achar uma [[interpretação (lógica)| interpretação]] ([[teoria dos modelos| modelo]]) que torne a fórmula verdadeira.<ref>See, for example, Boolos and Jeffrey, 1974, chapter 11.</ref> Uma fórmula é ''válida'' se todas as interpretações tornam a fórmula verdadeira. Os opostos deste conceito são '''insatisfatibilidade''' e '''invalidade''', isto é, uma fórmula é ''insatisfatívelinsatisfazível'' se nenhuma das interpretações tornam a fórmula verdadeira, e ''inválida'' se alguma dessas interpretações tornam a fórmula falsa. Estes quatro conceitos estão relacionados uns aos outros de maneira exatamente análoga ao [[quadrado das oposições]] de [[Aristóteles]].

Os quatro conceitos podem ser usados para aplicar todas as teorias: uma teoria é satisfatívelsatisfazível (válida) se uma (todas) as interpretações torna(m) cada um dos axiomas da teoria verdade, e a teoria é insatisfatívelinsatisfazível (inválida) se todas (uma) as interpretações tornam(a) cada um dos axiomas da teoria falso.

Para a lógica clássica, geralmente é possível reexpressar a questão da validade da fórmula para uma envolvendo satisfatibilidade, por causa da relação entre os conceitos expressados acima, no quadrado das oposições. Em particular φ é válido se e somente se ¬φ é insatisfatívelinsatisfazível, o que significa dizer que não é verdade que ¬φ é satisfatívelsatisfazível. Por outro lado, φ é satisfatívelsatisfazível se e somente se ¬φ é inválida.

Para lógica sem negação, tal como o cálculo proposicional positivo, as questões de validade e satisfatibilidade não devem estar relacionadas. No caso do cálculo proposicional positivo, o problema da satisfatibilidade é trivial, pois toda fórmula é satisfatívelsatisfazível, enquanto o problema da validade é co-NP completo.

Na teoria dos modelos, uma formula atômica é satisfatívelsatisfazível se existe uma coleção de elementos da estrutura que tornam a fórmula verdadeira.<ref>{{cite book|author1=Wilifrid Hodges|title=A Shorter Model Theory|year=1997|publisher=Cambridge University Press|isbn=0521587131|pages=12}}</ref> Se ''A'' é uma estrutura, &phi; é uma fórmula, e ''a'' é uma coleção de elementos, tirados da estrutura, que satisfazem &phi;. Comumente é escrito assim