Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
    
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
2  
@TRiG - I'm pretty sure it's just a tearful face emoticon. – Malice Vidrine Mar 7 at 17:01
up vote 19 down vote accepted

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

share|cite|improve this answer
1  
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)$.

share|cite|improve this answer

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.

share|cite|improve this answer
1  
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.

share|cite|improve this answer

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.

share|cite|improve this answer

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

share|cite|improve this answer

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

share|cite|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.