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)
but the answer shows:
¬ (p ∧ q) ∨ (p ∨ q) (by logical equivalence)
I don't see a equivalence law that explains this.
Best Answer
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).$$