0
$\begingroup$

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

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

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.

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

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.