2.3 The logic model

We now turn to our logic model. Its structure is exactly similar to that of the parity model, although some of the technical terms are different; we list the correspondence in the following table.

We shall now explain the features of the logic model one at a time.

Universe. We shall take as the universe for this model the set of all allowable statements. Here, a statement is called allowable if it is definitely either true or false. For example, ‘‘$3^{2}+4^{2}=5^{2}$’’ and ‘‘every person in this room is female’’ are allowable statements. On the other hand, we are not concerned with

• •

  questions (such as ‘‘is Lancaster better than York?’’);
  

• •

  commands (such as ‘‘switch off that mobile ’phone!’’);
  

• •

  expressions of emotion (such as ‘‘I feel happy’’);
  

• •

  matters of opinion (such as ‘‘Hitchcock is the greatest film director’’).

Note that for a statement to be allowable, we do not need to know whether it is true or false; for example, the statement ‘‘the seventeenth oldest student in this room is male’’ is certainly either true or false, but no-one knows which. For convenience, we shall simply write statement for allowable statement from now on.

Statement variables. We shall use letters (usually lower case) as the basic variables to represent statements from our universe. For example, we might write $p$ for the statement ‘‘$3^{2}+4^{2}=5^{2}$’’, or $q$ for the statement ‘‘every person in this room is female’’.

Truth values. There are two truth values $T$ (for ‘‘true’’) and $F$ (for ‘‘false’’) which any statement variable can take, depending on which element of the universe it represents. For example, if $p$ represents the statement ‘‘$3^{2}+4^{2}=5^{2}$’’, then its truth value is $T$, and if $q$ represents the statement ‘‘every person in this room is female’’, then its truth value is $F.$

The negation. Given a statement variable $p$, we write $\neg p$ (read ‘‘not $p$’’) for the negation of $p$. For example, if $p$ represents the statement ‘‘I cycled to university today’’, then $\neg p$ represents the statement ‘‘I did not cycle to university today’’. (We do not enter into a discussion of whether I walked, ran, drove a car or took the bus.)

Truth tables. These are used to list the truth values of a given statement according to the truth values taken by the basic statement variables which it contains. For example, the truth table of $\neg p$ is as follows.

Logically equivalent statements. We say that two statements are logically equivalent (or simply equivalent) if they have the same truth table. For example, any statement $p$ is logically equivalent to its double negation $\neg(\neg p)$ because the first and third column of the following truth table are the same.

Note that this agrees with the use of double negations in everyday language. For instance, the statement ‘‘I did not miss yesterday’s lecture’’ means (essentially) the same as ‘‘I attended yesterday’s lecture’’. To transform the former statement into the latter, observe that in this context ‘‘miss’’ means (essentially) the same as ‘‘not attend’’, and therefore we may rewrite the former statement as

‘‘I did not not attend yesterday’s lecture’’.

We now get the latter statement by cancelling the double negation.

Connectives and compound statements. Out of the basic statement variables $p,\,q,$ $r,\,\ldots$ (and their negations $\neg p,\,\neg q,\,\neg r,\,\ldots$), we construct more complicated statements, or compound statements, by using connectives. In doing so we assume that the truth value of any compound statement is determined entirely by the truth values of the basic statement variables out of which it is constructed. We shall use five connectives, as given in the following table wherein the first and third columns are the most important.

The alternative symbols here are listed as they are widely used, but they are not recommended as they can cause confusion. Some of the connectives obey rules similar to those satisfied by algebraic operations.

We shall now consider each in turn and give the corresponding truth table.

1. $\&$:

   If $p$ represents the statement ‘‘grass is green’’, while $q$ represents ‘‘pigs can fly’’, then ‘‘$p\ \&\ q$’’ represents the statement ‘‘grass is green and pigs can fly’’. For such a compound statement to be true, we need both statements out of which it is built to be true. In other words the truth value of ‘‘$p\ \&\ q$’’ is $T$ if the truth values of both $p$ and $q$ are $T$, and is $F$ otherwise. This is summarized in the following truth table.

   $p$	$q$	$p\ \&\ q$
   $T$	$T$	T
   $T$	$F$	F
   $F$	$T$	F
   $F$	$F$	F

2. or:

   If, as before, $p$ represents the statement ‘‘grass is green’’, while $q$ represents ‘‘pigs can fly’’, then ‘‘$p$ or $q$’’ represents the statement ‘‘grass is green or pigs can fly’’.

   Here we run into a linguistic problem, since in English there are two possible meanings of the word ‘‘or’’. If someone says ‘‘I will see you today or tomorrow’’, they might mean that seeing you both today and tomorrow is possible. On the other hand, if someone says ‘‘We can stay at home tonight or go to the cinema’’, they cannot mean that both are possible. For our model to be unambiguous, we must be clear what we mean by ‘‘$p$ or $q$’’; we choose the inclusive sense (‘‘one or other or both’’) rather than the exclusive sense (‘‘one or other, but not both’’), because the inclusive sense is the one more commonly used in mathematics. Thus the truth table is as follows.

   $p$	$q$	$p$ or $q$
   $T$	$T$	T
   $T$	$F$	T
   $F$	$T$	T
   $F$	$F$	F

3. $\Rightarrow$:

   Again, suppose that $p$ represents the statement ‘‘grass is green’’, while $q$ represents ‘‘pigs can fly’’. Then ‘‘$p\Rightarrow q$’’ represents the statement ‘‘if grass is green, then pigs can fly’’ (or in other words ‘‘grass being green implies that pigs can fly’’). (In colloquial English, ‘‘then’’ is often omitted, whereas in mathematics, ‘‘if’’ is normally followed by ‘‘then’’.)

   Here we face a more serious problem than above: in colloquial English, such constructions tend only to be used when there is some causal link between the two simple statements, as in ‘‘if you study hard, then you will pass this course’’; the first statement (‘‘you study hard’’) causes or produces the second (‘‘you will pass this course’’). In our model, however, we need to be able to form ‘‘$p\Rightarrow q$’’ regardless of whether the statements represented by $p$ and $q$ are linked in this way.

   To get round this problem, we ignore the question of causality, and decide the truth or falsity of ‘‘$p\Rightarrow q$’’ entirely on the basis of the truth or falsity of $p$ and $q$. This can be decided by considering when ‘‘$p\Rightarrow q$’’ is false; this occurs only if $p$ is true, but $q$ is nevertheless false. (If you don’t study hard, then the above statement cannot be said to be false whether you pass the course or not.) Thus the truth table is as follows.

   $p$	$q$	$p\Rightarrow q$
   $T$	$T$	T
   $T$	$F$	F
   $F$	$T$	T
   $F$	$F$	T

   This has some slightly strange consequences; for example, the statement ‘‘if grass is pink, then $1+1=3$’’ is true. Starting from a silly statement, we can deduce silly or sensible things. Consider also the two statements:

   $$1+1=3$$

   both are true because the condition (‘‘$1+1=3$’’) is false.

   However, in all cases where there is a genuine causal link between the two halves of the compound statement, the truth value assigned by the model is what we would expect. What we have defined is sometimes called material implication; it extends genuine, causal implication to cover all cases of the form $p\Rightarrow q$. Untrue statements imply true statements and false statements, but a true statement cannot imply a false statement.

   Finally, note that we use ‘‘implies’’ differently from ‘‘hence’’; ‘‘hence’’ means ‘‘and so’’ or ‘‘consequently’’, and acts as a conjunction between two true statements. To exemplify how this differs from our use of ‘‘implies’’, compare the two statements:

   • $r\colon$

     ‘‘I have drunk a bottle of vodka implies that I shall fall over’’;

   • $t\colon$

     ‘‘I have drunk a bottle of vodka, hence I shall fall over’’.

   Here $r$ is true, whereas $t$ is false. Indeed, we can express $r$ as the conditional statement ‘‘if I had drunk a bottle of vodka, then I would fall over’’, which is true; the condition, however, is not satisfied — I have not drunk a bottle of vodka (and this is why $t$ is false).

4. $\Leftarrow$:

   This is now easy; ‘‘$p\Leftarrow q$’’ means the same as ‘‘$q\Rightarrow p$’’. Thus the truth table for ‘‘$p\Leftarrow q$’’ is as follows.
   

   $p$	$q$	$p\Leftarrow q$
   $T$	$T$	T
   $T$	$F$	T
   $F$	$T$	F
   $F$	$F$	T

   We call the compound statement ‘‘$q\Rightarrow p$’’ the converse of ‘‘$p\Rightarrow q$’’.

   Important note: these two compound statements are not equivalent. To see this, consider for instance the following two basic statements:

   • $p\colon$

     ‘‘I have drunk a bottle of vodka’’;

   • $q\colon$

     ‘‘I fall over’’.

   As observed above, the statement ‘‘$p\Rightarrow q$’’ is true. (If I had drunk a bottle of vodka, then I would fall over.) However, the converse statement ‘‘$q\Rightarrow p$’’ is false; for instance, I might fall over because I stumbled over the computer cable, so $q$ could well be true without $p$ being true.

5. $\Leftrightarrow$:

   Finally we define ‘‘$p\Leftrightarrow q$’’ (read ‘‘$p$ if and only if $q$’’) to mean ‘‘$(p\Rightarrow q)\ \&\ (q\Rightarrow p)$’’. From the above, we see that the truth table is as follows.

   $p$	$q$	$p\Leftrightarrow q$
   $T$	$T$	T
   $T$	$F$	F
   $F$	$T$	F
   $F$	$F$	T

As in the parity model, we may go on to construct truth tables for more complicated compound statements by using the tables already given and building up new ones column by column. As before, if only two basic statement variables are involved, then the truth table needs $2^{2}=4$ rows, whereas if there are three basic statement variables, then the truth table must have $2^{3}=8$ rows to allow for all possible combinations of the truth values.

In general, we can introduce basic statement variables $p,\,q,\,r,\,s,\,t,\,\ldots$ and build up compound statements from them. The corresponding truth tables need to allow all possible combinations of $T$ and $F$ for these statement variables, and therefore:

if a compound statement involves $n$ basic statement variables,

then there should be $2^{n}$ rows in the corresponding truth table.

We shall now give an example of how to construct the truth table for a compound statement built from basic statement variables and connectives.

Once we know how to construct truth tables, we can use them to verify that certain compound statements are logically equivalent, as we shall do in the following examples. Some of these logical equivalences will be useful later in the course.

Solution. We construct the truth tables.

As the fourth and seventh columns are the same, we conclude that the statements ‘‘$\neg(p\ \text{or}\ q)$’’ and ‘‘$(\neg p)\ \&\ (\neg q)$’’ are logically equivalent.

Solution. We construct the truth tables.

As the third and sixth columns are the same, we conclude that the statements ‘‘$p\Rightarrow q$’’ and ‘‘$(\neg q)\Rightarrow(\neg p)$’’ are logically equivalent. This result is called the law of contraposition and will be important in our study of proof techniques in the next chapter.

Solution. We construct the truth tables.

As the fourth and sixth columns are the same, we conclude that the statements ‘‘$\neg(p\Rightarrow q)$’’ and ‘‘$p\ \&\ (\neg q)$’’ are logically equivalent. Again, this result will be useful when we shall study proofs in the next chapter.