What is flip

Assignment Help Mathematics
Reference no: EM132136441

Assignment -

Question 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?)

Question 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(φ).

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

1743_figure.png

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

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

613_figure4.png

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.

Reference no: EM132136441

How fast is the water level rising when the water is 4 cm

Water is poured into a canonical container at the rate of 10 cm3/sec. The cone points directly down, and it has a height of 30 cm and a base radius of 10 cm. How fast is the w

Sam buys some shoes online for $30 per pair including tax

Sam buys some shoes online for $ 30 per pair including tax and the shipping is $ 2. If he decides to buy more pairs of those shoes and it does not change the shipping cost, ho

In a classroom 4 friends are seated at the points a b c

In a classroom, 4 friends are seated at the points A, B, C and D as shown in the following figure. Champa and Chameli walk into the class and after observing for a few minutes

How many ways a president vice-president and a secretary

How many ways a president, vice-president and a secretary-treasurer for a high school Safe Grad committee be selected from 58 grade 12 students? Abby walks 9 blocks from her h

The differential equation whose linearly independent

The differential equation dy/dx+py = Q are function of x only, have integrating factor 3. The differential equation whose linearly independent solutions are cos 2x, sin 2x, an

Find the solution of differential equation

If curve cuts every member of a given family of curve at an angle θ (≠90°), then it is called. The orthogonal trajectories of the circle x2 + y2 = a2 is given by.  The particu

The orthogonal trajectory to the family of circles

The solution of D.E dy/dx = (y2 cos?x + cos?y)/(x sin?y-2y sin?x) y (Π/2) = 0 is:.....(a) y2 cos x + x sin y = 0 (b) y2 sin x + x cos y = Π/2 (c) y2 sin x + x sin y = 0 (d) y2

The orthogonal trajectory to the family of circles

1. If y1 and y2 are two solution of y" +p (x) y' + q(x) y = 0 then the general solution of this given equation y1 & y2 are. Order and degree of the D.E ey'" - xy" + y = 0 are

Reviews

urv2136441

11/23/2018 12:57:28 AM

love it. keep going. It was on time and completed, I am very happy with that. I would prefer your service again. definitely gonna using service in future. thanks you so much guys.

len2136441

10/9/2018 11:58:15 PM

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.

Write a Review

 
Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd