Logic, Sets & Counting Mind Map

Every logic, sets & counting visualization on this site on one map. The branches are the main ideas. Each leaf is a page; the grey line under it is the one thing to remember about it. Click a branch to focus on it, click a page to open it.

Recall mode hides the page names. Read the hint, say the name, then click the "?" to check.

1. How the map is organized

Overview of the logic, sets & counting mind map: Boolean logic, Counting principles, Automata, Proofs. — The map at a glance: 4 branches, 9 pages.

Ask what the page answers:

Is a statement true, and how small can the formula be? Boolean logic.
How many objects are there, or must two collide? Counting principles.
Does a string match a pattern? Automata: a regex becomes a machine that reads one character at a time.

2. The branches side by side

Branch	Works on	Main tool
Boolean logic	true/false formulas	truth table, K-map grouping
Counting principles	finite sets	add/subtract overlaps, worst case
Automata	strings	states and transitions

3. Five facts to remember

De Morgan: NOT (A AND B) = (NOT A) OR (NOT B), and the same for sets with complement.
Neighbouring cells of a Karnaugh map differ in one bit (Gray code), so a group drops a variable.
|A ∪ B ∪ C| = |A| + |B| + |C| − |A∩B| − |A∩C| − |B∩C| + |A∩B∩C|.
The n-th Catalan number is C(2n, n) / (n + 1).
Every NFA has an equivalent DFA, but it can need up to 2ⁿ states.

See all logic, sets & counting pages in the index, or the other mind maps.