Which of the following is an atomic formula in first-order logic?
A¬P(x) — a predicate applied to a variable, with negation
BP(x) ∧ Q(y) — two predicate applications joined by conjunction
CP(x, y) — a predicate symbol applied to two terms
D∀x P(x) — a predicate universally quantified over x
An atomic formula has no logical connectives or quantifiers — it is a predicate applied to terms (or an equality statement). P(x, y) is a predicate applied to two terms and contains no connectives, making it atomic. ¬P(x) has the negation connective (complex); P(x) ∧ Q(y) has conjunction (complex); ∀x P(x) has a quantifier (complex). Any use of ¬, ∧, ∨, →, ↔, ∀, or ∃ makes a formula complex, regardless of how many atoms it contains.
Question 2 Multiple Choice
In a parse tree for the formula (P(x) ∨ Q(y)) → R(z), where are the atomic formulas located?
AAt the root node, since atoms give the formula its overall truth value
BAt the leaves of the tree, since atoms are the base cases of the recursive definition with no logical subformulas
CAt the internal nodes, since connectives are defined in terms of atomic truth values
DScattered at all levels, since atomic formulas can appear anywhere in the parse tree
Parse trees have connectives and quantifiers at internal nodes and atomic formulas at the leaves. For (P(x) ∨ Q(y)) → R(z): the root is →, its left child is ∨, under which are leaves P(x) and Q(y); the right child of → is the leaf R(z). Atoms are always leaves because they have no subformulas — there is nothing to branch further. This is precisely why they are called 'base cases': they are where the recursive decomposition of a formula terminates.
Question 3 True / False
The truth value of a complex formula is determined compositionally — computed bottom-up from the truth values of its atomic subformulas and the semantics of its connectives.
TTrue
FFalse
Answer: True
Compositionality is the foundational principle of logical semantics. An interpretation directly assigns truth values to atomic formulas (by specifying which predicate-tuple pairs hold). Every complex formula's truth value is then computed mechanically: ¬φ is true iff φ is false; φ ∧ ψ is true iff both are true; etc. This bottom-up computation from atoms through the parse tree is what makes logical semantics tractable — without it, you couldn't evaluate arbitrarily complex formulas.
Question 4 True / False
A formula that contains exactly one logical connective is considered atomic because it involves mainly a single logical operation.
TTrue
FFalse
Answer: False
Any use of a logical connective or quantifier — even exactly one — makes a formula complex. ¬P(x) has one connective but is complex; P(x) ∧ Q(y) has one connective but is complex. Atomic formulas have *zero* connectives or quantifiers. The intuition from the parse tree: any connective creates an internal node, meaning the formula has decomposable subformulas. Atoms are formulas with no internal nodes — they cannot be broken down further.
Question 5 Short Answer
Why are atomic formulas called the 'base cases' of logical syntax, and what role do they play in determining the truth value of complex formulas?
Think about your answer, then reveal below.
Model answer: Atomic formulas are base cases in the recursive definition of well-formed formulas: they are the starting point from which all complex formulas are built using connectives and quantifiers, and they are the only formulas with no logical subformulas. In the parse tree, atoms appear at the leaves — there is nothing further to decompose. For truth-value assignment, atoms play a unique role: an interpretation directly specifies which atomic formulas are true (by declaring which predicate-tuple pairs hold). Every other formula's truth value is computed compositionally from these atomic truth values, working up the parse tree through the semantics of each connective. Atoms are the 'inputs' to the compositional truth function; everything else is derived from them.
The term 'base case' maps directly to the mathematical structure: the recursive definition of formulas has atoms as base cases (non-recursive) and complex formulas as recursive cases (defined in terms of simpler formulas). Truth evaluation mirrors this: atom truth values are given; complex truth values are computed. This is the same pattern as in inductive definitions throughout mathematics — understand the base case and the recursive step, and you understand the whole structure.