0.3 Discrete structures logic  (Page 7/23)

13. (P ⋁False) ⇔P

14. (P ⋀True) ⇔P

15. (P ⋁¬P) ⇔True

What this says is that a statement such as "Tom is 6 foot tall or he is not 6 foot tall." is always true.

16. (P ⋀¬P) ⇔False

What this says is that a statement such as "Tom is 6 foot tall and he is not 6 foot tall." is always false.

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

What this says is, for example, that "It is not the case that Tom is not 6 foot tall." is equivalent to "Tom is 6 foot tall."

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

For example, the statement "If I win the lottery, I will give you a million dollars." is not true, that is, I am lying, if I win the lottery and don't give you a million dollars. It is true in all the other cases. Similarly, the statement "I don't win the lottery or I give you a million dollars." is false, if I win the lottery and don't give you a million dollars. It is true in all the other cases. Thus these two statements are logically equivalent.

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

What this says is, for example, that "Tom is happy if and only if he is healthy." is logically equivalent to ""if Tom is happy then he is healthy, and if Tom is healthy he is happy."

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

For example, "If Tom is healthy, then if he is rich, then he is happy." is logically equivalent to "If Tom is healthy and rich, then he is happy."

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

For example, if "If Tom is guilty then he must have been in that room." and "If Tom is guilty then he could not have been in that room." are both true, then there must be something wrong about the assumption that Tom is guilty.

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

For example, "If Tom is healthy, then he is happy." is logically equivalent to "If Tom is not happy, he is not healthy."

The identities 1 ~ 16 listed above can be paired by duality relation, which is defined below, as 1 and 2, 3 and 4, ..., 15 and 16. That is 1 and 2 are dual to each other, 3 and 4 are dual to each other, .... Thus if you know one of a pair, you can obtain the other of the pair by using the duality.

Dual of proposition

Let X be a proposition involving only ¬, ⋀, and ⋁ as a connective. Let X* be the proposition obtained from X by replacing ⋀ with ⋁, ⋁with ⋀, T with F, and F with T. Then X* is called the dual of X.

For example, the dual of [P ⋀Q ] ⋁P is [P ⋁Q ]⋀P, and the dual of [¬ P ⋀Q] ⋁¬[ T ⋀¬R]is [¬ P ⋁Q] ⋀¬[ F ⋁¬R].

Property of Dual: If two propositions P and Q involving only ¬, ⋀, and ⋁ as connectives are equivalent, then their duals P* and Q* are also equivalent.

Examples of use of identities

Here a few examples are presented to show how the identities in section Identities can be used to prove some useful results.

1. ¬( P →Q ) ⇔( P ⋀¬Q )

What this means is that the negation of "if P then Q" is "P but not Q". For example, if you said to someone "If I win a lottery, I will give you $100,000." and later that person says "You lied to me." Then what that person means is that you won the lottery but you did not give that person $100,000 you promised.