Department of Mathematics

MATHS 315 Assignment 1

Due: August 3, 2pm, online

1. [Marks: 4]

Find truth tables for the following statement forms, and say whether the statement form is a tautology, is a contradiction or is contingent. (If you make a truth table, order rows as in the slides. In the first row assign 0 to all variables. Then proceed lexicographically, such as in 00, 01, 10, 11.)

(a) (((p → q) ∧ (¬p → q)) → q).

(b) (((p → q) ∧ (q → ¬p)) → (p → ¬r)).

2. [Marks: 4]

Consider the modified system of logical equivalences where the second implication law is removed from the list of logical laws.

Is the modified system still sound? Is it still adequate?

3. [Marks: 4]

Determine whether or not the argument form

r,(p ∨ (¬q ∨ ¬r)) ∴ (q → p)

is valid. Don’t draw a truth table please. Rather, use Theorem 1.15.

4. [Marks: 2]

Write the statement form in disjunctive normal form that is eqivalent to (p0 → p1). (Make sure your string really is a statement form according to our definitions, and it meets the specifications for DNF given on page 11.)

5. [Marks: 2]

Write the statement form in DNF representing the parity function f for the sum of three bits: f(t1, t2, t3) = t1 +t2 +t3 mod 2. (Again make sure your string really is a statement form according to our definitions, and it meets the specifications for DNF given on page 11. E.g., you can’t write things like (p1 ∧ p2 ∧ p3). However, you can use shorthand such as .)