1
$\begingroup$

So I have been looking at this question all day and have made a few attempts but can't seem to get any further.

Can someone please help with me proving this algebra equation and what laws I would need to use?

Forgive me for not knowing how to use the proper symbols on this. first time here, Didn't even know there was a forum for this.

I have also looked through already answered questions, and could not find anything similar.

This is the equation I need to prove

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

So far I have

$ p \leftrightarrow q \equiv (p \to q) \land (q \to p) $ The Equivalence Law

$(p \to q) \land (q \to p) \equiv (\lnot p \lor q) \land (\lnot q \lor p) $ Implication Law

$(\lnot p \lor q) \land (\lnot q \lor p) \equiv (p \land q) \lor (\lnot p \land \lnot q) $ not sure what law(I used a truth table)

I am not sure if I am even on the right track but if I am, when does it become proved? I think I may need like 3 or 4 more laws to be used.

$\endgroup$
11
  • $\begingroup$ axiom-of-choice ??????? $\endgroup$
    – Mauro ALLEGRANZA
    May 11, 2017 at 14:15
  • $\begingroup$ the questions states to Use the laws and axioms of logic. when I was typing a tag, that is what came up... $\endgroup$
    – Noob
    May 11, 2017 at 14:16
  • $\begingroup$ What little squares? I don't see any squares? $\endgroup$
    – Noob
    May 11, 2017 at 14:16
  • $\begingroup$ Not quite sure what you need, but if one of your "laws" was derived by truth table, why don't you just check what you are trying to prove by a truth table? $\endgroup$
    – Mees de Vries
    May 11, 2017 at 14:18
  • 1
    $\begingroup$ Using LaTeX (math.meta.stackexchange.com/questions/5020/…) would avoid these problems. $\endgroup$
    – martin.koeberl
    May 11, 2017 at 14:20

1 Answer 1

Reset to default
0
$\begingroup$

That last equivalence, while true, is not in the 'standard' list of equivalences. Below is how you prove it using 'standard' equivalences:

$$p \leftrightarrow q \equiv \text{ Equivalence}$$

$$(p \rightarrow q) \land (q \rightarrow p) \text{ Implication}$$

$$(\neg p \lor q) \land (\neg q \lor p) \text{ Distribution}$$

$$((\neg p \lor q) \land \neg q)) \lor ((\neg p \lor q) \land p) \text{ Distribution x 2}$$

$$(\neg p \land \neg q) \lor (q \land \neg q) \lor (\neg p \land p) \lor (q \land p) \text{ Complement x 2}$$

$$(\neg p \land \neg q) \lor \bot \lor \bot \lor (q \land p) \text{ Identity x 2}$$

$$(\neg p \land \neg q)\lor (q \land p) \text{ DeMorgan}$$

$$\neg (p \lor q) \lor (q \land p) \text{ Implication}$$

$$(p \lor q) \rightarrow (q \land p)$$

So here I used the following Equivalences in addition to Equivalence and Implication:

Distribution

$p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$

Complement

$p \land \neg p \equiv \bot$

Identity

$p \lor \bot \equiv p$

DeMorgan

$\neg(p \lor q) \equiv \neg p \land \neg q$

$\endgroup$
2
  • $\begingroup$ Such an excellent answer. Thank you. I had no idea how to do the distributive law part with the given variables. $\endgroup$
    – Noob
    May 11, 2017 at 22:49
  • $\begingroup$ @Noob You're welcome! :) $\endgroup$
    – Bram28
    May 11, 2017 at 23:21

You must log in to answer this question.

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