Propositional Logic · step 10 of 13

Functional completeness & adequate sets

A set of connectives is functionally complete (or adequate) if every truth function can be written using only its members. {¬, ∧, ∨} is complete because every formula has a DNF; {¬, ∧} and {¬, ∨} are complete by De Morgan; and remarkably each of NAND and NOR is complete on its own, which is why real chips can be built from a single gate type.

Practise functional completeness & adequate sets free → All Propositional Logic subtopics

✓ Unlimited questions · marked criterion by criterion · no card needed

Method: how to approach it

The order below is what examiners expect to see, and each step carries its own marks.

Take a known complete set as your targetStandard practice: show you can express ¬ and ∧ (or ¬ and ∨) using your connectives. Completeness then follows because every function has a DNF.
Build negation firstWith NAND, ¬p = p ↑ p. With NOR, ¬p = p ↓ p. Negation is almost always the easiest starting brick.
Build one binary connectivep ∧ q = ¬(p ↑ q) = (p ↑ q) ↑ (p ↑ q). Composing with the negation you just built gets you the rest.
To prove INCOMPLETENESS, find a preserved propertyIf every connective in the set preserves truth (all-T input gives T), no formula over it can be a contradiction, so the set is inadequate. {∧, ∨, →} fails this way.

Worked example

Express p ∨ q using only NAND (↑).

Recall p ↑ q is ¬(p ∧ q).
Negation: ¬p = p ↑ p, and ¬q = q ↑ q.
By De Morgan, p ∨ q = ¬(¬p ∧ ¬q) = ¬p ↑ ¬q.
Substitute the negations built above.

Answer. p ∨ q = (p ↑ p) ↑ (q ↑ q).

Where marks get dropped

These are the specific errors that cost credit on functional completeness & adequate sets questions — QED's rubric penalises each of them separately.

Claiming completeness after expressing only one connective. You need enough to reach a full adequate set — ¬ alone is not enough.
Confusing NAND with NOR. p ↑ q is ¬(p ∧ q); p ↓ q is ¬(p ∨ q). Their tables agree in only two rows.
Assuming {∧, ∨} is complete. It is not: with no negation available, every formula built from it is true when all variables are true, so ¬p is unreachable.

Practise this until it is automatic

Unlimited fresh questions

QED generates new functional completeness & adequate sets problems on demand at warm-up, exam and challenge level, so you can drill this one skill until it stops costing you marks.

Marked like an examiner

Every answer is scored against a point-by-point rubric with partial credit, so you see exactly which step of the method broke down — not just a tick or a cross.

Answer in real notation

A one-tap symbol palette, a visual equation editor and a truth-table builder — or photograph your handwritten working and QED converts it to LaTeX.

Saved to your library

Every question you generate is kept and re-takeable as a timed exam, and your Propositional Logic mastery is tracked so you know when this is exam-ready.

Functional completeness & adequate sets — frequently asked questions

Why is NAND used in real hardware?

Because one gate type can implement every Boolean function, fabrication is simpler and cheaper. CMOS NAND is also faster and uses fewer transistors than the AND it would replace.

Is {→, ¬} functionally complete?

Yes. p ∨ q = ¬p → q, and with ¬ available De Morgan then gives ∧. Many axiomatic proof systems use exactly this pair as primitives.

How do I prove a set is NOT complete?

Find a property preserved by every connective in the set but not by some truth function. Truth-preservation, falsity-preservation, monotonicity and self-duality are the standard four (Post’s theorem).

The rest of Propositional Logic

Connectives, truth tables, equivalences and normal forms. Each subtopic below has its own method, worked example and mark-losing traps.

Ready to make functional completeness & adequate sets exam-proof?

Generate your first questions free — no card, no setup, no personal data stored. Practise until the method is second nature.

Start practising free →