2024-04-26
24T1
00

目录

Part 1
1.1
1.2
1.3
Part 2
2.1
2.2
Part 3
3.1
3.2
3.3
Part 4
4.1
4.2

COMP9020 – Foundations of Computer Science

FINAL Exam – Term 3 2022

From Question 1 to Question 4

With my own solution (might be incorrect)

Part 1

It seems that I can't prove this question perfectly.

It is confusing.

1.1

Question

Prove that for all m,n,pNm,n,p ∈ ℕ :

If lcm(m,p)=lcm(n,p)lcm(m,p) = lcm(n,p), then lcm(m+n,p)lcm(n,p)lcm(m+n,p) \le lcm(n,p).

I can't prove it because I think it is incorrect. lcm(m+n,p)lcm(m+n,p) should greater or equal lcm(n,p)lcm(n,p).

The counter example is in Part 1.2

1.2

Question

Find a counter example to show that it is not the case that for all m,n,pNm,n,p ∈ ℕ :

If lcm(m,p)=lcm(n,p)lcm(m,p) = lcm(n,p), then lcm(m+n,p)=lcm(n,p)lcm(m+n,p) = lcm(n,p).

Assum:

  • m=1m = 1
  • n=4n = 4
  • p=8p = 8

Then:

  • lcm(m,p)=8lcm(m,p) = 8
  • lcm(n,p)=8lcm(n,p) = 8
  • lcm(m+n,p)=40lcm(m+n,p) = 40

Therefore:

lcm(m+n,p)lcm(n,p)lcm(m+n, p) \ne lcm(n,p)

1.3

Question

Prove that for all m,n,pNm,n,p ∈ ℕ :

If lcm(m,p)=lcm(n,p)lcm(m,p) = lcm(n,p), then lcm(m+n,p)lcm(n,p)lcm(m+n,p) | lcm(n,p).

Part 2

2.1

Question

Prove, or find a counter example to disprove, for all sets A, B, C:

A(B\C)C=(AC)(ABC)A \cap (B \backslash C)^C=(A \cap C) \cap (A \cap B^C)

Definition of \: A\B=ABcA\backslash B = A∩Bᶜ:

A(B\C)C=A(BCC)CA \cap (B \backslash C)^C = A \cap (B \cap C^C)^C

De Morgan's, C over ∩: (AB)C=ACBC(A∩B)^C = A^C \cap B^C:

A(BCC)C=A(BCC)A \cap (B \cap C^C)^C = A \cap (B^C \cup C)

Distributivity of ∩ over ∪: A(BC)=(AB)(AC)A∩(B∪C) = (A∩B)∪(A∩C):

A(BCC)=(ABC)(AC)A \cap (B^C \cup C) = (A \cap B^C) \cup (A \cap C)

Therefore, it is incorrect.

2.2

Question

Let Σ = {0,1}.

Prove, or find a counter example to disprove that for all X,Y ⊆ Σ*:

(XY)(XY)(X^*Y)^* \subseteq (X \cup Y)^*

Assum:

(XY)=w1w2...wi(X^*Y)^* = w_1w_2...w_i

Every element wi=xi1xi2...xikyiw_i = x_{i1}x_{i2}...x_{ik}y_i

and it could also be that:

xi1xi2...xikyi=(xi)(yi)(XY)x_{i1}x_{i2}...x_{ik}y_i = (x_i \cup \empty)^* \cup (\empty \cup y_i) \subseteq (X \cup Y)^*

Therefore, we could find that every element wiw_i in string (XY)(X^*Y)^* could be restructed by (XY)(X \cup Y)^*.

Proved:

(XY)(XY)(X^*Y)^* \subseteq (X \cup Y)^*

Part 3

Let F denote the set of all well-formed formulas. Define the relation RF×FR ⊆ F×F as follows:

(φ,ψ)R if and only if (φψ) is satisfiable(\varphi, \psi) \in \mathbb{R} \text{ if and only if } (\varphi \rightarrow \psi) \text{ is satisfiable}

3.1

Question

Prove that for all φ,ψF\varphi, \psi \in F,

If φψ\varphi \models \psi then (φ,ψ)R(\varphi, \psi) \in R.

Because φψ\varphi \models \psi, when φ\varphi is true, the ψ\psi is true.

φψ=¬φψ\varphi \rightarrow \psi = \neg \varphi \lor \psi

When φ=true\varphi = true, ¬φψ=true\neg \varphi \lor \psi = true.

When φ=false\varphi = false, ¬φψ=true\neg \varphi \lor \psi = true.

Because φψ\varphi \rightarrow \psi could be truetrue, it means that φψ\varphi \rightarrow \psi is satisfiable.

Therefore, (φ,ψ)R(\varphi, \psi) \in R.

3.2

Question

Prove or disprove:

R is reflexive

You may use the result of part (a) [without proof] if it helps

If we want to prove that R is reflexive, we should prove that for every element φF\varphi \in F, (φ,φ)R(\varphi, \varphi) \in R.

It is easy to find that:

When φ\varphi is truetrue, φ\varphi is truetrue.

It means that:

φφ\varphi \models \varphi

According to the result of part (a), if φφ\varphi \models \varphi then (φ,φ)R(\varphi, \varphi) \in R.

Therefore, we could prove that R is reflexive.

3.3

Question

Prove or disprove:

R is transitive

You may use the result of part (a) [without proof] if it helps

Assum:

  • XYX \models Y
  • YZY \models Z

According to the result of part (a), we could find that:

(X,Y)R(Y,Z)R(X,Y) \in R \\ (Y,Z) \in R

Because XYX \models Y, YmodelsZY models Z, when X=trueX = true, we could find that Y=trueY = true and Z=trueZ = true.

Therefore, we could find that XZX \models Z.

According to the result of part (a), we could find that:

(X,Z)R(X,Z) \in R

Because:

(X,Y)R(Y,Z)R(X,Z)R(X,Y) \in R \\ (Y,Z) \in R \\ (X,Z) \in R

We could prove that R is transitive.

Part 4

4.1

Question

Arrange the following functions in increasing order of asymptotic complexity (i.e. if f ∈ O(g) then f appears before g in the list

(For recursively defined functions, assume T(0) = T(1) = 1).

  • T(n)=T(n/2)+log(n)T(n) = T(n/2) + log(n)
  • T(n)=4T(n/4)+4nT(n) = 4T(n/4) + 4n
  • T(n)=T(n2)+2nT(n) = T(n - 2) + 2n
  • T(n)=T(n/3)+3nT(n) = T(n/3) + \sqrt{3n}
  • n2+2n13\sqrt[3]{n^2+2n-1}
  • 100n+n100\frac{100}{n}+\frac{n}{100}
  • T(n)=T(n/2)+log(n)T(n) = T(n/2) + log(n)

    Use Main Theorem, we could find that:

    a=1b=2f(n)=log(n)nlogba=nlog21=n0=1a = 1 \\ b = 2 \\ f(n) = log(n) \\ n^{log_ba} = n^{log_21} = n^0 = 1

    Because f(n)=O(log(n))=O(nlog21log1(n))f(n) = O(log(n)) = O(n^{log_21}log^1(n)), we could prove that:

    T(n)=O(nlog21log1+1(n))=O(log2(n))T(n) = O(n^{log_21}log^{1+1}(n)) = O(log^2(n)).

  • T(n)=4T(n/4)+4nT(n) = 4T(n/4) + 4n

    Use Main Theorem, we could find that:

    a=4b=4f(n)=4nnlogba=nlog44=n1=na = 4 \\ b = 4 \\ f(n) = 4n \\ n^{log_ba} = n^{log_44} = n^1 = n

    Because f(n)=4n=O(n)=O(nlogbalog0(n))f(n) = 4n = O(n) = O(n^{log_ba}log^0(n)), we could prove that:

    T(n)=O(nlogbalog0+1(n))=O(nlog(n))T(n) = O(n^{log_ba}log^{0+1}(n)) = O(nlog(n)).

  • T(n)=T(n2)+2nT(n) = T(n - 2) + 2n

    Every time the nn decrease by 2. Therefore, the recursion time is n/2n/2.

    Every recursion we have to execute 2n2n times.

    Therefore, T(n)=n2×2n=O(n2)T(n) = \frac{n}{2} \times 2n = O(n^2).

  • T(n)=T(n/3)+3nT(n) = T(n/3) + \sqrt{3n}

    Use Main Theorem, we could find that:

    a=1b=3f(n)=3nnlogba=nlog31=n0=1a = 1 \\ b = 3 \\ f(n) = \sqrt{3n} \\ n^{log_ba} = n^{log_31} = n^0 = 1

    Use Main Theorem Case 3, we could prove that:

    T(n)=O(n0.5)T(n) = O(n^{0.5}).

  • n2+2n13\sqrt[3]{n^2+2n-1}

    We could find that:n2+2n13=O(n2/3)\sqrt[3]{n^2+2n-1} = O(n^{2/3})

  • 100n+n100\frac{100}{n}+\frac{n}{100}

    We could find that: 100n+n100=O(n+1/n)=O(n)\frac{100}{n}+\frac{n}{100}= O(n + 1/n) = O(n)

This is the list of functions:

  1. O(log2(n))O(log^2(n)): T(n)=T(n/2)+log(n)T(n) = T(n/2) + log(n)
  2. O(n1/2)O(n^{1/2}): T(n)=T(n/3)+3nT(n) = T(n/3) + \sqrt{3n}
  3. O(n2/3)O(n^{2/3}): n2+2n13\sqrt[3]{n^2+2n-1}
  4. O(n)O(n): 100n+n100\frac{100}{n}+\frac{n}{100}
  5. O(nlogn)O(nlogn): T(n)=4T(n/4)+4nT(n) = 4T(n/4) + 4n
  6. O(n2)O(n^2): T(n)=T(n2)+2nT(n) = T(n - 2) + 2n

4.2

Question

Consider the function f:ℕ→ℕ defined as:

f(n)=3n+2 (if n is even)f(n)=n2 (if n is odd)f(n) = 3n + 2 \text{ (if n is even)} \\ f(n) = n^2 \text{ (if n is odd)}

Which of the following properties does f satisfy?

Select all that apply:

  • f∘f (n) = (f(n))² for all n
  • f(n) ∈ O(n²)
  • f is injective
  • f(n) ≤ f(n+2) for all n
  • f is surjective
  • f(n) ≤ f(n+1) for all n
  • f(n) ∈ O(n)

Correct:

  • f(n) ∈ O(n²)
  • f is injective
  • f(n) ≤ f(n+2) for all n

本文作者:Jeff Wu

本文链接:

版权声明:本博客所有文章除特别声明外,均采用 BY-NC-SA 许可协议。转载请注明出处!