How to Prove an Expression Is Not a Well-Formed Formula

To prove that a string is not a well-formed formula (often abbreviated WFF), you need to use the formation rules of the formal language. There is no grammar-independent test: a string accepted in one notation may be rejected in another. Since no particular expression or grammar is specified here, the method below uses a common fully parenthesized propositional language and shows how to adapt the argument.

State the formation rules first

For example, suppose the language has propositional letters $p,q,r,\ldots$, the unary connective $\neg$, and the binary connectives $\land$ and $\lor$. Use these formation rules:

1. Every propositional letter is a formula.
2. If $A$ is a formula, then $(\neg A)$ is a formula.
3. If $A$ and $B$ are formulas, then $(A\land B)$ and $(A\lor B)$ are formulas.
4. Nothing else is a formula.

The last rule matters: the rules do not merely give examples of formulas; they define the whole set of formulas. Under this grammar, $p$ and $(\neg p)$ are formulas, as are $(p\land q)$ and $(p\lor(\neg q))$. But the unparenthesized string $p\land q$ is not a formula in this particular notation, even though many textbooks allow it by using precedence conventions.

Try to parse the expression

A formula must be generated from the rules. Work from the outside in: is the string a single propositional letter? If not, does it have the exact shape of a negation, or of a binary connective with a formula on each side? For a binary formula in this grammar, the outermost form must be $(A\land B)$ or $(A\lor B)$, where both $A$ and $B$ are formulas.

Consider

$$((p\land q)\lor\land r).$$

The string has matching outer parentheses, so simply counting parentheses does not show that it is malformed. Look inside those outer parentheses. The connective at the outermost level is $\lor$, giving the proposed split

$$A=(p\land q), \qquad B=\land r.$$

The left side is a formula, but the right side is not: it begins with a binary connective and has no formula to its left. It is not a propositional letter, a negation of a formula, or a parenthesized binary formula. Therefore the whole string cannot be formed by any of the rules and is not a WFF.

Make the argument a proof

For a short malformed string, a failed parse is usually enough, provided you explain why the possible grammar rules have all been ruled out. For a more formal presentation, organize it as an exhaustive case analysis:

• It is not a propositional letter.
• It does not have the required form $(\neg A)$ for a formula $A$.
• Its outermost connective, if it is a binary connective, leaves at least one side that is not a formula.
• No other formation rule applies.

Since the listed rules are the only ways to construct formulas, the string is not a formula. This is a syntactic proof: it concerns the structure of the string, not its truth value under an interpretation.

You can also use a property that every formula must satisfy. For example, in the grammar above, each formula has balanced parentheses. So an expression with an unmatched parenthesis cannot be a formula. Such a test gives a quick rejection, but it is only a necessary condition: the example above has balanced parentheses and is still malformed. A property-based proof works only if you establish that every formula has the property and show that the expression does not.

Check the notation being used

Different formal systems use different formation rules. Some allow $\neg p$ without parentheses; some omit parentheses around binary connectives and rely on precedence and associativity; predicate logic adds quantifiers and rules about variable binding. A string that looks incomplete under one convention may be acceptable under another. State the convention before declaring an expression malformed, and apply the rules exactly as given.

Common mistakes

• Calling a false formula malformed. A WFF can be false; truth and well-formedness are different questions.
• Relying on appearance. “It looks wrong” is not a proof. Identify which production rule fails.
• Checking only parentheses. Balanced parentheses do not guarantee a valid parse.
• Assuming notation is universal. If parentheses or precedence conventions differ, the same string can receive a different judgment.
• Stopping at one bad-looking part. For an exhaustive proof, explain why no other formation rule could generate the whole expression.