Is this proof correct? I'm trying to prove a tautology without truth tables.

Conclude that $(p\land q)\rightarrow p$ is a tautology without using truth tables. Here's what I did: $$(p\land q)\rightarrow p \equiv \lnot(p\land q)\lor p$$ By De Morgan's Law: $$\lnot(p\land q)\lor p\equiv \lnot p\lor \lnot q\lor p$$ Then By the Associative Property: $$\lnot p\lor \lnot q\lor p\equiv \lnot q \lor(\lnot p\lor p)$$

After this, I specified that $\lnot p\lor p$ is always true, so by the definition of a disjunction $\lnot q \lor(\lnot p\lor p)$ must also be true. Therefore, since $(p\land q)\rightarrow p\equiv \lnot q \lor(\lnot p\lor p)$ and $\lnot q \lor(\lnot p\lor p)$ is always true, it stands to reason that $(p\land q)\rightarrow p$ is also always true.

However, my textbook simply says "If the hypothesis $p\land q$ is true, then by the definition of conjunction, the conclusion $p$ must also be true."

I don't understand how this concludes the statement is a tautology. Is my proof not correct? Did I go overboard?

• I don't really see the point of "without using truth tables" but yes I think you went overboard. The statement $(p\wedge q)\rightarrow p$ could only be false if $p\wedge q$ is true and $p$ is false. But that's impossible since if $p$ were false, $p\wedge q$ would also be false. So the original statement cannot be false. This is what your book is saying and it's a correct argument but I don't see how it "doesn't use truth tables". they used the truth tables for $\wedge$ and $\rightarrow$ in the argument. Maybe they mean don't write out an explicit $4\times 4$ truth table for $p$ and $q$. – spaceisdarkgreen Jun 11 '17 at 21:13

Your proof is just fine. in fact, you might be happy to know that there are equivalence principles to do those last steps purely algebraically as well:

$$(p \land q) \to p \Leftrightarrow \text{ Implication}$$

$$\neg ( p \land q) \lor p \Leftrightarrow \text{ DeMorgan}$$

$$(\neg p \lor \neg q) \lor p \Leftrightarrow \text{ Commutation}$$

$$(\neg q \lor \neg p) \lor p \Leftrightarrow \text{ Association}$$

$$\neg q \lor (\neg p \lor p) \Leftrightarrow \text{ Complement}$$

$$\neg q \lor \top \Leftrightarrow \text{ Annihilation}$$

$$\top$$

$(p\land q)\rightarrow p$

OP: Did I go overboard? The book simply states

"If the hypothesis $p\land q$ true, then by the definition of conjunction, the conclusion $p$ must also be true."

Answer: You showed in detail that it is a tautology, but it can get tedious being so exact. In fact, the reason for defining the implication symbol is that it makes life simpler. You could make logical arguments using only negation, disjunction and conjunction, but it is cumbersome - you aren't a computer. Also, disjunction is preferred to using the 'exclusive OR' - it is a more natural way of expressing statements.

Using logical implications allows you to see a 'flow'. You can usually just jump on the premise and assume it is true, and of course you can also use the contraposition method. This "implication flow" is a comfortable way of handling tautologies and proving theorems.

Book Technique: $(p\land q)\rightarrow p\;\;\;\;\;\;$ (1)

Assume the hypothesis $p\land q\;\;\;\;\;\;\;\;$ (2) is TRUE.
We must show that $p$ is also TRUE.
But for the conjunction (2) to be TRUE, $p$ must be TRUE.
So (1) is a tautology.

Note that you also have these tautologies,

$(p\land q\land r)\rightarrow p$
$(p\land q\land r)\rightarrow q$
$(p\land q\land r)\rightarrow r$

Eventually this 'class of tautologies' can all be taken for granted.

• Thank you. This helps me understand the book's answer as well. – Joao Eanes Jun 12 '17 at 22:07

In fact, your proof is correct. You can use a truth table to ascertain that you are right:

$p$ | $q$ | $(p∧q)$ | $(p∧q)→p$

0 | 1 | _ 0 _ |___ 1

1 | 0 | _ 0 _ |___ 1

0 | 0 | _ 0 _ |___ 1

1 | 1 | _ 1 _ |___ 1

You can see that any combination of $p$ and $q$ gives TRUTH.

• That doesn't show that the proof is correct, only that the conclusion is correct, which he already knew. – md2perpe Jun 11 '17 at 21:43
• Since the proof is correct (as I mentioned) it shouldn't be proved again. I just showed that the conclusion is correct by other way. – Super-kenguru Jun 12 '17 at 7:33
• The author asked "Is my proof not correct? Did I go overboard?". And I answered that his proof is correct and got the same conclusion by other way. Read the question and answer properly, and only then start criticizing! – Super-kenguru Jun 12 '17 at 7:36
• @Super-kenguru You were probably downvoted since the question explicitly said that OP wanted to satisfy his/herself that the statement is a tautology without using truth tables. – Walt van Amstel Jun 12 '17 at 8:08

The textbook is correct as the truth value of the implication will always be true, by the way implication is defined, and hence the statement is a tautology.

The way you went about showing the statement is a tautology is also correct.

Another way of proving that it is a tautology without resorting to truth tables:

Assume that there are truth value assignments to $p$ and $q$ which make our implication false (hence assuming it is not a tautology). An implication $A\to B$ is false iff $A$ is true and $B$ is false.

Therefore we would need to have $p\land q$ true yet $p$ is false. This is a contradiction and so no such truth value assignments can be made to $p$ and $q$ hence $(p\land q)\to p$ must be a tautology.

Theorem
$(p \wedge q) \to p$.

Proof
Assume $p \wedge q.$ Then $p.$ Thus $(p \wedge q) \to p.$

This is how the formula is proven using natural deduction. I've just written the proof using text instead of inference rules.