[SOLVED] COMP9020 Week 2-Logic, Proofs, Boolean Algebra

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)
   1. Prove that follows logically from
   2. Which of the following formulae are logically entailed by ?
2. (Logical reasoning)
   1. See pages 21–23 of the lecture slides week 2 and answer the two questions.
   2. 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)
   1. Prove that for all integers .

Hint: Give a proof by cases.

1. 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.