5
$\begingroup$

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?

$\endgroup$
2
  • 8
    $\begingroup$ By De Morgan's Laws, $X \wedge Y = \neg(\neg{}X \lor \neg Y)$. Is this what you are looking for? $\endgroup$ Sep 23, 2014 at 17:39
  • 1
    $\begingroup$ 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. $\endgroup$ Sep 23, 2014 at 17:41

2 Answers 2

6
$\begingroup$

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!

$\endgroup$
0
4
$\begingroup$

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

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .