Propositional Logic
Language
This is what defines a well formed formula (wff) in a particular logic.
- We start with a set $\mathcal P$ of atoms, $\mathcal P = p, q, p_1, p_2,\ldots$
- These represent basic facts that we don’t analyse further.
The atoms determine the level of detail that we consider.
Well Formed Formulas
- Every $p\in \mathcal P$ is a wff.
- If $\phi$ and $\psi$ are wffs, then $\neg\phi,(\phi\wedge\psi),(\phi\vee\psi), (\phi\implies\psi),(\phi\iff\psi)$
- Each wff includes these brackets.
- Negation binds stronger than other connectives as it is unary.
- We can omit brackets if this does not cause ambiguity.
Symbols
| Symbol | Pronunciation | Capital |
|---|---|---|
| $\phi$ | phi | $\Phi$ |
| $\psi$ | psi | $\Psi$ |
| $\chi$ | chi | |
| $\xi$ | xi | |
| $\gamma$ | gamma | $\Gamma$ |
| $\alpha$ | alpha | |
| $\beta$ | beta |
| Symbol | Pronunciation |
|---|---|
| $\neg$ | not |
| $\wedge$ | and |
| $\vee$ | or |
| $\implies$ | implies |
| $\iff$ | if and only if |
Semantics
Not $\neg$
| $\phi$ | $\neg\phi$ |
|---|---|
| 0 | 1 |
| 1 | 0 |
Or & And $\vee, \wedge$
| $\phi$ | $\psi$ | $\phi\vee\psi$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
| $\phi$ | $\psi$ | $\phi\wedge\psi$ |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Implies $\implies$
| $\phi$ | $\psi$ | $\phi\implies\psi$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
If and Only If $\iff$
| $\phi$ | $\psi$ | $\phi\iff\psi$ |
|---|---|---|
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Validity
- Contingent Formulas
- This is the case if you can change whether a formula is true or false by changing the inputs.
- Valid Formulas $\vDash\phi$
- Formulas where only true is returned, no matter the input.
You can also write this as $\emptyset\vDash\phi$.
- Valid Inference ${p,q}\vDash p\wedge q$
- This is where a set of premises guarantee the truth of the conclusion.
Truth Tables
To find whether an inference is true then we can draw a truth table for all the premises:
${p,p\implies q}\vdash q$
| $p$ | $q$ | $p$ | $p\implies q$ | $q$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 1 |
We can then use the table to prove by example/counterexample.
Proof System
Axioms of Propositional Logic
| Name | Axiom |
|---|---|
| $(\implies1)$ | $\phi\implies(\psi\implies\phi)$ |
| $(\implies2)$ | $(\phi\implies(\chi\implies\psi))\implies((\phi\implies\chi)\implies(\phi\implies\psi))$ |
| $(\wedge1)$ | $(\phi\wedge\psi)\implies\phi$ |
| $(\wedge2)$ | $(\phi\wedge\psi)\implies\psi$ |
| $(\wedge3)$ | $\phi\implies(\psi\implies(\phi\implies\psi))$ |
| $(\vee1)$ | $\phi\implies(\phi\vee\psi)$ |
| $(\vee2)$ | $\psi\implies(\phi\vee\psi)$ |
| $(\vee3)$ | $((\phi\implies\chi)\wedge(\psi\implies\chi))\implies((\phi\vee\psi)\implies\chi)$ |
| $(\neg1)$ | $((\phi\implies\psi)\wedge(\phi\implies\neg\psi))\implies\neg\phi$ |
| $(\neg2)$ | $(\phi\wedge\neg\phi)\implies\psi$ |
| $(\neg3)$ | $\phi\wedge\neg\phi$ |
| $(\iff1)$ | $(\phi\iff\psi)\implies(\phi\implies\psi)$ |
| $(\iff2)$ | $(\phi\iff\psi)\implies(\psi\implies\phi)$ |
| $(\iff3)$ | $((\phi\implies\psi)\wedge(\psi\implies\phi))\implies(\phi\iff\psi)$ |
Derivation
You can use the following justifications to form your derivation:
- It is a premise.
- It is an instance of an axiom.
-
If we have derived $\phi$ and $\phi\implies\psi$ then we can use $\psi$.
This is the rule MP.
By combining our derivations (MP) and the axioms we can create a proof system $\mathfrak P$
Proof Example
$\Gamma\vdash_\mathfrak P\phi$ if $\phi$ can be derived $\Gamma$ in $\mathfrak P$.
For example we can prove the commutativity of $\wedge$:
\[p\wedge q\vdash q\wedge p\]| Step | Derivation | Justification |
|---|---|---|
| 1 | $p\wedge q$ | premise |
| 2 | $(p\wedge q)\implies p$ | $(\wedge1)$ |
| 3 | $(p\wedge q)\implies q$ | $(\wedge2)$ |
| 4 | $p$ | (MP) on 1 and 2 |
| 5 | $q$ | (MP) on 1 and 3 |
| 6 | $q\implies(p\implies(q\wedge p))$ | $(\wedge3)$ |
| 7 | $p\implies(q\wedge p)$ | (MP) on 5 and 6 |
| 8 | $q\wedge p$ | (MP) on 4 and 7 |
Soundness and Completeness
- If $\Gamma\vdash_\mathfrak P \phi$, then $\Gamma\vDash\phi$. So we can only derive valid inferences.
- This is called soundness.
- If $\Gamma\vDash\phi$, then $\Gamma\vdash_\mathfrak P\phi$. So every valid inference can be derived.
- This is called completeness.
A proof system is only considered useful if it is sound and complete.
This is to say we want our proof system $\mathfrak P$ to be complete and inline with the logics of mathematics.
Abbreviations
$\bot$ and $\top$
- $\top$ represents something that is always true (such as $p\vee\neg p$)
- $\bot$ represents something that is always false (such as $p\wedge\neg p$)
$\wedge$, $\implies$ and $\iff$
We can also define some of our connectives as abbreviations:
- $\phi\wedge\psi$ can abbreviate $\neg(\neg\psi\vee\neg\psi)$
- $\phi\implies\psi$ can abbreviate $\neg\phi\vee\psi$
- $\phi\iff\psi$ can abbreviate $(\phi\implies\psi)\wedge(\phi\implies\psi)$
Language Definition
As we can abbreviate our original atoms: $\neg,\vee,\wedge,\implies,\iff$ we can redefine the language of propositional logic as:
\[\phi::=p\mid\neg\phi\mid\phi\vee\phi\]