14
$\begingroup$

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.

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

8 Answers 8

20
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Thank you! I was unaware you could do it like that. $\endgroup$
    – Danny
    Mar 7, 2016 at 1:26
19
$\begingroup$

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

$\endgroup$
0
7
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ True, but doesn't address what seems to be the main question. $\endgroup$ Mar 7, 2016 at 21:01
6
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

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

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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