# Prove equivalence of 2 boolean functions

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.

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

## 1 Answer

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.