CSC165 Implication/disjunction, mixed quantifiers, proof

Week #4

Implication/disjunction, mixed quantifiers, proof

I really enjoyed this week’s material. As Professor Heap pointed out, algebra comes into play when dealing with logic. Perhaps, thinking of the predicates as algebraic expressions, and of the logical operators as algebraic operators made it easier to understand the material. I realized that the key point for this part of the course is to understand the logic behind the concepts, instead of just learning by heart the properties.

In terms of tutorials, I found that the questions really tackled the use of logical operators (¬, ∧, ∨, ⇒, ⇔). By the way, I found an easier solution for one of the problems that I would like to show here.

Prove that ((P ⇒ Q) ⇒ R) ⇒ S is equivalent to (¬ R ∧ ¬ P) ∨ (¬ R ∧ Q) ∨ S

RHS ⇔ ¬ ((P ⇒ Q) ⇒ R) ∨ S ⇔

⇔ ¬ (¬ (P ⇒ Q) ∨ R) ∨ S ⇔

⇔ ¬ (¬ (¬ P ∨ Q) ∨ R) ∨ S ⇔

⇔ (¬ P ∨ Q) ∧ ¬ R) ∨ S ⇔

⇔ (¬ R ∧ ¬ P) ∨ (¬ R ∧ Q) ∨ S ⇔ LHS

Implication, DeMorgan’s laws and distributive law were applied in this exercise.

Something that may be tricky sometimes, is implication, especially when it involves a negation operator. One example of this is the following:

P ⇒ ¬ Q ⇔ ¬ P ∨ ¬ Q

In this case, we really need to know how the implication works because we could easily miss the negation. Something useful is to think about the rule we are going to use, see how it works, and then apply it.