3

What is the set of propositional formulas?

I am not sure if I understand this

Alim Teacher
  • 1,261
  • 1
    Possibly as describe in the inductive definition in Wikipedia – Henry May 06 '15 at 19:10
  • It's generally taken to be the least set closed under the operations of (say) conjunction and negation (the other connectives being definable from these two). Do you have something more specific in mind? – Nagase May 06 '15 at 19:20
  • Well I have to define the set of propositional formulas using Type 2 grammar (context-free), so I was wondering what the set actually is. – Alim Teacher May 06 '15 at 19:25
  • The set of all strings which satisfy the formation rules. – Doug Spoonwood May 07 '15 at 02:44
  • @DougSpoonwood The smallest set of all strings which satisfy the formation rules. – Bruno Bentzen May 07 '15 at 03:31
  • @BrunoBentzen Why are you emphasizing smallest? The set of all strings which satisfy the formation rules seems unique to me. – Doug Spoonwood May 08 '15 at 01:07
  • 1
    @DougSpoonwood In fact it's not unique: the problem is because there are infinitely many sets of strings that satisfy the formation rules - rules such as (1), (2) and (3) in my answer below - but still contain some "garbage" like '$\rightarrow\neg$' or '$P \neg $' as elements of it. This is why we need (4), for "closing the back door" saying that the set of wff is the smallest set satisfying (1),(2) and (3). This closing the back door rule is actually the intersection of the family of all set of strings over $L_V$ satisfying the formation rules. – Bruno Bentzen May 08 '15 at 02:18
  • @BrunoBentzen " In fact it's not unique: the problem is because there are infinitely many sets of strings that satisfy the formation rules - rules such as (1), (2) and (3) in my answer below - but still contain some "garbage" like '→¬' or 'P¬' as elements of it."

    Alright, I see that given the way you've defined things. However, the way I usually understand things is more like "1. All lower case letters of the alphabet with or without subscripts are variables". And then we have rules for the connectives.

     – Doug Spoonwood May 08 '15 at 20:29
  • What are the formation rules you have for propositional formulas? – Doug Spoonwood May 08 '15 at 23:36

1 Answers1

2

From what I stated previously elsewhere:

I assume you are referring to a propositional language $L_V=\left<V,\rightarrow,\bot \right>$, where

  • $V$ is a set, called the proposition symbols of $L_V$.

Now let $L_\Sigma^*$ denote the set of all strings of $L_V$.

The usual definition of the set of well-formed formula of $L_V$, call it $PROP_{L_V}$ is then:

Definition (PROP) The set PROP of well-formed formulas of $L_V$ is the set satisfying:

  1. $\alpha \in PROP$ if $\alpha \in V$
  2. $(\neg\alpha) \in PROP$ if $\alpha$ is a wff
  3. $(\alpha \rightarrow \beta) \in PROP$ if $\alpha$ and $\beta$ are wff
  4. No string that is not obtained by (1),(2) or (3) is in PROP.

Note that (4) assures that this set is unique. Indeed, there are infinitely many sets of strings over $L_V$ satisfying (1), (2) and (3), but still containing some "garbage" such as

'P(¬', '¬→→', '$Q→(¬$' ...

as elements of it. That is, satisfying the formation rules is a sufficient condition for being in $PROP$, but it does not uniquely define any set (Intuitively, it's kind of similar with the fact that from a sentence such, say, "there is a book on the table", one cannot conclude that neither there is one and only one book nor that there are no more objects on the table.)

In order to exclude those undesirable strings we state (4) for "closing the back door" saying that $PROP$ is the smallest set of strings over the rules (1),(2) and (3), which is actually the intersection of the family of all set of strings over $L_V$ satisfying the formation rules.

Community
  • 1
Bruno Bentzen
  • 3,362