Formulas in Propositional Logic

We are now ready to properly define a formula in propositional logic.

Definition: A Formula in propositional logic must satisfy one of the criteria below: a) A statement is a formula. b) If $\varphi$ is a formula then $\neg \varphi$ is a formula. c) If $\varphi$ and $\psi$ are formulas then $\varphi \wedge \psi$ is a formula. d) If $\varphi$ and $\psi$ are formulas then $\varphi \vee \psi$ is a formula. e) If $\varphi$ and $\psi$ are formulas then $\varphi \rightarrow \psi$ is a formula. f) If $\varphi$ and $\psi$ are formulas then $\varphi \leftrightarrow \psi$ is a formula.

The definition above may be a little confusing at first, so let's look at an example. Let $P$, $Q$, and $R$ be statements.

Suppose that we want to determine whether the following is a formula or not:

(1)

\begin{align} \quad \neg (P \vee Q) \rightarrow (\neg R) \quad (*) \end{align}

By (a), $\varphi = P$, $\psi = Q$, and $\pi = R$ are all formulas. So we can rewrite the above as:

(2)

\begin{align} \quad \neg (\varphi \vee \psi) \rightarrow (\neg \pi) \end{align}

By (c), since $\varphi$ and $\psi$ are formulas, so is $\Phi = (\varphi \vee \psi)$. So we can rewrite the above as:

(3)

\begin{align} \quad \neg (\Phi) \rightarrow (\neg \pi) \end{align}

By (b), since $\Phi$ is a formula so is $\alpha = \neg \Phi$. Similarly, since $\pi$ is a formula so is $\beta = \neg \pi$. So we can rewrite the above as:

(4)

\begin{align} \quad \alpha \rightarrow \beta \end{align}

By (e), since $\alpha$ and $\beta$ are formulas so is $\alpha \rightarrow \beta$. Hence $(*)$ is indeed a formula.

Here's an example of something that is NOT a formula:

(5)

\begin{align} \quad \neg(\vee P) \rightarrow Q \end{align}

The above is not a formula because $(\vee P)$ does not make any sense. We need two statements to use the disjunction connective!