Is the following conditional statement: $\,(p\land q) \to p\,$ a tautology?

Question

Is $(p\land q) \to p$ a tautology?

So far I did the following

$$(p\land q)\to p \equiv \lnot (p\land q)\lor p \equiv (\lnot p\lor ¬q)\lor p$$

I'm having trouble trying to show that the conditional statement above is a tautology without using a truth table.

I'm assuming you would have to use logical equivalence to figure the rest of this out.

I know that a tautology is true, regardless of the truth-value assignments of the variables. Can someone help me finish this? Any additional explanation is welcome.

Answer 1

Yes, your initial work is correct:

$$(p\land q)\to p \equiv \lnot (p\land q)\lor p\tag{implication}$$

$$\equiv (\lnot p \lor \lnot q) \lor p\tag{DeMorgan's rule}$$

---

Now using the properties of associativity and commutativity of the $\lor$-operator, we have:

$$\equiv \lnot p \lor \lnot q \lor p\tag{associativity}$$

$$\equiv \lnot p \lor p \lor \lnot q \tag{commutativity}$$

$$\equiv (\lnot p \lor p)\lor \lnot q \tag{associativity}$$

$$\equiv \underbrace{(\lnot p \lor p)}_{\large \top} \lor \lnot q$$

$$\equiv \top \lor \lnot q\tag{Law of the excluded middle}$$ $$ \equiv \top \tag{annihilator of $\lor$}$$

Note that $\top$ is represents tautologically true.

This is true regardless of the truth value assigned to p or to q.

Answer 2

Here is a method called the 'short truth-table' method. As the name implies, it is not a full truth-table.

The idea is that you try to make the statement false ... and if you find that you cannot do that, then that means that the statement must be true, i.e. it is a tautology.

OK, so let's see what it would take for $(p \land q) \rightarrow p$ to be False. Well, a conditional can only be false when the antecedent is true, and the consequent is false. So, in order for $(p \land q) \rightarrow p$ to be false, we need that $p \land q$ is True, and that $p$ is False. OK, but for $p \land q$ to be True, both $p$ and $q$ need to be True. But that means we have a problem, because now we have that $p$ must both be True and False. So ... we conclude that it is impossible for $(p \land q) \rightarrow p$ to be False ... meaning it is a tautology.

Here is that same method, but simply with annotating the statements (the indices show the order in which I place the truth-values, and the red shows the contradiction):

\begin{array}{ccccccc} ( & p & \land & q & ) & \rightarrow & p\\ \hline & \color{red}T_4 & T_2 & T_5 && F_1 & \color{red}F_3\\ \end{array}

Another thing you can do is a formal proof: if you can derive $(p \land q) \rightarrow p$ from no premises at all, then that means the statements is a tautology. Here is a proof using a proof system called Fitch (there are many different proof systems):

Answer 3

We will massage $$(p\wedge q) \rightarrow p$$ into $\mbox{TRUE}$ showing justifications for each step.

By definition of the "implies" relation, $$(p\wedge q) \rightarrow p = \lnot (p\wedge q) \lor q$$

By negation of an and relationship $$(p\wedge q) \rightarrow p = \lnot (p\wedge q) \lor p = ( (\lnot p) \lor (\lnot q) \lor p $$ By associativity and commutativity of the or relationship

$$(p\wedge q) \rightarrow p =(\lnot p) \lor ((\lnot q) \lor p ) = (\lnot p) \lor (p \lor (\lnot q) ) = ((\lnot p) \lor p) \lor (\lnot q) $$

By the "law of the excluded middle" $$(p\wedge q) \rightarrow p = ((\lnot p) \lor p) \lor (\lnot q) = (\mbox{TRUE}) \lor q$$

By the axiom that $\forall s: \mbox{TRUE} \lor s = \mbox{TRUE} $ $$(p\wedge q) \rightarrow p = (\mbox{TRUE}) \lor q = \mbox{TRUE}$$