In Boolean algebra, A + A equals:

A. The idempotent law. Variables hold only 0 or 1, so there is nothing to accumulate — unlike ordinary algebra.

(A · B)‾ is equivalent to:

Ā + B̄. De Morgan: break the bar and change the AND to an OR.

Karnaugh map headings use Gray code so that adjacent cells:

differ in exactly one variable. Single-variable adjacency is what allows a variable to be eliminated when cells are grouped.

A valid Karnaugh map group may contain:

only powers of two. Groups must be 1, 2, 4, 8 … cells and rectangular. A group of three cannot eliminate a variable cleanly.

A group of 4 cells on a K-map eliminates how many variables?

2. Each doubling of the group size removes one more variable, so 4 cells remove two.

The four corner cells of a 4×4 Karnaugh map:

form a valid group of 4. The map wraps in both directions, so the corners are all adjacent to one another.

A + Ā·B simplifies to:

A + B. Expanding gives (A + Ā)(A + B) = 1·(A + B) = A + B.

NAND is functionally complete, which means:

any circuit can be built from NAND gates alone. NOT, AND and OR can all be constructed from NAND gates, so anything at all can be. NOR shares this property.

Boolean Algebra and Logic Circuits — Computer Science Notes, Worked Examples and Quiz

Algebra where everything is 0 or 1

Boolean algebra is ordinary algebra's stricter cousin: variables take only two values, and the operations are AND, OR and NOT rather than plus and times. Its purpose is practical — a simplified expression means fewer logic gates, which means a cheaper, smaller and faster circuit.

Many of the laws look familiar, which helps, but two do not exist in ordinary algebra at all. A + A = A and A · A = A hold here because there is nothing between 0 and 1 to accumulate. Those idempotent laws do much of the simplifying work.

Law	AND form	OR form
Identity	A · 1 = A	A + 0 = A
Null	A · 0 = 0	A + 1 = 1
Idempotent	A · A = A	A + A = A
Inverse	A · Ā = 0	A + Ā = 1
Absorption	A · (A + B) = A	A + A·B = A
De Morgan	(A·B)‾ = Ā + B̄	(A+B)‾ = Ā · B̄

De Morgan's laws, in words

Break the bar, change the sign. (A·B)‾ = Ā + B̄ — "not (both)" is the same as "either one is not". (A+B)‾ = Ā·B̄ — "not (either)" is the same as "neither". These are the laws that let a circuit be rebuilt entirely from NAND gates, which matters because NAND is the cheapest gate to manufacture.

Karnaugh maps

Algebraic simplification works but needs inspiration — you have to see which law to apply. A Karnaugh map makes simplification mechanical instead, which is why it is the method examined.

The map is a truth table drawn as a grid, with the crucial feature that the headings run in Gray code order — 00, 01, 11, 10 — so that adjacent cells differ in exactly one variable. That is what makes grouping valid: any variable that changes within a group cannot matter, so it drops out of the expression.

headings run 00, 01, 11, 10(Gray code)rules for grouping:• groups must contain 1, 2, 4, 8 … cells• groups must be rectangular• make groups as LARGE as possible• groups may overlap• the map wraps: edges and corners are adjacent• every 1 must be covered at least oncea bigger group means a simpler term — always take the largest

Gray code: the heading orderso adjacent cells differ in one variable only
group of 2: eliminates 1 variable
group of 4: eliminates 2 variablesalways prefer it to two groups of 2
wrapping: edges are adjacentthe corners of a 4×4 map form a valid group of 4

Worked example

Simplify the expression that is 1 for the minterms ĀB̄, ĀB, AB (that is, everything except AB̄) using a Karnaugh map.

Draw a 2×2 map with A across and B down, and place 1s in three cells, leaving AB̄ as 0.Placing the 1s correctly is where most errors happen — check each minterm against its cell.
Group the two cells where A = 0 (ĀB̄ and ĀB). B changes within the group, so it drops out, leaving Ā.A variable that changes inside a group cannot affect the output, so it is eliminated.
Group the two cells where B = 1 (ĀB and AB). A changes within this group, so it drops out, leaving B.Groups may overlap — ĀB is used twice, which is allowed and often necessary.
Every 1 is covered, so the simplified expression is Ā + B.The groups are combined with OR. Two gates instead of the four the original needed.

Ā + B

Take the largest groups, and use the wrap

Two groups of two give a longer expression than one group of four covering the same cells. And the map wraps round: the leftmost and rightmost columns are adjacent, as are the top and bottom rows, so the four corners of a 4×4 map form a legitimate group. Missing the wrap is the most common reason for an answer that is correct but not fully simplified — and questions usually ask for the simplest form.

Building circuits from one kind of gate

NAND and NOR are described as functionally complete: any logic circuit whatsoever can be built from copies of either one alone. This matters commercially, because a factory that makes only NAND gates can produce any chip.

The constructions follow from De Morgan's laws. A NAND with both inputs tied together gives NOT. A NAND followed by that NOT gives AND. And by De Morgan, an OR is a NAND fed with both inputs inverted.

The constructions worth knowing

NOT from NAND: tie both inputs together.
AND from NAND: a NAND followed by a NAND used as NOT — three gates in total.
OR from NAND: invert both inputs first, then NAND them.
A half adder produces sum = A XOR B and carry = A AND B.
A full adder takes a carry in as well and is built from two half adders plus an OR.
Simplifying first always reduces the gate count, and gate count is what costs money.

From a problem description to a circuit

The most demanding question in this topic gives a situation in words and asks for a logic circuit. The route is always the same four steps, and doing them in order is what makes it manageable.

First, identify the inputs and give each a letter, being explicit about what 1 means — a sensor that reads 1 when a door is open behaves quite differently from one that reads 1 when it is closed. Second, build the truth table, covering every combination of inputs. Third, write the Boolean expression by taking each row that outputs 1 and ORing those terms together. Fourth, simplify with a Karnaugh map and draw the result.

from a truth table to an expression:take every row whose output is 1write the AND term describing that row(variable if 1, complemented if 0)OR the terms togetherA=0 B=1 → Ā·BA=1 B=1 → A·Bexpression: Ā·B + A·Bwhich simplifies to Bthis is called sum-of-products form

each 1 row: one AND terma product of all the inputs
OR between them: the sumhence sum-of-products
simplify after: a Karnaugh mapthe raw form is never the simplest

Define what 1 means before anything else

An alarm should sound when the door is open and the system is armed. If the door sensor gives 1 for closed, then the expression needs D̄, not D — and every later step inherits the mistake. Writing "D = 1 means the door is closed" at the top of the answer costs one line and prevents the most expensive error in the topic.

Boolean Algebra and Logic Circuits