2
$\begingroup$

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$
3
  • $\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. $\endgroup$ Jul 3 at 3:06
  • $\begingroup$ The formal specifications of the language is needed: the first clause regards sentential letters, aka atoms and the further clauses are used to generate compound sentences (non-atomic) using the connectives. That’s all $\endgroup$ Jul 3 at 13:08
  • $\begingroup$ Having defined atoms of formula without connectives, this fits perfectly with the intuitive explanation that they are “simple” formulas devoided of “suntactical structure” $\endgroup$ Jul 3 at 13:39
1
$\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$ Thanks. I guess I need more background to understand your ans. Anywhere I read more (please note I have never studied logic before) $\endgroup$
    – aman_cc
    Jul 3 at 3:28
0
$\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
  • $\begingroup$ Thanks, But it I give you (S and W) and W can't you derive S? Also it is a language thing - maybe in my language I do not have words for sunny and warm. but together it is just "hot" - so I'll say its a hot day $\endgroup$
    – aman_cc
    Jul 3 at 3:25
  • $\begingroup$ @aman_cc Sure, non-atomic propositions can entail atomic propositions; after all, whether a proposition is atomic or not depends merely on its form, not on its interpretation. As such, just as $S$ and $W$ are atomic propositions, so too is $H$; this is indeed regardless of the fact that $(S\text{unny}\:\&\:W\text{arm})\rightarrow H\text{ot}.$ $\endgroup$
    – Ryan G
    Jul 3 at 6:21
  • $\begingroup$ @RyanG - No I actually think Atomic Proposition are more fundamental concept and I'm all confused. I actually agree with MathSimp but I'm not able to get it clearly in my head $\endgroup$
    – aman_cc
    Jul 3 at 7:00
  • $\begingroup$ @aman_cc My comment was not in disagreement with mathsimp’s answer. Incidentally, I don’t know what the first sentence of your last comment above is meant to be disagreeing with. To rehash my points clearly: 1) yes an atomic proposition can be derived from non-atomic ones 2) no it’s not an interpretation (“language”) thing, merely a symbolism thing (i.e., how you symbolise your original natural-language sentence). So, while “hot” is a compound concept (upon interpretation), when symbolised as H, it is an atomic proposition. $\endgroup$
    – Ryan G
    Jul 3 at 7:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.