Truth, models, consequence

Interpretations

Giving the variables a value

A formula is neither true nor false in absolute terms: $p \land q$ is true if $p$ and $q$ are. An interpretation (or valuation) $v$ gives each propositional variable a value: $1$ (true) or $0$ (false).

The value of a formula is computed bottom-up, along its tree, with the tables of the connectives.

The tables of the connectives

Only one row is surprising: $p \to q$ is true when $p$ is false, whatever $q$. The implication says nothing about what happens when its condition is not met. “If it rains, I take my umbrella” is not refuted on a sunny day, whether I take my umbrella or not. The only way to make it false is to have $p$ true and $q$ false.

The truth table of a formula

With $n$ variables, there are $2^n$ interpretations. The truth table of a formula goes through all of them.

Models, validity, satisfiability

Definitions

An interpretation $v$ is a model of $A$ if $A$ is true in $v$. We write $v \vDash A$. In the example above, $A$ has a single model.

A formula is:

• valid (a tautology) if every interpretation is a model of it. We write $\vDash A$. Example: $p \lor \lnot p$.
• satisfiable if it has at least one model. Example: $p \land q$.
• unsatisfiable (a contradiction) if it has no model. Example: $p \land \lnot p$.

Every valid formula is satisfiable. A satisfiable formula may or may not be valid. “Invalid” means “not valid”, which is not “unsatisfiable”: $p \land q$ is invalid and satisfiable.

Negation swaps the roles

• $A$ is valid if and only if $\lnot A$ is unsatisfiable.
• $A$ is satisfiable if and only if $\lnot A$ is not valid.

Indeed, $v$ is a model of $A$ exactly when $v$ is not a model of $\lnot A$. Practical consequence: to show that $A$ is valid, we can look for an interpretation that makes it false. If the search fails, $A$ is valid.

Logical consequence

Definition

Let $\Sigma$ be a set of formulas (hypotheses) and $A$ a formula. $A$ is a logical consequence of $\Sigma$, written $\Sigma \vDash A$, if every model of all the formulas of $\Sigma$ is a model of $A$. In other words: whenever the hypotheses are all true, the conclusion is true as well.

When $\Sigma$ is empty, we get $\vDash A$ back: $A$ is valid.

Three properties, and their proofs

The proofs all follow the same path: go back to the definition, and talk about interpretations.

Property 1. $\Sigma \vDash A \land B$ if and only if $\Sigma \vDash A$ and $\Sigma \vDash B$.

Forward direction. Let $v$ be a model of $\Sigma$. Since $\Sigma \vDash A \land B$, $v \vDash A \land B$, so $v \vDash A$ and $v \vDash B$ by the table of $\land$. This holds for every model $v$ of $\Sigma$: $\Sigma \vDash A$ and $\Sigma \vDash B$.

Converse. Let $v$ be a model of $\Sigma$. Then $v \vDash A$ and $v \vDash B$, so $v \vDash A \land B$. Hence $\Sigma \vDash A \land B$.

Property 2. $\vDash A \to B$ if and only if $A \vDash B$.

Forward direction. Let $v$ be a model of $A$. Since $A \to B$ is valid, $v \vDash A \to B$; together with $v \vDash A$, the table of $\to$ gives $v \vDash B$.

Converse. Let $v$ be any interpretation. If $v \vDash A$, then $v \vDash B$ by hypothesis, and $A \to B$ is true. Otherwise $A$ is false in $v$, and $A \to B$ is true. In both cases $v \vDash A \to B$: it is valid.

More generally, $\Sigma \cup \{A\} \vDash B$ if and only if $\Sigma \vDash A \to B$ (same proof). We use it to move a hypothesis from left to right.

Property 3. $\Sigma \vDash A$ if and only if $\Sigma \cup \{\lnot A\}$ is unsatisfiable.

$\Sigma \cup \{\lnot A\}$ has a model exactly when there is an interpretation that makes $\Sigma$ true and $A$ false, that is, when $\Sigma \not\vDash A$.

This is the principle of proof by contradiction, and the starting point of resolution (chapter 5).

Equivalence

Definition

Two formulas $A$ and $B$ are equivalent, written $A \equiv B$, if they have the same models: they take the same value in every interpretation. They say the same thing.

Property 4. $A \equiv B$ if and only if $\vDash A \leftrightarrow B$.

$A \leftrightarrow B$ is true in $v$ exactly when $A$ and $B$ have the same value there. So it is true in every interpretation exactly when $A$ and $B$ have the same value everywhere, that is, when $A \equiv B$.

This is the link announced in chapter 1: $\leftrightarrow$ is a connective, $\equiv$ a statement about two formulas, and the latter amounts to saying that the former is valid. Likewise, $A \vDash B$ amounts to saying that $A \to B$ is valid.

The usual laws

Each one can be checked with a truth table.

Replacement

If $B \equiv B'$ and $B$ occurs as a subformula of $A$, replacing $B$ by $B'$ in $A$ gives a formula equivalent to $A$. This is what allows us to compute with the laws, just as one simplifies an expression in algebra.