Valoração (lógica)

Na matemática, uma valoração, grosseiramente falando, é uma atribuição de valores específicos para as variáveis numa afirmação ou equação matemática.

Em lógica e teoria dos modelos, uma valoração é:

(i) ou uma atribuição de valores de verdade a cada sentença atômica, desde que cada elemento do domínio tenha um nome no caso de linguagens de primeira ordem ou de ordem superior.

(ii) ou uma função do vocabulário não-lógico para seus objetos correspondentes definidos sobre o domínio (por exemplo, uma função que leva símbolos de relações e de funções para relações e funções definidas no domínio, e constantes para elementos no domínio).

Por exemplo, numa tabela de verdade basicamente trabalhamos em cada linha com uma valoração.

Mais formalmente, considere uma dada linguagem formal

$\boldsymbol{L}=\{\boldsymbol{A},\boldsymbol{R},\boldsymbol{F}\}$

onde $A$ é seu alfabeto, $R$ um conjunto de regras de transformações sobre $A$ (uma gramática), e $F$ é um conjunto de fórmulas bem-formadas (o fecho de A sobre os elementos de R). Dada uma álgebra abstrata $\scriptstyle\mathfrak{A}$ com três operações binárias e uma operação unária, que pode ser álgebra das fórmulas da linguagem se a linguagem é ela própria de ordem $0$ ou $1$, isto é,

$\mathfrak{A}\equiv\{\boldsymbol{F},\vee,\wedge,\rightarrow,\neg\}$

com os símbolos lógicos de disjunção $\scriptstyle\vee$, conjução $\scriptstyle\wedge$, implicação $\scriptstyle\rightarrow$ e negação $\scriptstyle\neg$, uma valoração é alguma associação

$v:\boldsymbol{V_0}\rightarrow\mathfrak{A} \iff v \in \mathfrak{A}^\boldsymbol{V_0}$

onde $V_0$ é o conjunto de variáveis proposicionais da linguagem $L$. Assim, uma valoração associa variáveis proposicionais a formulas algébricas em $\scriptstyle\mathfrak{A}$.

Satifazibilidade

Em lógica matemática, o problema da satisfatibilidade consiste em determinar para uma dada fórmula ou conjunto de fórmulas de uma lógica $L$, se existe uma interpretação, i.e., uma atribuição de valores de verdade ou valoração que torna essas proposições verdadeiras. Este problema pertence à classe dos problemas genericamente designados como NP-completo, que desempenham um papel central em Lógica e na Teoria da Computabilidade.

Satisfatível

Uma fórmula é satisfatível se existe ao menos uma interpretação que a satisfaça.

Insatisfatível

Uma fórmula é insatisfatível se ela não é satisfeita para nenhuma interpretação.

Referências

• Benjamín René Callejas Bedregal, Benedito Melo Acióly. Lógica para a Ciência da Computação. Versão preliminar, 2002.
• Fingeretal, Lógica para Computação, FLAVIO SOARES CORREA DA SILVA & MARCELO FINGER & ANA CRISTINA VIEIRA DE MELO, Thomson Learning, 2006