Question

In addition to NAND and NOR, find four more two-input boolean functions that are each individually universal. Give a logic expression for each of your functions, using AND, OR, and NOT, and prove that each of these functions is individually universal, by showing for example that you can implement AND, OR, and NOT with your function. You may use the constant values zero and one as inputs to your universal functions to implement other functions. Name your functions f1, f2, f3, and f4, and then use these names for the operator symbol. i.e. "X f1 Y" would signify applying the f1 function to X and Y. Hint: There are only 16 boolean functions of 2 variables, so one approach to this problem is to list them all, and consider each in turn.

Answer 1

For two variables X and Y, 16 Boolean functions can be con- structed, as there would be 16 two variables Boolean functions f(X,Y), as shown in the table below:-

X	Y	f(X,Y)
0	0	a
0	1	b
1	0	c
1	1	d

Here, we can see that the values a,b,c,d can be either a 0 or 1, so each have two options, hence a total of 16=2⁴ different functions.

We can make a following table showing all those 16 functions:-

Gate No. #	XY 00	XY 01	XY 10	XY 11	Symbolic Logical Description	Name
0	0	0	0	0	0	AlwaysZero
1	1	1	1	1	1	Always 1
2	0	0	0	1	X&Y	AND
3	1	1	1	0	~(X & Y)	NAND
4	0	0	1	1	X	X
5	0	1	0	1	Y	Y
6	0	1	1	0	(X&~Y) | (~X&Y)	XOR
7	0	1	1	1	X | Y	OR
8	1	0	0	0	~(X | Y)	NOR
9	1	0	0	1	(X & Y) | (~X & ~Y)	XNOR
10	1	0	1	0	~Y	Not Y
11	1	1	0	0	~X	Not X
12	0	0	1	0	X & ~Y	X and Not Y
13	0	1	0	0	~X & Y	Y and Not X
14	1	0	1	1	X | ~Y	X or Not Y
15	1	1	0	1	~X | Y	Y or Not X

The following four functions could be universal gates:-

• Gate 12- f1(X & ~Y)
• Gate 13- f2(~X & Y)
• Gate 14- f3(X | ~Y)
• Gate 15- f4(~X | Y)

Gates 12 and 13 are mirror gates of each other, and gates 14 and 15 are also mirror gates of each other. Now to prove the above four as universal gates, we need to prove Gates 12 and 14 to be universal logic gates as:-

Expressions-:

Expressions:-

Comment in case of any doubt.