# Tautological statements [closed]

I have been tasked with finding how many of the following statements are tautologies, and was wondering which method would be the best to solve this assignment fast. My teacher said I should use no more than 5 minutes on it. How can I quickly spot which of these statements are tautologies?

• A tautology is always true. Figure out the general form of the statements, and the conditions which would make them false. Then check if those conditions are possible. Ex. 5) An if and only if statement is true if both sides have the same truth value, as by definition not p and p have different truth values... 5) is actually a contradiction and is never true. Sep 23 at 13:36
• Well, to start, look for the one which is sublimely, ridiculously false. Now you're down to 4 in just a few seconds. Sep 23 at 13:48
• @MarcusK.Johnson The point is that it isn't necessary to construct the entire truth table. Have you been taught about reductio ad absurdum?
– zaq
Sep 23 at 16:35
• For every formula whose main connective is the arrow "$\to$," I suggest assigning a truth value of "False" to the connective and then reasoning backwards to determine the truth values of the propositional variables on each side of the arrow. In the process of doing so, if you find that a contradiction exists, then the formula cannot be false and must be tautology. Otherwise, if no contradiciton exists, then it is indeed possible for the formula to be false, implying it is not a tautology. Sep 23 at 17:42
• For every formula whose main connective is the biconditional "$\leftrightarrow$," one approach is to manipulate one or both sides of the biconditional using logically equivalent statement forms until both sides of the biconditional are the same exact expression. In this event, both sides of the biconditional will always have the same truth value, implying the formula is a tautology. Sep 23 at 17:47

Since no one seems to be mentioning it and since I'm actually having some trouble finding an English-language source for what I'm talking about, I'll describe here the method of reductio ad absurdum. Reductio ad absurdum is essentially a pretentious philosophical name for the method of contradiction (literally means reduction to the absurd).

I'll demonstrate the method on the tautology $$P \rightarrow (P \lor Q)$$. We want to check if it is possible that this sentence is in some case false. We begin by assuming the sentence is false and writing a $$0$$ under the conditional.

$$P \underset{0}{\rightarrow} (P \lor Q)$$

Now we see what must hold if the conditional is false. For a conditional to be false, the left-hand side must be true and the right-hand side false. So, we write a $$1$$ under the $$P$$ and a $$0$$ under the outer connector of the right-hand side (in this case, $$\lor$$).

$$\underset{1}{P} \underset{0}{\rightarrow} (P \underset{0}{\lor} Q)$$

We continue with this process until we obtain the values of all of the atomic formulas. In this case, there is only one step left: for a disjunction to be false, both terms of it must be false. So we write a $$0$$ under the $$P$$ and under the $$Q$$.

$$\underset{1}{P} \underset{0}{\rightarrow} (\underset{0}{P} \underset{0}{\lor} \underset{0}{Q})$$

Notice that we've obtained a contradiction: $$P$$ is simultaneously true and false in this sentence. Therefore, it is impossible for this sentence to be false under any interpretation, so it is a tautology.

If the sentence is more complicated, we might need multiple rows to check all of the cases. For example, consider the tautology $$\neg (P \lor Q) \leftrightarrow (\neg P \land \neg Q)$$. We write a $$0$$ under the biconditional, but then we notice that a biconditional can be false in two cases: if the left-hand side is false and the right-hand side is true, or if the left-hand side is true and the right-hand side is false. So we write down two rows for the two cases.

$$\underset{\substack{0 \\ 1}}{\neg} (P \lor Q) \underset{\substack{0 \\ 0}}{\leftrightarrow} (\neg P \underset{\substack{1 \\ 0}}{\land} \neg Q)$$

At this point, some finesse is required in extracting information. For example, let's focus on the first row. In order for the conjunction to be true, both terms must be true, so both $$P$$ and $$Q$$ must be false:

$$\underset{0}{\neg} (P \lor Q) \underset{0}{\leftrightarrow} (\underset{1}{\neg} \underset{0}{P} \underset{1}{\land} \underset{1}{\neg} \underset{0}{Q})$$

On the left-hand side, we see that the negation of $$\lor$$ is false, so $$\lor$$ is true. Copying over that both $$P$$ and $$Q$$ are false, we have

$$\underset{0}{\neg} (\underset{0}{P} \underset{1}{\lor} \underset{0}{Q}) \underset{0}{\leftrightarrow} (\underset{1}{\neg} \underset{0}{P} \underset{1}{\land} \underset{1}{\neg} \underset{0}{Q})$$

This is a contradiction, since both $$P$$ and $$Q$$ are false, but $$P \lor Q$$ is true. That completes the first row and the second row can be similarly checked to end in contradiction. It was also possible to check the first row by again writing out the subcases on when $$\lor$$ is false (if we didn't think of first copying over the values of the atomic formulas), but this would obviously take longer. To be fair, you can really always just copy the values of the atomic formulas to all of their places in the sentence right after you obtain them and this will always be faster.

Finally, let's see how the method produces a counterexample when the sentence is not a tautology. Take $$P \rightarrow (P \land Q)$$. Assuming that it is false, we get

$$\underset{1}{P} \underset{0}{\rightarrow} (P \underset{0}{\land} Q)$$

Now we copy over the value of $$P$$:

$$\underset{1}{P} \underset{0}{\rightarrow} (\underset{1}{P} \underset{0}{\land} Q)$$

and we've used up all of the information without obtaining a contradiction. Setting $$Q = 0$$ here gives a valid formula, so this sentence isn't a tautology.

To work out example $$(1)$$ from your post, set the main conditional to $$0$$. Then the right-hand side must be $$0$$, so we have

$$(((p \land r) \rightarrow q) \land (q \rightarrow r)) \underset{0}{\rightarrow} ((p \land r) \underset{0}{\rightarrow} r)$$

Following up on the right-hand side, we get

$$(((p \land r) \rightarrow q) \land (q \rightarrow r)) \underset{0}{\rightarrow} ((\underset{1}{p} \underset{1}{\land} \underset{1}{r}) \underset{0}{\rightarrow} \underset{0}{r}),$$

which is immediately a contradiction since $$r$$ is simultaneously $$1$$ and $$0$$. The rest can be done similarly and it'll take you a few seconds for each.

• This method is called the ‘indirect truth table’ or ‘short truth table’ method. Sep 23 at 22:03
• Interesting. RAA is the standard name for much of the non-English-speaking world.
– zaq
Sep 24 at 19:15
• Yes, the short truth-table method is a kind of RAA …. if you get a contradiction… which you don’t always get … But RAA is a much more general proof technique that can be used in settings that have nothing to do with evaluating statements or propositional logic. It is this specific method of assigning truth-values to statements and seeing what happens that makes it the short truth-table method. And in doing so it is different from the full truth-table method, and from the formal proof method, and from the tree method, etc. Sep 24 at 19:45