Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I would just like to clarify if I am on the right track or not; I have these questions:

Consider the Boolean functions f(x,y,z) in three variables such that the table of values of f contains exactly four 1’s. (i) Calculate the total number of such functions. (ii) We apply the Karnaugh map method to such a function f. Suppose that the map does not contain any blocks of four 1’s, and all four 1’s are covered by three blocks of two 1’s. Moreover, we find that it is not possible to cover all 1’s by fewer than three blocks. Calculate the number of the functions with this property.

1a: I have answered 70 (8C4) *C is combinaiton 1b: I have manually drawn up karnaugh maps and have obtained the answer 12 but my friend has 24, is there another way to do this?

Thank you

share|improve this question
    
Like you, I count $12$, $8$ in which the $1$’s occupy an L-shaped region and $4$ in which they occupy a sort of T-shaped region. –  Brian M. Scott Oct 17 '12 at 12:04
    
Why $70\cdot \binom{8}{4}$ instead of just $\binom{8}{4}$ for part (i)? For part (ii), consider functions of the form $xy \vee xz \vee yz$. –  Dilip Sarwate Oct 17 '12 at 12:05
    
sorry for the confusion, i meant the answer was 70 and i obtained it by (8C4) thank you for your responses –  Z Oj Oct 17 '12 at 12:07
    
@Brian M.Scott In addition to the L and T shapes aren't there also some S-like shapes? –  Alan Gee Oct 17 '12 at 12:26
    
@Alan: You’re right. It’s clearly my bedtime. They add another $4$, if I’m not mistaken, bringing my total to $16$. –  Brian M. Scott Oct 17 '12 at 12:33

2 Answers 2

L shapes: --. or --' or '-- or .-- count: 8

T shapes: -'- or -.- count: 4

Z shapes: -.. or ..- count: 4

Each of these shapes is 3-across on the map, so you can shift each across by one to get another boolean function.

total: 16

If you treat the side edges as wrap-arounds you get 32

share|improve this answer
    
The wording of that question was quite confusing, but I think this is what it means... –  Sean O'Brien Oct 17 '12 at 12:48
    
Yeah the wording of the question is very unclear. Keep in mind that the L-blocks can be covered by only two as well. Also I think the wrap-around of the edges should be included because that wrap-around takes into account renaming the variables (ie: making the x column the y column can produce a shape which appears disconnected on the map) –  Sean O'Brien Oct 17 '12 at 13:00
    
yeah thats whats confusing me a little now; from my understanding of the maps you try to obtain the minimum # of blocks that covers all the 1's (which in this case is 3) but a couple of my 's', and t maps can be undertaken with 2 blocks of 2 which brings my original total down to 8 if they don't need to overlap –  Z Oj Oct 17 '12 at 13:16

A "block of two" on a Karnaugh map corresponds to a Boolean function of the form $xy$ (complements of variables allowed). So we are looking for Boolean functions of weight $4$ ($4$ ONEs in the truth table or on the Karnaugh map) that can be covered by $3$ "blocks of two" but not by $2$ "blocks of two", that is, the minimum sum of products expression has three terms, and not two. The simplest form is thus $$xy \vee xz \vee yz$$ which is the T shape referred to (see also my comment on the main question), and complementing variables gives us $2^3 = 8$ different T shapes, some of which are "wrapped around" the edges (which is perfectly acceptable). Are there any others? Well, let's try counting. The principle of inclusion-exclusion tells us that

the total weight of $4$ equals the sum of the weights of the three "blocks of two" minus the sum of the weights of the pairwise intersections of "blocks of two" plus the weight of the intersection of all three "blocks of two".

Well, two different "blocks of two" must intersect in one position because if they intersect in both positions, they are identical, and if they don't intersect at all, they cover all $4$ ONEs in the function. So, all three "blocks of two" must also intersect in the same position giving $$4 = (2+2+2) - (1 + 1 + 1) + 1$$ as the total weight, and also showing that the T shape is the only one possible.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.