Problem Set 3—Propositional Logic

Purpose

This problem set develops your ability to reason with propositional logic. In particular, by the time you finish this problem set you should be able to create truth tables for compound statements, use truth tables to show that statements are equivalent, use algebraic properties of connectives to show that statements are equivalent, and write formal proofs of the equivalence of statements.

Background

This problem set is based on material in sections 2.1 and 2.2 of our textbook. We discussed section 2.1 in class on September 12 and 2.2 on September 14 (and possibly 16).

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

Progress Check 2.3 in section 2.1 of our textbook (construct a truth table for P ↔ Q).

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. 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.