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:
By (a), $\varphi = P$, $\psi = Q$, and $\pi = R$ are all formulas. So we can rewrite the above as:
By (c), since $\varphi$ and $\psi$ are formulas, so is $\Phi = (\varphi \vee \psi)$. So we can rewrite the above as:
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:
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:
The above is not a formula because $(\vee P)$ does not make any sense. We need two statements to use the disjunction connective!
- Reisch receives SUNY Chancellor’s Award | News, Sports, Jobs – Evening Observer
- An overall 2nd place for Malta in an International Mental Mathematics Challenge – Malta Independent Online
- DU Admissions 2019: Mathematics Must In Best Of Four Subjects For Admission Into Eco(H); JMC, Stephen’s Stick To Old Rule – Swarajya
- Agami Education Foundation holds teachers’ training on Teaching Mathematics by Olympiad Technique – Dhaka Tribune
- 2nd place for Malta in international Mental Mathematics Challenge – Newsbook
- Darlington pupils among most-skilled mathematics in the UK – Darlington and Stockton Times
- Women and minority faculty in science, technology, engineering and mathematics (STEM) – Open Access Government
- The messy mathematics of British Columbia’s CleanBC plan – Business in Vancouver
- All Limerick student’s hard work adds up to him winning top mathematics award in Ireland – Limerick Leader
- CMU-Q researchers explore the mathematics of personalised medicine – The Peninsula Qatar