0.3 Discrete structures logic  (Page 6/23)

2. P ⇔(P ⋀P) ----- idempotence of ⋀

3. (P ⋁Q) ⇔(Q ⋁P) ----- commutativity of ⋁

4. (P ⋀Q) ⇔(Q ⋀P) ----- commutativity of ⋀

5. [(P ⋁Q) ⋁R] ⇔[P ⋁(Q ⋁R)]----- associativity of ⋁

6. [(P ⋀Q) ⋀R] ⇔[P ⋀(Q ⋀R)]----- associativity of ⋀

7. ¬(P ⋁Q) ⇔(¬ P ⋀ ¬Q) ----- DeMorgan's Law

8. ¬(P ⋀Q) ⇔(¬ P ⋁ ¬Q) ----- DeMorgan's Law

9. [P ⋀(Q ⋁R] ⇔[(P ⋀Q) ⋁(P ⋀R)]----- distributivity of ⋀over ⋁

10. [P ⋁(Q ⋀R] ⇔[(P ⋁Q) ⋀(P ⋁R)]----- distributivity of ⋁over ⋀

11. (P ⋁True) ⇔True

12. (P ⋀False) ⇔False

13. (P ⋁False) ⇔P

14. (P ⋀True) ⇔P

15. (P ⋁¬P) ⇔True

16. (P ⋀¬P) ⇔False

17. P ⇔¬(¬ P) ----- double negation

18. (P →Q) ⇔(¬ P ⋁Q) ----- implication

19. (P ↔Q) ⇔[(P →Q) ⋀(Q →P)]----- equivalence

20. [(P ⋀Q) →R] ⇔[P →(Q→R)]----- exportation

21. [(P →Q) ⋀(P→¬Q)] ⇔¬P ----- absurdity

22. (P →Q) ⇔(¬Q →¬P) ----- contrapositive

Let us see some example statements in English that illustrate these identities.

Examples: 1. P ⇔(P ⋁P) ----- idempotence of ⋁

What this says is, for example, that "Tom is happy." is equivalent to "Tom is happy or Tom is happy". This and the next identity are rarely used, if ever, in everyday life. However, these are useful when manipulating propositions in reasoning in symbolic form.

2. P ⇔(P ⋀P) ----- idempotence of ⋀

Similar to 1. above.

3. (P ⋁Q) ⇔(Q ⋁P) ----- commutativity of ⋁

What this says is, for example, that "Tom is rich or (Tom is) famous." is equivalent to "Tom is famous or (Tom is) rich".

4. (P ⋀Q) ⇔(Q ⋀P) ----- commutativity of ⋀

What this says is, for example, that "Tom is rich and (Tom is) famous." is equivalent to "Tom is famous and (Tom is) rich".

5. [(P ⋁Q) ⋁R] ⇔[P ⋁(Q ⋁R)]----- associativity of ⋁

What this says is, for example, that "Tom is rich or (Tom is) famous, or he is also happy." is equivalent to "Tom is rich, or he is also famous or (he is) happy".

6. [(P ⋀Q) ⋀R] ⇔[P ⋀(Q ⋀R)]----- associativity of ⋀

Similar to 5. above.

7. ¬(P ⋁Q) ⇔(¬ P ⋀¬Q) ----- DeMorgan's Law

For example, "It is not the case that Tom is rich or famous." is true if and only if "Tom is not rich and he is not famous."

8. ¬(P ⋀Q) ⇔(¬ P ⋁¬Q) ----- DeMorgan's Law

For example, "It is not the case that Tom is rich and famous." is true if and only if "Tom is not rich or he is not famous."

9. [P ⋀(Q ⋁R] ⇔[(P ⋀Q) ⋁(P ⋀R)]----- distributivity of ⋀ over ⋁

What this says is, for example, that "Tom is rich, and he is famous or (he is) happy." is equivalent to "Tom is rich and (he is) famous, or Tom is rich and (he is) happy".

10. [P ⋁(Q ⋀R] ⇔[(P ⋁Q) ⋀(P ⋁R)]----- distributivity of ⋁over ⋀

Similarly to 9. above, what this says is, for example, that "Tom is rich, or he is famous and (he is) happy." is equivalent to "Tom is rich or (he is) famous, and Tom is rich or (he is) happy".

11. (P ⋁True) ⇔ True. Here True is a proposition that is always true. Thus the proposition (P ⋁True) is always true regardless of what P is.

This and the next three identities, like identities 1 and 2, are rarely used, if ever, in everyday life. However, these are useful when manipulating propositions in reasoning in symbolic form.

12. (P ⋀False) ⇔False