Before you start:
Download and read a short essay on Good Mathematical Writing and write up your solutions to the following exercises with these guidelines in mind.
1. (Entailment)
a. Prove that follows logically from
b. Which of the following formulae are logically entailed by ?
2. (Logical reasoning)
a. See pages 21–23 of the lecture slides week 2 and answer the two questions.
b. The country of Mew is inhabited by two types of people: liars always lie and "truars" always tell the truth. At a cocktail party the newly appointed Australian ambassador to Mew talked to three inhabitants. Peter remarked that Joan and Shane were liars. Shane denied he was a liar, but Joan said that Shane was indeed a liar. Now the ambassador wondered how many of the three were liars.
Use propositional logic formulae to help the ambassador.
3. (Mathematical proofs)
a. Prove that for all integers .
Hint: Give a proof by cases.
b. Prove that for every odd integer (that is, for every such that ).
4. (Boolean algebra)
Consider a boolean algebra over a set . For each of the following, either prove that the equation is true for all or give a counterexample.
6. Challenge Exercise
Digital circuits are often built only from nand-gates with two inputs and one output. The function nand:
is defined by or, equivalently, . Show that any Boolean
function can be encoded with only nand-gates
