[SOLVED] COMP9020-Set 2 Logic, Proofs and Boolean Algebra

Description

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.