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?
$\begingroup$
$\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$– Joseph DiNataleSep 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$– Ross MillikanSep 23, 2014 at 17:41
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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!
$\begingroup$
$\endgroup$
0
Hint: Are you familiar with De Morgan's laws? One of them (if you negate both sides) is just what you want.
answered Sep 23, 2014 at 17:39