Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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$?

share|improve this question
    
Sorry if it's badly expressed. I'm deeply confused. –  Vladimir Putin Mar 21 '13 at 6: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. –  Isaac Solomon Mar 21 '13 at 6: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 6:16
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. –  Isaac Solomon Mar 21 '13 at 6:22
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. –  Isaac Solomon Mar 21 '13 at 6:27

2 Answers 2

up vote 3 down vote accepted

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$.

share|improve this answer
    
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? –  Vladimir Putin Mar 22 '13 at 1:35

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.