Boolean Algebra代写 assignment代写 equivalence relation代写

COMP9020 Assignment 3 2019 Term 3

Boolean Algebra代写 Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should be typed, not handwritten.

Due: Sunday, 24th November, 23:59

Submission is through WebCMS/give and should be a single pdf file, maximum size 2Mb. Prose should be typed, not handwritten. Use of LATEX is encouraged, but not required.Boolean Algebra代写

Discussion of assignment material with others is permitted, but the work submitted must be your own in line with the University’s plagiarism policy.

Problem 1 (40 marks) Boolean Algebra代写

For this question, let F denote the set of well-formed formulas over a set Prop of propositional variables.

• Showthat the logical equivalence relation, ≡, is an equivalence relation on F. (12 marks)
• List four elements in [⊥], the equivalence classof ⊥. (4 marks)
• For all ϕ, ϕ^j, ψ, ψ^j∈ F with ϕ ≡ ϕ^j and ψ ≡ ψ^j; show that:
  • ¬ϕ≡ ¬ϕ^j (4 marks)
  • ϕ∧ ψ ≡ ϕ^j ∧ ψ^j (4 marks)Boolean Algebra代写
  • ϕ∨ ψ ≡ ϕ^j ∨ ψ^j (4 marks)

Let us define F_≡ to be the set of equivalence classes of F under ≡. That is,

F_≡ := {[ϕ] :  ϕ ∈ F}.

Part (c) above shows that the following operations are well-defined1 on F_≡:

• [ϕ]∧ [ψ] defined to be [ϕ ∧ ψ]Boolean Algebra代写
• [ϕ]∨ [ψ] defined to be [ϕ ∨ ψ]
• [ϕ]j defined to be[¬ϕ]
• Show that F_≡together with the operations defined above forms a Boolean Algebra. Note: you  will have to give a suitable definition of a zero element and a one element in F_≡. (12 marks)Boolean Algebra代写

1well-defined means that the output is not dependent on different representations of the same input.

Problem 2 (10 marks)

This is the Petersen graph:

(a)Givean argument to show that the Petersen graph does not contain a subdivision of K₅. (5 marks)Boolean Algebra代写

(b)Show that the Petersen graph contains a subdivisionof K_3,3. (5 marks)

Problem 3 (10 marks)Boolean Algebra代写

Harry would like to take each of the following subjects: Defence against the Dark Arts; Potions; Herbology; Transfiguration; and Charms. Unfortunately some of the classes clash, meaning Harry cannot take them both. The list of clashes are:

• Defenceagainst the Dark Arts clashes with Potions and Charms
• Potions also clashes with Herbology
• Herbology also clashes with Transfiguration,and
• Transfiguration also clashes with Charms.

Harry would like to know the maximum number of classes he can take.

(a)Model this as a graph problem. Rememberto:

(i)Clearlydefine the vertices and edges of your  (4 marks)

(ii)State the associated graph problem that you need to  (2 marks)Boolean Algebra代写

(b)Givethe solution to the graph problem corresponding to this scenario; and solve Harry’s problem.(4 marks)

Problem 4 (22 marks) Boolean Algebra代写

Recall from Assignment 2 the definition of a binary tree data structure: either an empty tree, or a node with two children that are trees.

Let T(n) denote the number of binary trees with n nodes. For example T(3) = 5 because there are five binary trees with three nodes:

(a)Using the recursive definition of a binary tree structure, or otherwise, derive a recurrence equation for T(n).

A full binary tree is a non-empty binary tree where every node has either two non-empty children (i.e. is  a fully-internal node) or two empty children (i.e. is a leaf).

(b)Using observations from Assignment 2, or otherwise, explain why a full binary tree must have an odd numberof  (4 marks)Boolean Algebra代写

(c)Let B(n) denote the number of full binary trees with n Derive an expression for B(n), involving of T(nj ) where nj  ≤ n.  Hint:  Relate the internal nodes of a full binary treeto T(n). (6 marks)

A well-formed formula is in Negated normal form if it consists of just , , and literals (i.e. propositional variables or negations of propositional variables).  That is, a formula that results after two steps of the process for transforming a formula into a logically equivalent one. For example, p ∨ (¬q ∧ ¬r) is in negated normal form; but p ∨ ¬(q ∨ r) is not.Boolean Algebra代写

Let F(n) denote the number of well-formed, negated normal form formulas2 there are that use precisely n propositional variables exactly one time each. So F(1) = 2, F(2) = 16, and F(4) = 15360.

(d)Using your answer for part (c), give  an expression for F(n). (4 marks)

2Note: we do not assume ∧ and ∨ are associative

Problem 5 (18 marks)

Consider the following graph:

and consider the following process:

• Initially, start atv₁.
• At each time step, choose one of the vertices adjacent to your current location uniformly at random, and move there.Boolean Algebra代写

Let p₁(n), p₂(n), p₃(n), p₄(n) be the probability your location after n time steps is v₁, v₂, v₃, or v₄ respectively. So p₁(0) = 1 and p₂(0) = p₃(0) = p₄(0) = 0.

(a)Expressp₁(n + 1), p₂(n + 1), p₃(n + 1), and p₄(n + 1) in terms of p₁(n), p₂(n), p₃(n), and p₄(n).(6 marks)Boolean Algebra代写

(b)As n gets larger, each p_i(n) converges to a single value (called the steady state) which can be deter- mined by setting p_i(n + 1) = p_i(n) in the above    Determine the steady state probabilities  forall vertices. (8 marks)

(c)The distance between any two vertices is the length of the shortest path between them. What is your expected distance from v₁in the steady state? (4 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 Plagiarism” policies.Boolean Algebra代写

• Assignmentsare to be submitted via WebCMS (or give) as a single pdf
• 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.Boolean Algebra代写
• 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/explain/motivate your an- swers.Boolean Algebra代写
• If you use further resources (books, scientific papers, the internet,…) to formulate your answers, then add references to your sources.

其他代写：考试助攻 计算机代写 java代写 algorithm代写 assembly代写 function代写paper代写 web代写 编程代写 report代写 algorithm代写 数学代写 finance代写 作业代写  python代写 code代写 Haskell代写

合作平台：天才代写 幽灵代写 写手招聘 Essay代写