5

Is it possible to express the logical AND in terms of XOR, OR, or NOT?

The closest I can come is NOT (p XOR q); the only problem is that the case when both p and q are false, this will turn out to be true. Is there any way around it?

Artem
  • 1,208
  • 8
    By De Morgan's Laws, $X \wedge Y = \neg(\neg{}X \lor \neg Y)$. Is this what you are looking for? – Joseph DiNatale Sep 23 '14 at 17:39
  • 1
    The problem with XOR is that it is true twice and false twice. Not doesn't change whether the number of true cases is even. You need something, like OR that is true an odd number of times. – Ross Millikan Sep 23 '14 at 17:41

2 Answers2

6

Using De Morgan's laws, you can use:

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

Apart from using De Morgan's laws, you can come up with a combination of XOR, NOT and OR:

$$A \wedge B = \neg\big((A\oplus B) \vee \neg(A\vee B)\big)$$

I found this combination using Karnaugh maps. I used the map for $\neg(A \wedge B)$ and got $$\begin{array}{c|c|c} A\backslash B&0&1\\\hline 0&1&1\\\hline 1&1&0 \end{array}$$ and found which combinations were useful. Try it out!

cjferes
  • 2,216
4

Hint: Are you familiar with De Morgan's laws? One of them (if you negate both sides) is just what you want.

beep-boop
  • 11,595
Ross Millikan
  • 374,822