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. You should also be able to apply past material from this course outside of the context in which it was introduced (see “proofs out of context” below).

This problem set introduces a new feature that I will include in many future problem sets: “proofs out of context.” The idea here is that this course is central to the mathematics major because most later courses expect you to read and write proofs, definitions, and similar things about whatever that later course studies — in other words, to be able to use the material you learned in this course outside of the context in which you learned it. So to get you used to doing that, I will inject problems into many problem sets that apply concepts covered in this course to branches of math not otherwise used as examples in the textbook or lectures. Problem 5 on this problem set is the first example.

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 January 27 and 30, and 2.2 on January 30 and February 1.

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

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

Problem 2

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 3

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 4

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

Problem 5 (Proofs Out Of Context)

Define an alphabet to be any non-empty finite set. If A is an alphabet, then its members are called the symbols of that alphabet.

If A is an alphabet, then a string over A is any finite sequence of symbols from A.

Determine whether the following statement is true or false (but you do not have to write a formal proof): The sequence 1+3 is a string over { 1, 2, 3, - }.

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.