Function covers possible and boolean functions possible


#1

a) let g and h be two boolean functions with 3 variables.Function g has x minterms and let h be a function that covers g. Then how many such functions (i.e h are possible)?
b) How many boolean functions are possible with 3 variables such that there are exactly 3 minterms?


#2

Solution for B:

We have 3 variables, so total number of entries in the table will be 2^3 = 8 rows out of which any 3 rows can have a value mapped to it as 1, i.e., only 3 rows can be min-terms.

So, answer 8C3 = 56 (i.e., out of 8 combinations i will assign value 1 to any of the 3 combinations).


Solution for A:
A switching function h is said to cover g only if h assumes true value ( 1 ) wherever g does.

Let us look at a table:

  •        g   h    
    
  •    0   0   0,1   --> 2 options for h
    
  •    1   0   0,1   --> 2 options for h
    
  •    2   0   0,1   --> 2 options for h
    
  •    3   1   1     --> h has to have 1 here if it has to cover g, so only 1 option
    

h here assumes true value at ( 0, 1, 2 & 3 ) whereas g assumes true value at ( 3 ) , so here we can say that h covers g.
We will have ( 2 * 2 * 2 = 8) funtions which can cover g.

Given here is that both g and h are a boolean function of 3 variables,
so, out of 2^3 = 8 rows in g it is given that x min-terms are present so function h will have to have a value of 1 (i.e., min-terms) wherever g has a true value so out of 8 rows we now only have ( 8 - x ) rows left for h where it can accept any value, either 0 or 1.

Therefore the answer to your question is ( 2^(8 - x) ) functions are possible which can cover g .


#4

(a)
Here we can choose the x minterms.
So if we write like this ’ C(8,x) * 2^(8-x) ’ then we would be calculating a lot of redundant functions.

So in this question we would be having a selection approach to solve the problem.

C(8,x) + C(8,x+1) + ..... C(8,8)

In general we can write:

C(2^n,x) + C(2^n,x+1) +…C(2^n,2^n)

(b)
The answer is simply C(8,3)


#5

If we consider the general solution , let us have x minterms of a function at a time… So every x minterm combination may lead to a distinct function… So for covering we may have (x+1) minterms , or (x+2) minterms and so on till 2^n which will be 8 here.

What I mean to say is if (x+1) minterm constitute a function , so is (x+2) minterm combination… Hence required number of functions here will be = C(8,x) + C(8,x+1) + C(8,x+2) + C(8,x+3) + … + C(8,8) which should be the required answer to a) part…

It is just like given that every x attributes of a relation form a candidate key of that relation , how many super-keys are possible…I hope this analogy makes the problem clear.


#6

Let us consider the value of x = 3, i.e., 3 min-terms.

If we solve it like:
C(8,3) + C(8,4) + C(8,5) + C(8,6) + C(8,7) + C(8,8) = 56 + 70 + 56 + 28 + 8 + 1 = 219 (ANSWER)

If we solve it like:
( 2^( 8 - 3 ) ) = 2^5 = 32 (ANSWER)

So what is the correct answer, can you please clear my doubt ? :slight_smile:


#7

Read the question again. You are fixing the minterms. But you can choose the minterms here.
Example:
.. g h
0 0 x
1 1 1
2 0 x
3 0 x

x - don’t care

Now h cover g in the above example. according to your answer it would be 2^(4-1) = 8
Here you have assumed minterm 1 to be true. But in question it is given that function g has 1 minterm(say x=1).

Now if i choose minterm 0 as 1 or minterm 2 as 1 or minterm 3 as 1.

Say minterm 2=1
.. g h
0 0 x
1 0 x
2 1 1
3 0 x


#8

That means I will first have to select the min-terms and then find its covering functions, in that case my answer should be ( C( 8, 3 ) * 2^( 5 ) ) = 56 * 32 = 1792 and here we are considering many redundant solutions too.
So we should follow the general solution:
C(8,3) + C(8,4) + C(8,5) + C(8,6) + C(8,7) + C(8,8) = 56 + 70 + 56 + 28 + 8 + 1 = 219.

Didi i get it right now?


#9

Yes thats what i wrote first. if you select and then multiply then there would be a lot of redundant functions.

For example in my above given example,
for minterm 0 and minterm 1 you will get the same h function (1 1 1 1) . So by multiplying you would be calculating it twice. Like this many repetitions would be there. Try figuring it out.

Then read the description of my solution. You will understand the logic well…


#10

I got it… Thanks :+1: