# What is the set of propositional formulas?

What is the set of propositional formulas?

I am not sure if I understand this

• Possibly as describe in the inductive definition in Wikipedia May 6, 2015 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? May 6, 2015 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. May 6, 2015 at 19:25
• The set of all strings which satisfy the formation rules. May 7, 2015 at 2:44
• @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. May 8, 2015 at 2:18

From what I stated previously elsewhere:

I assume you are referring to a propositional language $$L_V=\left$$, 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.