I'm struggling with proving that theese 2 boolean functions are equivalent.

$$(a \vee b) \equiv c$$ $$(a \equiv c) \equiv (b \Rightarrow a)$$

I'm not allowed to use truth tables or Vienn diagrams.

My teacher told me that I need to get one of the formulas to look like the other one, but I struggle with that. Here's that I got so far:

$$(a \lor b) \equiv c \\ \equiv ((a \lor b) \land c) \lor (\lnot (a \lor b) \land \lnot c) \\ \equiv (a \land c \lor a \land b) \lor (\lnot a \land \lnot b \land \lnot c) \\ \equiv a \land c \lor a \land b \lor \lnot a \land \lnot b \land \lnot c \\ \equiv a \land (b \lor c) \lor \lnot a \land (\lnot b \land \lnot c)$$

I don't know what to do next, I'm not sure how to make it look like the other formula at this point.

Edit: first formula was wrong, sorry.

  • $\begingroup$ For the first one if you take a true and b false then you ll get that $T \equiv F$ $\endgroup$ – arberavdullahu Nov 12 '16 at 11:26

First of all, make sure you use parentheses to disambiguate an expression like $A \land B \lor C$: is this $(A \land B) \lor C$ or is it $A \land (B \lor C)$? Those are two different statements, so parentheses matter!

Second, you made a mistake:

$$(a \lor b) \equiv c \Leftrightarrow (rewrite \: equivalence) $$

$$ ((a \lor b) \land c) \lor (\lnot (a \lor b) \land \lnot c) \Leftrightarrow (Distribution)$$

$$ ((a \land c) \lor \color{red}{(b \land c)}) \lor (\lnot a \land \lnot b \land \lnot c) \Leftrightarrow (Association)$$

$$ (a \land c) \lor (b \land c) \lor (\lnot a \land \lnot b \land \lnot c) $$

... and that's as far as it gets. So, see if you can get the other statement in this form as well.


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.