Turn Disjunctive Normal Form into only AND and NOT statements

43 Views Asked by At

I'm working on implementing logic gates and want to implement an OR gate using only AND and NOT gates.

I came up with this canonical form for the OR function. $$Or(x, y) = (\lnot{x} \land y) \lor (x \land \lnot y) \lor (x \land y)$$ $$= y \lor (x \land \lnot y)$$

Then, working with DeMorgan's laws, I tried (following from above):

$$= \lnot(\lnot y) \lor \lnot(\lnot(x \land \lnot y))$$ $$= \lnot(\lnot y \land \lnot(x \land \lnot y))$$

But I can't figure out how to simplify it any further. Am I missing something or is this it?

1

There are 1 best solutions below

2
On BEST ANSWER

I would just start with the double negation and then apply De Morgan's law:

$$x\lor y = \lnot(\lnot( x\lor y)) = \lnot (\lnot x \land \lnot y)$$