# GATE2015-2-37

6.3k views
The number of min-terms after minimizing the following Boolean expression is _______.

[D'+AB'+A'C+AC'D+A'C'D]'

edited
7
Directly apply the boolean algebra and get the right answer

min-term=1
1

15 max terms

1 min terms

$F = [D'+AB'+A'C+AC'D+A'C'D]'$

$F'= D'+AB'+A'C+AC'D+A'C'D$

Now we have F', so fill 0's (maxterms) in K-map for each term

As for D'

Similarly for $AB'$, $A'C, AC'D$ and $A'C'D$.  We will get

We get one place for minterm and that is ABCD

edited
1
@praveen _sir why we need to make k map,

suppose if i put A=B=C=D= 1 and solve the F  then we get 0 so the value of F' = 1

correct sir ??
1
it will work with this problem
1
@praveen_sir only this particular problem ??

I always used to solve such type of question , am i going in wrong direction??
1
actually here we get F= ABCD, on putting 1  , we get  F= 1 , it is only possible with one combination.
if suppose we got F= 0, there are 4 possibilities
2

Sir m not getting this step

F=[D′+AB′+A′C+AC′D+A′C′D]′

F′=D′+AB′+A′C+AC′D+A′C′D

2nd equation above represent in F' function whatever on RHS are minterms (as it is SOP )So ..for K map of F'

we should fill minterms why maxterms filled here..

7

Let $F={[{D}'+A{B}'+{A}'C+A{C}'D+{A}'{C}'D]}'$

Apply both side complement

${F}'={[{[{D}'+A{B}'+{A}'C+A{C}'D+{A}'{C}'D]}']}'$

${F}'=[{D}'+A{B}'+{A}'C+A{C}'D+{A}'{C}'D]$         $[({X}')'=X]$

${F}'={D}'+A{B}'+{A}'C+A{C}'D+{A}'{C}'D$

${F}'={D}'+A{B}'+{A}'C+(A+{A}'){C}'D$

${F}'={D}'+A{B}'+{A}'C+1.{C}'D$            $[X+{X}'=1]$

${F}'={D}'+{C}'D+A{B}'+{A}'C$

${F}'=({D}'+{C}').({D}'+D)+A{B}'+{A}'C$          $[X+YZ=(X+Y).(X+Z)]$

${F}'=({D}'+{C}').1+A{B}'+{A}'C$

${F}'={D}'+{C}'+A{B}'+{A}'C$

${F}'={D}'+A{B}'+{C}'+{A}'C$​​

${F}'={D}'+A{B}'+({C}'+{A}').({C}'+C)$

${F}'={D}'+A{B}'+({C}'+{A}').1$

${F}'={D}'+A{B}'+{C}'+{A}'$

${F}'={D}'+{A}'+A{B}'+{C}'$

${F}'={D}'+({A}'+A).({A}'+{B}')+{C}'$

${F}'={D}'+1.({A}'+{B}')+{C}'$

${F}'={D}'+{A}'+{B}'+{C}'$

${F}'={A}'+{B}'+{C}'+{D}'$

Apply both side complement

$({{F}'})'=({{A}'+{B}'+{C}'+{D}'})'$

Apply Demorgan's laws

$({A+B})'={A}'.{B}'$

$({A.B})'={A}'+{B}'$

$({F}')'=({A}')'.({B}')'.({C}')'.({D}')'$

$F=ABCD$

So,this is the minterm.

1
I understood this method ..but not getting that K map method :(
1
@jatin we've complimented the function now where there was min terms they got changed to max terms and maxterms to minterms in K-map.

In K-map method D' means we have a subcube of size 8 beacuse of which three variables got eliminated ...so we form a Subcube of size 8 in K Map ..in case of AC' ..two variables are missing therefore we've to form a subcube of size 4 in the K-map by filling the max terms appropriately...like wise we've to fill for all.
3

So is it like this

# of minterms in F = ?

We know # of minterms in F = # of maxterms in F'

F = [D′+AB′+A′C+AC′D+A′C′D]′

So, F′ = [D′+AB′+A′C+AC′D+A′C′D]

K map for F'

 C'D' C'D CD CD' A'B' 1 1 1 1 A'B 1 1 1 1 AB 1 1 0 1 AB' 1 1 1 1

Maxterm in F' => A'+B'+C'+D'

So in F only one Minterm ABCD

Correct me if i am wrong?

2
Yes it is right

and you also see my answer, below the comment section.
1
Yes ..i have seen ..that will be very easy..just to make concept clear on mint and max t..i did this ..
1
Good :)
2
Sir..it is always true that
1) # of minterms in F = # maxterms in its complemented form.
2) So Demorgans law is the only way to find complement of the function
1

@jatin khachane 1 Please don't say sir to me

I'm also an aspirant like yours.

I think both statements are looking right.

1

@jatin khachane 1 don't get confused unnecessarily. Stick to basics. Recall basic functions that we study in discrete.

1. If there are total n terms in domain and x of which are mapped to 1 then n-x will be mapped to 0.

2. f(n)=1 all combination of input where f gives 1. Complement of f : remaining combination where f(n) gives 0.

3. Check question we are asked about combination where f(n) = 1. But function is complimented that means bracket will give all the terms which will be mapped to 0.(all terms except 15)

4. If you take compliment the result is combination which is mapped to 1.

5. Hence the canonical collection inside bracket represents max terms (mapping to 0) hence sir has written 0 in k map.

0
There might be a chance that it a question could be proven wrong with other outputs :)
0
Simply Apply De Morgan's Law & Boolean Algebra, you will get it.

$[D'+AB'+A'C+AC'D+A'C'D]'$

=> $(D)(A'+B)(A+C')(A'+C+D')(A+C+D')$

=> $(A'D+BD)(AD+C'D)(A'D+CD)(AD+CD)$  {ON MULTIPLYING, those terms which have both A & A' will nullify}

=>${A'C'D+ABD+BC'D}{A'CD+ACD+CD}$

=>$ABCD$

Let's First Simplify it

[D' + AB' + A'C + AC'D + A'C'D ]'

[D' + AB' + A'C + C'D (A + A') ]'     // A + A' =1

[AB' +A'C + (D' + C') (D' + D) ]'    // Apply Distributive Rule Among D' and C'D

[AB' + A'C + D' + C' ]'

[AB' + (A' + C') (C + C') + D'  ] '   //Apply distributive Law B/w A'C and C'

[AB' + A' +C' +D' ]'

[(A+ A') (A' + B') +  C' + D' ]'    //Apply Distributive law b/w AB' and A'

Finally we got

[A' +B' +C' + D' ]'

Apply Demorgan's Law

ABCD

Canonical SOP of the expression D'+AB'+A'C+AC'D+A'C'D is ∑m(0,1,2,3,4,5,6,7,9,13,12,14,11,8,10)

So corresponding POS form is ⫪M(15)

minterm=(maxterm)'

minterm=(A'+B'+C'+D')'=ABCD

Therefore number of minterms = 1

solve it we get 15 max terms

so no. of min terms are 1

$F=[D'+AB'+A'C+AC'D+A'C'D]'$

$F'=D'+AB'+A'C+AC'D+A'C'D$

$F'=1.D'+AB'.1+A'.1C+A.1C'D+A'.1C'D$

$F'=(A+A')D'+AB'(C+C')+A'(B+B')C+A(B+B')C'D+A'(B+B')C'D$

$F'=AD'+A'D'+AB'C+AB'C'+A'BC+A'B'C+ABC'D+AB'C'D+A'BC'D+A'B'C'D$

$F'=A.1D'+A.1'D'+AB'C.1+AB'C'.1+A'BC.1+A'B'C.1+ABC'D+AB'C'D+A'BC'D+A'B'C'D$

$F'=A(B+B')D'+A'(B+B')D'+AB'C(D+D')+AB'C'(D+D')+A'BC(D+D')+A'B'C(D+D')+ABC'D+AB'C'D+A'BC'D+A'B'C'D$

$F'=ABD'+AB'D'+A'BD'+A'B'D'+AB'CD+AB'CD'+AB'C'D+AB'C'D'+A'BCD+A'BCD'+A'B'CD+A'B'CD'+ABC'D+AB'C'D+A'BC'D+A'B'C'D$

$F'=AB.1D'+AB'.1D'+A'B.1D'+A'B'.1D'+AB'CD+AB'CD'+AB'C'D+AB'C'D'+A'BCD+A'BCD'+A'B'CD+A'B'CD'+ABC'D+AB'C'D+A'BC'D+A'B'C'D$

$F'=AB(C+C')D'+AB'(C+C')D'+A'B(C+C')D'+A'B'(C+C')D'+AB'CD+AB'CD'+AB'C'D+AB'C'D'+A'BCD+A'BCD'+A'B'CD+A'B'CD'+ABC'D+AB'C'D+A'BC'D+A'B'C'D$

$F'=ABCD'+ABC'D'+AB'CD'+AB'C'D'+A'BCD'+A'BC'D'+A'B'CD'+A'B'C'D'+AB'CD+AB'CD'+AB'C'D+AB'C'D'+A'BCD+A'BCD'+A'B'CD+A'B'CD'+ABC'D+AB'C'D+A'BC'D+A'B'C'D$

Remove similar tearm,because $[X+X=X]$

$F'=ABCD'+ABC'D'+AB'CD'+AB'C'D'+A'BCD'+A'BC'D'+A'B'CD'+A'B'C'D'+AB'CD+AB'C'D+A'BCD+A'B'CD+ABC'D+A'BC'D+A'B'C'D$

Apply both side complement

$(F')'=[ABCD'+ABC'D'+AB'CD'+AB'C'D'+A'BCD'+A'BC'D'+A'B'CD'+A'B'C'D'+AB'CD+AB'C'D+A'BCD+A'B'CD+ABC'D+A'BC'D+A'B'C'D]'$

Apply Demorgan's laws

$(A+B)'=A'.B'$

$(A.B)'=A'+B'$

$F=(A'+B'+C'+D).(A'+B'+C+D).(A'+B+C'+D).(A'+B+C+D).(A+B'+C'+D).(A+B'+C+D).(A+B+C'+D).(A+B+C+D).(A'+B+C'+D').(A'+B+C+D').(A+B'+C'+D').(A+B+C'+D').(A'+B'+C+D').(A+B'+C+D').(A+B+C+D')$                 $[(X')'=X]$

This is Canonical Product Of Sum Term(Maxterm)

$1)A'+B'+C'+D=1110=14$

$2)A'+B'+C+D=1100=12$

$3)A'+B+C'+D=1010=10$

$4)A'+B+C+D=1000=8$

$5)A+B'+C'+D=0110=6$

$6)A+B'+C+D=0100=4$

$7)A+B+C'+D=0010=2$

$8)A+B+C+D=0000=0$

$9)A'+B+C'+D'=1011=11$

$10)A'+B+C+D'=1001=9$

$11)A+B'+C'+D'=0111=7$

$12)A+B+C'+D'=0011=3$

$13)A'+B'+C+D'=1101=13$

$14)A+B'+C+D'=0101=5$

$15)A+B+C+D'=0001=1$

$F(A,B,C,D)=\prod (1,2,3,4,5,6,7,8,9,,10,11,12,13,14)$

$F(A,B,C,D)=\sum (15)$

$$\textbf{(OR)}$$

Let's First Simplify it

$F=[D'+AB'+A'C+AC'D+A'C'D]'$

$F=[D'+AB'+A'C+C'D(A+A')]'$

$F=[D'+AB'+A'C+C'D.1]'$        $[A+A'=1]$

$F=[D'+AB'+A'C+C'D]'$

$F=(D')'.(AB')'.(A'C)'.(C'D)'$       [ Using Demorgan's  Law$: (A+B)=A'.B'$  $(or)$ $(A.B)'=A'+B' ]$

$F=(D).(A'+B).(A+C').(C+D')$    [Again using Demorgan's law ]

$F=(A'D+BD).(AC+AD'+C'C+C'D')$   [Simple multiply]

$F=(A'D+BD).(AC+AD'+0+C'D')$     $[C.C'=0]$

$F=(A'D+BD).(AC+AD'+C'D')$

$F=(A'D.AC+A'D.AD'+A'D.C'D'+BD.AC+BD.AD'+BD.C'D')$

$F=ABCD$       $[A.A'=0,D.D'=0]$

$$\textbf(OR)$$

Let $f(A,B,C,D) = \bigg[D'+AB'+A'C+AC'D+A'C'D\bigg]'$

$\implies \bigg[D'+AB'+A'C+C'D\bigg]'$

$\implies \bigg[D'+C'+ AB' + A'C\bigg]'$

$\implies \bigg[D'+C'+A'+ AB'\bigg]'$

$\implies \bigg[D'+C'+A'+ B'\bigg]'$​​​​​​​

$\implies ABCD$​​​​​​​

So the number of min-terms$=1$

edited
1

3

BTW in the part of your simplification, it can be done in shorter way like this below (especially in the part of distribution).

\begin{align} F &=\overline{\overline{D}+A\overline{B}+\overline{A}C+A\overline{C}D+\overline{A}\overline{C}D}\\&=\overline{\overline{D}+A\overline{B}+\overline{A}C+\overline{C}D};~~[\because (A+\overline{A})\overline{C}D=1\cdot \overline{C}D]\\&=D(\overline{A}+B)(A+\overline{C})(C+\overline{D});~~[\text{Applying De Morgan's law}]\\&=(\overline{A}+B)(A+\overline{C})(CD+\overline{D}D)\\&=(0+\overline{A}\overline{C}+AB+B\overline{C})(CD+0);~~[\because X\cdot\overline{X}=0]\\&=(\overline{A}\overline{C}+AB+B\overline{C})CD\\&=0+ABCD+0\\&=ABCD \end{align}

on putting some element say A = 0 we solve the boolean expression we get ans = 0; so for all minterms where A=0 function is 0. On taking A=1 we solve the boolean expression and get function = BCD, on K-Map its easy to put value of BCD.

The end result of this gives us only one minterm = ABCD

The minterm we get after minimizing this expression is ABCD.
So, number of minterms is 1.

## Related questions

1
19k views
A half adder is implemented with XOR and AND gates. A full adder is implemented with two half adders and one OR gate. The propagation delay of an XOR gate is twice that of an AND/OR gate. The propagation delay of an AND/OR gate is 1.2 microseconds ... ripple-carry binary adder is implemented by using four full adders. The total propagation time of this 4-bit binary adder in microseconds is ______.
Let $X$ and $Y$ denote the sets containing 2 and 20 distinct objects respectively and $F$ denote the set of all possible functions defined from $X$ to $Y$. Let $f$ be randomly chosen from $F$. The probability of $f$ being one-to-one is ______.
The number of states in the minimal deterministic finite automaton corresponding to the regular expression $(0+1)^* (10)$ is _____.