Boolean algebra and Karnaugh maps

Boolean operations are not ordinary arithmetic

P, Q and R take values 0 or 1. Write the product of P and Q for and, the sum of P and Q for inclusive or, and a bar over P for not P. These are the connectives from 3A in Boolean notation. In particular, one or one is one. Evaluate complements, then products, then sums unless brackets say otherwise

Identity, domination, repetition and complements

Use these laws for either possible value of P. The constants are Boolean false and true. Repeating an input does not change it, and complementing twice restores it

Which Boolean calculation is correct?

Order, brackets and two distributive laws

Sum and product are each commutative and associative. Both distributive laws hold. The second is unfamiliar from ordinary arithmetic, so use Boolean laws rather than integer algebra

Sets give the same algebra

Fix a universe U. For an arbitrary x in U, let P mean x belongs to A and Q mean x belongs to B. Union corresponds to inclusive or, intersection to and, and complement relative to U to not. The empty set corresponds to 0 and U to 1. A Boolean identity therefore gives a set identity by testing membership of an arbitrary element

Prove a set identity, ungraded

For A and B contained in the same universe U, prove that the complement of their union equals the intersection of their complements. Use an arbitrary x in U and explain both directions through membership equivalences. Independently written proof is ungraded

Model: membership proves equality

An arbitrary x in U belongs to the complement of A union B exactly when it belongs to neither A nor B. That means it belongs to the complement of A and to the complement of B, hence to their intersection. Every step is reversible, so the sets have exactly the same members. Complements must use the same universe

De Morgan and duality

To complement a sum, complement every input and change the sum to a product. To complement a product, change it to a sum of complements. More generally the dual of a Boolean identity exchanges sum with product and 0 with 1. Duality creates another identity; it does not say that the two expressions are equal

P = 1 and Q = 0. What is the value of the complement of PQ?

Absorb a redundant term

The first reduction holds because P already covers every assignment where PQ is true. Its dual absorbs a redundant sum in a product. For the other reduction shown, distribute the sum over the product, then use the complement law

Simplify with justified steps, ungraded

Simplify the displayed expression using Boolean laws. Name the law used at each significant step, then check all four input assignments. A selected equivalent expression does not assess this independently written derivation

Model: a dual distribution

Commutativity puts Q first in each bracket. The reverse of the dual distributive law gives Q + P(not P). The complement product is 0 and Q + 0 = Q. In input order 00, 01, 10, 11, the original product has values 0, 1, 0, 1, agreeing with Q in every case

Products, literals and minimum forms

A literal is a variable or its complement. A product term is an and of literals; a sum of products is an or of such terms. A full three-input product such as P(not Q)R selects one assignment. In this section minimum means fewest product terms first, then fewest total literals. Equivalent minimum forms can differ. The constants 0 and 1 are allowed

A two-input map is a rearranged truth table

Use rows P = 0, 1 and columns Q = 0, 1. Each cell represents one input assignment. For ones at 01, 10 and 11, group the P = 1 row and the Q = 1 column. The two groups overlap at 11 and give F = P + Q. The zero at 00 prevents one four-cell group

A two-input map has ones only at 00 and 11. Can they form one group?

Three inputs need Gray column order

Use rows P = 0, 1 and columns QR = 00, 01, 11, 10. QR here labels a pair of input digits. Adjacent columns differ in exactly one digit, including the first and last across the boundary. The order 00, 01, 10, 11 would wrongly put a two-digit change between middle columns

F is 1 exactly at 000, 010 and 111. What entry belongs in row P = 0, column QR = 10?

Valid groups and how they remove literals

Group rectangles of 1, 2, 4 or 8 one-cells. Rectangles may wrap across the left and right edges; top and bottom rows are also adjacent. Every combination of the changing inputs must be present. A group may not include a zero. Keep each input that is constant: positive if 1, complemented if 0. Drop each input that varies. Larger groups remove more literals

Worked boundary group

Suppose the ones are 000, 010, 100 and 110. They occupy the first and last columns in both rows. Those columns are adjacent across the boundary, forming a four-cell group. P and Q both vary while R stays 0, so F is the complement of R

A group contains only assignments 000 and 010. Which inputs remain in its product?

Overlap may be necessary for a small cover

For ones at 001, 011, 101, 110 and 111, the four R = 1 cells give R. The pair 110, 111 gives PQ and covers the remaining one at 110. Reusing 111 is valid because Boolean repetition changes nothing. Together the groups give F = R + PQ

Check coverage as well as group size

Every one must be covered and no zero may be covered. Compare complete covers; choosing one large group is not by itself a proof that the final expression is minimum. An essential group is one that must be chosen because it alone among the maximal valid groups covers a particular one-cell. Check any remaining choices against the stated term and literal criteria

Construct and compare covers, ungraded

Draw a three-input map for ones at 000, 001, 010, 101, 110 and 111. Find two different minimum sums of products. List the assignments in each group, justify why no smaller cover works, and verify both expressions against all eight assignments. Independent map construction and justification are ungraded

Model: two equally small answers

There is no all-one quad: every possible four-cell group meets a zero, at 011 or 100. Each valid group therefore covers at most two ones, so six ones need at least three groups. One cover pairs (000,001), (010,110), (101,111). Another pairs (000,010), (001,101), (110,111). Each uses three two-literal terms, proving both are minimum. Both have output 1,1,1,0,0,1,1,1 in input order 000 through 111

Constants and isolated cells

An all-zero map gives F = 0 with no one-groups. An all-one map gives F = 1 because all inputs vary in a single full-map group. An isolated one must be a singleton and keeps every input literal. Do not join diagonal ones or introduce unspecified don’t-care cells to make a simpler answer

Use an exhaustive check as a second method

For two or three inputs, a short program or spreadsheet can enumerate all four or eight assignments. Evaluate the original specification and the proposed expression separately and compare each row. One mismatch refutes equivalence. Agreement on every assignment proves equivalence for that Boolean function, but does not alone prove minimality; compare valid covers for that. This check is optional technology practice, not automatic credit

A proposed simplification agrees with the original in all eight three-input assignments. What does that establish?