1

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.

Сергей Позняк
  • 11

1 Answers1

1

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.

Bram28
  • 100,612
  • 6
  • 70
  • 118