0

Question:

Implement $F(A,B,C,D)=AB\bar{C}D+A\bar{D}+\bar{A}D$ using only AND & XOR gates

My try:

I know that $A\bar{D}+\bar{A}D$ functions like a XOR gate which takes $A$ and $D$ as input. But then I don't know what to do which the part $+AB\bar{C}D$. I mean, with this method, I'm stuck on designing the OR gate.
I also tried using the Karnaugh map to simplify the equation but the result didn't help me either.
It seems that there's no way to get rid of the OR gate...

Any idea on this implementation?

Thanks in advance.

Arman Malekzadeh
  • 4,108
  • Are you allowed to use $0$ or $1$? – Bram28 Oct 04 '17 at 19:48
  • @Bram28 the question doesn't mention it... Is it possible not to use $0$ or $1$ ? – Arman Malekzadeh Oct 04 '17 at 19:53
  • If you have a $1$ then you can do any functin, since ${ \land, \oplus, 1 }$ is expressively complete ... but ${ \land , \oplus }$ is not expressively complete ... which does not mean that this specific function cannot be captured ... but it is possible that it can't ... let me try ... – Bram28 Oct 04 '17 at 19:55
  • @Bram28 Thanks for taking your time to help me :) – Arman Malekzadeh Oct 04 '17 at 19:55

1 Answers1

1

With just $XOR$ and $AND$ gates it cannot be done: By induction you can prove that any function composed of $XOR$'s and $AND$'s will be true in at most half of the cases, and the function you are supposed to capture is true in $9$ out of $16$ cases.

If you can use a $1$ as an input as well, then you can do it, since to capture $P'$ you can use $P \ XOR \ 1$, and with the conjunction and the negation you have an expressively complete system.

For your particular function:

$$ABC'D + AD' + A'D =$$

$$ABC'D+ (A \ XOR \ D)=$$

$$((ABC'D)'(A \ XOR \ D)')'=$$

$$(((AB(C \ XOR \ 1)D) \ XOR \ 1)((A \ XOR \ D) \ XOR \ 1)) \ XOR \ 1$$

Bram28
  • 100,612
  • 6
  • 70
  • 118