Reflection of CSC165 Lec. 3 Sep. 27th.

Reflection of CSC165 Lec. 3 Sep. 27th.

3.1 Conjunctions, Disjunctions

3.1.1 Conjunctions

Conjunction is “the action or an instance of two or more events or things occurring at the same point in time or space.” It works almost the same as "and" and they are interchangable.

The symbol of conjunction is "∧". This symbol are mostly used with predicates. Thus, if we have two sets and there is an element belongs to both the sets, we should use SET1 ∩ SET2 rather than SET1 ∧ SET2.

The using of and may sometimes lead to ambiguity. For example, we say there are boys and girls in the groupX and let B(x) be he is a boy and G(x) be she is a girl. Then the expression may be :

∃x∈X, B(x) ∧ G(x)

This statement could be said as: there exist a guy in the group X who is both a boy and a girl, which is impossible.

The contradiction here comes from the exclusive property between B(x) and G(x). They cannot be achieved on the same person at the same time, though most of time the two predicates are inclusive (The man is both happy and rich, I am tall and strong) .

In the situation that the two statements are exclusive, we need to manifest that the 'x' ∈ X is not the same x. In this case, there exist a guy in group X who is a boy and another guy in group X who is a girl. Thus, this statement may works better:

(∃x∈X, B(x)) ∧ (∃x∈X, G(x))

This solution is also given by the professor. However, I still think using x two times may lead to confusion. It is better to state like:

 ∀x,y ∈X, (∃x, B(x))  ∧ (∃y, G(x) ) ∧ y != x

This point is also endorsed in 3.2.2, which are the ways to avoid ambiguity. I just reminded that the professor talked about Precise in the first lecture. At that time I don’t really get his point, but in the process of CSC165 studying, I found how important it is to be clear to state everything.

3.1.2 Disjunctions

Disjunctions Combine two statements by claiming that at least one of them is true. It works quiet the same as conjunction, so I will not repeat the same properties.

The symbol of disjunciton is '∨'.

Also, the ∨ with two exclusive predicates may also lead to ambiguity. For example, we go to either this Chinese restaurant for lunch or that Thai one for lunch. In mathematical definition, the term 'or' could contain the meaning 'both'. But it is impossible to go to both the Chinese restaurant and the Thai restaurant for lunch. Thus, compare to

∀x ∈X, ∃x, C(x) ∨ T(x)

C(x): Go to Chinese restaurant

T(x): Go to Thai restaurant

Set X means all possible ways to have lunch

It is better to say:

∀x ∈X, (∃x, C(x)) ∨ (∃x, T(x))

To avoid ambiguity.

3.2 Negations

3.2.1 Negations
 

The concept of negation has been mentioned and emphasized in a lot of courses like MAT137 and CSC108, but it is still confusing sometimes as the rules of negation may change all the time according to different situations.

This time a practical way of negation is taught, which enables us to negate a statement step by step. For example:

All Chinese people are male.

Set X means all people

C(x) means people who are Chinese.

M(x) means people who are male.

①. Simply add 'Not' before the statement, so 'not all people in the world are male', so in symbolic languague it becomes "¬(∀x ∈X, C(x) => M(x))"

②. Diminish the scope or parenthesis by negating the statement part by part, so "¬(∀x ∈X, C(x) => M(x))" would then become ∃x ∈ X, ¬(C(x) => M(x))

③. Apply ② again and agin until the negation sign just apply to the smallest possible part of the expression, so ¬(∀x ∈X, C(x) => M(x)) would finally becomes ∃x ∈ X, C(x) => ¬M(x)

3.2.2 Scope

Again, some expressions would be ambiguous. For example: P(x)  ∨ Q(x) => R(x) may have two ways to understand.

1. (P(x)  ∨ Q(x)) => R(x)
2. P(x)  ∨ (Q(x) => R(x))

However, as the above shows, the statement with parenthesis would be very clear.

Also, in 3.1.1 and 3.1.2, we mentioned the situation that ∨ and ∧ may cause ambiguity when the two preconditions are exclusive. The solution here may give all elements in the same set different names rather tha simply name them 'x'.

3.3 Truth tables, and some laws

3.3.1 Truth Table

Truth tables are used when there are more than two predicates as Venn diagram would become to complicate. No matter how many predicates there are, truth table would always present it in a clear form.

Then let's try to use Truth table to judge the statement. There are two predicates P(x) and Q(x). We want to know if P ∧ Q, P ∧ ¬P, P ∨ ¬P are true.

P & Q	P ∧ Q	P ∧ ¬P	P ∨ ¬P
T & T	T	F	T
T & F	F	F	T
F & T	F	F	T
F & F	F	F	T

There are three kinds of statement.

P ∧ Q is satisfiable as we need to determine whether it is true or false. It is meaningful.

P ∧ ¬P is unsatisfiable or contradiction, because P ∧ ¬P means both predicate P and the negate of predicate P should be true, which would only left an empty set. It is meaningless as its always false.

P ∨ ¬P is called tautology or universal truth as it contains all possibilities. It is also meaningless as it is always true.

3.3.2 Laws

There are a lot of laws could be applied in symbolic expression. These laws may reduce our workload. The most important one is called De Morgan's Law:

¬(P ∨ Q) <=> ¬P ∧ ¬Q

¬(P ∧ Q) <=> ¬P ∨ ¬Q

Reflection of CSC165 Lec. 2 Sep. 16th.

Reflection of CSC165 Lec. 2 Sep. 16th. 

2.1 Quantifiers

2.1.1 Definition

The concept of quantifier has been mentioned in the first lecture. It is really important to remember all the definitions so I want to repeat it here as I do not think the professor did enough review on this.

"Quantifier is the expression that indicates the scope of a term to which it is attached. Moreover, quantifiers connect properties of elements to properties of sets." 

Examples of quantifiers could be all ans some.

2.1.2 Verify and Falsify

So far we have learnt two quantifiers which are universal quantification(∀) and existential quantification(∃). Verify and Falsify these quantification follow these rules as Figure 2.1 shows.

Figure 2.1

Venn diagram could visualize the problem with X and O presenting the parts is empty or occupied.

2.1.3 Quantifiers as claims about sets 

Several symbols could be used to present the relation between sets.

A ⊆ B means set A is a subset of set B. Keep in mind the symbol   ⊂ would also be used sometimes for the same meaning. Its okay to interchange these two.

A ⊄ B means set A is not a subset of set B.

A∩B means the union of set A and set B.

A∪B means the intersection between set A and set B.

A with a line on it (A-bar) means the part except A. A-bar is also refers to the average value of A sometimes, but it is not the case in terms of programming.

Ø means the empty set, where no elements are inside.

All symbols mentioned above could just be used to present the relation between two sets, so it is not correct to say a ( an element)  ⊆ A (a set) as a is just an element while ⊆ could just be used between sets. Instead, a ∈A is the correction expression.

2.1.4 Evaluating quantified claims

Using python functions to evaluate the quantified claims is somehow confused as I did not quite get the point when in the lecture, so it's important to review it again

From the statement "all employees" and "earn over $42.000", set E and O could be referred. However, it is hard to get the logic and relation between S1 and S2 from the sentence "X in S2 for X in S1".  From the answer given by professor (q3(E,O)) I could imply S2 refers to the smaller set while S1 stands for the larger set, or the statement after "for" is the larger one.

2.2 Sentences, Statements and Implications

2.2.1 Sentences V.S. Statements  

Figure 2.2 shows the brief relationship between sentences and statements, or, by using the expression studied in 2.1.4, we can say set Statement ⊆ Sentence.

Figure 2.2

More specifically,' A statement is a sentence that is NOT "open". The object in a statement is quantified, thus a statement can be evaluated true or false while a sentence can't be evaluated.'

The term quantified is the key term here. It is also suggest we can distinguish a statement by finding if it could be evaluated, but all these explanations are somehow confused as the following examples shows:

"

Exercise: Is it a statement?

➔ Someone ate my sandwich.

◆ YES

➔ The sandwich tastes delicious.

◆ NO"

I honestly think both these sentences could be evaluated by saying true or false, so the apparent different between statement and sentence is still how open the sentence is, or in other words, the quantifier. In first example, the keyword Someone leaves the sentence open as this "someone" could be anyone while in the second example, the word "the" makes the sentence stable and fixed.

With these confusions, I did more researches about sentence and statement in order to differentiate them more clearly. After asking others I know that Statement should be  a meaningful declarative sentence that is either true or false. "The sandwich tastes delicious " is not a statement because it’s a subjective personal opinion. Thus, I would like to say compare to quantified or open, subjective and objective should be the real key to distinguish statement and sentence. A statement should be a subjective fact while everyone would lead to the same result. A sentence is just a declarative description.

2.2.2 Predicate

Predicate is a Boolean-valued function P: X→ {true, false}. The concept of Boolean is also mentioned in CSC108. The result of Boolean would just be true and false so its close the property of statement.

The expression could be x (an element) ∈L(a set)

Or L(x), which means X has the property of L

We use the symbol "¬" to present the meaning neagtion. ¬L(x) means the element X does not have the property L.

Predicates without specifying X is an open sentence and it could be converted to a statement by being universally quantified or existentially quantified.

Sometimes it is hard to distinguish between a set and a predicate. Predicate is more like a property (easier to say if it is true or false.)

2.2.3 Implications

Implication works like causality. It is  presented with a antecedent and a consequent. It could also be written as P ⇒ Q which means P implies Q. The verify and falsify of an implication works the same as a universal quantifiction.

In common sense, causality should works with direct relation P causes Q, but this is not always the case in the mathematical expression. For example, we would normally say If it rains, then the ground would being wet. Here the wet ground is the direct result of the rain. However, what if we say "If it rains yesterday, then the sun rose today."  It seems ridiculous as there is no relationship between the two events, but we cannot falsify it as the sun will always rise. This implication is true mathematically.

There are two more examples to show, converse and contrapositive. Converse is the exchange between antecedent and consequent. The converse of implication may not always be true.  Contrapositive exchange the negation of antecedent and consequent. The contrapositive of a implication is exactly the same as the implication. 

2.2.4 Equivalence, sufficient and necessary

Compare to implication P ⇒ Q which is single side, Equivalence means P if and only if Q or P <=> Q.  

Necessary means P => Q, or "For P to be true, Q must to be true" while sufficient means Q => P, or the conditions P are enough to lead to result Q (Q could also be proved by other conditions).

Reflection of CSC165 Lec1 2014.Sep.9th.

Reflection of CSC165 Lec1 2014.Sep.9th.

1.1 Introduction

Since its the first lecture, plenty of time is spent on emphasizing rules and requirements of the course. Its not necessary to spend time describing that in the blog, but the part after becomes really hard to understand.(1.2 of the lecture)

1.2 Precision

1.2.1 Four paragraphs of codes

Four paragraphs of codes are showed and compared in section 1.2. As I did not use any Python and my first CSC108 course started one day after this CSC165, I am so confused of these codes during the lecture. I cannot figure out the difference between 1&3, 2&4 (Figure 1.1) as I think they just change the order of expression as the picture shows in my note (Figure 1.2).

Figure 1.1

Figure 1.2


After reviewing the slides, I found professor's comment for Q1 is:

"whether every element of S1 is not in S2".

while for Q3 is:

"Whether there exists an element in S1 which is not in S2".

These notes make me understand the difference between Q1 and Q3. Basically it implies how we understand the words after "if". Moreover, it really matters about what we defined directly and indirectly. So we can paraphrase the Q1 and Q3 like this:

Q1:"(all) x is in S1, if (all) x is in S2     ==>false
    (all) x is in S1, if (any) x is not in S2 ==>true"

Q3:"(all) x is in S1, if (all) x is not in S2 ==>true
    (all) x is in S1, if (any) x is in S2     ==>false"

In Q1 we directly define what is false. The negation of false is true then. This is why we have "any" but not "all" before the X in the negation part. This idea makes sense to me after the MAT137 course which we review the concept negation and how it works in different cases.

Now it becomes clear, if we want to prove "all X is in S2" is not false, only one case that "X is in S2" is enough.

By concluding this, we say there is a implied "all" before the X which's condition is directly mentioned.

1.2.2 Python syntactic sugar

There are two main symbols all(L) and any(L). Understanding them could to summarize the content in 1.2.1 better.

"all(L): whether all elements in L are True.
➔ all([True, True, True])
◆ TRUE
➔ all([True, False, True])
◆ FALSE

any(L): whether any element in L is True
➔ any([False, False, False])
◆ FALSE
➔ any([False, False, True])
◆ TRUE"

So Q1 in 1.2.1 could also be written like

Q1: return all([X not in S2 for X in S1]) which is the same as
    return any([X in S2 for X in S1])

As mentioned in the powerpoint, it is an cooler way to code as it saves space.

1.3 Problem Solving and Quantifiers

1.3.1 Problem Solving

The section of problem solving provides us a general pattern we might follow when facing all problems. Basically these steps are recommended:

• Understand the problem
• Plan a solution
• Carry out your plan
• Review any solution you achieve

In CSC108, we learnt about how to define a function. It also follow these steps and lead to the program.

1.3.2 Quantifiers

The conception of quantifiers are mentioned in both this course and MAT137. In MAT137 we have studied the symbol of there exists (∃) and for all (∀) and used them in certain questions. In this course ∃ is called existential quantification while ∀ is called universal quantification. 

To prove universal quantification, we need verify every elements as "all" of them must satisfy. To disprove universal quantification, we just need to give a single counterexample which does not meet the requirement.  To prove existential quantification, give single example. To disprove existential quantification, verify all elements that does not meet the quantification. They are vice versa basically.