Questions: Adequacy and Completeness of Connective Sets

Question 1

Why is {∧, ∨} not an adequate set of connectives for propositional logic?

• A. Because ∧ and ∨ cannot express conditional (→) statements
• B. Because every formula built from only ∧ and ∨ is a monotone function, and negation is non-monotone so it cannot be expressed
• C. Because {∧, ∨} requires too many connectives — only single connectives can be adequate
• D. Because ∧ and ∨ share the same truth table when both inputs are true

Answer: (B)

The structural argument for non-adequacy of {∧, ∨} is monotonicity: every formula built using only ∧ and ∨ has the property that flipping any variable from F to T can never change the output from T to F. But negation is not monotone — ¬T = F, so flipping the input from F to T flips the output from T to F. Since monotonicity is preserved by ∧ and ∨ and negation violates it, negation cannot be expressed using only {∧, ∨}. This is not about expressibility of specific connectives (option A) but about a fundamental structural property the inadequate set cannot simulate.

Question 2

Which of the following is a singly adequate connective — one that can express all truth functions by itself?

• A. Disjunction (∨), because any formula can be written as a disjunction of cases
• B. Conditional (→), because → combined with itself can simulate all other connectives
• C. NAND (↑), because ¬p ≡ p ↑ p and p ∧ q ≡ (p ↑ q) ↑ (p ↑ q)
• D. Exclusive-OR (⊕), because any two truth values can be combined with XOR

Answer: (C)

NAND (p ↑ q, true unless both are true) is singly adequate. You can derive: ¬p ≡ p ↑ p (NAND with itself = negation), and p ∧ q ≡ (p ↑ q) ↑ (p ↑ q) (negate the NAND). With negation and conjunction, {¬, ∧} is adequate, so NAND alone suffices. Disjunction (option A) is not adequate alone — it cannot express negation. Conditional (option B) cannot express constant-false or negation without a false constant. XOR (option D) is not adequate — it can only express parity functions and cannot simulate conjunction.

Question 3

The set {¬, →} is an adequate set of connectives because negation and the conditional together can express all truth functions.

• T. True
• F. False

Answer: True

This follows by showing {¬, →} can simulate all connectives in {¬, ∧, ∨}, which is already known adequate. The key step: p ∨ q ≡ ¬p → q (if not-p then q). Once you have ¬ and ∨, De Morgan's gives ∧. So {¬, →} can express ¬, ∧, and ∨, and since {¬, ∧, ∨} is adequate (any truth function can be written in DNF), {¬, →} inherits adequacy. This is why Hilbert-style proof systems for propositional logic often use only {¬, →} as primitive connectives.

Question 4

A set of connectives is adequate if and only if it contains at least three connectives.

• T. True
• F. False

Answer: False

This is wrong in both directions. NAND alone (a single connective) is adequate — so fewer than three suffices. Meanwhile, {∧, ∨, →} contains three connectives but is not adequate, because no combination of these can express negation: every formula using only ∧, ∨, → evaluates to T when all variables are T, so the constant-false function ⊥ and ¬p are both inexpressible. Adequacy depends on the logical structure of the connectives chosen, not merely their number.

Question 5

Prove informally that {∧, ∨} is not an adequate set of connectives by identifying a structural property that all formulas built from only ∧ and ∨ share.

Model answer: Every formula built from only ∧ and ∨ is monotone: if you flip any variable's value from F to T, the output can only stay the same or change from F to T — it can never change from T to F. This is because ∧ and ∨ are each monotone operations (making an input 'more true' can only make the output 'more true'), and the composition of monotone functions is monotone. Negation violates monotonicity — when p = T, ¬p = F, so flipping p from F to T flips the output from T to F. Since monotonicity is preserved by {∧, ∨} but negation is not monotone, negation cannot be expressed.

This proof technique — finding a structural invariant that the target function violates — is the standard approach to proving non-adequacy. Rather than trying all possible formulas (infinitely many), you identify a property that every formula in the set must satisfy, then show the target truth function lacks that property. The same technique proves that {→} alone is not adequate (all tautologies map all-T inputs to T, so constant-false is inexpressible).