The truth of formulas

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

The truth of the statement

The first thing we'll specify is 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 will have a truth value of 1 and a false statement will have a truth value of 0.

The truth value is then a rule e, which assigns either 0 or 1 to a given statement. If we write e(p), we want to determine the truth value of the statement p. If p is equal to the statement "two times two is four", then e(p) = 1, because it is a true statement. If q is equal to the statement "Václav Klaus is a woman", then e(q) = 0, because Vasek is not a woman. Thus e is a function that returns whether the statement is true.

The thing to remember here is that e is not some magical function that knows everything in the world. It behaves as we tell it to. It does not know whether Václav Klaus is a man or a woman. We should declare at the beginning of the calculation how the evaluation function should behave. If we tell her that Václav Klaus is a woman, she will return e(q) = 1.

The truth of propositional conjunctions

To determine the truth of a formula, we need to know how to evaluate the truth of propositional conjunctions. That is, if we know the evaluation of e(p) and e(q), what will be the truth value of the formulas p ∧ q, $p \Rightarrow q$, etc.

Each propositional conjunction behaves differently and is used for something different, so we will discuss each conjunction separately.

The truth value of the conjunction

The conjunction is denoted by p ∧ q and reads "p and also q". As an example, consider the formula "The Czech Republic is located in Central Europe and at the same time its capital is Prague". When will the whole sentence be true?

The conjunction "and at the same time" alone will help us to determine the truth. It explicitly tells us that it wants both the statements on the left and on the right to be true. Thus, if both statements p and q are true, that is, e(p) = 1 and e(q) = 1, then the entire conjunction is true. Otherwise, when either one of the statements is false or both are false, the whole formula is false.

An example of a conjunction that is not true might be "The Vltava is a river and at the same time the Vltava flows through Russia". It is true that the Vltava is a river, but it is not true that it flows in Russia, so the whole conjunction is not true.

The following table clearly states this:

$$\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 are the truth values of the statements p and q and the third column is the truth value of the formula p ∧ q.

The truth value of the disjunction

The disjunction is denoted by p ∨ q and reads "p or q". Example: "Russia is in Europe or Asia." When will the whole sentence be true?

For disjunction, we only need at least one of the options to be true. The conjunction "or" gives us the choice of whether the left or right part of the conjunction is true. The only slight difference from ordinary speech is that the logical or is true even if both statements are satisfied at the same time. This is not entirely usual; often in ordinary speech we use "or" in an exclusionary way, i.e. "either ... or ..."

There's a classic joke about this: a family is picking out a new car at a second-hand shop. The dad tells the salesman, "we've decided to get a blue or a red car". The salesman sells them both cars. This is an illustration of the difference between logical and spoken or: the dad probably meant that they would choose one of the cars, whereas the salesman considered it a valid option to sell them both cars.

The previous sentence with 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 prime. It may not be divisible by three, but that doesn't matter anymore. Truth value table:

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

Truthfulness of the implication

The implication is denoted by $p \Rightarrow q$ and reads "if p, then q". An example of an implication might be the sentence "if we drink a lot of vodka, then we will vomit". When will the sentence be true?

Logical implication is the most tricky of all conjunctions, and even in common speech it is often misunderstood and confused with equivalence. Let's try to answer the question of whether the reverse implication is also true: $q \Rightarrow p$.

We know that if we drink a lot of vodka, we will vomit. Does it also hold that if we vomit, then we have drunk a lot of vodka? It certainly doesn't, we could have drunk completely different alcohol and still be sick, or we could be sick from something else entirely. So the reverse implication may not automatically apply. If $p \Rightarrow q$ applies and $q \Rightarrow p$ applies at the same time, it is an equivalence, see below.

Another example: 'if it rains tomorrow, then Honza will take an umbrella with him'. Now, I'll tell you that Honza took his umbrella with him. The question is, did it rain that day? A lot of people tend to say that of course it did, because Honza took his umbrella with him when it was going to rain. But that's not how the original sentence is constructed!

In fact, Honza may have taken an umbrella for something else that we have no idea about. Maybe Honza takes an umbrella with him whenever he goes to visit his mother-in-law so he can poke her eye out. Or maybe he's decided to buy a new umbrella and wants to throw the old one away. These are all legitimate reasons why Honza might have brought an umbrella even though it might not be raining.

Now we can answer the question of when the implication will be true. If both statements are true, then the implication will certainly be true: "if 42 is a natural number, then it is positive". Both statements are true, so the whole implication is true. Another example would be the implication "if 42 is a natural number, then it is negative". This implication is not true because we are trying to infer something from the truth that is not true.

Finally, we are left with cases where the first statement is false. In that case, we are no longer interested in the truth of the second statement. If we start from an untruth, we can go on babbling all we want. These are sentences like "if 1 is a negative number, then we are the Chinese god of fun" or "if the Beatles are a famous construction company, then the sun is blue." In such cases, the implication is automatically true because it is simply based on an untruth. Table:

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

Truthfulness of equivalence

Equivalence is written p ⇔ q and reads "p just when q". An example of equivalence might be "the number x is divisible by two just when it is even". When will the whole sentence be true?

For equivalence, we expect the two statements to be in such symbiosis that either both are true or neither is true. So either the number x is both even and divisible by two, or it is neither. It cannot be the case that x is even but not divisible by two.

Example. In order for the equivalence to be satisfied, every time George sits 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 be that he's reading a book in bed.

Equivalence can be expressed by two implications. So p ⇔ q could be rewritten as $p \Rightarrow q$ and at the same time $q \Rightarrow p$. Table:

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

Negation of

Negation is a unary operation, we write it either with the comma p' or with this symbol: $\neg p$. Negation will invalidate our original statement. If we have the statement "Lucie Bílá is a singer", then by negation we would get the statement "It is not true that Lucie Bílá is a singer" or in short "Lucie Bílá is not a singer". We can almost always create a negation by putting "It is not true that..." in front of the statement.

The negation reverses the truth value, i.e. it makes 0 into 1 and 1 into 0. We can write $\neg0=1$ and $\neg1=0$.

Beware of some tricky things. Let's have the statement "lime is white". What is the negation? One might think that "lime is black", but that is not true! Using the previous lesson, the negation would be the statement "it is not true that lime is white". Does that necessarily mean it must be black? It doesn't, it can be pinkish.

Table of all conjunctions

$$\begin{array}{cccccc} p&q&p \wedge q&p \vee q&p \Rightarrow q&p \Leftrightarrow 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}$$

The truth of the whole formula

We can now evaluate the truth of two statements that are joined by a propositional conjunction. We will evaluate the whole formula in a completely analogous way. If we have the formula $(p \Rightarrow q) \wedge r$, then the moment we evaluate the formula $(p \Rightarrow q)$ to 1, for example, we get the classical conjunction 1 ∧ r, which we already know how to solve.

By successive application of the simplest propositional conjunctions we arrive at the final truth value of the whole formula. Often the so-called table method is used to do this, which is described next.

The tabular method

The tabular method is used when evaluating more complex formulas. In the first n columns, we write down the n propositional symbols that the formula works with, and in the next columns we successively place the subformulas that the formula contains. The example will make this clearer:

Let's have the formula $(p \vee q) \wedge (q \Rightarrow p)$. At the beginning, we write down all the propositional symbols, i.e. p and q, and all their evaluation combinations:

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

Next, let's add columns for each subformula p ∨ q and $q \Rightarrow 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 formulas and add zeros or ones to the columns. In the table we have all the necessary information. We proceed by evaluating p ∨ q in the first row, then we add 1 after p and 1 after q. This gives us the expression 1 ∨ 1. The evaluation of this expression is again 1, 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}$$

This completes the table one by one:

$$\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. For example, let's label it $\varphi=(p \vee q) \wedge (q \Rightarrow p)$. We add a column with $\varphi$ to the table and evaluate it, using the previous two columns for evaluation.

$$\begin{array}{ccccc} p&q&p \vee q&q \Rightarrow p&\varphi\\ 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 in all possible evaluations. For example, if e(p) = 1 and at the same time e(q) = 1, then the formula is true. If e(p) = 0 and e(q) = 1, then the formula is not true.

Note that we cannot say that "the formula is true". This sentence makes no sense, because to say that the formula is true, we would have to say in what valuation the formula is true. So we can say that "the formula $\varphi$ is true in the valuation e₁ and is not true in the valuation e₂".

The only case where we could say that a formula is true is if it is true in all possible evaluations. For example, the formula $p \vee \neg p$ is true in all evaluations, so we can say that the formula is true. Similarly for the case where the formula is false in all evaluations.

Such formulas then have a special label. A formula that is true in all evaluations is called a tautology. A formula that is not satisfied in any evaluation is called a contradiction.