If you have looked at the solutions of the puzzles from the previous theory page, you will have seen that it is useful to construct a truth table for the formulas that appear in the conclusion. The secret behind this is that you can find an exclusive model for the set of formulas of the puzzle in it. This theory page discusses this.
We first look back at the concept of valuation. A valuation is, by definition, a function that assigns truth values to all propositional variables (\(0\) if the proposition is false, \(1\) for a true proposition). You can then also assign a truth value to a (well-formed) logical formula according to the rules of the game. In the table below, we have emphasised the function aspect of a valuation by writing the rules as function rules, so that a valuation of a formula amounts to a composition of mathematical functions.
Suppose that \(x\) and \(y\) can take on the value \(0\) or \(1\) (as with a valuation of proposition variables), then the following rules apply when using the logical connectives: \[\begin{aligned} f_{\neg}(x)&=1-x\\[0.2cm] f_{\land}(x,y) &= \min(x,y)\\[0.2cm] f_{\lor}(x,y) &= \max(x,y)\\[0.2cm] f_{\rightarrow}(x,y) &= \max(1-x,y)\\[0.2cm] f_{\leftrightarrow}(x,y) &= \begin{cases} 1 & \text{als } x=y\\ 0 & \text{otherwise}\end{cases}\end{aligned}\]
Suppose \(p\), \(q\), and \(r\) are propositional variables with valuations \(v(p)=0\), \(v(q)=1\), and \(v(r)=0\). Let's look at the formula \(\varphi=p\lor (q\rightarrow r)\). Then the valuation \(v(\varphi)\) can be computed in steps as follows: \[\begin{aligned} v(\varphi) &= v\bigl(p\lor (q\rightarrow r)\bigr)\\[0.2cm] &= f_{\lor}\bigl(v(p), v(q\rightarrow r)\bigr)\\[0.2cm] &= f_{\lor}\Bigl(0, f_{\rightarrow}(v(q),v(r)\bigr)\Bigr) \\[0.2cm] &= f_{\lor}\bigl(0, f_{\rightarrow}(1,0)\bigr) \\[0.2cm] &= f_{\lor}(0, 0) \\[0.2cm] &= 0\end{aligned}\]
If \(v\) and \(w\) are valuations such that \(v(p)=w(p)\) for every propositional variable \(p\) that appears in a logical formula \(\varphi\), then \(v(\varphi)=w(\varphi)\).
In the remainder of this theory page we will define important concepts such as model, tautology, valid consequence and consistency.
A valuation \(w\) is called a model of a logical formula \(\varphi\) if: \(v(\varphi)=1\). A valuation is called a model of a formula set \(\Sigma\) if it is a model of any formula \(\varphi\in\Sigma\). The set of models of a formula set \(\Sigma\) is denoted as \(\mathrm{MOD}(\Sigma)\). A formula set \(\Sigma\) is said to be satisfiable if the set of models of \(\Sigma\) is not empty, i.e., if there exists a valuation \(v\) that is a model of \(\Sigma\); we therefore say that \(\Sigma\) is satisfied by \(vv\). A formula set \(\Sigma\) is said to be inconsistent if no model of \(\Sigma\) exists.
If we extend a formula set \(\Sigma\) with a formula \(\varphi\), then the set of models becomes a subset of the original set of corresponding models. Every model of the new formula set is a model of the original formula set, but the converse need not be true. In formula language: \(\mathrm{MOD}\bigl(\Sigma\cup \{\varphi\}\bigr)\subseteq \mathrm{MOD}\bigl(\Sigma\bigr)\).
In previous examples of logic puzzles, we have already seen that each new formula in a problem provides additional information about the situation. This means that when we expand a set of formulas we generally get a smaller set of models and ideally end up with only one model that is the solution to the problem.
Let us use the party puzzle as an illustration. There were three statements and we'll give them names right away:
\(u_1\) : "Bob comes to the party if Ann or Claudia come."
\(u_2\) : "Ann comes to the party if Claudia does not come."
\(u_3\) : "If Ann comes to the party, then Bob does not come ."
The question asked now boils down to: does the formula set \(\{u_1, u_2,u_3\}\) have a unique model?
We use the letters \(a\), \(b\) and \(c\) for the propositions "Anna is coming to the party.", "Bob comes to the party.", and "Claudia comes to the party.", respectively. We first determine all models of \(\{u_1\}\), then of \(\{u_1,u_2\}\), and finally of \(\{u_1,u_2,u_3\}\). The results are shown in the table below.
| ratings |
model of |
| \(a\) |
\(b\) |
\(c\) |
\(\{u_1\}\) |
\(\{u_1,u_2\}\) |
\(\{u_1,u_2,u_3\}\) |
| 0 |
0 |
0 |
Yes |
no |
- |
| 0 |
0 |
1 |
no |
- |
- |
| 0 |
1 |
0 |
Yes |
no |
- |
| 0 |
1 |
1 |
Yes |
Yes |
Yes |
| 1 |
0 |
0 |
no |
- |
- |
| 1 |
0 |
1 |
no |
- |
- |
| 1 |
1 |
0 |
Yes |
Yes |
no |
| 1 |
1 |
1 |
Yes |
Yes |
no |
The only model that remains of the three statements is the valuation with \(v(a)=0\), \(v(b)=1\) and \(v(c)=1\). Bob and Claudio come to the party.
The definition of the term "valid consequence" corresponds with the previous intuitive description of a logically valid inference \(\psi\) based on one or more premises \(\varphi_1, \ldots, \varphi_n\). Such an argument is correct, i.e., logically valid, if and only if the conclusion \(\psi\) is a valid consequence of \(\Sigma=\{\varphi_1, \ldots, \varphi_n\}\). So every model of \(\Sigma\) is also a model of the conclusion \(\psi\). If an argument is not correct, then a valuation \(v\) must exist such that \(v(\varphi_1)= \ldots = v(\varphi_n)=1\), but \(v(\psi)=0\).
A logical formula \(\varphi\) is called a tautology if every valuation is a model of \(\varphi\), i.e., if \(v(\varphi)=1\) for every valuation \(v\).
Any formula of the form \(\varphi\lor \neg\,\varphi\) is a tautology. Also, any formula of the form \(\neg(\varphi\land \neg\,\varphi)\) is a tautology. You can see this from the truth tables below \[\begin{array}{c|cccc} \varphi & \neg\,\varphi & \varphi\lor \neg\,\varphi & \varphi\land \neg\,\varphi & \neg(\varphi\land \neg\,\varphi) \\ \hline 0 & 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 & 1\end{array}\]
A logical formula \(\varphi\) is called a contradiction if no valuation is a model of \(\varphi\), i.e. if \(v(\varphi)=0\) for every valuation \(v\). The formula \(\varphi\) is a contradiction if and only if \(\neg\,\phi\) is a tautology. We call a logical formula \(\varphi\) a contingency if at least one valuation exists that is a model of \(\varphi\). Each formula set can be divided into contradictions, contingencies and tautologies.
Any formula of the form \(\varphi\land \neg\,\varphi\) is a contraction. Also, any formula of the form \((\varphi\rightarrow\psi)\leftrightarrow \varphi\land\neg\,\psi\) is a contradiction. You can see this from the truth table \[\begin{array}{cc|ccc} \varphi & \psi & \varphi\rightarrow \psi & \varphi\land\neg\,\psi & (\varphi\rightarrow\psi)\leftrightarrow \varphi\land\neg\,\psi\\ \hline 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 & 0\\ 1 & 0 & 0 & 1 & 0\\ 1 & 1 & 1 & 0 & 0 \end{array}\] below. The formula \(\varphi\lor \psi\) is a contingent formula because you can choose the valuation \(v(\varphi)=v(\psi)=1\).
Two formulas \(\varphi\) and \(\psi\) are called logical equivalent if the formula \(\varphi\leftrightarrow \psi\) is a tautology. In other words, for every valuation \(w\) we have \(v(\varphi)=v(\psi)\), that is, \(\varphi\vDash \psi\) and \(\psi\vDash \varphi\).
The formulas \(\varphi\) and \(\neg\,\neg\,\varphi\) are equivalent, i.e., \(\neg\,\neg\,\varphi\leftrightarrow \varphi\) is a tautology. This follows from the truth table below. \[\begin{array}{c|cc} \varphi & \neg\,\varphi & \varphi\leftrightarrow \neg\,\neg\,\varphi \\ \hline 0 & 0 & 1 \\ 1 & 1 & 1 \end{array}\] For the formulas \(\varphi\) and \(\psi\), the formulas \(\neg(\varphi\land\psi)\) and \(\neg\,\varphi \lor \neg\,\psi\) are equivalent. This follows from the truth table below. \[\begin{array}{cc|cccccc} \varphi & \psi & \neg\,\varphi & \neg\psi & \varphi\land\psi & \neg(\varphi\land\psi) & \neg\,\varphi \lor \neg\,\psi & \neg(\varphi\land\psi) \leftrightarrow (\neg\,\varphi \lor \neg\,\psi) \\ \hline 0 & 0 & 1 & 1 & 0 & 1 & 1 & 1\\ 0 & 1 & 1 & 0 & 0 & 1 & 1 & 1 \\ 1 & 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1\end{array}\] That the formula \(\neg(\varphi\rightarrow \psi)\leftrightarrow \varphi\land \neg\,\psi\) is a tautology can also be shown via a truth table, but perhaps more convenient is the following kind of calculation in metalanguage, with \(\iff\) as the symbol for "if and only if" and \(\&\) as the symbol for the conjunction "and": \[\begin{aligned} v\bigl(\neg(\varphi\rightarrow \psi)\bigr) &\iff v(\varphi\rightarrow \psi)=0\\[0.2cm] &\iff v(\varphi)=1\;\&\; v(\psi)=0\\[0.2cm] &\iff v(\varphi)=1\;\&\; v(\neg\,\psi)=1\\[0.2cm] &\iff v(\varphi\land \neg\,\psi)=1\end{aligned}\]
It is already included in the name "logical equivalence", but indeed the three characteristics of an equivalence relation are fulfilled:
- (reflexivity) Every formula \(\varphi\) is logically equivalent to itself ( \(\vDash \varphi\leftrightarrow \varphi\) ).
- (symmetry) If the formula \(\varphi\) is logically equivalent to the formula \(\psi\), then also \(\psi\) is logically equivalent to the formula \(\varphi\) (in metalanguage: \(\vDash\varphi\leftrightarrow \psi\iff \vDash\psi\leftrightarrow\varphi\) ).
- (transitivity) If the formula \(\varphi\) is logically equivalent to the formula \(\psi\) and \(\psi\) \(\varphi\) is logically equivalent to the formula \(\chi\), then \(\varphi\) is logically equivalent to \(\chi\) (in metalanguage using \(\implies\) as implication arrow: \(\vDash\varphi\leftrightarrow \psi\;\&\; \vDash\psi\leftrightarrow \chi \implies\vDash\varphi\leftrightarrow\chi\) ).
A formula \(\psi\) is called a valid consequence of a formula set \(\Sigma\) if every model of \(\Sigma\) is also a model of \(\psi\). This is denoted as \(\Sigma\vDash \psi\). In other words, the reasoning that the formula \(\psi\) being true follows from formula set \(\Sigma\) is valid.
If \(\Sigma=\{\varphi_1,\ldots, \varphi_n\}\), then we also write \(\Sigma\vDash \psi\) as \(\varphi_1,\ldots, \varphi_n\vDash \psi\) and we say that \(\psi\) follows logically from the premises \(\varphi_1,\ldots, \varphi_n\).
For the propositions \(p\), \(q\) and \(r\) we have: \[\begin{aligned}p, p\rightarrow q&\vDash q\\[0.2cm] p, p\rightarrow q, q\rightarrow r&\vDash r\end{aligned}\]
For an empty formula set, i.e., \(\Sigma=\{\}\), then \(\{\}\vDash \psi\), abbreviated as \(\vDash \psi\), means that each valuation is a model of \(\Sigma\), i.e., \(\psi\) is a tautology.
If the formula \(\psi\) is not a valid consequence of the formula set \(\Sigma\), i.ei, there exists a model of \(\Sigma\) that is not a model of \(\psi\), then we denote this as \(\Sigma\nvDash \psi\).
For example, for propositions \(p\) and \(q\) we have \(q,p\rightarrow q \nvDash p\) because it follows from the valuation \(v(p)=0, v(q)=1\) via the truth table of the connective \(\rightarrow\) that \(v( p\rightarrow q)\). This valuation makes \(q\) and \(p\rightarrow q\) true, but \(p\) is false. So the valuation \(v\) is a model of \(\{q,p\rightarrow q\}\), but not of \(p\). This valuation is called a counterexample.
To make this example more concrete, let's make \(p\) and \(q\) the statements "The computer code is correct." and "The program terminates." From the propositions "If the computer code is correct, the program terminates" and "The computer code is correct." it follows that the program terminates. But a terminating program does not mean that the computer code is correct. That is not a valid consequence of the propostions.
You can also make statements about valid inferences in metalanguage (here with the "if then" symbol \(\implies\), a "if and only if " symbol \(\iff\) and a conjunction "and" symbolized by \(\&\) ). The following metapropositions are some examples.
For formulas \(\phi\) and \(\psi\) we have: \[\vDash \varphi\; \&\vDash \psi\implies \vDash \varphi\land \psi\]
For formulas \(\phi\) and \(\psi\) we have: \[\varphi \vDash \psi \implies \vDash \varphi\rightarrow \psi\]
For formulas \(\varphi_1\), \(\varphi_2\) and \(\psi\) we have: \[\begin{aligned} \varphi_1, \varphi_2\vDash \psi &\iff \varphi_1\vDash \varphi_2\rightarrow \psi\\[0.2cm] &\iff \vDash (\varphi_1\land \varphi_2)\rightarrow \psi\end{aligned}\]
A formula set \(\Sigma\) is called (semantically) consistent if a model of \(\Sigma\) exists. If no model of the formula set \(\Sigma\) exists, then \(\Sigma\) is called (semantically) inconsistent. The latter is often undesirable, because the absence of models means that every formula then follows validly from this set, and therefore also its negation.
Suppose \(p\) and \(q\) are proposition variables. Then \(\Sigma=\{p\rightarrow q, \neg\, p,q\}\) is a fulfillable set. After all, the valuation \(v(p)=0\) and \(v(q)=1\) is a model of \(\Sigma\).
The formula set \(\Sigma=\{p\rightarrow q, \neg\, p, q\}\) on the other hand, is an unfulfillable set. After all, for a valuation \(v\) to be a model of \(\Sigma\), \(v(p)=0\) and \(v(q)=1\). But then \(v(p\rightarrow q)=0\).
A formula set is (semantically) consistent if and only if the set is satisfiable. The concepts of consistency and satisfiability are therefore closely related. The first concept, consistency, is about ensuring that the set of formulas does not lead to a contradiction; thus, it is related to proof theory. The second concept, satisfiability, is more about the existence of a valuation for which all formulas in the given formula set have the truth value \(1\). It is therefore more about finding a suitable valuation than about excluding a contradiction.
Models and valid consequence
