Tautological statements [closed]

Question

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?

Answer 1

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.