Propositional Logic: Atomic Statements
In Propositional Logic most books I read say - Atomic Statements are statements which can't be simplified further.
I find the above definition ambiguous or maybe based on intuition (i.e. what is 'simple')
Is there a more rigorous definition? For e.g. how do I go about proving, that a proposition P is atomic?
(I think this question is important - as I think if you have 'n' atomic statements, they will have more 'information' than any 'n-1' statements and any formula based on the 'n' statements - I know I'm vague here as I do not understand this well and is just intuitions right now)
$\endgroup$ 32 Answers
$\begingroup$You're correct -- this question is very important, because many statements in proof theory are proved by induction on the length of formulae, so it's essential to understand which formulae are atomic in order to understand the proof.
Atomic formulae are defined using the concept of "terms." Terms are defined recursively. A constant of your language is a term. A variable of your language is a term. If $t_1, \ldots, t_n$ are terms and $f$ is an $n$-ary function of your language, then $f(t_1, \ldots, t_n)$ is a term.
With terms defined, we can move on to atomic formulas. If $t_1, t_2$ are terms, then $t_1=t_2$ is an atomic formula. If $t_1, \ldots, t_m$ are terms and $P$ is an $m$-ary predicate of your language, then $P(t_1, \ldots, t_m)$ is an atomic formula.
And that's it. From the atomic formulae, we use the logical symbols $\lnot$ and $\land$, along with the existential quantifier $\exists$ to build up more complicated formulae. (Those are all that are necessary because we can use combinations of those symbols to create $\lor$ and $\forall$.)
$\endgroup$ 1 $\begingroup$Think of atomic sentences as sentences with no connectives. In sentential logic, $S$ = "it's sunny" is atomic but $S \land W$ = "it's sunny and it's warm" is not, since it has conjunctive meaning. So, a sentence is atomic iff it has no logical connectives.
$\endgroup$ 4
