Problem Set 3 — Propositional Logic

Purpose

This problem set develops your ability to work with propositional logic (i.e., the logic of statements and connectives) and to prove conjectures about it. The problem set thus addresses the following learning outcomes:

• Outcome 1.1, prove equivalence of statements involving Boolean connectives
• Outcome 5.1, recognize claims amenable to proof using definitions and algebraic or other relationships pertinent to the subject of the claim, and construct the corresponding proofs
• Outcome 7, write solutions to problems and proofs of theorems that meet rigorous standards based on content, organization and coherence, argument and support, and style and mechanics.

Background

This exercise is mainly based on sections 2.1 and 2.2 of our textbook. We discussed that material in classes between February 15 and 19.

This exercise also expects you to devise and write formal proofs, as discussed in section 1.2 of the textbook and classes on February 10 and 12.

Activity

Answer the following questions. Any formal proofs should be typed according to the usual mathematical conventions, including typeface rules (e.g., italic variable names, emphasized labels for theorems and proofs, etc.)

Question 1

(An extension of exercise 8a 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 “Laura got an A on the mathematics test” is true or false. You do not have to write a formal proof.

Part B

Letting $G$ stand for “Laura is in the seventh grade,” $L$ stand for “Laura got an A on the mathematics test,” and $S$ stand for “Sarah got an A on the mathematics test,” rewrite the 3-part assumption given to you in the introduction to this question as a single logical expression involving $G$, $L$, and $S$ and various logical connectives (with parentheses as needed). Beware that I want a single expression, not three separate ones.

Question 2

Assuming that $P$ and $Q$ are mathematical statements, give a truth table for $(P\to Q)\wedge (P\to \mathrm{\neg }Q)$.

Question 3

Use Boolean algebra (i.e., other known equivalencies) to prove that if $P$ and $Q$ are mathematical statements, then $P\to Q\equiv \mathrm{\neg }Q\to \mathrm{\neg }P$. Write your proof as a formal proof.

Question 4

(Exercise 8 in section 2.2 of our textbook.) Given that $P$ and $Q$ are statements, determine whether $(P\vee Q)\wedge \mathrm{\neg }(P\wedge Q)$ is logically equivalent to $(P\wedge \mathrm{\neg }Q)\vee (Q\wedge \mathrm{\neg }P)$. Show why your answer is correct, but you don’t have to do it as a formal proof.

Follow-Up

I will grade this exercise during one of your weekly individual meetings with me. That meeting should happen on or before the “Grade By” date above. During the meeting I will look at your solution, ask you any questions I have about it, answer questions you have, etc. Sign up for the meeting via Google calendar. Please have a written solution to the exercise ready to share with me during your meeting, as that will speed the process along.