Semantic consequence and equivalence

What is used from the previous lesson

The lesson on the semantics of propositional logic gave meaning to formulas, and this lesson takes it as known. A valuation is a function $v\colon V \to \{0, 1\}$, which assigns to each variable a truth value, $1$ (true) or $0$ (false). By the theorem of definition by recursion on formulas, from the lesson on induction, each valuation extends in a unique way to all formulas through the clause for joint denial, the only one needed, because the language has a single connective:

By the uniqueness of the extension, one also writes $v(\varphi)$ for the value of the extension; the letter $v$ without a subscript always denotes a valuation (and $v'$, $w$, $u$, others), whereas variables always carry their subscript. As in the lesson on formalization, $p$, $q$, $r$, $s$ and $t$ name the variables $v_1$ to $v_5$, and $V(\varphi)$ is the set of the variables of $\varphi$. One says that $v$ satisfies $\varphi$, and writes $v \models \varphi$, when $v(\varphi) = 1$, and that it falsifies it, $v \not\models \varphi$, when $v(\varphi) = 0$. A formula is valid (or a tautology), and one writes $\models \varphi$, if every valuation satisfies it; satisfiable, if some valuation satisfies it; unsatisfiable (or a contradiction), if none satisfies it; contingent, if it is satisfiable without being valid. A valuation satisfies a set $\Gamma$ of formulas, $v \models \Gamma$, when it satisfies each of them, and $\Gamma$ is satisfiable if some valuation satisfies it and unsatisfiable otherwise. Finally, $\top := (v_1 \rightarrow v_1)$ and $\bot := \neg\top$, so that $v(\top) = 1$ and $v(\bot) = 0$ for every valuation.

Two further results are used from that lesson. The first is the coincidence lemma: if two valuations agree on the variables of $\varphi$, they agree on $\varphi$; by it, the value of a formula with $n$ variables depends only on $2^{n}$ combinations, and its truth table is finite. The second is the theorem on the values of the defined connectives, which computes from the official abbreviations the value of each connective as a polynomial in the values of the components. If $a = v(\varphi)$ and $b = v(\psi)$:

The proofs in this lesson consist, almost all of them, in comparing truth values, and these polynomials make it possible to do so by a calculation instead of a run through cases. Their only additional rule is that $0$ and $1$ are the only numbers that coincide with their square: if $x$ is $0$ or $1$, then $x^{2} = x$ and $x(1 - x) = 0$. It is also convenient to have at hand three other ways of writing the same values, which are obtained by expanding the products:

The first is the clause for joint denial (the product of $1 - a$ and $1 - b$ is $1$ exactly when $a = b = 0$); the second says that the disjunction is $0$ only if both components are $0$; the third, that the biconditional is $1$ if $a = b$ (because $1 - 2a + 2a^{2} = 1$) and $0$ if $a \neq b$ (because then $a + b = 1$ and $ab = 0$).