Truth values of formulae

If we have some atomic statements and combine them into a formula, we can try to decide whether the whole formula is true or false.

Truth of a statement

First we make precise what the truth value of a statement is. Given a statement p, we should be able to decide whether it is true or false. A true statement has truth value 1 and a false one has 0.

A truth assignment is then a rule e that gives a given statement either 0 or 1. If we write e(p), we want to find out whether the statement p is true. If p is the statement “twice two is four”, then e(p) = 1, because it is a true statement. If q is the statement “Oliver is a woman”, then e(q) = 0, because Oliver is not a woman. So e is a function that tells us whether a statement is true.

It is important to realise that e is not some magic function that knows everything in the world. It behaves the way we tell it to. It does not know whether Oliver is a man or a woman. At the start of a calculation we should declare how the evaluation function is to behave. If we tell it that Oliver is a woman, it will return e(q) = 1.

Truth of logical connectives

To determine the truth of a formula, we need to know how to evaluate the truth of logical connectives. That is, if we know the assignments e(p) and e(q), what will the truth value of formulae such as p ∧ q or p ⇒ q be?

Each logical connective behaves differently and is used for something different, so we will go through each connective separately.

Truth of conjunction

Conjunction is written p ∧ q and read “p and at the same time q”. As an example, take the formula “The United Kingdom lies in western Europe and at the same time its capital city is London”. When will this whole sentence be true?

The connective “and at the same time” itself helps us decide. It says explicitly that it wants both statements, on the left and on the right, to be true. So if both statements p and q are true, that is e(p) = 1 and e(q) = 1, then the whole conjunction is true. Otherwise, when one of the statements is false or both are false, the whole formula is false.

An example of a conjunction that is not true is: “The Thames is a river and at the same time the Thames flows through Russia”. It is true that the Thames is a river, but it is not true that it flows through Russia, so the whole conjunction is not true.

The following table shows this at a glance:

$$\begin{array}{ccc}p& q& p\wedge q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 0\end{array}$$

The first two columns contain the truth values of the statements p and q, and the third contains the truth value of the formula p ∧ q.

Truth of disjunction

Disjunction is written p ∨ q and read “p or q”. An example: “Russia lies in Europe or in Asia.” When will the whole sentence be true?

For a disjunction it is enough for at least one of the options to be true. The connective “or” gives us a choice, and it is enough for its left or right part to be true. The only small difference from everyday speech is that the logical “or” is true even when both statements hold at the same time. That is not usually the case: in everyday speech we often use “or” in an exclusive way, that is “either … or …”

There is a classic joke about this: a family is choosing a new car at a used-car dealer’s. Dad tells the salesman, “we’ve decided to take a blue or a red car”. The salesman sold them both cars. This illustrates the difference between the logical “or” and the spoken “or”: Dad probably meant that they would choose exactly one of the cars, whereas the salesman considered it a valid option to sell them both.

The previous sentence about Russia is true because both statements are true. The sentence “the number 7 is divisible by 3 or the number 7 is prime” is true because seven is a prime number. It is not divisible by three, but that doesn’t matter to us now. The truth table:

$$\begin{array}{ccc}p& q& p\vee q\\ 1& 1& 1\\ 1& 0& 1\\ 0& 1& 1\\ 0& 0& 0\end{array}$$

Truth of implication

Implication is written p ⇒ q and read “if p, then q”. An example of an implication is the sentence “if we drink a lot of vodka, then we will be sick”. When is the sentence true?

Logical implication is the trickiest of all the connectives, and even in everyday speech it is often misunderstood and confused with the biconditional. Let’s try to answer the question of whether the converse implication q ⇒ p also holds.

We know that if we drink a lot of vodka, then we will be sick. Is it also true that if we are sick, then we drank a lot of vodka? That certainly isn’t true: we could have drunk a completely different kind of alcohol and still felt ill, or we might feel ill from something else entirely. So the converse implication does not have to hold automatically. If p ⇒ q holds and q ⇒ p holds as well, it is a biconditional (equivalence), see below.

Another example: “if it rains tomorrow, then Tommy will take an umbrella with him”. Now I tell you that Tommy did take an umbrella with him. The question is: did it rain that day? A lot of people tend to say that of course it did, because Tommy took an umbrella when it was supposed to rain. But that is not how the original sentence is built!

Tommy may in fact have taken the umbrella for some other reason we have no idea about. Perhaps Tommy always takes an umbrella when he goes to visit his mother-in-law, so that he can poke her eye out. Or he decided to buy a new umbrella and wants to throw the old one away. These are all perfectly legitimate reasons why Tommy might have taken an umbrella even though it didn’t have to rain.

Now we can answer the question of when an implication is true. When both statements are true, the implication is definitely true: “if 42 is a positive integer, then it is positive”. Both statements are true, so the whole implication is true. Another example is the implication “if 42 is a positive integer, then it is negative”. This implication is not true, because from a truth we are trying to derive something that isn’t true.

Finally, there are the cases where the first statement is false. In that case we no longer care about the truth of the second statement. If we start from a falsehood, we can go on babbling whatever we like. These are sentences like “if 1 is a negative number, then I’m the king of comedy” or “if the Thames is a well-known pop group, then the sun is blue”. In such cases the implication is automatically true, simply because it starts from a falsehood. The table:

$$\begin{array}{ccc}p& q& p\Rightarrow q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 1\\ 0& 0& 1\end{array}$$

Truth of the biconditional

The biconditional (equivalence) is written p ⇔ q and read “p if and only if q”. An example of a biconditional is “the number x is divisible by two if and only if it is even”. When will the whole sentence be true?

For a biconditional we expect the two statements to be in such symbiosis that either both hold or neither does. So either the number x is even and also divisible by two, or it is neither. The case where x was even but not divisible by two cannot occur.

An example: “Jack reads a book if and only if he is sitting on the toilet.” For the biconditional to hold, whenever Jack is sitting on the toilet he must be reading a book. And at the same time, whenever he is reading a book, he must be sitting on the toilet. It can’t happen that he reads a book in bed, say.

We can express a biconditional using two implications. So p ⇔ q could be rewritten as p ⇒ q and at the same time q ⇒ p. The table:

$$\begin{array}{ccc}p& q& p\iff q\\ 1& 1& 1\\ 1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}$$

Negation

Negation is a unary operation, written either with a prime p' or with this symbol: ¬p. Negation negates the original claim. Given the statement “Amelia is a singer”, the negation gives the statement “It is not true that Amelia is a singer”, or in short “Amelia is not a singer”. Almost always we can form a negation by putting “It is not true that…” in front of the statement.

Negation reverses the truth value, that is, it turns 0 into 1 and 1 into 0. So we can write ¬0 = 1 and ¬1 = 0.

Watch out for some tricky things. Take the claim “chalk is white”. What is its negation? Someone might think of “chalk is black”, but that isn’t right! Using the rule above, the negation is the statement “it is not true that chalk is white”. Does that necessarily mean it must be black? No, it could be bright pink, for example.

Table of all the connectives

$$\begin{array}{cccccc}p& q& p\wedge q& p\vee q& p\Rightarrow q& p\iff q\\ 1& 1& 1& 1& 1& 1\\ 1& 0& 0& 1& 0& 0\\ 0& 1& 0& 1& 1& 0\\ 0& 0& 0& 0& 1& 1\end{array}$$

Truth of a whole formula

We can now evaluate the truth of two statements joined by a logical connective. We evaluate a whole formula in exactly the same way. If we have the formula (p ⇒ q) ∧ r, then once we evaluate the formula (p ⇒ q), say as 1, we get the classic conjunction 1 ∧ r, which we already know how to solve.

By applying the simplest logical connectives step by step, we arrive at the final truth value of the whole formula. For this we often use the so-called truth table method, which is described next.

Truth table method

The truth table method is used to evaluate more complicated formulae. In the first n columns we write the n propositional variables that the formula works with, and in the further columns we gradually add the subformulae that the formula contains. An example will make it clearer:

Take the formula (p ∨ q) ∧ (q ⇒ p). At the start we write all the propositional variables in the table, that is p and q, and all the combinations of their assignments:

$$\begin{array}{cc}p& q\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Next we add columns for the individual subformulae p ∨ q and q ⇒ p.

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

Now we evaluate these formulae and fill the columns with zeros and ones. The table holds all the information we need. We proceed like this: when evaluating p ∨ q in the first row, we substitute 1 for p and 1 for q as well. That gives the expression 1 ∨ 1. Evaluating this expression gives 1 again, so we write a one in the table:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1\\ 1& 0\\ 0& 1\\ 0& 0\end{array}$$

We fill in the whole table step by step:

$$\begin{array}{cccc}p& q& p\vee q& q\Rightarrow p\\ 1& 1& 1& 1\\ 1& 0& 1& 1\\ 0& 1& 1& 0\\ 0& 0& 0& 1\end{array}$$

Now it remains to evaluate the whole formula. Let’s call it φ = (p ∨ q) ∧ (q ⇒ p). We add a column for φ to the table and evaluate it, this time using the previous two columns.

$$\begin{array}{ccccc}p& q& p\vee q& q\Rightarrow p& \phi \\ 1& 1& 1& 1& 1\\ 1& 0& 1& 1& 1\\ 0& 1& 1& 0& 0\\ 0& 0& 0& 1& 0\end{array}$$

The table is now complete and gives us the truth value of the formula for all possible assignments. For example, if e(p) = 1 and e(q) = 1 at the same time, then the formula is true. If e(p) = 0 and e(q) = 1, then the formula is not true.

Notice that we can’t say “the formula is true”. That sentence makes no sense, because to say that a formula is true, we would have to say under which assignment it is true. So we can say that “the formula φ is true under the assignment e₁ and is not true under the assignment e₂”.

The only case in which we could say that a formula is true is when it is true under all possible assignments. For example, the formula p ∨ ¬p is true under all assignments, so we can say that the formula is true. Similarly for the case when a formula is false under all assignments.

Such formulae have special names. A formula that is true under all assignments is called a tautology. A formula that is satisfied under no assignment is called a contradiction.