Solving a Problem with Polya (and why it killed me)

In this second SLog post I will write about a "problem-solving episode" using Polya's method, despite my reservations against using "catch-all" problem solving blueprints. The problem I want to tackle is one presented in the second tutorial handout, problem 1(g). The problem asks:

Let C be a set of courses, and let P(x, y) mean course x is a prerequisite for course y.  Rewrite the following symbolically:

(g) "Some courses have the same prerequisites."

I chose this problem because it presented me with the greatest difficulty in tutorial; I must have spent half the tutorial time thinking about it.

I will start with the first step, according to Polya, which is to understand the problem. Our objective is to rewrite the English statement given in (g) in symbolic notation, using what we have learned in the course so far. The data we are given is that C is a set of all courses and that P(x, y) describes a relation between two courses. The statement in (g) also gives us some more data. "Some courses have the same prerequisites" can be interpreted to mean that at least two different courses share one prerequisite. This immediately tells us that three objects are needed to express (g) in mathematical notation.

Now that we have identified the relevant information, let us assign variables to the objects:

• Let x be one course with at least one prerequisite
• Let y be a second course with at least one prerequisite
• Let z be a course that is a prerequisite of some other course(s)

If we are visual problem solvers, we could also draw a Venn diagram at this point consisting of two interlocking circles contained within a box. The box would represent C, the set of courses, and the two circles would represent the sets "prerequisites of x" and "prerequisites of y," for some x and y. The intersection of the sets contains all the possible values of z that are prerequisites of both x and y. In other words, our solution should be true if and only if the intersection is not empty.

With just these facts in mind, we do not yet have enough information to translate the phrase into notation, so we should move to Step 2 of Polya's problem solving model: Devising a Plan. 

First, we should determine the general structure of our symbolic statement. From previous questions (a) to (f), we know that these statements should always be introduced by quantifiers, either ∀ or ∃. The term "some courses" in (g) immediately tells us that the "courses," x and y, must be existentially quantified because of the use of the word "some." To determine the quantifier used to introduce z, we can think about the nature of the problem. Our final solution will be a statement that is true if and only if there exists some x and some y such that a certain condition is met. This means that the existence of a specific x and a specific y is needed to fulfill the condition, so we use the existential quantifier. However, the truth value of the statement does not depend on the existence of a specific z. The identity of z can be any value in set C, and is only specified if we assign actual values to x and y. Therefore, we must use the universal quantifier ∀ to introduce z.

Now that we know which quantifiers to use for x, y, and z, we must solve the bulk of the problem: how do we represent the condition in (g) using mathematical notation? We know that in order for the courses x and y to have the same prerequisite z, both P(z, x) and P(z, y) must be true. At first, this might lead us to conclude that the condition could be represented as P(z, x) ∧ P(z, y), but this means something different. P(z, x) ∧ P(z, y) would only be true if there exists some x and some y such that all possible values of z are prerequisites of both. This is clearly very different from what we want, and is a mistake I initially made. If we don't want to imply that the statement is true if and only if x and y share every possible prerequisite, we need to use an implication. Using an implication would ensure that our statement is true only so long as at least one possible z is a prerequisite of both y and x. Which direction should the implication go? If the implication went in only one direction [ P(z, x) → P(z, y) ] then there could be the case where z is a prerequisite in the consequent but not in the antecedent. Since the antecedent is false, the implication is true and the statement will be true even if z is an element of only one of the two courses. Therefore, the implication must go both ways; if z is a prerequisite for one course it must also be a prerequisite for the other course for the implication to be true. 

We finally have all the parts we need to construct our mathematical representation of the phrase "Some courses have the same prerequisites." This marks our transition into Part 3 of the Polya model, Carrying Out the Plan. To summarize, here is the plan so far:

1. The statement begins with three quantifying statements, ∃x ∈ C, ∃y ∈ C, ∀z ∈ C
2. The statement makes the double implication that if z is a prerequisite for x, then z is a prerequisite for y and that if z is a prerequisite for y then z is a prerequisite for x. Written as P(z, x) ↔ P(z, y)

The implementation of this plan is simply the combination of the two steps, into the statement:

∃x ∈ C, ∃y ∈ C, ∀z ∈ C, P(z, x) ↔ P(z, y)

To check our solution, we should try using test cases. For example:

If x, y both have a prerequisite z

• P(z, x) is True and P(z, y) is True, P(z, x) ↔ P(z, y) is True.

If x has a prerequisite z but y does not

• P(z, x) is True and P(z, y) is False, P(z, x) ↔ P(z, y) is False.

If y has a prerequisite z but x does not

• P(z, y) is true and P(z, x) is False, P(z, x) ↔ P(z, y) is False. 

Here ends my explanation of how I solved problem 1(g) from last tutorial, organized by Polya's model. However, I have to express some annoyance because only now after I have finished writing my SLog do I realize that I have run into the same problem I did last week. Despite being able to arrive at the solution using Polya's method, I was still rather uncomfortable with the answer. Some part of it didn't seem to make sense to me, and I couldn't figure out why, until I just realized that I had misunderstood the phrasing of the question again. This miscommunication has been the sole root of my frustration for the past 7 hours, and I can only describe my emotional state as "mortified." I had spent so long trying to understand a question I thought was difficult, only to realize that it wasn't complicated, just ambiguous. Again. 

I suppose I could have asked for clarification on the question, but I know at least one other person in my tutorial was confused by this as well, and I am sure there are many others. "Some courses have the same prerequisites" can be taken to mean two very different things, that "Some courses share the exact same prerequisites" or that "Some courses share some of the same prerequisites" depending on how you look at it. For example, if I say that "some people have the same pants" I mean that some people have at least one pair of pants in common, not that they all have the same set of pants in their wardrobe. If I say "some people like the same movies," however, I am much more likely to mean that some people have the exact same taste in movies. 

In closing, English is one of the most unpredictable languages in the world, and it has more exceptions to its rules than any other European language. While I started off writing about a problem I had solved, I am going to end my post with an appeal to the CSC165 teaching team. I like this course, and I know that Danny, the TAs, and the rest of the staff work hard to make sure the students learn as much as they can, but there is absolutely nothing more frustrating in a logic course than finding out that you chose the wrong interpretation of an ambiguously worded question. I hope that in the future greater care can be taken to ensure that each question has only one possible meaning. especially on the graded portions of the course. 

January 16th, 2013 - "Why is my answer wrong?!?!?!"

CSC165 SLog Post - January 16th, 2013

The first week of CSC165 sneaked by quietly. With no assignments (except this one) having been assigned yet, I had been focusing most of my attention on my other courses. However, contrary to my expectations for a course called "Mathematical expression and reasoning", I now find myself enjoying CSC165. I am planning on taking PHL245, Modern Symbolic Logic, next year, and I really think CSC165 will give me an opportunity to acclimatize myself with the mode of thinking required of courses on logic. This course is surprisingly independent of programming languages and I can already see how I can apply the material learned to other facets of my life. Logic and reasoning play very large roles in my decision making process as well as my personality.

I met Maria, my TA, in tutorial on Tuesday. It feels strange to write about someone when you know they will be reading what you wrote in the near future. After we had worked through the tutorial handout and the answers had been put up, I realized that the answer my partner and I had for the last question was the only one that was different than what was on the board. I tried to find where I went wrong but the more I examined the question the more convinced I became that our answer was right. I asked Maria about the question but our initial discussion did not provide me with a satisfactory answer, and I still did not understand why my answer was different. A friendly colleague sitting in front of me tried to explain to me the answer we were given, and after he explained his reasoning I shared mine. In my argument I made use of counterexamples, quantifiers, and sets and I realized that just a week into the course I had already absorbed enough information for me to verbally illustrate my points using what I learned. After we mulled over the question some more, the other student agreed that my answer was right.

Knowing now that I wasn't crazy or just stupid and emboldened by the support of my fellow student, I approached Maria again to continue our discussion. Another student who had apparently reached the same conclusion I had went up as well and together we debated what the answer to the last question was. Eventually, the three of us agreed that the mistake was not in our answers but in the question itself; it was not phrased the right way.

The question asked for a Venn diagram of the False condition of the statement "There is one of the three python programs that fails all three test suites." However, no set was given for programs that "fail all three test suites." This set is not complementary to the set of programs that pass all three test suites (T), since there exist cases where a program does not fail all three but does not pass all three either, passing either one or two of the test suites. Therefore, in the Venn Diagram of the False condition of that statement, Q can be occupied if some program passes 1 or 2 test suites or empty if all three programs pass all three test suites. T can be occupied or unoccupied as well since there may or may not be programs in set P that pass all three tests and are not in Q. The intersection of Q and T can be occupied if there is a program of Q that passes all three tests (is also in T), or unoccupied if all three programs in Q only pass either 1 or 2 tests. Therefore, it is impossible to know whether any of the three regions of this Venn diagram are occupied, and the identity of all three regions should be "?." My conclusion was later verified when Danny sent the class an email with corrections made to the last question.

In the hours after, I thought more about the question and I now believe that the statement the last question had intended to convey is "There is one of the three python programs that does not pass all three test suites." Thanks to the murky ambiguities of the English language, the meaning of "fails all three test suites" is subtly (but importantly) different from "does not pass all three test suites." To "fail all three test suites" requires that the program fail all three of t1, t2, and t3. To "not pass all three test suites" requires that not all of t1, t2, and t3 are passed by the program, i.e. the program fails at least one test suite. If we use this statement for the question instead, the answer does indeed work out to be the one given, [X - O - ?]

The frustrations of lexical miscommunication aside, I rather enjoyed working through why the question didn't match the answer. Figuring out what the question actually meant was much more difficult of a puzzle than the questions given in tutorial. I think my experience working on this problem made me realize one great thing about CSC165: the material it covers and the language it uses leaves absolutely no room for ambiguity and uncertainty when it comes to writing and grading assignments and exams. So long as you understand the question, you already have everything you need to write down the answer; it's just a matter of putting everything in the right place. I can't believe I'm saying this, but I think I'm actually looking forward to our first test.