2
$\begingroup$

I am trying to prove that

$p \leftrightarrow q \equiv (p\lor q)\to(p \land q)$

and am really lost in the steps to solve this.

So far I have:

$p \leftrightarrow q \equiv (p\to q)\land(q\to p) \qquad$|equivalence
$p \leftrightarrow q\equiv (\neg p\lor q)\land(\neg q\lor p) \qquad$|implication

and I am not sure how to proceed from here. Any advice would be greatly appreciated!

edit:

Thanks to lord farin i now have

≡ (~p ∨ q) ∧ (q → p) Implication Law
≡ (q → p) ∧ (~p ∨ q) Commutative Law
≡ (q → p ∧ ~p ) ∨ (q → p ∧ q) Distributive Law
≡ (~p ∧ q → p) ∨ (q ∧ q → p) Commutative Law

but i am unsure of how to get there still.

$\endgroup$
1
  • $\begingroup$ i forgot to add that the first step p↔q≡(p→q)∧(q→p)p↔q≡(p→q)∧(q→p)|equivalence is mandatory and i am to work from there to prove it $\endgroup$
    – Damien Lim
    May 16, 2016 at 18:56

4 Answers 4

3
$\begingroup$

The trick is to expand only one of the two implications materially at first:

$$\begin{align*} (p\to q)\land(q \to p) &\equiv (\neg p \lor q)\land (q\to p)\\ &\equiv \underbrace{(\neg p \land q \to p)}_{\downarrow} \lor \underbrace{(q \land q\to p)}_\downarrow& & \text{distribution}\\ &\equiv \underbrace{(\neg p \land \neg q) \hspace{1.5em} \lor\quad(p \land q)}_\downarrow\\ &\equiv \hspace{2em}(p \lor q) \to (p \land q) \end{align*}$$

I'll leave it up to you to take care of the transitions represented by the arrows.


Additional details: For the first two, you can rewrite the conditionals, then use distribution of the $\land$. For e.g. the first, this will leave $(\neg p \land \neg q) \lor (\neg p \land p)$, the second term of which is always false. Thus the whole expression is equivalent to $\neg p \land \neg q$.

A similar approach works for $q \land q \to p$.

$\endgroup$
2
  • $\begingroup$ im really sorry but can you please expand on the first arrow transitions? Ive spent a few hours to no avail on how to get it there. $\endgroup$
    – Damien Lim
    May 17, 2016 at 9:04
  • $\begingroup$ @DamienLim See edit. $\endgroup$
    – Lord_Farin
    May 17, 2016 at 17:03
0
$\begingroup$

\begin{align} (p\lor q)\to(p \land q) & \equiv (p\lor q)'\lor(p \land q)\\ & \equiv (p'\land q')\lor(p \land q)\\ & \equiv (p'\lor(p \land q))\land (q'\lor(p \land q))\\ & \equiv ((p'\lor p) \land (p'\lor q))\land ((q'\lor p) \land (q'\lor q))\\ & \equiv (T \land (p'\lor q))\land ((q'\lor p) \land T)\\ & \equiv (p'\lor q)\land (q'\lor p)\\ & \equiv (p\rightarrow q)\land (q\rightarrow p)\\ & \equiv p \leftrightarrow q \end{align}

$\endgroup$
1
  • $\begingroup$ To downvoter: could you please explain what is wrong with this answer? $\endgroup$
    – CiaPan
    Jul 29, 2016 at 9:52
0
$\begingroup$

$(1)$ equivalence consists of two implications in opposite directions

$(2)$ it is enough to negate just one of the two implications in order to negate the equivalence

$(3)$ truth can imply no lie, therefore, to negate an implication, the second predicate must be negated, while the first stays unchanged

Having in mind these simple facts, no other tool is required. $$\neg(\neg P)\equiv P$$ $$\neg(\neg (p\iff q))\equiv p\iff q$$ $$\neg((p\wedge \neg q)\vee(\neg p\wedge q))\equiv p\iff q$$ Neutral for disjunction: $$\neg(((p\wedge \neg q)\vee (q\wedge \neg q))\vee((\neg p\wedge q)\vee (p \wedge \neg p)))$$ Distribution: $$\neg(((p\vee q)\wedge\neg q)\vee ((p \vee q)\wedge \neg p))\equiv\neg((p\vee q)\wedge(\neg p \vee \neg q))\equiv \neg((p\vee q)\wedge \neg(p\wedge q))$$ Finally: $$\neg(\neg((p\vee q)\implies(p\wedge q)))\equiv(p\vee q)\implies(p\wedge q)$$

Hope it helps. So, you can see how, using 'primitive' elementary tools, we can transform more complicated statements.

$\endgroup$
-2
$\begingroup$

You could write equivalence as $(p \land q) \lor (\lnot p \land \lnot q)$, which gives us, using commutation and implication law, the result you desire.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .