# 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. – Jared Mar 7 at 1:21
Another question about the same formula: math.stackexchange.com/questions/275689/… – Martin Sleziak Mar 7 at 9:15
What does "T.T." in the middle of your question mean? – TRiG Mar 7 at 16:14
@TRiG - I'm pretty sure it's just a tearful face emoticon. – Malice Vidrine Mar 7 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. – Danny Mar 7 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. – Carl Witthoft Mar 7 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.

-

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$.

-

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}$$

-