Week 3: Conjunction, Disjunction, Negation

In week 3, Danny taught the concept of conjunction, disjunction, and implication. I learnt these new learning by reviewing the material consequently. What I really found easy and got surprised during week 3 was how the course material tied up with Venn diagram question using 'or' and 'and'. Using the word, 'or', I can make a conjunction (also known as intersection). Whereas using the word 'and', I can simply find the disjunction.

The following symbols are used to represent conjunction and disjunction.  

Type	Meaning	Symbol
Disjunction	Or	∨
Conjunction	And	∧

The next important concept I learnt was the concept of logical negation. Danny taught the class that not not can be reinterpreted as negation of negation meaning there is no change from the original example. For instance, below example below deals with concept of negation.

Sam: "I am not not UofT student".

Here, the above sentence describes 'I am UofT student' as two 'not' cancels with each other. However, in our real life, we don't use word 'not not', and the reason behind this may be to make a sentence simpler. This also goes true when I am constructing the code in computer programming.

After that, in the standard negation slide in the PowerPoint I learnt the following negation means the same to each other.

¬∀x∈ X,... ↔ ∃x∈ X, ¬...	¬(P(x) → Q(x)) ↔ P(x) ∧ ¬Q(x)
¬∃x∈ X,... ↔ ∀x∈ X, ¬...	P(x) ∧ ¬Q(x) ↔ ¬(P(x) → Q(x))

The following below standard negation was what I found the most hard. 

 ¬(P(x) → Q(x)) ↔ P(x) ∧ ¬Q(x)

This can be interpreted as not (if p is true, then Q is also true) is the same with intersection of P(x) and  not Q(x). Later, Danny showed us the truth table which I learnt in week 2: implication. The concept of implication being false is the only case when if P is true, then Q is false. Using this knowledge as our basis to truth table,  I was able to answer how the relation between P,Q, and R (which is the third variable defined by Danny) depending on the situation. 

Mathematical approach I came up with for this week is to change the below equation without using conjunction and negation.  

¬((¬P(x) → Q(x)) ∧ R(x)) → S(x))

This can be interpreted as Not (Not(if P(x) is true, then Q(x) is also true) and R(x)) is true, then S(x) is true)

First I took out the negation which is placed at the beginning using 
¬(P(x) → Q(x)) ↔ P(x) ∧ ¬Q(x).

Then new equation would be (¬P(x) → Q(x)) ∧ R(x)) → ¬S(x)

Then, (¬P(x) → Q(x)) ∧ R(x)) can be simplified into ¬(R(x) → (P(x) → Q(x))).

Now, ¬(R(x) → (P(x) → Q(x))) → ¬S(x) can be come up without using conjunction. This can be interpreted as "not[(if R(x) is is true, then (if P(x) is true, then Q(x) is true) is also true )] is true, then not(S(x) is also true." 

And as two "not" is used, even if I cancel "not" and restate the following statement as 
(R(x) → (P(x) → Q(x))) → S(x), the statement still contains the same information as 
¬((¬P(x) → Q(x)) ∧ R(x)) → S(x)). 

Week 3 seems to be a bit more difficult than week 2, but the course material is fairly consistent with the Slog writing enabling me to remind myself what I learnt during the week. 

Week 1 & 2: Implication and Claim

     Throughout the first two weeks of CSC165 course, I was able to expand my knowledge on how the mathematical reasoning is related to computer science. During the first week, I learnt about two types of claim; universal and existential claim. 

    Universal claim is when there is not a single counter argument towards the claim, I can justify that the claim is universal claim. Nonetheless if there is at least one counter argument which is true, then the claim is no longer an universal claim. On the other hands, for existential claim, there can only be one evidence to support the claim. 

    One of the most difficult part throughout this two weeks was the concept of implication, converse, and contrapositive. Not to mention I had to learn the symbol for both universal claim and and existential claim. 

    Following below symbols were required to recognize during the week 2 classes. 

Symbol   Definition

∀:           for every, for all

∃:            some, there is 

¬:            not 

∈:           is a subset(or element) of

    Basic concept of implication, converse, and contrapostive was as follows;

∀x ∈ Z, f(x) → g(x)   This indicates that for every element of x is a subset(or element) of set Z. 

                                 And if f(x) is true, then g(x) is also true (or If f(x) then g(x)).

     Now this is an implication which uses the format of 'if f(x), then g(x)'. However later in week 2, I was able to realize that implications can take any form (meaning it is not necessary to follow the written form, "if x, then y")  as I listened to "natural" language slide on Danny's PowerPoint.   

∀x ∈ Z, f(x) → g(x)  can be rewritten as ∀x ∈ Z, if f(x), then g(x)

    Now let ∀x ∈ Z, f(x) → g(x) be my example of implication. Then converse of my implication would be ∀x ∈ Z, g(x) → f(x), which tells "For every element of x is a subset Z, and if g(x) is true, then f(x) is also true. However the converse of the original example of implication contains a different information compare to the original implication example I used. This was later proven by Danny's lecture using "numerical example".

   Yet, unlike the converse of the implication, the contrapostive of the implication contains the same information as the original implication. The contrapositive of my implication example would be 

∀x ∈ Z, ¬f(x) → ¬g(x)

The above claim can be interpreted as "for every element of x is a subset of Z, and if f(x) is false, then g(x) is also false". The understanding of contrapositive was also understood by the same slide "numerical example". 

For instance, using a numerical example, let f(x): x be a multiple of 3, and g(x): x³ is a multiple of 3. (This will be my mathematical approach for week 1 and 2.) And let's say the claim "x is a multiple of 3" is true. Given the following information, the result is as follows;. 

Claim                             Type of claim        Result

∀x ∈ Z, f(x) → g(x)           Implication             x is a multiple of 3 → x³ is also a multiple of 3. 

∀x ∈ Z, g(x) → f(x)           Converse               No information 

∀x ∈ Z, ¬g(x) → ¬f(x)       Contrapositive        x³ is not a multiple of 3 → x is not a multiple of 3.
                                                                  (contains the same information as the implication) 

As a result, whenever implication, f(x) → g(x) is true, ¬g(x) → ¬f(x) is true as well. 

 Thus, at a first glance, the course material looked insanely difficult, however as I pay a close attention to professor's lecture, I was able to learn what the course is step by step. Of course, I decide to review every course material I did in order to not forget the information I learnt. As for the first tutorial and quiz, I think it went pretty well considering how I was able to understand what the question was asking. In conclusion, the course material was good and I cannot wait to write for my next entry of slog.