Consecuencia y equivalencia semántica

Lo que se usa de la clase anterior

La clase sobre la semántica de la lógica proposicional dio significado a las fórmulas, y esta clase lo da por sabido. Una valoración es una función $v\colon V \to \{0, 1\}$, que asigna a cada variable un valor de verdad, $1$ (verdadero) o $0$ (falso). Por el teorema de definición por recursión de la clase sobre la inducción sobre las fórmulas, cada valoración se extiende de un único modo a todas las fórmulas mediante la cláusula de la negación conjunta, la única que hace falta, porque la lengua tiene un solo conector:

Por la unicidad de la extensión, se escribe $v(\varphi)$ también para el valor de la extensión; la letra $v$ sin subíndice designa siempre una valoración (y $v'$, $w$, $u$, otras), mientras que las variables llevan siempre su subíndice. Como en la clase sobre la formalización, $p$, $q$, $r$, $s$ y $t$ nombran las variables $v_1$ a $v_5$, y $V(\varphi)$ es el conjunto de las variables de $\varphi$. Se dice que $v$ satisface $\varphi$, y se escribe $v \models \varphi$, cuando $v(\varphi) = 1$, y que la refuta, $v \not\models \varphi$, cuando $v(\varphi) = 0$. Una fórmula es válida (o tautología), y se escribe $\models \varphi$, si toda valoración la satisface; satisfacible, si alguna la satisface; insatisfacible (o contradicción), si ninguna la satisface; contingente, si es satisfacible sin ser válida. Una valoración satisface un conjunto $\Gamma$ de fórmulas, $v \models \Gamma$, cuando satisface cada una de ellas, y $\Gamma$ es satisfacible si alguna valoración lo satisface e insatisfacible en caso contrario. Por último, $\top := (v_1 \rightarrow v_1)$ y $\bot := \neg\top$, de modo que $v(\top) = 1$ y $v(\bot) = 0$ para toda valoración.

De aquella clase se usan además dos resultados. El primero es el lema de coincidencia: si dos valoraciones coinciden en las variables de $\varphi$, coinciden en $\varphi$; por él, el valor de una fórmula con $n$ variables depende solo de $2^{n}$ combinaciones, y su tabla de verdad es finita. El segundo es el teorema de los valores de los conectores derivados, que calcula desde las abreviaturas oficiales el valor de cada conector como un polinomio en los valores de las componentes. Si $a = v(\varphi)$ y $b = v(\psi)$:

Las demostraciones de esta clase consisten, casi todas, en comparar valores de verdad, y estos polinomios permiten hacerlo con un cálculo en lugar de un recorrido de casos. Su única regla adicional es que $0$ y $1$ son los únicos números que coinciden con su cuadrado: si $x$ vale $0$ o $1$, entonces $x^{2} = x$ y $x(1 - x) = 0$. Conviene tener a mano, además, otras tres escrituras de los mismos valores, que se obtienen desarrollando los productos:

La primera es la cláusula de la negación conjunta (el producto de $1 - a$ y $1 - b$ vale $1$ exactamente cuando $a = b = 0$); la segunda dice que la disyunción vale $0$ solo si ambas componentes valen $0$; la tercera, que la doble implicación vale $1$ si $a = b$ (porque $1 - 2a + 2a^{2} = 1$) y $0$ si $a \neq b$ (porque entonces $a + b = 1$ y $ab = 0$).