Register

GATE CSE 1997 | Question: 5.1

• edited by
24,583 views
50 50 votes

Let $f(x, y, z)=\bar{x} + \bar{y}x + xz$ be a switching function. Which one of the following is valid?

  1. $\bar{y} x$ is a prime implicant of $f$

  2. $xz$ is a minterm of $f$

  3. $xz$ is an implicant of $f$

  4. $y$ is a prime implicant of $f$

9 Answers

Best answer
59 59 votes

In sum of terms, any term is an implicant because it implies the function. So, $xz$ is an implicant and hence C is the answer. Still, lets see the other options. 

If no minimization is possible for an implicant (by removing any variable) it becomes a prime implicant. 

If a prime implicant is present in any possible expression for a function, it is called an essential prime implicant. (For example in K-map we might be able to choose among several prime implicants but for essential prime implicants there won't be a choice). 

So, $f = x' + y'x + xz$
$= y' + x' + z$ (could be also derived using algebraic rules as in http://www.ee.surrey.ac.uk/Projects/Labview/boolalgebra/ )

So, the prime implicants are $x', y'$ and $z$. Being single variable ones and with no common variables, all must be essential also.  

Choice a) False - $y'$ is a prime implicant and hence, $y'x$ is just an implicant but not prime. 
Choice b) False - $xz$ is not a minterm. A minterm must include all variables. So, $xyz$ is a minterm so, is $xy'z$, but not $xz$. 
Choice d) False - $y'$ is a prime implicant not $y$. 
 

• edited by
35 35 votes

Answer: C

f(x,y,z) = x' + y'x + xz

An implicant of a function is a product term that is included in the function.

so x', y'x and xz ,all are implicants of given function.

A prime implicant of a function is an implicant that is not included in any other implicant of the function. 

option a)   y'x is not a prime implicant as it is included in xz [ xy'z+ xyz]

option d) y is not a prime implicant as it include in both x' and xz.

a product term in which all the variables appear is called a minterm of the function

option b) xz is not a minterm

6 6 votes

$xz$ is an implicant and $\neg y$ is both prime and essential prime implicant. The sop would be $z+\neg x+\neg y$. 

Implicant: Something that implies a function is its implicant
Prime implicant: The most reduced (minimal) implicant
Essential prime implicant: The prime implicant which cannot be avoided in any SOP

Ref: https://en.wikipedia.org/wiki/Implicant

• edited by
5 5 votes

let suppose Y=f(A,B,C)

the expression for y=AB+ABC+BC

1)Implicant : for y the implicants are AB,ABC,BC basically in simple words implicant is 'for any SOP , the product term that implies our y is basically implicant ' i mean when your implicant would be 1 then y would be 1.

for given sop set any product term (AB or ABC or BC) 1 and it will make y=1.

2)Prime implicant : Implicants whose removal don't now imply y (mean their presence is prime)are called PI.

for y PI are AB,BC as if they are removed and here we lost y. ABC is not PI as if you remove it from y then still our y is not lost.

3)Essential PI : An EPI of a function y is one that cover a minterm of F , not covered by any other PI of y.

Minterm for given function are x'(y+y')(z+z') and y'z(x+x') and xz(y+y')

When you would solve given function using K-Map you will get f=x'+y'+z

For f if any one of (x' , y'z , xz) is 1 then it would make f=1 so these all are implicants.

as f= x'+y'+z and if we remove anyone of x' or y' or z then here we lost f so all three are PI.

http://web.cecs.pdx.edu/~mcnames/ECE171/Lectures/Lecture10.html

0 0 votes

 prime implicant isthe biggest subcube possible . if you minimize Z+~X+~Y ,~Y is one of the prime implicant of this not Y .

if you see z is a prime implicant so xz is an implicant of this function .

so option 3 . 

Page:
Voting & Accepting an answer helps improve the community
Answer:
← Previous · GATE CSE 1997 | Ques...Next → · GATE CSE 1997 | Ques...
← Previous in category · GATE CSE 1997 | Ques...Next in category → · GATE CSE 1997 | Ques...
Position:
Show:

Related questions

32 32 votes
1 answers 1 answer
8.9k
8.9k views
Kathleen asked Sep 29, 2014
8,905 views
GATE CSE 1997 | Question: 5.5
Consider a logic circuit shown in figure below. The functions $f_1, f_2 \text{ and } f$ (in canonical sum of products form in decimal notation) are :$f_1 (w, x, y, z) = \...
36 36 votes
2 answers 2 answers
15.5k
15.5k views
Kathleen asked Sep 29, 2014
15,501 views
GATE CSE 1997 | Question: 5.4
Given $\sqrt{(224)_r} =(13)_r$.The value of the radix $r$ is:$10$$8$$5$$6$
57 57 votes
5 answers 5 answers
17.3k
17.3k views
Kathleen asked Sep 29, 2014
17,335 views
GATE CSE 1997 | Question: 2.5
An N-bit carry lookahead adder, where $N$ is a multiple of $4$, employs ICs $74181$ ($4$ bit ALU) and $74182$ ( $4$ bit carry lookahead generator).The minimum addition ti...
11 11 votes
1 answers 1 answer
4.0k
4.0k views
Ruturaj Mohanty asked Dec 27, 2018
4,021 views
GATE Overflow | Mock GATE | Test 1 | Question: 58
Let $f(A, B, C, D)=\Pi (2, 3, 5, 9, 11, 12, 13)$The total number of prime implicants and essential prime implicants are denoted by $P$ and $Q$ respectively. What is the v...