Construct a circuit which takes three
binary inputs, a, b, c, and creates as outputs their complements, a',
b', c', (NOT a, NOT b, NOT c) with the restriction that you may only
use two inverters (NOT gates). You are allowed as many AND and OR
gates as you wish, but no other gates, besides these and the two
inverters, can be used.
A neat generalization of this
problem is "how many inverters do you need to compute the complements
of N inputs", but I do not know the answer to this (I don't even know
if the answer is known).
the firs question's answer:
In black below is a circuit for the 3
with 2 case. Its not the smallest possible such circuit but is written
as a hint toward the more general case.
Its written in C code for easy verification.
1 #include <stdio.h>
2 void main(){
3 int a,b,c,x,y,z,g,h,a1,b1,c1,x1,y1,z1;
4 int i;
5 for(i=0;i<8;i++){
6 // set up all possible inputs a,b,c
7 a = i & 1;
8 b = (i & 2) >> 1;
9 c = (i & 4) >> 2;
10
11 x = a & b & c;
12 y = a & b | a & c | b & c;
13 z = a | b | c;
14
15 //Here are our 2 inverters
16 g = !(y);
17 h = !(x | g & z);
18
19 x1 = g | h;
20 y1 = g;
21 z1 = g & h;
22 a1 = b & c & x1 | (b | c) & y1 | z1;
23 b1 = a & c & x1 | (a | c) & y1 | z1;
24 c1 = b & a & x1 | (b | a) & y1 | z1;
25
26 //print outputs to verify
27 printf("%d-->%d %d-->%d %d-->%d\n",a,a1,b,b1,c,c1);
28 }
29 }