Sir can you please explain this step?

The Gateway to Computer Science Excellence

+9 votes

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:

- $\Sigma(7,8,11)$
- $\Sigma (2,7,8,11,14)$
- $\Sigma (2,14)$
- $\Sigma (0,2,3,5,6,7,8,11,14,15)$

+16 votes

Best answer

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)$

$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)$

+7

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...

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...

+3

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\}$

0

* Ex-OR* is

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

0

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?

+6 votes

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)

(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)

+2 votes

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.

- All categories
- General Aptitude 1.9k
- Engineering Mathematics 7.5k
- Digital Logic 2.9k
- Programming and DS 4.9k
- Algorithms 4.4k
- Theory of Computation 6.2k
- Compiler Design 2.1k
- Databases 4.1k
- CO and Architecture 3.4k
- Computer Networks 4.2k
- Non GATE 1.4k
- Others 1.4k
- Admissions 595
- Exam Queries 573
- Tier 1 Placement Questions 23
- Job Queries 72
- Projects 18

50,737 questions

57,292 answers

198,237 comments

104,919 users