Week 4

This week, materials were getting harder and more complicated. 

The following topics were introduced in the past week: Bi-implications, transitivity, double quantifiers, and intro to proofs.

For bi-implication, that's say we had the statement of P <=> Q, which it was equivalent to the following statement: (P => Q) and (Q => P), then we could transform this bi-implication into a conjunction between two disjunctions and a disjunction between two conjunctions, which was shown as the following: 

P <=> Q was equivalent to (P => Q) ∧ (Q =>P).

I applied the distributive law, then I got (¬P ∨ Q) ∧ (¬Q ∨ P) <=>  [(¬ P ∨ Q) ∧ ¬ Q] ∨ [( ¬ P ∨ Q) ∧ P] 

I applied the distributive law again, then I got [(¬ P ∧ ¬ Q) ∨ (Q ∧ ¬ Q)] ∨ [( ¬ P ∧ P) ∨ (Q ∧ P)]

Next, according to the identity law, P ∨ (Q ∧ ¬Q) <=> P which was equivalent to Q ∨ (P ∧ ¬P) <=> Q. 

Then  I  got  [(¬ P ∧ ¬ Q) ∨ (Q ∧ ¬ Q)] ∨ [( ¬ P ∧ P) ∨ (Q ∧ P)] <=> Q ∨ (P ∧ ¬P) 

Finally, by applying distributive law again, I got the result of  [(¬ P ∧ ¬ Q) ∨ (Q ∧ ¬ Q)] ∨ [( ¬ P ∧ P) ∨ (Q ∧ P)] <=> ( ¬ P ∧ Q) ∨ (Q ∧ P). 

Transitivity was simply a description of a relationship between elements in the statement/expression. For example in the following implication:

If A implies B and B implies C, then A implies C too.

This statement could be proved to be true through contradiction. 

If A implies B and B implies C and A doesn't imply C. 

Statement above causes a contradiction;therefore, transitivity is always true. 

As for double quantifiers, we talked about how we could claim that a certain subset of cartesian product ( for example M*M) was not empty. Moreover,  we also talked about ways to prove that entire cartesian product got to have some property.

Lastly,  professor heap briefly talked about the steps and format of proof. He also came up with a discussion about the importance of assumptions and indentations.

Example of proof from the lecture: