### Give an asymptotic upper bound

Assignment Help Engineering Mathematics
##### Reference no: EM132136341

Assignment -

1. Let (T, ∧, ∨,', 0, 1) be a Boolean Algebra.

Define ∗ : T × T → T and o : T × T → T as follows:

x ∗ y := (x ∨ y)' x o y := (x ∧ y)'

(a) Show, using the laws of Boolean Algebra, how to define x ∗ y using only x, y, o and parentheses.

(b) Show, using the laws of Boolean Algebra, how to define x o y using only x, y, ∗ and parentheses.

Define R ⊆ T × T as follows: (x, y) ∈ R if, and only if, (x ∧ y) ∨ (x' ∧ y') = 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?)

2. Let P F denote the set of well-formed propositional formulas made up of propositional variables, T, ⊥, and the connectives ¬, ∧, and ∨. Recall from Quiz 7 the definitions of dual and flip as functions from PF to PF:

 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 φ ∈ PF: flip(φ) is logically equivalent to ¬dual(φ).

3. Let P(n) be the proposition that: for all k, with 1 ≤ k ≤ n,

(a) Prove that P(n) holds for all n ≥ 1. (Note: it is possible to do this without using induction)

We can compute from the formula given in lectures, however this can often require computing unnecessarily large numbers. For example,= 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 more efficiently. Here are two algorithms for doing this:

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)).

#### Derive the formula of time period of simple pendulum

Calculate the time period of simple pendulum having length 100m and g=10m/sec2. Draw the PV graph of isothermal process. Write the formula of Lorentz force and write unit of f

#### Find the eigen values and eigen vectors of the matrix

All parts for this question are compulsory a) Find the 5th derivative of exx3. b) Find the stationary point of f(x,y) = 5x2 + 10y2 + 12xy - 4x - 6y + 1 c) If u= x2-y2 + sin yz

#### Find the average number of items sold in june

Plot the graph of y = x3- 2 in the range -10 ≤ x ≤ 10 Name the axes and add a title. Where PV= Present Value, P=Payment per period, r=interest rate and n=number of years. Writ

#### Prove that h is orthogonal

Consider the matrix H = I -hhT, where h is a column vector in M.n and I is the properly sized identity matrix. Prove that H is orthogonal, provided that h T h = 1. This matr

#### How do the coefficient estimates from the usual rule

These are the results of running 5-fold cross-validation on each of the ridge and lasso models, and using the usual rule (min) or the one-standard-error rule (1se) to select

#### Find the core and the least core

Here, wi ≥ 0 are called weights and q > 0 is called a quota. Take q = 1/2 Σi ε N wi . Suppose that there is one large group with two-fifths of the votes and two equal-sized g

#### Analyze the problems the author uses the concept of duality

In one of the papers (to be cited along with solutions) published in Operations Research journal, the author considers the following problem and its LP model: To analyze the

#### What is the standard deviation of the project npv

Consolidated Oilfield plc is interested in exploring for oil near the west coast of Australia. The Australian government is prepared to grant an exploration license to the

### Reviews

#### len2136341

10/9/2018 10:33:25 PM

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.

#### len2136341

10/9/2018 10:33:20 PM

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. 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 150x150 -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.

#### len2136341

10/9/2018 10:33:15 PM