Computer Science 260
Assignment 1
Please submit your assignment electronically via moodle. Submissions will be accepted in
either plain text (.txt) or PDF. Clearly define all non-standard symbols used. For example,
if you use & in place of ∧, you must clearly state this in your assignment.
1. Use a truth table to show that (p → q) ↔ (p ∧ ∼q) is a contradiction. Include a column
for each distinct substatement form . State in a sentence why the use of the truth table
allows you to say that the expression is contradiction.
2. Give a formal proof that one can conclude b given the premise (a → b)∧((∼d ∨ a)∧ d).
Use the rules of equivalence from Thm 2.1.1 of the text, or the rules of inference in table
2.3.1 of the text. At each step state the law used and the previous lines referred to.
3. Give a formal proof that one can conclude d, given the three premises ∼ a, b, and
b → (a ∨ d) Use the rules of equivalence from Thm 2.1.1 of the text, or the rules of
inference in table 2.3.1 of the text. For each step of the proof, give the reason for the step
and the numbers of any previous steps referred to.
