Assignment Task

Questions

1. Consider the following compound proposition

(¬q → ¬p) ∧ ¬(r ∨ q) → ¬p

(a) Work out the truth table for this proposition and explain why your truth table shows that it is a logical implication.

(b) Use the fundamental logical equivalences and implications (Tables 7.6–7.8 in the Unit Notes, or the ‘logic tables’ pdf on the LMS) to prove that it is a logical implication.

2. Express the following argument in symbolic form and test its logical validity by hand. If the argument is invalid, give a counterexample; otherwise, prove its validity using the rules of inference.

3. Decide whether the following quantified propositions are true or false, and justify each of your conclusions with a proof or a counterexample.

(a) ∃n ∈ N : n + 3 < 2n>

(b) ∀z ∈ Z : 3(z + 2) > 3z + 5

(c) ¬(∀x ∈ R : x + 3 ≥ 2x)

4. Use mathematical induction to prove that if (tn) is a sequence defined recursively by.

t1 = 1; tn = tn−1 + 4n − 2, n ≥ 2, then tn = 2n 2 − 1 for all integers n ≥ 1.

5. Use the axioms and fundamental identities of Boolean algebra to simplify the following Boolean [removed]showing all the steps):

x 0 x(y + z)