Are there some techniques for checking whether a statement implies another without truth tables?

Question

Are there some techniques for checking whether a statement implies another without truth tables?

For example, I was asked whether $P\Longrightarrow P_{1}$ given the following statements:

$$P: [p \land (q \land r)]\lor \neg[p \lor (q \land r)],$$

$$P_{1}: [p \land (q \lor r)]\lor \neg[p\lor(q\lor r)].$$

What I did was to find the logical equivalences of the negations of $\neg[p \lor (q \land r)]$ and $\neg[p\lor(q\lor r)]$, then tested some values, with the negations done, it was slightly easier to see what was happening as I drew 0's and 1's under $p,q,r$. I find that for $p:0,q:1,r:0$, $P$ and $P_{1}$ does not have the same truth statement, so $P\nRightarrow P_{1}$, yet it was still a tedious process.

Answer 1

Yes. I always think of using truth tables as a last resort; sometimes it actually pays off because the effort spent constructing the truth table can be considerably less than that using logical deductions, but there is not much at all learned by proving something with a truth table--it's very mechanical.

When trying to prove an implication of the form $\Omega\to\Psi$ without using a truth table, your job is to show that, given $\Omega$, the implication $\Omega\to\Psi$ is a tautology. I will give you two examples of how to check whether or not a statement implies another without a truth table (the first will not be a tautology but the second will be).

Example 1: Given $p$, does $p\to(p\land q)$?

Solution. Notice the following: \begin{align} p\to(p\land q) &\equiv \neg p\lor(p\land q)\tag{since $r\to s\equiv \neg r\lor s$}\\[0.5em] &\equiv \underbrace{(\neg p\lor p)}_{\text{Always true}}\;\;\land\underbrace{(\neg p\lor q)}_{\substack{\text{True if $q$ is true}\\\text{False if $q$ is false}}}\tag{distributivity} \end{align} Hence, the implication $p\to(p\land q)$ is not a tautology since it will be false when $q$ is false.

Example 2: Given $p\land q$, does $(p\land q)\to p$?

Solution. Notice the following: \begin{align} (p\land q)\to p &\equiv \neg(p\land q)\lor p\tag{since $r\to s\equiv \neg r\lor s$}\\[0.5em] &\equiv (\neg p\lor\neg q)\lor p\tag{DeMorgan}\\[0.5em] &\equiv \underbrace{(\neg p\lor p)}_{\text{Always true}}\lor\neg q.\tag{associativity of $\lor$} \end{align} Since $\neg p\lor p$ is always true, we have that $(p\land q)\to p$ is a tautology, and we proved this without using a truth table.

Answer 2

You could write a proof instead. Suppose $P$.

If $p\land q\land r$, then $p\land(q\lor r)$. Therefore $P_1$ tautologically.

Otherwise $\neg[p \lor (q \land r)]\Leftrightarrow \neg p \land \neg(q\land r)$. Then $p$ being true contradicts $P$, so $P\Rightarrow P_1$ in that case. In the case that $p$ is false, $P$ reduces to $\neg q \lor \neg r$ and $P_1$ reduces to $\neg q \land \neg r$. If $\neg q\not= \neg r$, then $P$ and not $P_1$, so $P\not\Rightarrow P_1$; otherwise $P$ and $P_1$ are both true or both false, so $P\Rightarrow P_1$.

Therefore $P\Rightarrow P_1$ exactly when $p$ is true or $q=r$, and $P\not\Rightarrow P_1$ exactly when $p$ is false and $q\not=r$.