Boolean logic --> Convert And to Or

$\begingroup$

To convert an AND into an XOR, I can do:

AND(NOT(AND(A,B)), NOT(AND(NOT(A), NOT(B))))

$$\neg(A∧B)∧\neg (\neg A∧ \neg B)$$

How could I convert an AND into an OR with the constraint that I only use the AND and NOT logical operators?

$\endgroup$

1 Answer

$\begingroup$

Via De Morgan,

$$A \vee B = \neg(\neg A ∧ \neg B)$$

Edit: To be more explicit, using the De Morgan law $ \neg(p \vee q) = \neg p ∧ \neg q$, set $p = \neg A$, and $q = \neg B$. Note that $\neg p = A$, and $ \neg q = B$. Then, we get

$$A \vee B = \neg p \vee \neg q \overset{DM}= \neg (p ∧ q) = \neg (\neg A ∧ \neg B) $$

Or, if you prefer it without a change of varible,

$$ \neg(\neg A ∧ \neg B) = \neg((\neg A) ∧ (\neg B)) \overset{DM}= \neg(\neg A) \vee \neg(\neg B) = A \vee B$$

$\endgroup$ 2

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy