Question

How many of $16$ boolean functions in $2$ variables $x$ and $y$ can be represented using only the given set of operators, variables $x$ and $y$ ,and values $0$ and $1$?

a) $\{\, \sim \,\}$

b) $\{\, \cdot \,\}$

c) $\{\, + \,\}$

d) $\{\, \cdot \,,\, + \,\}$

Answer 1

a) The only function values we can get are x, y, 0, 1, x', y', Therefore the answer is 6.
b) Since x.x = x, x.1 = x, and x.0 = 0 for all x, the only functions we can get are x, y, 0, 1, and xy.
Therefore the answer is 5.
c) By duality the answer here has to be the same as the answer to part (b),  5.
d) We can get the 6 distinct functions x, y, 0, 1, xy and x+y. Any further applications of these operations,however, returns us to one of these functions. For example, xy+ y=x

Therefore final answer is a)6 b) 5 c)5 b)6

Thanks to pramod!!

Comments

a~c) we can use idempotence to prove using the operator multiple times won't increase represented functions.

d) Since one of {x,y,0,1,xy} ANDed($\cdot$) with x+y won't increase represented functions and similarly for {x,y,0,1,x+y} ORed($+$) with xy. Then based on induction, using operators multiple times won't increase represented functions.

Please point out errors if any. Thanks in advance.

Answer 2

x	y	f0	f1	f2	f3	f4	f5	f6	f7	f8	f9	f10	f11	f12	f13	f14	f15
0	0	0	0	0	0	0	0	0	0	1	1	1	1	1	1	1	1
0	1	0	0	0	0	1	1	1	1	0	0	0	0	1	1	1	1
1	0	0	0	1	1	0	0	1	1	0	0	1	1	0	0	1	1
1	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1	0	1

f0=0,    f1= x.y,     f2=x.y',    f3= x,    f4=x'.y,   f5=y,    f6=x xor y,    f7= x +y,   f8=(x+y)' ,   f9= x xnor y,   f10=y',   f11=x+y', f12 = x',   f13= x'+y,    f14=(x.y)',   f15=1

a) {~} = using only NOT , we can get only f0=0, f15=1, f5=y,f6=x,f10=y',f12=x'  (6 functions)

b){.} = using AND only f0=0, f1=x.y,f15 =1 , f5=y,f6= x(5 functions){ using idempotentency properties}

c){+} = using it only f0=0,f15=1, f7=x+y ,f5=y,f6=y(5 function)

d){. +} = using these we get f0=0,f15=1,f5=y,f6=x,f7=x+y,f1 =x.y ....(6 functions)

Answer 3

for option (a) ans is 0 because the complement operator is unary and we cannot build a boolean expression in 2 boolean variables using only the complement operator.

for (b) is 1 because any boolean expression consisting of only x,y, ⋅ and 0 can be simplified (by the identity, idempotent law) to x⋅y which has the mapping 00 to 0, 01 to 0, 10 to 0 and 11 to 1 and any boolean expression having only x,y, ⋅ simplifies to 1 for any input value x and y.

Similarly, for (c) is 1.

For (d) the answer is 2 because the expressions  x+y,x⋅y have 2 boolean variables and only 2 of the 16 boolean functions can be represented by these 2 expressions.

Correct me if i am wrong.