Atomic formula

This article is about a concept in mathematical logic. For the concept from chemistry, seechemical formula.

Inmathematical logic,anatomic formula(also known as anatomor aprime formula) is aformulawith no deeperpropositionalstructure, that is, a formula that contains nological connectivesor equivalently a formula that has no strict subformulas. Atoms are thus the simplestwell-formed formulasof the logic. Compound formulas are formed by combining the atomic formulas using the logical connectives.

The precise form of atomic formulas depends on the logic under consideration; forpropositional logic,for example, apropositional variableis often more briefly referred to as an "atomic formula", but, more precisely, a propositional variable is not an atomic formula but a formal expression that denotes an atomic formula. Forpredicate logic,the atoms are predicate symbols together with their arguments, each argument being aterm.Inmodel theory,atomic formulas are merelystringsof symbols with a givensignature,which may or may not besatisfiablewith respect to a given model.

Atomic formula in first-order logic

The well-formed terms and propositions of ordinaryfirst-order logichave the followingsyntax:

Terms:

• $t\equiv c\mid x\mid f(t_{1},\dotsc,t_{n})$,

that is, a term isrecursively definedto be a constantc(a named object from thedomain of discourse), or a variablex(ranging over the objects in the domain of discourse), or ann-ary functionfwhose arguments are termst_k.Functions maptuplesof objects to objects.

Propositions:

• $A,B,...\equiv P(t_{1},\dotsc,t_{n})\mid A\wedge B\mid \top \mid A\vee B\mid \bot \mid A\supset B\mid \forall x.\ A\mid \exists x.\ A$,

that is, a proposition is recursively defined to be ann-arypredicatePwhose arguments are termst_k,or an expression composed oflogical connectives(and, or) andquantifiers(for-all, there-exists) used with other propositions.

Anatomic formulaoratomis simply a predicate applied to a tuple of terms; that is, an atomic formula is a formula of the formP(t₁,…,t_n) forPa predicate, and thet_nterms.

All other well-formed formulae are obtained by composing atoms with logical connectives and quantifiers.

For example, the formula ∀x. P(x) ∧ ∃y. Q(y,f(x)) ∨ ∃z. R(z) contains the atoms

• $P(x)$
• $Q(y,f(x))$
• $R(z)$.

As there are no quantifiers appearing in an atomic formula, all occurrences of variable symbols in an atomic formula are free.

See also

• Inmodel theory,structuresassign an interpretation to the atomic formulas.
• Inproof theory,polarityassignment for atomic formulas is an essential component offocusing.
• Atomic sentence

Further reading

• Hinman, P. (2005).Fundamentals of Mathematical Logic.A K Peters.ISBN1-56881-262-0.