Problem Set 2 — Propositional Logic

Purpose

This problem set develops your ability to reason with propositional logic.

Background

This problem set is based on material in sections 2.1 and 2.2 of our textbook. I plan to discuss section 2.1 in class on January 29, and 2.2 on January 31.

Activity

Solve the following problems. Formal proofs should be word-processed (i.e., not hand-written) and should follow the guidelines in Sundstrom’s text.

Problem 1

An extension of exercise 8b in section 2.1 of our textbook. Assume that the statements (1) “Laura is in the seventh grade,” (2) “Laura got an A on the mathematics test or Sarah got an A on the mathematics test,” and (3) “If Sarah got an A on the mathematics test then Laura is not in the seventh grade” are all true.

Part A

Determine whether the statement “Sarah got an A on the mathematics test” is true or false.

Part B

Problem 2

Exercise 12a in section 2.1 of our textbook (show that ((P→Q) ∧ P) → Q is a tautology).

Problem 3

Exercise 3f in section 2.2 of our textbook (give a negation for “if you graduate from college, then you will get a job or go to graduate school”; see the textbook for additional guidelines).

Problem 4

Exercise 5a from section 2.2 of our textbook (use truth tables to prove that or distributes over and). Write your proof as a formal proof.

Problem 5

Exercise 9c from section 2.2 of our textbook (use previously proven logical equivalences to prove that ¬(P ↔ Q) is equivalent to (P ∧ ¬Q) ∨ (Q ∧ ¬P)). Write the proof as a formal proof.

Follow-Up

I will grade this exercise in a face-to-face meeting with you. During this meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Please bring a written solution to the exercise to your meeting, as that will speed the process along.

Sign up for a meeting via Google calendar. Please make the meeting 15 minutes long, and schedule it to finish before the end of the “Grade By” date above.

I will use the following guidelines to grade this problem set:

• What I expect (8 points). Between your written answers and verbal explanations, I expect you to show that you understand (1) The meanings of the logical connectives, (2) how to use them in symbolic statements, (3) how to reason about statements that use them, (4) how to use truth tables to prove a claim about logic, (5) how to use logical equivalences to prove a claim about logic, and (6) how to write formal mathematical proofs.
• Half of what I expect (4 points). Here some plausible, but not the only, examples of solutions that would meet half my expectations: you fully understand 2 to 4 of the items listed as expected, and don’t understand the others at all, OR you partially understand all 6 items.
• Exceeding expectations (typically 1 point added to what you otherwise earn). One way of exceeding expectations on this problem set specifically would be to use LaTeX rather than some more familiar word processor to write a clear and correctly formatted solution. Plausible but not exclusive examples of more generic things that go beyond what I expect could include particularly clearly written solutions, OR particularly elegant ones, etc.