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

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