Due: 14th of October 2018 at 11:59pm
COMP 9020 – Assignment 3
Note: In your assignment, how you arrived at your solution is as important (if not more so) than the solution itself and will be assessed accordingly. There may be more than one way to find a solution, and your approach should contain enough detail to justify its correctness. Lecture content can be assumed to be common knowledge.
1. Let (T, ∧, ∨,j , 0, 1) be a Boolean Algebra.
Define ∗ : T × T → T and ◦ : T × T → T as follows:
x ∗ y := (x ∨ y)j x ◦ y := (x ∧ y)j
(a) Show, using the laws of Boolean Algebra, how to define x ∗ y using only x, y, ◦ and parentheses.
(b) Show, using the laws of Boolean Algebra, how to define x ◦ y using only x, y, ∗ and parentheses.
(10 marks)
Define R ⊆ T × T as follows:
(x, y) ∈ R if, and only if, (x ∧ y) ∨ (xj ∧ yj) = 1
(c) Show, using the laws of Boolean Algebra, that R is an equivalence relation. Hint: You may want to use the observation that if A = B = 1 then A ∧ B ∧ C = A ∧ B implies C = 1 (why?)
(10 marks)
2. 
Let P F denote the set of well-formed propositional formulas made up of propositional variables, , , and the connectives , , and . Recall from Quiz 7 the definitions of dual and flip as functions from P F to P F :
• dual(p) = p • flip(p) = ¬p
• dual(T) = ⊥; dual(⊥) = T • flip(T) = T; flip(⊥) = ⊥
• dual(¬ϕ) = ¬dual(ϕ) • flip(¬ϕ) = ¬flip(ϕ)
• dual(ϕ ∧ ψ) = dual(ϕ) ∨ dual(ψ) • flip(ϕ ∧ ψ) = flip(ϕ) ∧ flip(ψ)
• dual(ϕ ∨ ψ) = dual(ϕ) ∧ dual(ψ) • flip(ϕ ∨ ψ) = flip(ϕ) ∨ flip(ψ)
(a) For the formula ϕ = p ∨ (q ∧ ¬r):
(i) What is dual(ϕ)?
(ii) What is flip(ϕ)?
(b) Prove that for all ϕ ∈ P F : flip(ϕ) is logically equivalent to ¬dual(ϕ).
(10 marks)
3. Let P (n) be the proposition that: for all k, with 1 ≤ k ≤ n,
.nΣ = .n − 1Σ + .n − 1Σ.
k k − 1 k
(a) Prove that P (n) holds for all n 1. (Note: it is possible to do this without using induction)
(10 marks)
We can compute n from the formula given in lectures, however this can often require computing unnecessarily large numbers. For example,
100 = 253338471349988640 which can be expressed as a 64-bit integer,
but 100! is larger than a 512-bit integer. We can, however, make use of the equation above to compute n more efficiently. Here are two algorithms
for doing this:
chooseRec(n, k) : chooseIter(n, k) :
if k = 0 or k = n : return 1 Let C be a n n array else : for m = 1 to n :
x := chooseRec(n 1, k 1) C[m][0]=C[m][m]=1
y := chooseRec(n 1, k) for j = 1 to m 1 :
return x + y C[m][j]=C[m 1][j 1]
+ C[m 1][j]
return C[n][k]
Let trec(n, k) be the running time for chooseRec(n, k), and let titer(n) be the running time for chooseIter(n, k). Let Trec(n) = max0≤k≤n trec(n, k) and Titer(n) = max0≤k≤n titer(n, k) (so Trec(n) ≥ trec(n, k) for all k, and likewise for Titer(n)).
(b) Give an asymptotic upper bound for Trec(n). Justify your answer.
(c) Give an asymptotic upper bound for Titer(n). Justify your answer.
(10 marks)
Advice on how to do the assignment
All submitted work must be done individually without consulting someone else’s solutions in accordance with the University’s “Academic Dishonesty and Pla- giarism” policies.
Assignments are to be submitted via WebCMS (or give) as a single pdf (max size 2Mb). In Linux, the following command
pdfjoin –outfile output.pdf input1.pdf input2.pdf …
can be used to combine multiple pdf files. The command
convert -density 150×150 -compress jpeg input.pdf output.pdf
can be used to reduce the filesize of a pdf (change 150 to reduce/improve quality/filesize). Please ensure your files are legible before submitting.
Be careful with giving multiple or alternative answers. If you give multiple answers, then we will give you marks only for ”your worst answer”, as this indicates how well you understood the question.
Some of the questions are very easy (with the help of the lecture notes or book). You can use the material presented in the lecture or book (without proving it). You do not need to write more than necessary (see comment above).
When giving answers to questions, we always would like you to prove/exp- lain/motivate your answers.
If you use further resources (books, scientific papers, the internet,…) to formulate your answers, then add references to your sources.
