GATE CSE 2019 | Question: 30

Question

Consider three $4$-variable functions $f_1, f_2$, and $f_3$, which are expressed in sum-of-minterms as

$f_1=\Sigma(0,2,5,8,14),$

$f_2=\Sigma(2,3,6,8,14,15),$

$f_3=\Sigma (2,7,11,14)$

For the following circuit with one AND gate and one XOR gate the output function $f$ can be expressed as:

• A. $\Sigma(7,8,11)$
• B. $\Sigma (2,7,8,11,14)$
• C. $\Sigma (2,14)$
• D. $\Sigma (0,2,3,5,6,7,8,11,14,15)$

Comments

https://gateoverflow.in/302818/gate-cse-2019-question-30?show=302940#a302940 preferred

---

Watch the Detailed Video Solution by clicking the below button..!

Watch Video Detailed Solution   

---

f1​=Σ(0,2,5,8,14)

f2=Σ(2,3,6,8,14,15)

f1 AND f2 = common element = (2,8,14) = f(lets)

f XOR F3 = (2,8,14) xor (2,7,11,14) = (7,8,11)

option A is correct

Answer 1

Perform $f_1 \cdot f_2$ first, then with the result perform $XOR$ with $f_3$.

$f1 \cdot f2$ means just take common minterms in $f_1$ and $f_2$ (WHY? due to AND gate present, the minterm should be present in both functions.)

$f_1.f_2 = \Sigma (0,2,5,8,14) \cdot  \Sigma (2,3,6,8,14,15) = \Sigma (2,8,14)$

$\Sigma (2,8,14) \oplus  \Sigma (2,7,11,14) = \Sigma (7,8,11)$

Comments

∑(2,8,14) ⊕ ∑(2,7,11,14) = ∑(7,8,11)

 

Sir can you please explain this step?

---

ex-or means, odd no.of times that minterm exist !

2 appeared even number of times, so it can't be in the result !

8 appeared odd number of times, so it should be in the result !

continue this procedure...

---

XOR i.e. $\bigoplus$ is related to Symmetric Difference. Let two sets $A=\{2,8,14\}$ and $B=\{2,7,11,14\}$

$A\bigoplus B=A\cup B-A\cap B=\{2,7,8,11,14\}-\{2,14\}=\{7,8,11\}$

---

@Shaik Masthan

Ex-OR is Odd number of 1's detector i.e. Output is 1, if we have Odd number of input variable as 1. 

Can you prove that, how it works on Number of minterms?

---

@techbd123

 

XOR i.e. ⨁⨁ is related to Symmetric Difference. Let two sets A={2,8,14}A={2,8,14} and B={2,7,11,14}B={2,7,11,14}

A⨁B=A∪B−A∩B={2,7,8,11,14}−{2,14}={7,8,11}

This is a good point but i don't think its the fundamental property of $\mathbf{\oplus}$, right?

 

---

Nope. It's the fundamental property.

---

what if here would have been x-nor gate insted x-or then what would be the answer?

---

ayushsomani  that’s because if say x is present 1 time and is in f1 then it will occur in f1.f2’ . If x is in f2 then it will generate from term f2.f1’ in result . (remember . results in common terms )

---

2 input exor will select a term only if it is present only in one of the inputs since exor is 1 for inputs 01 and 10.

---

Anyone confirm this. For xnor gate, the ans is (2, 14)?

---

Yep! You’re correct.

---

@may12day result of xnor should be (0,1,2,4,5,6,9,10,12,13,15) since 

 

Xnor of A,B =A⋅B+ A’B’

---

@bhumik805 result of xnor is $\Sigma \left ( 0,1,2,3,4,5,6,9,10,12,13,14,15 \right )$.

---

Can you tell me how you calculate for the EX-NOR?

---

formula for X-NOR is A'B' + AB first calc A' and B' by taking complement of A and B respectively. Then same take common from A' and B' you will get A'B' and take common from A and B you will get AB and take union of both A'B' + AB.

---

can i say those which isnt common that is xor?

---

@pavansan That trick of picking 'uncommon' elements works great for a 2-input XOR. However, for a 3-fan-in XOR ($A \oplus B \oplus C$), you have to use the odd-frequency rule(That's the main rule or XOR).

Example: If an element appears in all 3 sets, it actually stays in the final output because its frequency is 3 (which is odd), rather than canceling out.

Conclusion: Across any number of inputs, XOR always keeps elements that appear an odd frequency of times!

Answer 2

Option:A

 

$(f1.f2)\bigoplus f3$

$(f1.f2)'.f3+(f1.f2).f3'$

$(2,8,14)'.(2,7,11,14)+(2,8,14).(2,7,11,14)'$

$(0,1,3,4,5,6,7,9,10,11,12,13,15).(2,7,11,14)+(2,8,14).(0,1,3,4,5,6,8,9,10,12,13,15)$

$(7,11)+(8)$

$(7,8,11)$

Comments

best one

---

This one is better explanation than other....👍👍

Answer 3

From the  given diagram we can write like

$f=(f_{1}.f_{2})\oplus f_{3}$

We know that $A\oplus B=A\overline{B}+\overline{A}B$

So ,we can expend it and get

$f=(f_{1}.f_{2}).\overline{f_{3}}+\overline{(f_{1}.f_{2})}.f_{3}$

Apply De-Morgan's  laws

$\overline{(A.B)}=\overline{A}+\overline{B}$

$\overline{(A+B)}=\overline{A}.\overline{B}$

Now $f=(f_{1}.f_{2}).\overline{f_{3}}+\overline{(f_{1}}+\overline{f_{2})}.f_{3}$

             Apply distributive rule

$f=(f_{1}.f_{2}).\overline{f_{3}}+\overline{f_{1}}.f_{3}+\overline{f_{2}}.f_{3}$  -------------$>(1)$

Given that

$f_1=\Sigma(0,2,5,8,14)$

$\overline{f_{1}}=\Sigma(1,3,4,6,7,9,10,11,12,13,15)$

$f_2=\Sigma(2,3,6,8,14,15)$

$\overline{f_{2}}=\Sigma(0,1,4,5,7,9,10,11,12,13)$

$f_3=\Sigma (2,7,11,14)$

$\overline{f_{3}}=\Sigma(0,1,3,4,5,6,8,9,10,12,13,15)$

Now 

$f_{1}.f_{2}=\Sigma(0,2,5,8,14).\Sigma(2,3,6,8,14,15)$

Perform Intersection and get it

$f_{1}.f_{2}=\Sigma(2,8,14)$

$(f_{1}.f_{2}).\overline{f_{3}}=\Sigma(2,8,14).\Sigma(0,1,3,4,5,6,8,9,10,12,13,15)$

Perform Intersection and get it

$(f_{1}.f_{2}).\overline{f_{3}}=\Sigma(8)$

and $\overline{f_{1}}.f_{3}=\Sigma(1,3,4,6,7,9,10,11,12,13,15).\Sigma (2,7,11,14)$

      Perform Intersection and get it

      $\overline{f_{1}}.f_{3}=\Sigma(7,11)$

and last one 

$\overline{f_{2}}.f_{3}=\Sigma(0,1,4,5,7,9,10,11,12,13).\Sigma (2,7,11,14)$

 Perform Intersection and get it

$\overline{f_{2}}.f_{3}=\Sigma(7,11)$

Now put the values in the equation $(1)$ and get

$f=(f_{1}.f_{2}).\overline{f_{3}}+\overline{f_{1}}.f_{3}+\overline{f_{2}}.f_{3}$

$f=\Sigma(8)+\Sigma(7,11)+\Sigma(7,11)$

Perform Union and get it

$f=\Sigma(7,8,11)$

---------------------------------------------------------------------------------------------------------

This is better way to analyze,how GATE works.

Comments

$\textbf{Symmetric difference,}$ denoted $\triangle$, refers to the set of elements which are in one of the two sets but not both. For example, $\{1,2,3\} \triangle \{3,4,5\} = \{1,2,4,5\}$. In Boolean logic, symmetric difference is expressed as a logical $\textbf{XOR}$ gate.

Reference:

• https://brilliant.org/wiki/sets/
• https://math.stackexchange.com/questions/84184/relation-between-xor-and-symmetric-difference

---

awesome explanation

Answer 4

f1 and f2 = ∑(0,2,5,8,14) and ∑(2,3,6,8,14,15) = ∑(2,8,14)  (common minterms)
(f1 and f2) xor f3 = ∑(2,8,14) xor ∑(2,7,11,14)
we know a ⊕ b = a'b + ab', so
∑(2,8,14) xor ∑(2,7,11,14)
= (∑(0,1,3,4,5,6,7,9,10,11,12,13,15) and ∑(2,7,11,14))  or  (∑(2,8,14) and ∑(0,1,3,4,5,6,8,9,10,12,13,15))
= ∑(7,11) or ∑(8)
= ∑(7,8,11)   (union)

Answer 5

f1*f2 = ∑(2,8,14)
f3 = ∑(2,7,11,14)
f1*f2 ⊕ f3 = ∑(2,8,14) ⊕ ∑(2,7,11,14)
= ∑(8,7,11) (Note: Choose the terms which are not common)

Answer 6

f1=Σ(0,2,5,8,14)^f2=Σ(2,3,6,8,14,15)

   =Σ(2,8,14)

now

(f1 ^ f2)⊕f3

=Σ(2,8,14)⊕Σ(2,7,11,14)

=Σ(7,8,11)