Course Conclusion

Like I always say, it's always sad to say goodbye :(

I would just like to say a few things about my experience in this course.

First of all, the course material was very very very very very relevant to me as a computer science student. You may think that this course may not be helpful in the real world or even outside this course, but you would be very wrong. My fellow students and I were utilising knowledge that we've learned from CSC165 without even realising it sometimes! There were many instances of this. For example when fellow students and I were having a friendly argument about something (I forgot exactly what it was), it was settled by bringing in implication and negation, P => Q, P and not Q, etc. Another example is having learned list comprehensions in CSC165 and actually using them in CSC148 and for general testing involving generating a random list (i.e. I used [int(100*random()) for i in range(20)] a lot to test functions I've made). The most recent example of CSC165 being useful outside of CSC165 is for if statements involving conjunction and disjunction. While my fellow classmates and I were discussing about a certain very long if statement with a lot of conjunctions and disjunctions, we wanted to know when it would go to the else statement and how to simplify this if statement. To figure out when it would go to the else statement, we automatically started writing up the if statement in P and Q form with conjunctions and disjunctions and then negated it. We did this automatically and we didn't even notice that we are utilizing tools we've learned in CSC165! This was an awesome experience and it was so much more awesome when we realized what we were doing! This course and all its materials is tremendously more useful than I ever thought it would be!

Though I found that the course started out really tough, everything became really clear afterwards. I'm assuming the a lot of the course material was purposely made to be difficult for us to gain a much better understanding of the less difficult material.

I would like to thank all my fellow classmates, partners, and friends for helping me better understand the material. I would also like to thank all those I've helped as well because it gave me the chance to better understand the material myself by explaining it to someone else!

I would like to thank my awesome TA Ekaterina S! Thanks for putting up with my tutorial section. I know we were very unenthusiastic but you still pushed through and brightened up everybody's day. Thanks for being clear and concise and thanks for staying after tutorials to help us sometimes. Thanks a lot kat!

Finally, I would like to thank our professor Danny Heap, for being a great and wonderful professor. He was very enthusiastic, very helpful, and very understanding. Thanks for always staying after lectures to discuss problems and clear up confusions. Thanks for staying in your office to help students, especially for all those times you've stayed to help students in your office when it was not your declared office hour. Thanks for being a good teacher and a friendly prof. Some of my fellow classmates and I were discussing how much of an amazing professor you are because most of us did not try to memorize anything from this course, but some how we just knew how to do it all.
Thanks for everything professor Danny heap!

Thanks everyone, it has been a great, enjoyable semester!

Feel free to contact me, see you all around!

Halt Right There!

I'm going to be brutally honest here. I haven't had time to review course notes recently and so I was really really lost during the lectures involving reduction and halting functions. I had almost no idea what was going on and I was really confused.

Halts? Halting? Naval_gaze? Infinite loop? Halt cannot exist? What?!?

I felt horrified that I didn't have the slightest clue what was going on especially since Assignment #3's deadline was closing in, which involved using halts. So I did some strenuous reviewing of the lecture notes along with the course notes.

After reviewing, I still felt dazed and confused about what a function halts was all about. It was only when I was semi-explaining (I had a vague idea of what halts was but didn't really understand it) the course notes/lecture notes to a fellow CSC165 classmate that I had an epiphany and almost fully understood what halts is all about.

Halts is a function that would take a function and an input as a parameters and return True if and only if the given function halted on the given parameter.

Halts has proven to not be computable (i.e. impossible to write in code) because there exists a contradiction. The proof is in the course notes on page 70. With this knowledge in mind, we can reduce the halting function to another function that is similar and show that a contradiction exists to prove that this other function can not be computed as well.

For example, let's consider this function (I made this example and I'm assuming this function is not computable so let me know if I'm mistaken):

def prints_something(f, x):
    ''' (function, object) -> bool
    Return whether the given function prints anything on the given input x.
    '''
    # Here exists valid Python code that scans the functions codes and
    # returns True if and only if the given function prints anything on
    # the given input x

Now, let's assume this function is computable and reduce the uncomputable function halts to this function:

Assume prints_something is computable

def halts(F, i):
    ''' (function, object) -> bool
    Return True if and onlf if function F halts on input i.
    '''

    def prints_something(f, x):
        ''' (function, object) -> bool
        Return whether the given function prints
        anything on the given input x.
        '''
        # Here exists valid Python code that scans the functions codes and
        # returns True if and only if the given function prints anything on
        # the given input x

        pass
   
    pass

So far this doesn't tell us anything. Now let's create an arbitrary function that function prints_something will analyze:

def f_naught(g):
    ''' (str) -> NoneType
    After calling F(i), the function and input that was passed
    to halts as arguments, print g.
    '''
    F(i)
    print(g)

Considering the function f_naught, we can see that if F(i) (a function and input that was passed to halts) halts, f_naught will print something thus prints_something will return True. If F(i) does not halt, f_naught will never print something and prints_something will return False.

So now let's put all these functions together. Obviously, f_naught must go into halts since it uses F(i) from halts:


Assume prints_something is computable with valid Python code

def halts(F, i):
    ''' (function, object) -> bool
    Return True if and onlf if function F halts on input i.
    '''

    def prints_something(f, x):
        ''' (function, object) -> bool
        Return whether the given function prints
        anything on the given input x.
        '''
        # Here exists valid Python code that scans the functions codes and
        # returns True if and only if the given function prints anything on
        # the given input x

     def f_naught(g):
        ''' (str) -> NoneType
        After calling F(i), the function and input that was passed
        to halts as arguments, print g.
        '''
        F(i)
        print(g)
   
    return prints_something(f_naught, '')

If F(i) halts, prints_something(f_naught,'') will return True because the "F(i)" line in f_naught will stop running, thus allowing print(g) to print something.Thus halts(F, i) will consequently return True as well.

If F(i) doesn't halt, prints_something(f_naught, '') will return False because the "F(i)" line in f_naught will never stop running, thus never allowing print(g) to print anything. Thus halts(F, i) will consequently return False as well.

Thus halts(F, i) returns True when F(i) halts, and it returns False when F(i) doesn't halt.

Now, the problem should be pretty clear. We've somehow successfully created a halting function!

The meaning of reducing one function to another is if this inner function can be made, the outter function can be made. Thus:

prints_something is computable implies halts is computable.

But there exists a contradiction; halts was previously proven to not be computable

Also, if we take the contrapositive of the statement:

"prints_something is computable implies halts is computable"

 We get:

"halts is not computable implies prints_something is not computable"

Thus, since halts was previously proven to not be computable, this implies prints_something is also not computable!

I hope this helps someone better understanding the halting function and related information!

Understanding Big-Oh (upperbounds) with the help of 1i

The concept of Big-Oh can be quite terrifying if you don't really understand it at first. However, after more rigorous overview of course notes and reading students' slogs about Big-Oh, I felt much more comfortable with this concept and now I know why it is such an important concept for computer science students.

Refer to 1i's March 21st, 2013 slog post : http://oneicsc165.blogspot.ca/

In this course, we've been dealing with proofs for a while now and it is fairly easy to just focus on the the structure of the proof, the symbolic statement of the proof, and the math involved in linking the antecedent to the consequent. However, because it is fairly easy to do this now and it almost becomes an automatic thought process, it becomes fairly easy to forget about what each line actually means outside of all the math and steps.

This is why I liked 1i's approach at understanding exactly what Big-Oh means by going through and understanding each step of a proof. If you understand what each of the relevant lines of the proof mean instead of just performing the steps to finish the proof, you'll have a better understanding of Big-Oh.

Through each step, 1i continuously reminds us that we are making our function f(n) that is bounded by our function g(n), bigger and bigger and eventually it is shown that a constant multipled by function g(n) is still bigger in the end. This is what it means to have an upper bound and this is what Big-Oh means. Through the proof, which I initially thought was just some mathematical equations, operations, inequalities, etc that would not give us a bigger/real world picture, and through 1i's slog post, I now have a better understanding of what Big-Oh actually means.

Thanks 1i for your post!

The Folding Problem

After reading about Mandy's "Streetcar Drama" and attempting it myself last week, I've decided that I'm going to try solving the "Folding" problem Danny Heap has presented to us in lectures.

The "Folding Problem" handout can be found here:
http://www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/folding.pdf


1. Understand the problem:

What the problem presented to us is finding a solution to predict the sequence of up creases and down creases for any number of times you carry out a folding operation.

2. Device a plan:

My plan - a bit rudimentary and brute force - is to do carry out fold operations starting from 1 fold and observe any apparent patterns in the next fold that are relative to the the first fold. I will do this until I find a certain/definite pattern:

3. Carry out the plan:

Let v represent up creases and ^ represent up creases.

Folds	Crease Sequence
1	v
2	^vv
3	^^vv^vv
4	^^v^^vvv^^vv^vv

Here's a look at the table again, pointing out the noticable patterns:

Folds	Crease Sequence
1	|v|
2	^|v|v
3	^^v|v|^vv
4	^^v^^vv|v|^^vv^vv

  4. Look back:

As we can see, the first crease, which is an up crease, remains throughout each new fold and it is the pivotal point of the crease sequence. There is always an equal number of creases to the left of the pivotal first crease and to the right of the pivotal first crease. After each new fold, the previous crease sequence is replicated to the right of the middle crease sequence. Most importantly, the sub crease sequence to the left of the middle pivotal first crease is a 180 degree rotation of the sub crease sequence to the right of the middle pivotal first crease. This means that each new fold has the previous fold's crease sequence to the right of the middle crease, which is the first initial up crease, and to the left of that middle crease is the 180 degree rotation of the previous fold's crease sequence. These patterns are shown in the table above with the first crease, which is the pivotal point through each new fold, shown as |v| and the sub crease sequence that are 180 degree rotations of eachother shown in green and red. Also, the crease sequence with the slight blue background colour shows that the previous fold's crease sequence is exactly the same as the sub crease sequence to the right of the middle crease on the next fold. Here is the necessary information again listed:

• First crease is an up crease
• First crease remains as the middle crease in the sequence throughout each new fold
• After each new fold, the previous fold's crease sequence is replicated to the right of the middle crease, which is the initial upcrease, and a 180 degree rotation of the previous fold's crease sequence is on the left of the middle crease

Now, with this information, we can accurately predict a pattern.

Using Python, we can write a miniture program to predict the sequence of creases for n folds:

def crease_sequence(folds):
    ''' (int) -> str
    Return the crease sequence of a paper with certain number of given folds.
    '''
    if folds == 1:
        return 'v'
    else:
        previous_seq = crease_sequence(folds - 1)
        return rotate(previous_seq) + 'v' + previous_seq

def rotate(sequence):
    ''' (str) -> str
    Return a 180 degree rotation of a given crease sequence.
    '''
    rotation = ''
    for c in sequence:
        if c == 'v':
            rotation = '^' + rotation
        elif c == '^':
            rotation = 'v' + rotation

    return rotation
 

 Yay! I used recursion!
 This Python has been tested and is working! Please feel free to try it out yourself!

What??? That was possible???

I've recently been browsing Slogs of fellow students and I've stumbled upon a very interesting post by Mandy Xu slog: http://mandyxu.blog.com/

During one of Danny Heap's lectures, a problem presented to us as "Streetcar Drama" was discussed. We did not really go in-depth on this problem and I left with the impression that this problem was unsolvable because there just wasn't enough information.

However, Mandy's slog showed me that this problem did actually have a solution and I should not have been so lazy, taking the easy path of assuming that it was unsolvable so I wouldn't have to think about it much more!

Here is the "Streetcar Drama" problem:

There are two friends having a conversation on a streetcar. We'll label them A and B:

A: Haven't seen you in a long time! How old are your three kids now?

B: The product of their ages (rounded down to nearest) is 36.

A: That doesn't really answer my question.

B: Well, the sum of their ages is - [fire engine goes by]

A: That still doesn't tell me how old they are.

B: Well, the eldest plays piano.

A: Okay, I see: their ages are - [you have to get off the streetcar]



Mandy concisely takes a mathematical approach to solving this problem. The best part of her post is that she does not tell you the answer right away. She simply gives you hints to how you might come close to the answer at first, so you can try to figure it out for yourself first.

Here was my thought process of reading her post:

As I was going along with her post, I prevented myself from scrolling all the way to see the next step or answer and only considering some of her hints to see whether I can solve this myself first.

So the first piece of information that is given to us is "The product of their ages (rounded down to the nearest) is 36." Thus you can represent this mathematically using 3 variables:

x = age of first child
y = age of second child
z = age of third child

thus x*y*z = 36

Before looking at any more of Mandy's solution or hints, I tried to solve this problem myself further first. So I considered the line "Well, the eldest plays piano."

This tells us that of the three children, there is 1 older than the others.
Let x = the eldest child. Then y and z must be < x.
Thus y and z may or may not be the same age, but we know they have to be younger.

since x*y*z = 36

What 3 numbers, one of which must be larger than the other two, gives you a product of 36?

Well, let's consider all the pairs of natural numbers that multiply to give you 36:

1 * 36 = 36
2 * 18 = 36
3 * 12 = 36
4 * 9 = 36
6 * 6 = 36

Now let's try to split any of these numbers so that they're a combination of 3 numbers, with one of the numbers being greater than the other two numbers:

1 * 1 * 36 = 36
1 * 2 * 18 = 36
1 * 3 * 12 = 36
1 * 4 * 9 = 36

2 * 3 * 6 = 36
2 * 2 * 9 = 36

3 * 3 * 4 = 36

Thus one x, y, and z have to be one of the combinations above. What other lines give us more information??
I on my own can not decipher the lines of information much further. The only things I can think of, that may not be entirely concrete are:

• Friend A asked how old are your "kids" now. Usually you wouldn't refer to someone's child as a "kid" if that child was 18 or older. Thus I don't think the eldest can be 18 or 36. This is not a concrete assumption though.
• Friend A mentions how he hasn't seen friend B "in a very long time". Assuming "a very long time" means over a year, this may indicate that if friend B does have any children that is 1 years of age, friend B probably wouldn't have known about it (unless through social networking). Thus I don't think any of the children can be 1 years of age. This is also not a concrete assumption as well.
• Finally, friend B mentions that the eldest plays piano. Children don't go to school until 4, the youngest age children usually start taking piano lessons is age 5 or 6. At that age, they are just starting to learn how to play the piano. Thus to be able to "play" the piano, they must be older than 5 or 6. These assumptions are also not concrete

With the not-for-sure information I gathered through real-life intuition, this would mean any combination with:

• ages >= 18 would not be valid
• age 1 would not be valid
• and the eldest has to be >= 6 (assuming children can start playing the piano after at least a year of lessons)

1 * 1 * 36 = 36

1 * 2 * 18 = 36

1 * 3 * 12 = 36

1 * 4 * 9 = 36

2 * 3 * 6 = 36

2 * 2 * 9 = 36

3 * 3 * 4 = 36

This leaves us with 1 combination: 

2 * 2 * 9

Thus x = 9, y = 2, and z = 2

Since my steps to the solution involves making some very bold assumptions, I am not confident in this solution at all. I am, however, happy with the fact that I even found a solution. This is the point where I looked at Mandy's steps and solutions to compare.

Well surprise surprise. After I looked at Mandy's solutions, I have the same answers!!! HOWEVER, the steps I took were completely wrong and ridiculous! 

Mandy's solution was completely mathematical and the main pieces of information taken in and considered were:

• The product of their ages is 36
• The sum of their ages doesn't give you any exact information
• And there is an eldest

The biggest clue I missed was that the sum of their ages doesn't give you an exact answer.

Thus this means there are two product of 3 numbers, x*y*z, whose sum are the same:

As Mandy demonstrated, just find the possible combinations (as I did earlier), find the two combinations that have an identical sum, and choose the one that has only 1 exact eldest!

I would like to thank Mandy for posting that and for making me realize that I should not be so lazy when it comes to thinking about a complex problem!

Proofs: Simple Structures, Complicated Content

I just wanted to slog about how to generally start a proof and set it up/structure it. There is nothing more really to say about writing up proofs beyond that because each proof is unique and the meatiest part of the proof, finding the connections, is vastly different with each different proof.

The example I will be using (even though this example is covered in lecture, I want to go more in-depth, step-by-step):

"For every natural number n, n² odd implies that n is odd"

1. Decide whether you want to prove the statement or disprove the statement. Do this by using intuition or scribbling some cases you think will make the statement wrong. Basically look for some counter-examples.

Since I can't think of any odd numbers` that has an even root, I'm going to attempt to prove this.

2. Now you're ready to begin. Always start with the symbolic representation of the original statement of what you're trying to prove or disprove. After figuring out the symbolic representation of the statement, if you decided you want to disprove it, NEGATE the statement before proceeding with the next steps.

• What does an odd natural number mean symbolically??? We'll have to refer to the symbolic definition of what it means to be an odd number by either looking it up on the internet, or finding it in the Course Notes.
• We see that for a natural number to be odd, it means there exists a natural number where 2 multiplied by that natural number, plus one, equals to our odd number. Thus the symbolic statement would be:

∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)

• Since we want to prove this, then we don't need to negate it.

3. Now it's time to set up the structure for the proof, while leaving out the meat of it. While setting up the structure for a proof, you want to follow these guide lines:

• Start from left to right of the symbolic statement

• Whenever you have have a Universal Quantifier (∀), you want to assume there is a generic number of this set, and then proceed with the proof with everything below with one indent. After completing the structure and/or proof for all the proceeding elements after the universal quantifier, the whole statement after the universal quantifier, including the universal quantifier should be restated in conclusion form, aligned vertically with the original assumption line of this universal quantifier. 
• Assume x∋Y     # x is a generic to introduce ∀ 
• proceeding lines start here vertically (without a bullet obviously)
•  
• # ***Lines connecting the antecedent to the consequent ***
•  
• 
  
• Then x∋Y................  # conclude for all x in Y
• For our example:
• Assume ∀n∋N     # n is a generic natural number to introduce ∀
•  
•  
•  
• Then  conclude ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)  # for all n in N

• Whenever you have an Existential Quantifier (∃), you want to "pick" or "let" that number equal to something that you haven't decided yet, unless the existential is a part of your antecedent for a direct proof. So you want to have either:
• pick x = _____ then x∋Y
• or let x = _____ then x∋Y

• For our example, since our existential is part of our antecedent for a direct proof, we don't pick until we get the the consequent part of our proof

•  Whenever you get to an antecedent of an implication, you want to assume the antecedent is true and the lines proceeding the proof should be indented by one. The proceeding lines should be the meat of your proof where you show a connection from the antecedent to the consequent. Then, after these lines, the consequent should be stated. Then on the next line afterwards, the whole implication should be stated without the indent, thus lined back up with the antecedent vertically.
• Assume x = y   # x = y is an example antecedent
• proceeding lines start here vertically (without the bullet obviously)
•  
•  
• then consequent 
• Then x=y ⇒consequent

• For our example:
• Then ∃ k∋N, n² = 2k + 1
•  
•  
•  
• Then ∃ k₀∋N, n² = 2(k₀) + 1
• Then (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)

• Keep in mind that the meatiest part of the proof, the fruit of the proof, the most meaningful part of the proof, the hardest part of the proof, are the ***Lines connecting the antecedent to the consequent ***, from the antecedent assumption. Thus you can have this structure set up while leaving space for these lines.

4. If you suspect that your antecedent implies a conjunction, you may want to have different cases set up in your proof that follow the same structure guidelines.

5. Now that you have enough information to start, setup, and structure a proof, all you need is to figure out the hard part of connecting any antecedent to the consequent. In the case of just showing if a conjunction or disjunction is true, the same structure can be followed.

• For our example:
• Then ∃ k∋N, n² = 2k + 1
• Then n² - 1 = 2k
• Then (n + 1)(n - 1) = 2k
• Then n = 2(k/(n+1)) + 1
• Then let k₀ = (k/(n+1))
• Then∃ k₀∋N, n² = 2(k₀) + 1

6. When concluding a disprove, state that the original statement is incorrect because you showed the negation to be true.

7. This is just a simple guide, there are many other things you may need to think of while proving such as should you take the contrapositive of the statement? Should you perform a direct proof? Should you perform an indirect proof? Should you prove by contradiction? Etc.

So he final product for our proof of ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)

is:

• Assume ∀n∋N     # n is a generic natural number to introduce ∀
• Then ∃ k∋N, n² = 2k + 1
• Then n² - 1 = 2k
• Then (n + 1)(n - 1) = 2k
• Then n = 2(k/(n+1)) + 1
• Then let k₀ = (k/(n+1))
• Then∃ k₀∋N, n² = 2(k₀) + 1
• Then ∃ k₀∋N, n² = 2(k₀) + 1
• Then (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)
• Then  conclude ∀n∋N, (∃ k∋N, n² = 2k + 1) ⇒ (∃ k₀∋N, n² = 2(k₀) + 1)  # for all n in N

So this would be a proper proof with proper structure (minus the bullet points on each line).

Hope someone finds this helpful!

Applying skills learned in CSC165

I found it very interesting that something we've learned from CSC165 was very useful and relevant to courses outside of CSC165. For example, in our CSC148 project, one of our tasks was to compare two sets of elements to see whether they had any elements in common.

After reading the instructions for this particular task my partners and I instantly thought of Venn Diagrams, sets, subsets, etc. We were conditioned on how to approach this question logically through CSC165. So basically, what it boiled down to, was that we had to create a class method that would check whether two sets had no elements in common. In regards to Venn Diagrams, this meant that there must be no overlapping elements in the two sets (no elements in the intersection of the two sets).

Thinking about this logically, like we were taught in CSC165, was not so difficult anymore. What was even more surprising was that we've made very similar functions in CSC165 lectures. We've made functions that addressed these exact questions and the functions involved List Comprehension!

We were taught how to understand and make use of list comprehension in CSC165, but not in CSC148, and now my partners and I had the opportunity to apply what we've learned from one course to the other. It was an exciting moment!

The best part of this experience was that the class method worked flawlessly with the list comprehension and the method's body was only a one-liner; return one list comprehension.

Now, here's what I was talking about:

The required method's docstring:

"Return True iff there are no elements in common between this multiset and the other multiset."

Our body for the function:

return True not in [item in other.multiset for item in self.multiset]

This way, our function looked a lot cleaner and a lot more lines of space were saved because we didn't have to create actual looks to make this function (which we would have done if we didn't know about list comprehensions).

Use LOGIC!

While going through the first test, in preparation for term-test #1, I found that Part B of the first question was pretty time consuming and a tad difficult. Since it is part of the first question and each sub-question(i, ii, iii, iv, v, vi) was only worth 1 mark, this indicated that these questions weren't supposed to be that difficult.

################################################################################
The question:

Recall these python functions from lecture:

def quant1(L1, L2): return False in [x in L2 for x in L1]
def quant2(L1, L2): return True in [x in L2 for x in L1]
def quant3(L1, L2): return False not in [x in L2 for x in L1]
def quant4(L1, L2): return True not in [x in L2 for x in L1]


Part(B)

For each output (i)-(vi), either devise lists L1 and L2 so that the python expression:
[quant1(L1, L2), quant2(L1, L2), quant3(L1, L2), quant4(L1, L2)]
evaluates to that output, or else explain why it is impossible to devise such lists.


(i) [T,F,T,F]
(ii) [T,F,F,T]
(iii) [T,T,F,F]
(iv) [F,T,F,T]
(v) [F,F,T,T]
(vi) [F,T,T,F]


################################################################################

I was wondering why I was taking so long with these questions that are assumed to be easy, so I spent some time trying to figure out what the problem was.

My first attempts at these questions, for each of the questions (i) - (vi), I didn't have an attack plan. I just jumped straight into the question, creating a small random list in my head, and then going through each of the 4 quants individually. Now that I think about it, that was kind of crazy. No wonder why I took so long. I was going through each function in my head, sometimes more than once for a question using a newly created list in my head, and I did this for each question the first time. Thus I ran over 4*6 functions using random made up lists in my head. That was such a waste of time! That definitely wasn't the method the prof had intended.

So then I kept trying to see whether there was a better method, an attack plan, something we've learned in lectures. Then I thought to myself that this is a logic course, and we've went over negations many times. So I went back to the quant functions and wrote comments to indicate what they predicate in English:


def quant1(L1, L2): return False in [x in L2 for x in L1]
## Means there exists an element in L1 that is not in L2

def quant2(L1, L2): return True in [x in L2 for x in L1]
## Means there exists an element in L1 that is also in L2

def quant3(L1, L2): return False not in [x in L2 for x in L1]
## Means all elements in L1 are in L2

def quant4(L1, L2): return True not in [x in L2 for x in L1]
## Means no elements in L1 are in L2

Now I can clearly see that quant1 and quant3 are negations of each other and quant2 and quant4 are negations of each other as well.

"What can I do with this information?" I thought to myself. Well, if some quants are negations of each other, then they both can't be True at the same time in each list. Now that was an easy way to find the impossible lists in (i) - (vi).

Now, thinking logically, it only makes sense that each list would have 2 Trues and 2 Falses in them. Also if any quant predicate is True, the negation quant predicate must be False, and vice versa. So now that eliminates having to go through each of the 4 quants in the list because you can trust that the negation of a quant is false if that quant is true.

So now, thanks to logic, I've developed an attack plan! All I had to do, after filtering out the impossible lists, was to find the quants corresponding to the Trues in the list and then generate a list that would satisfy the quants for them.

Now, with all this knowledge in mind derived from logic, all I had to do was eliminate the lists that have Trues for the quant and it's negation quant in the same list, then generate a list that would satisfy 2 quants.

Why didn't I think of this sooner?!?!

Since it took me a while to figure all this out, I'm guessing I didn't have a good grasp on logic and utilizing logic yet. This course is meant to teach you about logic and how to apply it and a lot of logic definitely applied in this question. Using logic, you can develop techniques for analyzing these types of questions swiftly. It was a good thing that I ran into these problems and figured out better ways to attack the problems because it really helped me with the actual term-test which had similar questions!



Also, for any TA or Professor reading my posts, I know they're pretty long and I apologize for that. I just like to ramble on and I feel that shorter posts aren't sufficient.

Sorry for making you guys read all this!

A Very Powerful Manipulation Rule

There is one manipulation rule that I feel is not emphasized enough (for me at least) and that is:

P ⇒ Q       ⇔     ¬P ∨ Q

To me, this is one of most powerful manipulation rules that is extremely important to know so I didn't just want to memorize it. I wanted to understand it.

At first, It was kind of hard to wrap my head around the idea that "If P is true, then Q must be true" is the exact same as "P is not true or Q is true." When trying to connect these two statements using English only, it felt kind of hard to visualize, for me at least.

So I ended up working out several different ways to try to grasp this idea logically.

First, I did the truth tables:

P	Q	P ⇒ Q	¬P ∨ Q
T	T	T	T
T	F	F	F
F	T	T	T
F	F	T	T

After I did the truth tables, it was clearly evident that the implication and the logical disjunction statements were identical (according to the truth table). However, in terms of wording and a way of making English sense of it in my head, I was still not fully understanding this. So I continued:

Second, I did the Venn Diagram for both:

For P ⇒ Q : If P is true, then Q must be true, meaning there cannot be anything in the set of P where Q is not true, hence:

(Where P is the antecedent, Q is the consequent, and U is the universe. White is unoccupied)

For ¬P ∨ Q : Everything that is not P can be occupied and all of Q can be occupied, hence:

(Where P and Q are both predicates and U is the universe. White is unoccupied)

After creating the Venn Diagrams for both. It was starting to make a lot more sense. The Venn Diagrams are exactly the same. Since P implies Q means that "If P is true, then Q must be true" which means that there can't be any P's that aren't Q, then that would mean anything that's not P is fine. Also, if it's not P, then it doesn't matter what Q is for the implication as a whole to be true; vacuously. This is making a lot of sense. However, I still wanted to justify this some more!

Finally, I found negating the implication helped finalize my understanding of this manipulation rule:

First, "If P is true, then Q must be true" may be reworded with sets: "Every D that is also a P is also a Q" which would symbolically be:

∀x ∈ D, P(x) ⇒ Q(x)

So, if this was negated, the English would be "There exists a D that is also a P but is not Q." Symbolically:

∃x ∈ D, P(x) ∧ ¬Q(x)

So, I tried to negate the negation, to get back the original implication using De Morgan's Law:

¬(∃x ∈ D, P(x) ∧ ¬Q(x))

∀x ∈ D, ¬(P(x) ∧ ¬Q(x))

∀x ∈ D, (¬P ∨ Q)

Here I stopped and I didn't bother to change the disjunction back to an implication because I now saw that they are truly equivalent. This may have seemed like a roundabout way to get this the implication and disjunction stuck in your head, but this really helped me out! I thought to myself "I think I fully understand this concept now!"

Venn Diagram Madness............

I came across something confusing for CSC165 Tutorial Exercise #1:

Drawing a Venn Diagram that Falsifies statement
d) "There is one of the three python programs that fails all three test suites."

So to falsify the above statement, you'd have to create a Venn Diagram portraying a situation where all python programs pass at least one test suite. If a python program passes at least 1 test suite, then it is not in the set of python programs that "fails all three test suites". Thus all we have to show on the Venn Diagram is that all of the 3 python programs in set Q passes at least one test suite. So technically, the programs can exist anywhere in Q, either in the overlapping Q and T area or just the Q area itself since the Q area itself just represents python programs, not stating how many test suites they pass or fail. So I figured the diagram for this would be:

(**Where Q is the set of 3 python programs, T is the set of universal python programs that pass all 3 test suites, and P is the universe of python programs. Also, O represents area must be occupied, X represents area that must not be occupied, and ? represents area could be empty or occupied.)

However, this diagram does not really say anything definite about making the statement false. For example, since ? represents may be empty or may be occupied, let's say for example that the overlapping T and Q area was empty. Now all the python programs in Q are in the Q only region. In this case, we may have a situation that falsifies the above statement (if all the programs in Q passed at least one test) or we may also have a situation that does not falsify it (any one of the python programs may fail all 3 tests and still be in this region). So this diagram wouldn't be enough to falsify the above claim.

During the tutorial, the Venn Diagram that was presented in answer to d) false situation was:

This Venn Diagram makes sense in that it presents a situation where the statement would be false for sure (if all of the 3 python programs passes all 3 test suites, then there can't be any that failed all 3), but there was just something still bothering me about this diagram. The area in Q may be occupied, not necessarily must not be. This diagram presents one situation where the statement would be false, but not a general diagram showing how to make the statement false. I don't know if I'm conveying myself properly, sorry for the confusion. For example, let's consider the Venn Diagram portraying a False situation for a) "All three python programs that passes all test suites." The correct diagram is:

However, another situation that would make the a) statement False would be this Venn Diagram:

This diagram would show a situation where a) would be False but it wouldn't be the correct most general Venn Diagram.

This is the feeling I'm getting for the tutorial provided Venn Diagram. I feel as if there is another region needed to indicate either programs that passed at least 1 test suite or a region indicating programs that failed all test suite.

The good thing about this experience is that after writing this blog, my head is a lot more clear about this whole situation!

First time SLOGger

Hhhhhmmmmmmmmmmmm. This will be an internet milestone for me. This is not only my first time slogging, it's my first time doing anything related to blogging as well!

This will be interesting!