2

I'm reading Shawn Hedman's A First Course in Logic: An Introduction to Model Theory, Proof Theory, Computability, and Complexity:

Definition 1.18 Formula $G$ is a consequence of formula $F$ if for every assignment $A$, if $A\models F$ then $A\models G$. We denote this by $F\models G$.

Proposition 1.19 For any formulas $F$ and $G$, $G$ is a consequence of $F$ if and only if $F \rightarrow G$ is a tautology.

Example 1.20 Let $F$ and $G$ be formulas. Each of the following can easily be verified by computing a truth table.

$$(F \wedge G)\models F \tag{1}$$

$$F\models (F \vee G) \tag{2}$$

$$(F\wedge ¬ F )\models G \tag{3}$$

I'm failing to understand why the truth table of $\models$ is so, (I'm not really sure that it exists, but according to the text, I guess it exists). For example, calculating from $(1)$, I'll obtain the following truth table:

$$\begin{array}[b]{cccc} F & G & (F\wedge G) & (F\wedge G)\models F\\ 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 1\\ 1 & 0 & 0 & 1\\ 1 & 1 & 1 & 1 \end{array}$$

I've also obtained tautologies by calculating the truth tables for the other examples and considering that both $(1)$, $(2)$ and $(3)$ are convenient examples chosen by the author to demonstrate examples of tautologies, I believe that the truth table of $\models$ is:

$$\begin{array}[b]{ccc} F' & G' & F'\models G'\\ 0 & 1 & 1\\ 1 & 1 & 1 \end{array} $$

What's not obvious to me at all is why is that so? why this is the truth table of $\models$?

Red Banana
  • 23,956
  • 20
  • 91
  • 192
  • Sorry if it's badly expressed. I'm deeply confused. – Red Banana Mar 21 '13 at 06:10
  • 2
    What's confusing here is that you need to distinguish between formal logical statements and meta-mathematical statements. $F \models G$ is not a formula in your logical system. It is shorthand for the idea of implication you are studying. Thus it does not make sense to work with truth tables of $F \models G$, since the truth of $F \models G$ is not based on assignments for $F$ and $G$, but on meta-mathematical considerations. – Elchanan Solomon Mar 21 '13 at 06:15
  • DISCLAIMER: I haven't taken a course on logic, so this might be off base: $\models$ does not have a truth table. Appeal directly to the definition. Is it true that every assignment $A$ making $F \land G$ true also makes $F$ true? – kahen Mar 21 '13 at 06:16
  • @IsaacSolomon What meta-mathematical statements? The book still didn't present me those, the only thing I've seen was in another book: We can say that the pythagorean theorem is a consequence of the axioms in euclidean geometry. Is that it? – Red Banana Mar 21 '13 at 06:17
  • 1
    What I'm trying to say is that $F \models G$ is not a statement in your logical system. $F \wedge G$ is a formal logical statement, and its truth is dependent on the truth of $F$ and $G$. But to discern whether $F \models G$ is true, you need to consider the truth tables of $F$ and $G$ and figure out if truth assignments that satisfy $F$ also satisfy $G$. In that sense, its truth has nothing to do with an assignment. In the sentence $F \models G$, $F$ cannot take a truth value, it actually stands for an idea. – Elchanan Solomon Mar 21 '13 at 06:22
  • Got it. But if that is so, why did he say: Each of the following can easily be verified by computing a truth table? I thought it had something to do with truth tables mainly because of this. – Red Banana Mar 21 '13 at 06:25
  • 1
    You look at a truth table to see all possible truth assignments. Then you can tell if the $\models$-statement is true by checking all the assignments yourself and seeing if the correct implication follows. The truth table involves the stuff on the left of the $\models$ sign, and the stuff on the right of the $\models$ sign. The $\models$ sign doesn't make sense as part of a truth table for the reasons I tried to explain above. – Elchanan Solomon Mar 21 '13 at 06:27

2 Answers2

3

It is incorrect to think of $\models$ as a truth function (or a relation between truth values). Instead it is a relation that holds between (a set of) formulas, and a single formula.

The basic idea is as follows: to see if $\Phi \models \Psi$, find all of the truth assignments which give $\Phi$ the value $\top$ (or $1$). If in each of these truth assignments $\Psi$ is also given the value $\top$, then the relation holds; otherwise it doesn't.

Let's go through the first example:

$$\begin{array}{cc|c|c} F & G & F \wedge G & F \\ \hline \top & \top & \top & \top \\ \top & \bot & \color{red}{\bot} & \color{red}{\top} \\ \bot & \top & \color{red}{\bot} & \color{red}{\bot} \\ \bot & \bot & \color{red}{\bot} & \color{red}{\bot} \end{array}$$

The only truth assignment that gives $F \wedge G$ the value true also gives $F$ the value $\top$, and so $F \wedge G \models F$.

For the second example: $$\begin{array}{cc|c|c} F & G & F & F \vee G \\ \hline \top & \top & \top & \top \\ \top & \bot & \top & \top \\ \bot & \top & \color{red}{\bot} & \color{red}{\top} \\ \bot & \bot & \color{red}{\bot} & \color{red}{\bot} \end{array}$$ There are two truth assignments that give $F$ the value $\top$, and in each of these $F \vee G$ is also given the value $\top$, and so $F \models F \vee G$.

And the third example $$\begin{array}{cc|c|c} F & G & F \wedge \neg F & G \\ \hline \top & \top & \color{red}{\bot} & \color{red}{\top} \\ \top & \bot & \color{red}{\bot} & \color{red}{\bot} \\ \bot & \top & \color{red}{\bot} & \color{red}{\top} \\ \bot & \bot & \color{red}{\bot} & \color{red}{\bot} \end{array}$$ Here no truth assignment gives $F \wedge \neg F$ the value $\top$, and so every time $F \wedge \neg F$ is given the value $\top$ so is $G$, and so $F \wedge \neg F \models G$.

user642796
  • 52,188
  • But it's possible to have a truth table with all formulas, right? I mean, it's possible to have a truth table for ecerything that doesn't have $\models$, right? – Red Banana Mar 22 '13 at 01:35
1

You have formulae (eg, $F \lor G$), you have assignments (eg, $F=\top, G= \bot$) and rules for 'propagating' assignments through formulae (eg, the above assigns the value $\top$ to $F \lor G$).

You can create a truth table for a formula which expresses the formula as a boolean function.

A formula is a tautology iff the value is true for any assignment, or equivalently, its truth table has all true results. Note that there is no truth table for being a tautology; it expresses something about the truth table itself. But it makes no sense to try and write down the truth table for a tautology.

Think of $F \models G$ in the same way. It expresses a relationship between the truth tables of $F$ and $G$, but it doesn't make any more sense to talk about the truth table of $\models$ than it does to talk about the truth table of a tautology. It means that if a line in the truth table for $F$ results in true, then the corresponding line in the truth table for $G$ must also result in true.

Proposition 1.19 shows that the statement $F \models G$ is the same as saying $F \rightarrow G$ is a tautology.

copper.hat
  • 172,524