Logical Equivalence, Part 2

Return to Course Outline

Previous Lecture

Anything You Want to Talk About?

(No.)

Misc

Question 4 in problem set 2 was very hard to read correctly: it doesn’t ask you to prove the definition of “rational number,” it asks you to do 2 things (parts A and B), one of which is a proof, both involving rational numbers. The version of the assignment that’s online now has been reworded to hopefully make this clearer.

Logical Equivalence

Continuing the conversation from Wednesday, based on section 2.2 in the textbook and this logical equivalence discussion.

Proofs

Show that the following equivalence holds:

¬( P ↔ Q) ≡ (P ∨ Q) ∧ (¬P ∨ ¬Q)

One way to show that equivalencies hold is to write a truth table that shows both sides of the equivalence. If the columns for the two sides are identical then the corresponding expressions are equivalent. For this example…

Checking the ¬( P ↔ Q) and (P ∨ Q) ∧ (¬P ∨ ¬Q) columns (underlined) shows that they are the same, and so ¬( P ↔ Q) is equivalent to (P ∨ Q) ∧ (¬P ∨ ¬Q).

Another way to prove equivalence is to use other equivalencies (sometimes also described as using Boolean algebra, since collectively the logical equivalencies make up the theorems of Boolean algebra). The idea is to show through a series of equivalencies that the two expressions you’re interested in are equivalent. For example…

¬( P ↔ Q) ≡ ¬( P→Q ∧ Q→P ) (by the definition of “P if and only if Q” as “P implies Q and Q implies P”)

≡ ¬(P→Q) ∨ ¬(Q→P) (Using one of De Morgan’s laws for the negation of a conjunction (i.e., an “and”))

≡ ¬( ¬P ∨ Q ) ∨ ¬(¬Q ∨ P) (Using the equivalence A→B ≡ ¬A ∨ B)

≡ ( ¬¬P ∧ ¬Q ) ∨ (¬¬Q ∧ ¬P) (By De Morgan’s law for the negation of a disjunction (i.e., an “or”))

≡ ( P ∧ ¬Q ) ∨ (Q ∧ ¬P) (Using the equivalence ¬¬A ≡ A)

≡ (P ∨ (Q ∧ ¬P)) ∧ (¬Q ∨ (Q ∧ ¬P)) (Distributing “or” over “and”)

≡ (P ∨ Q) ∧ (P ∨¬P) ∧ (¬Q ∨ Q) ∧  (¬Q ∨¬P) (Distributing “or” over “and” again)

≡ (P ∨ Q) ∧ true ∧ true ∧  (¬Q ∨¬P) (A ∨¬A is always true)

≡ (P ∨ Q)  ∧  (¬Q ∨¬P) (Constants of “true” don’t affect the value of a conjunction)

≡ (P ∨ Q)  ∧  (¬P ∨ ¬Q ) (Reordering ¬Q ∨¬P — “or” is commutative)

How about showing the equivalence P ∧ Q → R ≡ ¬P ∨ ¬Q ∨ R

People tried this on their own, but the general thinking was either to replace P ∧ Q → R with ¬(P ∧ Q) ∨ R on the left side of the original equivalence, or to replace ¬P ∨ ¬Q with ¬(P ∧ Q) on the right. Notice that both of these produce the same expression. Putting the ideas together and applying them to rewrite the left side into the right side gives

P ∧ Q → R ≡ ¬(P ∧ Q) ∨ R

≡ ¬P ∨ ¬Q ∨ R

which is a much shorter Boolean algebra derivation than the first example we looked at.

Notice that understanding parts of this expression relies on some order-of-evaluation rules that we haven’t really talked about before:

1. Do negations before anything else
2. Then do conjunctions
3. Then do disjunctions
4. Finally do implications (“if-then”) and biconditionals (“if-and-only-if”).

Parentheses over-ride all of these rules, of course.

Problem Set 3

Generally about logic and equivalencies.

Finish it by next Friday, grade it by the Friday after.

See the handout for details.

Next

Sets.

Please read “Beginning Activity 1 (Sets and Set Notation),” “Some Set Notation,” and “The Empty Set” in section 2.3 of our textbook.

Please also contribute to this discussion of basic set concepts.

Next Lecture