Consequência e equivalência semânticas

O que se usa da aula anterior

A aula sobre a semântica da lógica proposicional deu significado às fórmulas, e esta aula o dá por sabido. Uma valoração é uma função $v\colon V \to \{0, 1\}$, que atribui a cada variável um valor de verdade, $1$ (verdadeiro) ou $0$ (falso). Pelo teorema de definição por recursão sobre as fórmulas, da aula sobre a indução, cada valoração se estende de um único modo a todas as fórmulas mediante a cláusula da negação conjunta, a única necessária, porque a língua tem um só conectivo:

Pela unicidade da extensão, escreve-se $v(\varphi)$ também para o valor da extensão; a letra $v$ sem subíndice designa sempre uma valoração (e $v'$, $w$, $u$, outras), ao passo que as variáveis levam sempre seu subíndice. Como na aula sobre a formalização, $p$, $q$, $r$, $s$ e $t$ nomeiam as variáveis $v_1$ a $v_5$, e $V(\varphi)$ é o conjunto das variáveis de $\varphi$. Diz-se que $v$ satisfaz $\varphi$, e escreve-se $v \models \varphi$, quando $v(\varphi) = 1$, e que a falsifica, $v \not\models \varphi$, quando $v(\varphi) = 0$. Uma fórmula é válida (ou tautologia), e escreve-se $\models \varphi$, se toda valoração a satisfaz; satisfatível, se alguma a satisfaz; insatisfatível (ou contradição), se nenhuma a satisfaz; contingente, se é satisfatível sem ser válida. Uma valoração satisfaz um conjunto $\Gamma$ de fórmulas, $v \models \Gamma$, quando satisfaz cada uma delas, e $\Gamma$ é satisfatível se alguma valoração o satisfaz e insatisfatível em caso contrário. Por último, $\top := (v_1 \rightarrow v_1)$ e $\bot := \neg\top$, de modo que $v(\top) = 1$ e $v(\bot) = 0$ para toda valoração.

Daquela aula usam-se ainda dois resultados. O primeiro é o lema da coincidência: se duas valorações coincidem nas variáveis de $\varphi$, coincidem em $\varphi$; por ele, o valor de uma fórmula com $n$ variáveis depende só de $2^{n}$ combinações, e sua tabela-verdade é finita. O segundo é o teorema dos valores dos conectivos derivados, que calcula a partir das abreviaturas oficiais o valor de cada conectivo como um polinômio nos valores dos componentes. Se $a = v(\varphi)$ e $b = v(\psi)$:

As demonstrações desta aula consistem, quase todas, em comparar valores de verdade, e esses polinômios permitem fazê-lo com um cálculo em vez de um percurso de casos. Sua única regra adicional é que $0$ e $1$ são os únicos números que coincidem com seu quadrado: se $x$ vale $0$ ou $1$, então $x^{2} = x$ e $x(1 - x) = 0$. Convém ter à mão, além disso, outras três escritas dos mesmos valores, que se obtêm desenvolvendo os produtos:

A primeira é a cláusula da negação conjunta (o produto de $1 - a$ e $1 - b$ vale $1$ exatamente quando $a = b = 0$); a segunda diz que a disjunção vale $0$ só se ambos os componentes valem $0$; a terceira, que o bicondicional vale $1$ se $a = b$ (porque $1 - 2a + 2a^{2} = 1$) e $0$ se $a \neq b$ (porque então $a + b = 1$ e $ab = 0$).