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.