COT 3100 Sect. #7094X
Homework Assignment #1
Propositional Logic
Assigned Mon. 8/23, Due in class Mon. 8/30

For now, we are experimenting with a collaborative homework policy for this section. This is subject to alteration for later assignments, depending on how students like it, and how well it functions. The experimental policy is this:

If you wish, you may collaborate with a small number of other students, to help each other with the assignment and compare solutions. However, if you do this, each group of students that collaborate with each other must turn in just one shared assignment, for a shared grade. (All students in the collaborating group, and which problems each of them worked on, must be named on the group's handed-in joint assignment.) Your group may either work together on all the problems, or divide up the problems amongst yourselves, but you should make sure that everyone in your group understands how to do the solutions to all the problems, because any member of the group may be called on in class to explain the answer to any problem. (And you will all separately be responsible for all the material on quizzes and exams.)

Exercises from §1.1, pp. 11-14.

• Ex. 2 - Identify propositions & their truth values.
• Exs. 6, 8 - Translate statements between propositional logic & English.
• Ex. 14 - Creatively solve a simple logic puzzle.
• Ex. 20 - Generate the converse & contrapositive of implications.
• Exs. 22, 24 - Construct truth tables for compound propositions.
• Ex. 28 - Apply propositions in program IF statements.
• Ex. 30 - Apply propositions in bitwise operations on bit-strings.
• Ex. 36 - Consistency of sets of propositions.
• Ex. 38 - Apply propositions in text searches.
• Ex. 40 - Apply propositional logic to solve a more complex logic puzzle. (Hint: Draw the chains of implications that follow from the information given.)

  Exercises from §1.2, pp. 19-20.

• Exs. 4, 6 - Use truth tables to prove propositional equivalences.
• Ex. 8 - Prove tautologies using truth tables.
• Ex. 10 - Prove tautologies using symbolic derivation.
• Ex. 12 - Determine whether a proposition is a tautology.
• Exs. 14, 16, 18 - Prove propositional equivalences.

For extra credit (up to a maximum grade of 100%), you may also do any other even-numbered exercises in sections 1.1 or 1.2 (each counts 1 point). Once you understand the basic concepts, if you find that the above-listed exercises are starting to seem more like busy-work than useful practice, you might find some of these alternative exercises to be more interesting or challenging.