5 Symmetries of Propositional Logic
Summary:
Throughout this class, we will explore how double negation, hypothetical syllogism, the contrapositive of implication, deduction theorems, and the definitions of connectors combine to form the symmetries of propositional logic. With clear and simple demonstrations, you will learn to master the equivalences and apply them to your own logical challenges.
The symmetries addressed in the class include: \downarrow-Symmetry, \vee-Symmetry, \wedge-Symmetry, \leftrightarrow-Symmetry, and \veebar-Symmetry. Additionally, the interactions between the demonstrations are highlighted, showing how each one supports the previous ones to simplify future deductions. This class will not only provide you with a deep understanding of Propositional Logic but also teach you to use previous demonstrations to optimize your learning process.
Learning Objectives:
By the end of this class, the student will be able to
- Recall basic concepts of propositional logic, such as hypothetical syllogism and double negation.
- Recognize the 5 Symmetries of Propositional Logic.
- Understand the process of demonstrating symmetry equivalences.
- Apply Presumption, Deduction Theorem, and its Reciprocal in demonstrations.
- Relate the definitions of logical connectors to the symmetries.
- Appreciate the importance of performing demonstrations only once and reusing them in future demonstrations.
- Develop analytical and critical skills when performing logical demonstrations.
CONTENTS INDEX
\vee – SYMMETRY
\downarrow – SYMMETRY
\wedge – SYMMETRY
\leftrightarrow – SYMMETRY
\veebar – SYMMETRY
FINAL REMARKS
A direct consequence of the hypothetical syllogism, double negation, and the contrapositive of implication, deduction theorems, and the definitions of connectors are the 5 symmetries of propositional logic that we will review below.
| (\alpha \downarrow \beta) \dashv\vdash (\beta\downarrow \alpha) | \downarrow-Symmetry |
| (\alpha \vee \beta) \dashv\vdash (\beta\vee \alpha) | \vee-Symmetry |
| (\alpha \wedge \beta) \dashv\vdash (\beta\wedge \alpha) | \wedge-Symmetry |
| (\alpha \leftrightarrow \beta) \dashv\vdash (\beta\leftrightarrow \alpha) | \leftrightarrow-Symmetry |
| (\alpha \veebar \beta) \dashv\vdash (\beta\veebar\alpha) | \veebar-Symmetry |
The demonstrations of these equivalences are not entirely trivial, but unlike some demonstrations we have already seen, they are quite simple. Below is the demonstration of each in one direction; the demonstration in the reverse direction is almost identical and is left as an exercise for the reader.
\vee-Symmetry
| (1) | \{(\alpha \vee \beta)\}\vdash (\alpha \vee\beta) | ; Pre |
| (2) | \{(\alpha \vee \beta)\}\vdash (\neg \alpha \rightarrow \beta) | ; because (\alpha \vee \beta) := (\neg \alpha \rightarrow \beta) |
| (3) | \{(\alpha \vee \beta)\}\vdash (\neg \beta \rightarrow \alpha) | ; CPI(2) |
| (4) | \boxed{\{(\alpha \vee \beta)\}\vdash ( \beta \vee \alpha)} | ; because ( \beta \vee \alpha) := (\neg\beta\rightarrow\alpha) |
The reasoning in the reverse direction is obtained with very few variations starting with the presumption \{(\beta\vee\alpha)\}\vdash (\beta\vee\alpha)
\downarrow-Symmetry
| (1) | \{\neg(\alpha \downarrow \beta)\}\vdash \neg(\alpha \downarrow \beta) | ; Pre |
| (2) | \{\neg(\alpha \downarrow \beta)\}\vdash (\alpha \vee \beta) | ; from (1) because (\alpha\vee\beta) := \neg(\alpha \downarrow \beta) |
| (3) | \{\neg(\alpha \downarrow \beta)\}\vdash (\beta \vee \alpha) | ; \vee-Symmetry |
| (4) | \vdash (\neg(\alpha \downarrow \beta) \rightarrow (\beta \vee \alpha)) | ; TD(3) |
| (5) | \vdash (\neg(\beta \vee \alpha) \rightarrow (\alpha \downarrow \beta)) | ; CPI(4) |
| (6) | \vdash ((\beta \downarrow \alpha) \rightarrow (\alpha \downarrow \beta)) | ; from (5) because (\beta\vee\alpha) := \neg(\beta \downarrow \alpha) |
| (7) | \boxed{\{(\beta \downarrow \alpha) \} \vdash (\alpha \downarrow \beta)} | ; RTD(6) |
Finally, reasoning in the reverse direction, the deduction is obtained in the opposite direction starting with the presumption \{\neg(\beta\downarrow\alpha)\}\vdash \neg(\beta\downarrow\alpha)
\wedge-Symmetry
| (1) | \{(\alpha \wedge \beta)\} \vdash (\alpha \wedge \beta) | ; Pre |
| (2) | \{(\alpha \wedge \beta)\} \vdash (\neg\alpha \downarrow \neg\beta) | ; from (1) because (\alpha \wedge \beta) := (\neg\alpha \downarrow \neg\beta) |
| (3) | \{(\alpha \wedge \beta)\} \vdash (\neg\beta \downarrow \neg\alpha) | ; \downarrow-Symmetry (2) |
| (4) | \boxed{\{(\alpha \wedge \beta)\} \vdash ( \beta \wedge \alpha)} | ; from (3) because (\beta \wedge \alpha) := (\neg\beta \downarrow \neg\alpha) |
Just like before, if you reason in the reverse direction, it is obtained with very few variations starting with the presumption \{( \beta \wedge \alpha)\}\vdash ( \beta \wedge \alpha)
\leftrightarrow-Symmetry
| (1) | \{(\alpha \leftrightarrow \beta)\} \vdash (\alpha \leftrightarrow \beta) | ; Pre |
| (2) | \{(\alpha \leftrightarrow \beta)\} \vdash ((\alpha \rightarrow \beta) \wedge (\alpha \rightarrow \beta)) | ; From (1) because (\alpha \leftrightarrow \beta) := ((\alpha \rightarrow \beta) \wedge (\beta \rightarrow \alpha)) |
| (3) | \{(\alpha \leftrightarrow \beta)\} \vdash ((\beta \rightarrow \alpha) \wedge (\alpha \rightarrow \beta) ) | ; \wedge-Symmetry(2) |
| (4) | \boxed{\{(\alpha \leftrightarrow \beta)\} \vdash (\beta \leftrightarrow \alpha)} | ; From (3) because (\beta \leftrightarrow \alpha) := ((\beta \rightarrow \alpha) \wedge (\alpha \rightarrow \beta)) |
Just like the previous one, but starting with the presumption \{( \beta \leftrightarrow \alpha)\}\vdash ( \beta\leftrightarrow \alpha)
\veebar-Symmetry
| (1) | \{(\alpha \leftrightarrow \beta)\} \vdash (\alpha \leftrightarrow \beta) | ; Pre |
| (2) | \{(\alpha \leftrightarrow \beta)\} \vdash ( \beta \leftrightarrow \alpha) | ; \leftrightarrow-Symmetry(1) |
| (3) | \vdash ((\alpha \leftrightarrow \beta) \rightarrow ( \beta \leftrightarrow \alpha)) | ; TD(2) |
| (4) | \vdash (\neg ( \beta \leftrightarrow \alpha) \rightarrow \neg (\alpha \leftrightarrow \beta)) | ; CPI(3) |
| (5) | \{\neg ( \beta \leftrightarrow \alpha)\} \vdash \neg (\alpha \leftrightarrow \beta) | ; RTD(4) |
| (6) | \boxed{\{ ( \beta \veebar \alpha)\} \vdash (\alpha \veebar \beta)} | ; From (5) because ( \beta \veebar \alpha) := \neg\beta \leftrightarrow \alpha) and (\alpha \veebar \beta) := \neg (\alpha \leftrightarrow \beta) |
As in all other cases, it is enough to test the presumption in the reverse direction \{(\beta \leftrightarrow \alpha)\} \vdash (\beta \leftrightarrow \alpha) to obtain the deduction in that direction.
Final Remarks
One aspect that the reader should pay attention to is the order in which these 5 symmetries of propositional logic have been chosen to be demonstrated. Note that each one is done in such a way that it uses some of the previously performed demonstrations. This reflects the approach that should be followed when performing demonstrations: they are done only once (and never again!); after that, your goal should be to use previous demonstrations to simplify future ones.