<< Chapter < Page | Chapter >> Page > |
The following lists some propositional formula equivalences. Remember that we use the symbol $$ as a relation between two WFFs, not as a connective inside a WFF.In these, $$ , $$ , and $$ are meta-variables standing for any WFF.
Double Complementation | $\neg \neg \equiv $ | |
Complement | $\lor \neg \equiv \mbox{true}$ | $\land \neg \equiv \mbox{false}$ |
Identity | $\lor \mbox{false}\equiv $ | $\land \mbox{true}\equiv $ |
Dominance | $\lor \mbox{true}\equiv \mbox{true}$ | $\land \mbox{false}\equiv \mbox{false}$ |
Idempotency | $\lor \equiv $ | $\land \equiv $ |
Absorption | $\land \lor \equiv $ | $\lor (\land )\equiv $ |
Redundancy | $\land \neg \lor \equiv \land $ | $\lor (\neg \land )\equiv \lor $ |
DeMorgan's Laws | $\neg (\land )\equiv \neg \lor \neg $ | $\neg (\lor )\equiv \neg \land \neg $ |
Associativity | $\land \left(\land \right)\equiv \left(\land \right)\land $ | $\lor \left(\lor \right)\equiv \left(\lor \right)\lor $ |
Commutativity | $\land \equiv \land $ | $\lor \equiv \lor $ |
Distributivity | $\land \lor \equiv (\land )\lor (\land )$ | $\lor (\land )\equiv \lor \land \lor $ |
Equivalences for implication are omitted above for brevity and for tradition. They can be derived, using the definition $a\implies b\equiv \neg a\lor b$ .
For example, using Identity and Commutativity, we have $\mbox{true}\implies b\equiv \neg \mbox{true}\lor b\equiv \mbox{false}\lor b\equiv b\lor \mbox{false}\equiv b$ .
Notification Switch
Would you like to follow the 'Fundamentals of computer engineering' conversation and receive update notifications?