# Tag Info

6

"arbitrary chosen" in a NP problem where the followup results in a P algorithm typically means that the choice matters a lot and trying them all and backtracking over bad choices looking for the result is what pushes the algorithm out of P. In addition it is possible to create a subformula that you cannot simplify that way. For example a formula that is ...

3

Check for solution. Grouping should be done using 2 quads

3

Karnaugh maps do not always give the simplest expression possible, but they do always give the simplest "Sum of Products" expression possible (https://www.facstaff.bucknell.edu/mastascu/eLessonsHTML/Logic/Logic3.html).

2

You can verify that the two expressions are equivalent by using some logical equivalences. Below I'm using 1 to represent true. \begin{align} a'bc'+a'bc + ab'c'+ab'c &= (a'bc'+a'bc) + (ab'c'+ab'c) &\text{associativity of } +\\ &= a'b(c'+c) + ab'(c'+c) &\text{distributivity, twice}\\ &= a'b(1) + ab'(1) &\text{inverse for }+\\ &...

2

Does your material use the (strange) convention of notating $\neg A$ as $A'$? If so, there are 6 literals (5 without the LHS). If $A'$ is distinct from $A$, there are 9 (8 without LHS) and the solution book is wrong.

2

The misunderstanding here is the same as in your previous question. If $B$ is true, the formula is true whatever the values of $A$ and $C$ are. This means that the whole of the $B$ circle needs to be shaded. Shading just the part at the top corresponds to saying "The formula is true if $B$ is true and $A$ and $C$ are both false." That is ...

2

Yes you can do it directly on the K-map. In order to get a minimal product of maxterms (aka product-of-sum [POS], aka conjunctive-normal-form [CNF]), you simply circle/unify the zeros that appear in the K-map instead of the ones. (It doesn't matter how you got the K-map, it can be from any representaiton of the function, it's just a table of the function's ...

1

Good job on $f_a = \overline acd \lor bc \lor bd$. With $f_b$, I'd denote it as $b\overline d\lor b\overline cd$ - you missed overlap with $\overline d$: $f_b = b\overline c \lor b\overline d$. I'd tally that as and inputs: 11 complemented: 3 ands: 5 gates/ors: 2 In the combined implementation, groups are still allowed to overlap: both blue ones can be ...

1

minterms & maxterms are complements. see eg Minterms, Maxterms, and K-Maps which explains the interrelationship in more detail. see also DeMorgans law used for complements.

1

First, when you are trying to group, you must use the biggest possible group. A group's size has to be a power of 2 (1, 2, 4, 8...). In this case you need to make 2 groups: cells 4, 5, 12, 13: $A'D$ cells 8, 9, 12, 13: $A'C$ Represented as SOP: $A'D+A'C$ Using the Distributive Law: $A'D+A'C=A'(C+D)$ About the way that you tried: You grouped: cells ...

1

K-map Simplification leads to the expression which you have arrived at . For checking the same you can create a truth table for your simplified expression and match the outputs with those of the initial expression. Or you could also use set operations on the given expression and reduce it . The final expression also is a XOR B if it helps .

1

First, you need to describe all three of your options using a minimum amount of literals. To achieve this you will need to do the following (use basic boolean algebra laws): Using the Distributive Law ($A(B+C) = AB + AC$): (a) $(w + x)y = wy + xy$ Option $b$ is already shown in its minimal form, so we can leave it like that: (b) $xy + yw$ To minimize ...

1

The only other way to group the 1's into pairs would be to group the ones in indices 0,2/1,5/and 6,7. All of these are groups of two, like your original solution, and no 1 is left on it's own. This solution would give you a result of equal simplicity. No, this is the minimum representation. If it were not the minimum representation, you would see terms that ...

1

Your answer is correct. It is also more reduced. The reason your book and the solver give you a bigger equation is because they use a greedy algorithm that attempts to match bigger groups (groups with less variable in them). This will have an optimal behavior if the map has no "don't cares" [reference needed]. To have optimal behavior with "don't care", you ...

Only top voted, non community-wiki answers of a minimum length are eligible