Week 6

This week, we talked about proving, non-Boolean functions, disproving a claim, and how to prove different claims.

Non - Boolean functions:
The definition of non-boolean function meant the way it sounded, functions that didn't return true of false as results. Moreover, we are introduced with a new symbol, which was the "floor x" as it was shown below.

 

As  it was shown above,  floor x must be the largest integer that was equaled or less than x, which was same as saying that floor x represents the smallest integer that was less than or equal (<=) to x.

For example, in the lecture during the week, we did various examples of simple proofs that involved floor x in the given definition and the claim. 

Given definition: 

Prove:

We proved the claim step by step by using the given definition (there are various ways of proving a claim):

 

Most of the time, we were asked to prove a claim true with a given definition, but there were occasions when we were asked to prove a claim false. This meant that we would have to "negate" the claim then prove the negation was true, and by doing this, we disproved the original claim.

Next, when proving claims that contained:

1. Conjunction (and) 

2. Disjunction (Or)

Then we would have to prove the claim by breaking the claim into different cases. 

In the following example, we were asked to prove the claim where all n that belong to natural numbers such that n^2 plus n is even. 

Week 5

This week, I reviewed materials that we covered from the beginning of September until now. I studied and tried to understand better on the various topics and concepts that I needed for the term test. I believed I did most of the questions correctly (maybe?). The test was not really complicated, but it did require some thinking and logics to do well in it. Last, but not least, ENJOY YOUR THANKSGIVING BREAK!

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:

Week 3

In week 3, we came to the end of the beginning stage of this course where we were actually going to dig deeper into the realm of logics. Also, this was the week when the assignment 1 was assigned. At first, I thought the assignment was going to be difficult because I had not gotten all concepts and ideas from the previous lectures; however, I was lucky that I was able to work in groups with my friend who knew the materials much better than I did. Anyway, we went through the assignment and various materials together. It was really helpful for me because not only I was working on the assignment, but I also got to review some critical terminologies and concepts. Nevertheless, we were stuck on the last question because we could not find a better way explaining either statement #1 was implied by the statement #2 or implied statement #2. It was unfortunate that we couldn't make it to the office hours to ask professor heap for a better way explaining our answers due to some private reasons, but we were still quite positive that our answers were good enough to earn full marks.

Moreover, we learned about various laws: commutative, associative, distributive, and De Morgan's law.

I knew these laws were important because I will need to know them enable to identify my steps as I went through questions that wanted me to prove either two statements were equivalent or not. 

For example: 

(P ⇒ Q) is equivalent to [(P ∧ (¬Q)) ⇒ (¬P )]

• ⇐⇒  ¬(P∧(¬Q))∨(¬P)  --> Implication 
• ⇐⇒  (¬P∨¬(¬Q))∨(¬P) -->De Morgan's 
• ⇐⇒  (¬P∨Q))∨(¬P) --> Double negation 
• ⇐⇒  (¬P ∨¬P))∨Q --> associative and commutative 
• ⇐⇒  ¬P∨Q --> idempotency
• ⇐⇒  P⇒Q --> implication