TIFR CSE 2014 | Part B | Question: 17

Question

Let $f: \left\{0, 1\right\}^{n} \rightarrow \left\{0, 1\right\}$ be a boolean function computed by a logical circuit comprising just binary AND and binary OR gates (assume that the circuit does not have any feedback). Let PARITY : $\left\{0, 1\right\}^{n} \rightarrow \left\{0, 1\right\}$ be the boolean function that outputs $1$ if the total number of input bits set to $1$ is odd. Similarly, let MAJORITY be the boolean function that outputs $1$ if the number of input bits that are set to $1$ is at least as large as the number of input bits that are set to $0$. Then, which of the following is NOT possible?

• A. $f(0, 0, . . . , 0) = f(1, 1, . . . , 1) = 0$.
• B. $f(0, 0, . . . , 0) = f(1, 1. . . . , 1) = 1$
• C. $f$ is the MAJORITY function.
• D. $f$ is the PARITY function.
• E. $f$ outputs $1$ at exactly one assignment of the input bits.

Comments

The question looks incorrect. Please verify.

Answer 1

Note: NOT is absent in function $f$.

 

for two boolean variables, $p_{1}=1$,$p_{2}=1$,   neither $p_{1}\wedge p_{2}$ nor $p_{1} \vee p_{2}$ is $0$. ie, $f(1,1)$ is never $0.$

for $i = 1$ to $n$. $f(p_{i})$ is a function of AND,OR operations on $p_{i}$. if all $p_{i}=1$, then $f$ can never be $0$;

similarly, if all $p_{i}=0,$  $f$ can never be $1$;

Therefore  ${A,B}$ are not possible.

for $j<n$, if all $p_{j}=0$ and $p_{n-j}=1$,then  $f(p_{j}, p_{n-j}) =$majority if each $0$ is AND with each $1.$The remaining $1's$ or $0's$ are OR with the result.

Hence, MAJORITY can be computed from $f$.

Option C is possible.

To check odd number of $1's$, for PARITY function,  we have to get the result $0$ for even number of $1's$ which is not possible with just AND and OR operations, how might we combine(since NOT is absent in $f$);

D  is not possible.

For option E, we check by symmetry. When the inputs are complemented among $0's$ and $1's$, can $f$ change to $f'$? $f$ is not always fixed for a particular input,. example, $f(0,1) = 0\vee 1=1$   $0\wedge 1=0$,hence $f$ can take multiple values for same input. Therefore E is also not right.

The only possible answer is C .'Hence A,B,D,E are not possible.

Comments

question is asking which of the following is not possible..and it is not asking which are possible...

we can verify this q for 2 variable .

total no of boolean fn possible with 2 variable are 16 out of which only 6 can be implement using AND and OR "

F=0

F=1

F=A+B

F=A.B

F=A

F=B

option A possible for F=0

option B possible for F=1

option C possible for F=A+B(o/p 1 for 01,10,11 i.e no of 1's is atleast equal to no of 0's)

option D possible for F=A'B+AB'(for implementing this we require not gate) 

option E possible for F=A.B

therefore answer should be D

---

@Vikranth: I didn't understand your explanation for majority. Could you please explain it again?

Also, option E is possible. Simply and all inputs. It will output $1$ only when all inputs are $1$. It will output $0$ in all other possible assignments.

---

Option A says F=0 only when all of the input variables are same. How can we get F=0 when all input variables=1? I mean how is F(1,1)=0 computed from AND, OR operations for 2 variables?

---

@Saurav: You are only allowed AND and OR gates. No external sources of getting $1$ or $0$. If all inputs are $1$, the output will be $1$. If all inputs are $0$, output will be $0$ no matter what $f$ you choose.

---

example, for numberof 0's lessthan 1's

we map each 0 with each 1 with AND operation.The result will be 0.

now there will remain some 1's pending. We map all these 1's and the above 0 with OR operation.=1=Majority are 1's.

Similarly when |1|<|0|

in the second step, we map the result 0 with remainingpending 0's through OR operation=0=majority are 0's

ex :

f(0,0,0,1)= 0and1  or 0 or 0=0

---

ex2:

f(0,1,0,1,0,1,1,0,1)= 0 and 1 or 0 and 1 or 0 and 1 or 1 or 1=1

@Agarwal

f(0,1)=  1 when OR;

= 0 when AND.

Hnece for  fixed input, there is more than 1 value of the function. I am talking about option E.

---

@Vikranth: I still have no idea what you're doing.

About the majority: Let $n=5$. Let the inputs be called $p, q, r, s, t$. Now, find a function $f(p,q,r,s,t)$ which is made just from ANDs and ORs and which outputs the majority of the inputs. You do not know the value of the inputs. Give me an answer like $f = ab + ce + d$ or something.

About option E: Read what it says again: $f$ outputs $1$ at exactly one assignment of the input bits.

Let $f(p,q,r,s, \ldots) = p\cdot q \cdot r \cdot s \cdots$. Then, $f$ outputs $1$ at exactly one assignment of the input bits, and that assignment is $p = q = r = s = \cdots = 1$

---

MAJORITY FUNCTION

among pqrst, selectany three at a time, perform AND operation. Therefor  such terms will be 5C3=10 terms.

They are pqr, pqs,pqt .....rst=10 terms. when u OR all these terms, it will result 1 when atleast one term is a 1.

Ex, when n=3

f(p,q,r)= (pANDq)OR(pANDr)OR(qANDr).

majority function

p	q	r	pq	pr	qr	f
0	0	0	0	0	0	0
0	0	1	0	0	0	0
0	1	0	0	0	0	0
0	1	1	0	0	1	1
1	0	0	0	0	0	0
1	0	1	0	0	1	1
1	1	0	1	0	0	1
1	1	1	1	1	1	1

---

forn variables, f(x1,x2,...xn) there will be total nC[n/2] terms for OR operation. Each term contains [n/2] variables for AND operation.

ex: f(00111)= OR{ and(0,0,1) and(0,0,1) and(0,0,1) and(0,1,1)  and(,0,1,1) and(0,1,1,) and(0,1,1) and (0,1,1,) and(0,1,1,) and(1,1,1 )

=0 OR 0 OR 0 OR...... OR 1=1=majority of ones is true.

---

Thanks, that makes it clear :)

So, majority can be done, and option E can be done. I wonder if they gave marks to everyone in this question.

---

I think if we allow logic '0'  & logic '1' in circuit , then we can Have a valid option as D. As, then only D  would

  be not possible.

   Here no links are taken between inputs and output so, all combinations become 0.So, Option A can also be made possible..

Note: Here nothing else is used besides AND / OR

And if we take output 'f' from V_cc like this:

then Option B can be made possible.. As, output 'f' becomes 1 for every input combination.. 

---

Option A is possible with X-OR

Option B is possible with X-NOR

MAJORITY is possible

PARITY is possible

E is also possible. like if logic is ABC, it assigns 1 iff A=1 B=1 C=1

---

Please explain how to check for parity function using example.

---

@Arjun Sir, Pls check.

---

Note:

- NOT is absent in function $f$.
- For two boolean variables $p1=p2=1$, neither $p1 \wedge p2\ =0$ nor $\ p1\lor p2 = 0$. ie, $f(1,1)$ is never $0$.
- $f(p_1,p_2,\cdots,p_n)$ is a function of $AND,OR$ operations on $p_i$.

---

if all $p_i=1$, then $f$ can never be $0$;
Similarly if all $p_i=0$,  $f$ can never be $1$

Therefore  A) and B) are not possible.

---

It turns out that majority can be computed by formulas that consists of only $3$ gates (and no constants!).

Ref: https://cstheory.stackexchange.com/questions/21386/circuit-complexity-of-majority-function

http://www-inst.eecs.berkeley.edu/~cs150/fa01/homeworks/hw5sol.pdf

Option C is possible.

---

To check odd number of 1's, for $PARITY$ function,  we have to get the result $0$ for even number of 1's which is not possible with just $AND$ and $OR$ operations. (since $NOT$ is absent in $f$).

$PARITY(x_1,x_2,\cdots,x_n) = x_1\oplus x_2 \oplus \cdots x_n$

D  is not possible.

---

Option E is possible. Simply $AND$ all inputs. It will output $1$ only when all inputs are $1$. It will output $0$ in all other possible assignments.
 

---

Pragy sir. If in option instead of exactly one assignment there is only one assignment given.Answer will change coz f()=1 can be possible for other assignment than all 1's.

Answer 2

Only C is possible.

Comments

option E is also possible when the function is logical AND and all inputs are set to 1.

---

logical AND and logical OR both has to be checked .

---

Logical AND and logical OR are both different functions. It is not mentioned in the question that all functions in the set should satisfy any property given in the option .The question can be re-framed like this : ∃f∈A such that f outputs 1 at exactly one assignment of the input bits,where A is the set of all boolean functions g:{0,1}ⁿ→{0,1}. 

Answer 3

MAJORITY FUNCTION with n=3 with only AND , OR gates

http://stackoverflow.com/questions/16472171/how-to-simplify-boolean-function-into-two-logic-gates