TIFR CSE 2010 | Part B | Question: 21

Question

For $x \in \{0,1\}$, let $\lnot x$ denote the negation of $x$, that is $$\lnot \,  x = \begin{cases}1 & \mbox{iff } x = 0\\ 0 & \mbox{iff } x = 1\end{cases}$$.

If $x \in \{0,1\}^n$, then $\lnot \, x$ denotes the component wise negation of $x$; that is: $$(\lnot \, x)_i=\left (\lnot \, x_i \mid i \in [1..n] \right )$$

Consider a circuit $C$, computing a function $f: \{0,1\}^{n} \to \{0,1\}$ using AND $(\land)$, OR $(\lor)$,and NOT $(\lnot)$ gates. Let $D$ be the circuit obtained from $C$ by replacing each AND gate by an OR gate and replacing each OR gate by an AND. Suppose $D$ computes the function $g$. Which of the following is true for all inputs $x$?

• A. $g(x) = \lnot \, f(x)$
• B. $g(x) = f(x) \land f(\lnot x)$
• C. $g(x) = f(x) \lor f(\lnot x)$
• D. $g(x) = \lnot f(\lnot x)$
• E. None of the above.

Comments

Doesn't it also say D is correct?

---

yes here is no work with function I think

Answer 1

Option (D) is answer.

The circuit D is the $\text{dual}$ of the function $f(x)$ (i.e., replace $\text{AND}$ by $\text{OR}$ and vice versa)

We can find dual of any function $f(x)$ by doing $¬f(¬x).$

Comments

@Deepakk Poonia (Dee) Sir,

I think the answer should be D because ,

F(x)=0;
F(¬x)=0
¬F(¬x)=1=g(x)

hence g gives the dual of F.
Please see.

---

Given,

If $x \in \{0,1\}^n$, then $¬x$ denotes the component wise negation of $x;$ that is:

$(\lnot \, x)_i=\left (\lnot \, x_i \mid i \in [1..n] \right )$

What does component wise negation mean?

What’s the difference between $¬f(¬x), ¬f(x), f(¬x)$?

Explain the differences with an example.

---

@deepak poonia

Given in question,

Let $D$ be the circuit obtained from $C$ by replacing each AND gate by an OR gate and replacing each OR gate by an AND. Suppose D computes the function $g$.

Question didn’t say that $D$ computes dual of a function. It said that $D$ replaces each AND gate by an OR gate and each OR gate by an AND gate.

If $f(x) = 0, \forall x$ then $g(x)=¬f(¬x)=0$ which means Option D is true.

Answer 2

let f = a.b

then acc. to question g will be a+b (replacing AND by OR)

A. g(x)=¬f(x) 

a+b ≠ (a.b)'

⇒a+b ≠ (a'+b')  ------->false

B. g(x)=f(x)∧f(¬x)

a+b ≠ (ab).(a'b')

⇒a+b ≠ F-------------> false

C.  g(x)=f(x)∨f(¬x)

a+b ≠ ab+a'b'

⇒a+b≠a⊙b ----------------> false

D. g(x)=¬f(¬x)

a+b = (a'.b')' = a+b ------> true

Comments

examples are used to disprove something, not to prove anything. If option (E) is not present then you can eliminate other options and say (D) is correct. To make (E) as wrong, you have to prove the statement given in (D) or you can say it is the definition of something.

---

proof of (D) : https://math.stackexchange.com/questions/3627606/boolean-algebra-self-dual-boolean-function-gx-lnot-f-lnot-x

@Krithiga2101 answer is not correct.

Answer 3

Ans will be D

dual can change AND to OR gate and OR gate to AND

AB dual is (A'B')'=A+B

Comments

srestha ma'am Dual of a function is obtained by doing both of the following:

1. converting all ORs to ANDs and vice versa.
2. replacing all occurrences of 1's with 0's and vice versa.

Here, we're satisfying just the first condition, and not the second.

 

Thus, g(x) is not the dual of f(x).

g(x) is actually unrelated to f(x)

E should be the answer.