Logic Problems

[Casual]

I need help with the following logic problems: (Note, I don't simply need an answer. Instead, I need a complete step-by-step solution to each problem accompanied with logical proofs with operators such as AND, OR, IF, IF AND ONLY IF, and so on...) I would greatly appreciate it if you manage to solve any of these. It's a special type of homework I've got and if I manage to get them right I may earn a whole grade up. I would dig into them on my own, but since I've just received it and I have a very short time to get it done I can't manage to... given that I got my midterms the following week. Thanks!

1) George, Mary and Kyle are all students that never lie. When they were asked what grade they got on their last exam they said:
George: If Kyle and I both got 'A's, then Mary also got an 'A'.
Mary: If I got and 'A', then George also got an 'A'.
Kyle: If Mary and I both got 'A's, then George also got an 'A'.
It is known that one of them got a 'B', and the other two got 'A's. What grade did each one of them get?

2) Erica, Stanley and Robert were all witnesses in a car crash. Their statements are contradictory to one another, and all of them claimed that someone else lied. Erica claimed that Stanley lied, Stanley claimed that Robert lied, while Robert claimed that both of them lied. After thinking for a little bit, without any further questions the judged figured out who was telling the truth. Who was telling the truth?

3) A,B,C and D are all on the same canoe team. They don't know what sitting order they should make and all of them have a certain wish.
A: I'd like to sit at the back only if I sit next to B.
B: I don't want to sit next to C and I don't want to sit at the back.
C: If I sit at the back, I don't want to sit next to A.
D: I want to sit next to B or not next to A, and if I can't sit at the front, then I want to sit at the back.

4) 5 students, Oliver, Simon, Peter, Bob and Christie all seniors at Harvard, come from one of the following cities: Oregon, Seattle, Phoenix, Boston and Chicago. In the last semester, everyone picked a different subject and got a different grade. The grades were 10,9,8,7,6 and the subjects were Calculus, Computer Science, Biology, Physics and Spanish. It is known that:

None of the students come from the cities with the same first letter as their names, and there is only one student who's subject starts with the same first letter as his name.
Bob took the Spanish course and got a 7.
The professors that teach the subjects starting with the letter 'C', gave neither the smallest nor biggest grade for their course, but if anyone gave an 8, then it was the Computer Science teacher.
Simon's friend from Oregon got a grade that's greater than Simon's one, by 2 and that grade is a 9 only if Simon took the Physics course.
Peter is taking neither the Biology nor Physics course, and he comes from a city that has exactly one 'o' in its name.
The student from Phoenix took the Computer Science course if and only if the students from Seattle took the Biology course.

Find out the respective cities, subjects and grades for all the students listed.

 

[srmichael]

I need help with the following logic problems: (Note, I don't simply need an answer. Instead, I need a complete step-by-step solution to each problem accompanied with logical proofs with operators such as AND, OR, IF, IF AND ONLY IF, and so on...) I would greatly appreciate it if you manage to solve any of these. It's a special type of homework I've got and if I manage to get them right I may earn a whole grade up. I would dig into them on my own, but since I've just received it and I have a very short time to get it done I can't manage to... given that I got my midterms the following week. Thanks!

1) George, Mary and Kyle are all students that never lie. When they were asked what grade they got on their last exam they said:
George: If Kyle and I both got 'A's, then Mary also got an 'A'.
Mary: If I got and 'A', then George also got an 'A'.
Kyle: If Mary and I both got 'A's, then George also got an 'A'.
It is known that one of them got a 'B', and the other two got 'A's. What grade did each one of them get?

2) Erica, Stanley and Robert were all witnesses in a car crash. Their statements are contradictory to one another, and all of them claimed that someone else lied. Erica claimed that Stanley lied, Stanley claimed that Robert lied, while Robert claimed that both of them lied. After thinking for a little bit, without any further questions the judged figured out who was telling the truth. Who was telling the truth?

3) A,B,C and D are all on the same canoe team. They don't know what sitting order they should make and all of them have a certain wish.
A: I'd like to sit at the back only if I sit next to B.
B: I don't want to sit next to C and I don't want to sit at the back.
C: If I sit at the back, I don't want to sit next to A.
D: I want to sit next to B or not next to A, and if I can't sit at the front, then I want to sit at the back.

4) 5 students, Oliver, Simon, Peter, Bob and Christie all seniors at Harvard, come from one of the following cities: Oregon, Seattle, Phoenix, Boston and Chicago. In the last semester, everyone picked a different subject and got a different grade. The grades were 10,9,8,7,6 and the subjects were Calculus, Computer Science, Biology, Physics and Spanish. It is known that:

None of the students come from the cities with the same first letter as their names, and there is only one student who's subject starts with the same first letter as his name.
Bob took the Spanish course and got a 7.
The professors that teach the subjects starting with the letter 'C', gave neither the smallest nor biggest grade for their course, but if anyone gave an 8, then it was the Computer Science teacher.
Simon's friend from Oregon got a grade that's greater than Simon's one, by 2 and that grade is a 9 only if Simon took the Physics course.
Peter is taking neither the Biology nor Physics course, and he comes from a city that has exactly one 'o' in its name.
The student from Phoenix took the Computer Science course if and only if the students from Seattle took the Biology course.

Find out the respective cities, subjects and grades for all the students listed.

WHOA!! You are bold in your expectations here. We do not simply do your work for you. You need to show some initiative on your part, and then we can help you with areas you are stuck in.

 

[JeffM]

Furthermore, please explain to me the ethics of our doing the work for you to get extra credit?

 

[Casual]

I am terribly sorry, I should have read the posting guidelines. I didn't post any work done because when people ask me for help with an exercise, I'd rather have them give me the exercise and walk them through my solution. But I do see your point, and I agree. So if I were to post these exercises in 4 different threads and show where I've got on my own, would you be able to help then? Or should I just keep this thread open and do the exercises one by one here? I did give it a go at the first two and I think I might just have managed to solve the first one, but I'm not sure how rigorous should I be as far as deducing goes.

 

[JeffM]

I am terribly sorry, I should have read the posting guidelines. I didn't post any work done because when people ask me for help with an exercise, I'd rather have them give me the exercise and walk them through my solution. But I do see your point, and I agree. So if I were to post these exercises in 4 different threads and show where I've got on my own, would you be able to help then? Or should I just keep this thread open and do the exercises one by one here? I did give it a go at the first two and I think I might just have managed to solve the first one, but I'm not sure how rigorous should I be as far as deducing goes.

Maybe we should treat this as your posting for help on problem 1, and start new threads for the later problems. It will not be too burdensome because you can simply copy them from here. The problem is that the thread becomes VERY confusing when people are talking about different questions.

Why don't you show how you analyzed the first exercise, and then someone can comment on whether that is a rigorous enough presentation. If you are taking a course in symbolic logic, the degree of rigor may be different than it would be in some other course. So you will need to say what course you are taking.

 

[Casual]

Alright, then that's what I'll do. I am taking a course in Discrete Mathematics, I am a Computer Science major.

1) George, Mary and Kyle are all students that never lie. When they were asked what grade they got on their last exam they said:
George: If Kyle and I both got 'A's, then Mary also got an 'A'.
Mary: If I got and 'A', then George also got an 'A'.
Kyle: If Mary and I both got 'A's, then George also got an 'A'.
It is known that one of them got a 'B', and the other two got 'A's. What grade did each one of them get?

So here's my take:

p:George got an 'A'.
q:Mary got an 'A'.
s:Kyle got an 'A'.

1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
These three are considered true, because they are part of the condition stated. For the next statements, I will do transformations of these into logical equivalences or I will make deductions based on rules of logic.
4. ⌉q ->⌉(p ^ s) reverse implication of 3
5. ⌉q ->⌉p v ⌉s use of De Morgan's laws on 4
6. ⌉q -> ⌉p simplification of 5
7. ⌉q -> ⌉s simplification of 5
8. p -> q reverse implication on 6
9. p <-> q addition of 2 and 8
Can I deduce from here that because p and q have the same truth value, and it is specified that 2 students have 'A's(therefore two statements have the same truth value), that George and Mary have 'A's and Kyle has a 'B'? If not, can you please give me a tip in which direction to go as far as proving ⌉s goes? I was thinking of trying to add a 4th condition in the form of (p^q^⌉s) v (p^s^⌉q) v (q^s^⌉p), but I'm afraid it will just complicate things.

 

[JeffM]

Alright, then that's what I'll do. I am taking a course in Discrete Mathematics, I am a Computer Science major.

1) George, Mary and Kyle are all students that never lie. When they were asked what grade they got on their last exam they said:
George: If Kyle and I both got 'A's, then Mary also got an 'A'.
Mary: If I got and 'A', then George also got an 'A'.
Kyle: If Mary and I both got 'A's, then George also got an 'A'.
It is known that one of them got a 'B', and the other two got 'A's. What grade did each one of them get?

So here's my take:

p:George got an 'A'.
q:Mary got an 'A'.
s:Kyle got an 'A'.

1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
These three are considered true, because they are part of the condition stated. For the next statements, I will do transformations of these into logical equivalences or I will make deductions based on rules of logic.
4. ⌉q ->⌉(p ^ s) reverse implication of 3
5. ⌉q ->⌉p v ⌉s use of De Morgan's laws on 4
6. ⌉q -> ⌉p simplification of 5
7. ⌉q -> ⌉s simplification of 5
8. p -> q reverse implication on 6
9. p <-> q addition of 2 and 8
Can I deduce from here that because p and q have the same truth value, and it is specified that 2 students have 'A's(therefore two statements have the same truth value), that George and Mary have 'A's and Kyle has a 'B'? If not, can you please give me a tip in which direction to go as far as proving ⌉s goes? I was thinking of trying to add a 4th condition in the form of (p^q^⌉s) v (p^s^⌉q) v (q^s^⌉p), but I'm afraid it will just complicate things.

The 4th condition is given as true so you certainly may add it. The question is whether you must.

Steps 6 and 7 are not valid. One of them must be true, but it is false that both must be true.

Let's see why

[5 In English] Mary did not get an A implies that either George did not get an A or Kyle did not get an A or both failed to get an A.

[6 in English] So Mary did not get an A implies that George did not get an A. But that does not follow.

You do need the fourth condition.

But you were on the right track.

If George does not get an A, then, by the fourth condition, Kyle and Mary both get A's. So if George does not get an A, Mary does, which means that George does by condition 2. Contradiction.

So George gets an A. Can you finish it?

 

[Casual]

Case one.
1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
4.⌉p ^ s ^ q
5. ⌉p - simplification of 4.
6. q - simplification of 4
7. ⌉q - Modus Tolens of 2 and 5
8. q and ⌉q - Contradiction.

Case two.
1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
4.p ^ s ^ ⌉q
5. p ^ s - simplification of 4
6. ⌉q - simplification of 4
7. q - Modus Ponens of 1 and 5
8. q and ⌉q - Contraction.

Case 3.
1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
4.p ^ ⌉s ^ q
5.p simplification of 4.
6.⌉s simplification of 4.
7.q simplification of 4.

Is this it? Or do I need to somehow prove case 3? I think elimination of 1 and 2 should be enough...

 

[JeffM]

Case one.
1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
4.⌉p ^ s ^ q
5. ⌉p - simplification of 4.
6. q - simplification of 4
7. ⌉q - Modus Tolens of 2 and 5
8. q and ⌉q - Contradiction.

Case two.
1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
4.p ^ s ^ ⌉q
5. p ^ s - simplification of 4
6. ⌉q - simplification of 4
7. q - Modus Ponens of 1 and 5
8. q and ⌉q - Contraction.

Case 3.
1.(p ^ s) -> q
2. q->p
3.(q ^ s) -> p
4.p ^ ⌉s ^ q
5.p simplification of 4.
6.⌉s simplification of 4.
7.q simplification of 4.

Is this it? Or do I need to somehow prove case 3? I think elimination of 1 and 2 should be enough...

Your logic looks good to me through case 1. I did not review it further. However, if there are only three possible cases and you eliminate two, then the third case must be the correct one.

I am very out of date and rusty on the formalities of presentation of this branch of mathematics so I ask you to consider these as tentative suggestions. In your previous post, you explicitly wrote out a fourth given. You do not do so here, but it is implicit. I think you need to give it and all other givens before you start doing cases. Technically, your cases are conditionals that are justified by what you previously called condition 4. To keep the resulting proofs concise, I also suggest defining more terms. Here is how I would show your work through case 1.

Definitions

\(\displaystyle p = \text{George got an A.}\)

\(\displaystyle q = \text{Mary got an A.}\)

\(\displaystyle s = \text{Kyle got an A.}\) What happened to r?

\(\displaystyle x = \text{George and Mary each got an A, but Kyle got a B.}\)

\(\displaystyle y = \text{Kyle and Mary each got an A, but George got a B.}\)

\(\displaystyle z = \text{George and Kyle each got an A, but Mary got a B.}\)

Givens

\(\displaystyle [1]\ (p + s) \implies q.\)

\(\displaystyle [2]\ q \implies p.\)

\(\displaystyle [3]\ (q + s) \implies p.\)

\(\displaystyle [4]\ x\ or\ y\ or\ z.\)

\(\displaystyle [5]\ x = (p + q + \neg s).\)

\(\displaystyle [6]\ y = (\neg p + q + s).\)

\(\displaystyle [7]\ z =(p + \neg q + s).\)

Do you see where the last three givens come from?

Solution

\(\displaystyle [8]\ y \implies q.\) Simplification

\(\displaystyle [9]\ y \implies \neg p.\) Simplification

\(\displaystyle [10]\ y \implies \neg q.\) Modus Tollens on 2.

\(\displaystyle [11]\ y \implies q + \neg q.\) Combining 8 and 10.

\(\displaystyle [12]\ \neg y.\) Contradiction in 11.

\(\displaystyle [13]\ \{\neg y + (x\ or\ y\ or\ z)\} = (x\ or\ z).\) Simplification.

This is how I would show your work up through case 1, but, as I said, I am not the best person to talk to about presentation.

 

[Casual]

Ok, I understand. This way I'll have everything I need in a single sequence and therefore it would be more valid. Thanks a lot JeffM, you've been a lifesaver. I'll open up a new thread for the remaining three exercises as soon as I find the time to get at least some work done on my own.