I have the solutions provide for the following questions, I would just like to a

Question

I have the solutions provide for the following questions, I would just like to ask for an expert to, step by step, explain to me how this solution came about and how does one reach this solution from the very start. Thanks!

8. (a) (5 points) Consider the set U of bitstrings of length 6. Let A be the set of bitstrings of length 6 that begin with two 0's, (i.e., bitstrings of the form 00****), and let B be the set of bitstrings of length 6 whose second bit is a 0 and whose third bit is a 1 (i.e., bistrings of the form *01***). (The symbol is a wild-card for the bits 0 and 1.) Determine |A- Bl. Recall that A-B A'U B Solution: To prove this we will use the Addition and Inclusion-Exclusion (IE) Principle We use the following definitions: We have that Ul = a+6+e+ d = 26, IA] = b+ c = 24, BI = c+ d = 24, We also know that AnB is the set of bitstrings of the form 001*** and therefore An Bc23 Solving for a, b, c, and d, we have that a26 - (24 +2-2) b = 24-29 Since IAl-A' n Bl+ IA'n B-d+ a = 24-29 have by the IE Principle 2 -(21 + 24-23) = 26-24, we Therefore, (b) (5 points) Consider the letters A, B, C, D, E, F. Determine the number of permutations of length 5 such that the letters A and B occur in these permutations and such that the letter A occurs before the letter B in these permutations For example EFADB and AFEDB are such permutations, but ACDEF and BCAEF are not. Solution: A string of 5 letters has () pairs of positions in which to place the letter such pair of positions there are still 3 positions A before the letter B. Then for each vacant in which we can build 4x3x 2 permutations over the 4 remaining letters C, D, E, and F. So the total is G-30 4 × 3 × 2 = ( ?? ) P(43) = 240

Explanation / Answer

a) NOTE: I'm using here . for intersection and + for union.

First of all U =a + b + c + d = 26 .This is because we have 6 bit position and each bit can be either 0 or 1 therefore, we have two possibilities for these 6 bits so, we have 26 possible bit strings of length 6 and this is the universe.

|A| = b+c

this is because

b + c = A.B' + A.B = A.(B' + B) = A[as B+B' = 1]

Now A means all 6 bit strings whose first two bits are 00 so, the first two bits are fixed and we are left with 4 bits.Now, total number of bit strings possible with 4 bits is 24.

So |A| = 24

Similarly:

|B| = c+d

this is because

c + d = A.B + A'.B = (A' + A).B = B[as A+A' = 1]

Now B means all 6 bit strings whose second bit is 0 and third bit 1 so, the second and third bits are fixed and we are left with 4 bits.Now, total number of bit strings possible with 4 bits is 24.

So |B| = 24

Now A means that first two bits are 00 and B means that second bit is 0 and third bit is 1 so, the common strings between A and B is that first two bits are 00 and third bit is 1 so, the first three bits are fixed and we are left with 3 more bits and the possible number of bit strings with 3 bits is 23.So, |A.B| = 23.

Now for inclusion exclusion principle we need to find |A' + B| = |A'| + |B| - |A'.B|

Therefore we want |A'| , |B| and |A'.B|.

Now from above we already know |B| = 24

Now we need |A'|

Note that A' = a + d

as a + d = A'.B + A'.B' = A'.(B+B') = A' [as B + B' = 1]

Now a = |A'B'| = |U| - |A+B| [By demaorgans law]

and  |A+B| = |A| + |B| - |A.B| [By inclusion exclusion principle]

Therefore  |A+B| = 24 + 24 - 23

Therefore a= |A'B'| = 26 - 24 - 24 + 23

Now similarly d= |A'.B|= 24 - 23

Therefore |A'| = a + d = 26 - 24 - 24 + 23 + 24 - 23

Now |A'.B| is same as d and = 24 - 23

Therefore,

|A' + B| = |A'| + |B| - |A'.B| = 26 - 24 - 24 + 23 + 24 - 23 + 24 -  24 + 23 = 26 - 24 + 23 = 56.

b) Now A and B should be there and A should occur before B therefore we will first select two positions from the 5 positions to keep A and B there such that A occurs before B.

Now number of ways to select 2 places from5 places is C(5,2).

After selecting these two places these two places are fixed and 3 places are remaining.

As we have already selected A and B so remaining letters are C,D,E,F.

Now we have to fill these 3 places with these 4 letters in all possible orders.This is nothing but permutation of 3 objects from 4 objects and is given by P(4,3).

Therefore total number of ways = C(5,2)*P(4,3) = 240

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---