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!
- CSEC, CAPE results show students continue to struggle with Mathematics – Antigua Observer
- NTA JEE Main Application Process for January 2020 begins, students with mathematics eligible for B Planni – Times of India
- Latest Study explores the Mathematics Software Market Witness Highest Growth in near future| Maplesoft, MathWorks, Saltire Software, Gurobi Optimization – Indian Columnist
- New faces to look for in the halls – The Echo News
- PGCPS improves MCAP scores, introduces new principals – The Prince George’s Sentinel
- Novel maths could bring AI ‘to next level’ – Cosmos
- Bollinger ’20 Earns National Education Honor | Illinois Wesleyan – Illinois Wesleyan University
- Global Science, Technology, Engineering and Mathematics (STEM) Toys Market Overview 2019-2023: Segmented by Geography Trends and Opportunities growing with CAGR of 4.53%. – The Inherent News
- Revised Mathematics pattern only for Class 10 Board Exam, not for Class 9 examination: CBSE – Times Now
- Teen ACHIEVERS Pt 2 – Jamaica Observer