# How to decide if a propositional formula is a well formed?

So, I have the following propositional formula: (((P → Q) ∨ S) ↔ T) How do I decide if it's well formed?

• Do you understand what "well-formed" means? If so, I'm not sure what you're asking. – David Richerby Oct 25 '15 at 17:05

Perhaps this might help.

Well-formed: $(P \lor Q)$.

Not well-formed: $(P \lor Q$.

More generally, in class you must have been shown a definition of well-formed formulae. Use it.

Well-formed formulae are usually defined inductively. One possible definition is:

1. For every variable $v$, $v$ is a well-formed formula.

2. For every well-formed formula $\varphi$, $(\lnot \varphi)$ is well-formed.

3. For every binary symbol $\circ \in \{ \land, \lor, \rightarrow, \leftrightarrow \}$ and two well-formed formulae $\varphi,\psi$, $(\varphi \circ \psi)$ is well-formed.

4. "No other formula is well-formed."

The last "axiom" isn't quite formal. What we really mean is that a formula is well-formed only if it can be proved well-formed by using the first three axioms. (This is equivalent to the definition using least fixed points, which you might have seen in class.)

What all this means is that in order to show that a formula is well-formed, all you need to do is derive it from the axioms. Showing that a formula isn't well-formed could be more difficult. Since the set of well-formed formulae is context-free, there is an efficient algorithm which given a formula decides whether it is well-formed.

• Nice last paragraph. – Rick Decker Oct 27 '15 at 0:18