Well-formed Propositional Formula

logic propositional-logic

Definition

Well-formed Propositional Formula

In propositional logic, a well-formed propositional formula is a syntactically correct propositional formula generated by the following rules:

1. Every atom is a propositional formula.
2. $\top$ and $\perp$ are propositional formulas.
3. If $P_1,\dots ,P_n$ are propositional formulas with $n\ge 2$, then $(P_1\wedge \cdots \wedge P_n)$ and $(P_1\vee \cdots \vee P_n)$ are propositional formulas.
4. If $P$ is a propositional formula, then $(\neg P)$ is a propositional formula.
5. If $P_1$ and $P_2$ are propositional formulas, then $(P_1\to P_2)$ and $(P_1\leftrightarrow P_2)$ are propositional formulas.
6. Nothing else is a well-formed propositional formula.

Here, $\wedge$, $\vee$, $\neg$, $\to$, and $\leftrightarrow$ are connectives, namely conjunction, disjunction, negation, implication, and equivalence. The symbols $\top$ and $\perp$ are propositional constants.

Examples

Examples

The following are well-formed propositional formulas:

• $P$
• $\neg P$
• $(P\vee Q)$
• $\neg (P\to Q)$

The following are not well-formed:

• $\wedge P$
• $P\vee$
• $(PQ)$