# Show that (p ∧ q) → (p ∨ q) is a tautology?

I am having a little trouble understanding proofs without truth tables particularly when it comes to →

Here is a problem I am confused with:

Show that (p ∧ q) → (p ∨ q) is a tautology

The first step shows: (p ∧ q) → (p ∨ q) ≡ ¬(p ∧ q) ∨ (p ∨ q)

I've been reading my text book and looking at Equivalence Laws. I know the answer to this but I don't understand the first step.

How is (p ∧ q)→ ≡ ¬(p ∧ q)?

If someone could explain this I would be extremely grateful. I'm sure its something simple and I am overlooking it.

The first thing I want to do when seeing this is
(p ∧ q) → (p ∨ q) ≡ ¬(p → ¬q)→(p ∨ q)

¬ (p ∧ q) ∨ (p ∨ q) (by logical equivalence)

I don't see a equivalence law that explains this.

• It seems pretty obvious to me, the negation of the conclusion is $\neg p \wedge \neg q$ which clearly falsifies the hypothesis. Mar 7, 2016 at 1:21
• Another question about the same formula: math.stackexchange.com/questions/275689/… Mar 7, 2016 at 9:15
• What does "T.T." in the middle of your question mean?
– TRiG
Mar 7, 2016 at 16:14
• @TRiG - I'm pretty sure it's just a tearful face emoticon. Mar 7, 2016 at 17:01

It is because of the following equivalence law, which you can prove from a truth table: $$r\rightarrow s\equiv \lnot r\lor s.$$ If you let $r = p\land q$ and $s = p\lor q$, you get what you are looking for, namely that $$(p\land q)\rightarrow (p\lor q)\equiv \lnot(p\land q)\lor(p\lor q).$$

• Thank you! I was unaware you could do it like that. Mar 7, 2016 at 1:26

This is a classic equivalence $$p\to q \equiv \neg p\lor q.\tag 1$$

We can examine equivalence using a truth table \begin{array}{c|c|c|c|c} p&q&\neg p&p\to q&\neg p\lor q\\\hline T&T&F&T&T\\\hline T&F&F&F&F\\\hline F&T&T&T&T\\\hline F&F&T&T&T \end{array}

Hence, $p\to q\equiv \neg p\lor q$.

Further, if $a \equiv p\land q$ and $b\equiv p\lor q$, and so
$$a\to b\equiv \neg a\lor b\equiv \neg(p\land q)\lor(p\lor q)\equiv (\neg p\lor \neg q)\lor (p\lor q),$$ by using $(1)$.

To show (p ∧ q) → (p ∨ q).

If (p ∧ q) is true, then both p and q are true, so (p ∨ q) is true, and $T \to T$ is true.

If (p ∧ q) is false, then (p ∧ q) → (p ∨ q) is true, because false implies anything.

Q.E.D.

• True, but doesn't address what seems to be the main question. Mar 7, 2016 at 21:01

I know you asked specifically about a given proof, but here is another way:

(1) Assume p ∧ q

(2) By ∧-elimination, p

(3) By ∨-introduction, p ∨ q

(4) By →-introduction and marking the assumption (1), (p ∧ q) → (p ∨ q).

In less formal language: if P and Q is true, then you can look at either P or Q separately and it must be true. Now from any true statement you can create a longer true statement by creating a disjunction with any statement: if P is true, then "P or R" is also true for any statement R (e.g. if you are sure "it is raining", then it is also the case that "it is raining or you are a dragon"). In particular taking R = Q in this case allows you to reason that P or Q is true.

Combine your first step with De Morgan's Law:

$$\begin{array}{rcll} (p ∧ q) → (p ∨ q) & ≡ & ¬(p ∧ q) ∨ (p ∨ q) & \text{Definition of →} \\ & ≡ & (¬p ∨ ¬q) ∨ (p ∨ q) & \text{De Morgan's Law}\\ & ≡ & (¬p ∨ p) ∨ (¬q ∨ q) & \text{Associativity and commutativity of ∨} \\ & ≡ & T ∨ T \\ & ≡ & T\\ \end{array}$$

Alternately:

 p ∧ q        Assumed           <--------\
p            base Extract P ∧ Q ⊢ P     |
p ∨ q        base Widening P ⊢ P ∨ Q    |
(p∧q)→(p∨q)  pop assumption            -/


This isn't quite rendering right -- need a fixed width font.

As $\lnot p\lor p$ is trivial and $p→q$ means $p$ necessitates $q$. This gives $\lnot p\lor q$.

The following is an inference rule approach to showing that $P \to Q \equiv \neg P \lor Q$, using the Constructive Dillema inference rule:

$$\large \frac{P \to Q,~ R \to S, ~P \lor R}{ Q \lor S}$$

It can be shown that $\neg P \lor P$ and $\neg P \to \neg P$ are tautologies, and given that we know $P \to Q$ , we can substitute into the above inference rule.

$$\large \frac{ \neg P \to \neg P,~P \to Q,~ ~\neg P \lor P}{ \neg P \lor Q }$$

So far we have shown that $(P \to Q) ~\vdash (\neg P \lor Q)$. To finish proving the equivalency $P \to Q \equiv \neg P \lor Q ~$ we also need to show $(\neg P \lor Q) \vdash (\neg P \lor Q)$. I don't see an obvious inference rule at this point, but we could show it by contradiction.