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.
1 of 2 4/03/2020, 4:58 pm COMP9020 20T1 - Week 2 Problem Set https://cgi.cse.unsw.edu.au/~cs9020/20T1/probs/prob2/index.php
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.
