Complement of a function

Also called: function complement, complemented function, F prime, inverse function, complement function

The function F′ that is 1 exactly where F is 0, and 0 where F is 1. In Σm/ΠM form, it uses the same indices with the other symbol.

The complement of a function F, written F′ (or F with a bar), flips every output: F′ is 1 on F's 0-rows and 0 on F's 1-rows.

In canonical form it is just bookkeeping. If F = Σm(S) = ΠM(R):

So to complement, change the symbol or the list, never both. Changing both just rewrites F itself; see canonical form conversion.

From an expression, use de morgans laws: swap AND with OR and complement every literal, keeping the grouping. The complement of is .

Why it is useful:

The minimal POS of F is the De Morgan of the minimal SOP of F′. Grouping F's 0s gives F′.
Each maxterm is the complement of the matching minterm: Mᵢ = (mᵢ)′.
Some circuits naturally produce F′, and an inverter at the output fixes it.

Do not flip the bits of the indices. That renames rows; it does not swap 1s and 0s.

Worked examples

Example

F(A, B, C) = Σm(0, 3, 5). Write F and F′ both ways.

1.
1-rows of F: {0, 3, 5}. 0-rows of F: {1, 2, 4, 6, 7}.
2.
F = Σm(0, 3, 5) = ΠM(1, 2, 4, 6, 7).
3.
F′ = Σm(1, 2, 4, 6, 7) = ΠM(0, 3, 5).
4.
One step (symbol only, or list only) complements. Both steps gets you back to F.

Example

F = . Find F′.

1.
Bracket the product and break the outer bar: .
2.
= and = C.
3.
F′ = .
4.
Check A = 1, B = 1, C = 1: F = 1 + 0 = 1, and F′ = 0 · 1 = 0. The table above shows the columns are opposite in every row.

Changing both the symbol and the list. That gives F again, not F′.
Flipping the bits of each index, such as turning row 1 (001) into row 6 (110).
Complementing each literal without swapping AND and OR.

Interactive questions with instant feedback and a worked solution for every wrong answer.

Complement of a function is taught in Boolean Simplification and Boolean Algebra.