I need help with bit strings in discrete mathematics! Suppose U be the universal

Question

I need help with bit strings in discrete mathematics! Suppose U be the universal set. Then determine the bit strings for the following: a. An empty set b. Universal set,U c. Symmetric difference of two sets which are subset of universal set, U(The symmetric difference of A and B, is the set containing those element in either A or B, but not in both A and B.) d. Union of n sets that all are subsets of the universal set, U e. Intersection of n sets that all are subsets of the universal set, U Define any variables (such as name of the sets, size of the universal set or the bitstring length, etc), state any assumptions and provide brief justification or explanation of the derivation of each of the above bit strings. (Provide general case answer and not example specific answer for all including justification)

Explanation / Answer

--If we represent a set by using bit srring, then '1' represent elements present in set

and '0' represent elements not present in set.

Suppose U be the universal set.

Let U = {1,2,3,4,5,6,7,8,9,10}

total elements in set U is 10, then total length of 'bit strings' of U is 10.

a). An empty set is also called NULL set that is, a set that has no elements.

Suppose A is empty set of U

then A = {},

In general, bit string(of n length) for empty set is n number of '0' for n elements in universal set U.

So, bit string for an empty set in given example is

ans -- 0000000000 (no elements present of set U)

b). Universal set is the set containing all elements and of which all other sets are subsets.

Suppose A is universal set of U

then A = {1,2,3,4,5,6,7,8,9,10}

In general, bit string(of n length) for universal set is n number of '1' for n elements in universal set U.

So, bit string for universal set is

ans -- 1111111111 (all elements present of set U)

c). The bit string in the ith position of the bit string of symmetric difference of two sets is '1'

if the ith bit of the first string is not equal to the ith bit of the second string and is '0' otherwise.

Let a1,a2,.....,an and b1,b2,.....,bn be the bit strings of corresponding to two sets A and B respectively.

Let x1,x2,.....,xn be ith bit string corresponding to the symmetric difference of A and B.

Then,

xi  = 1 if ai != bi

xi = 0 otherwise

Suppose A = {1,3,4} and B = {2,3,4,5}

Then,

bit string of A = 1011000000

and bit string of B = 0111100000

Then,

bit string of Symmetric Difference of A and B is

ans -- 1100100000 i,e; {1,2,5}

d). The bit string in the ith position of the bit string of union of sets is '1'

if the ith bit of the first string is '1' or ith bit of the second string is '1'

and '0' if ith bit of the first and second string is '0'. Basically, the bit string for

the union is the 'bitwise OR' of the bit string for the sets.

Let a1,a2,.....,an and b1,b2,.....,bn be the bit strings of corresponding to two sets A and B respectively.

Let x1,x2,.....,xn be ith bit string corresponding to the union of A and B.

Then,

xi = 1 if ai = 1 or bi = 1

xi = 0 if ai = 0 and bi = 0

Suppose A = {1,3,4} and B = {2,3,4,5}

Then,

bit string of A = 1011000000

and bit string of B = 0111100000

Then,

bit string of Union of A and B is

ans -- 1111100000 i,e; {1,2,3,4,5}

e). The bit string in the ith position of the bit string of intersection of sets is '1'

if the ith bit of the first string is '1' and ith bit of the second string is '1'

and '0' if ith bit of the first bit string is '0' or ith bit of the second string is '0'.

Basically, the bit string for the intersection is the 'bitwise AND' of the bit string for the sets.

Let a1,a2,.....,an and b1,b2,.....,bn be the bit strings of corresponding to two sets A and B respectively.

Let x1,x2,.....,xn be ith bit string corresponding to the intersection of A and B.

Then,

xi = 1 if ai = 1 and bi = 1

xi = 0 if ai = 0 or bi = 0

Suppose A = {1,3,4} and B = {2,3,4,5}

Then,

bit string of A = 1011000000

and bit string of B = 0111100000

Then,

bit string of Intersection of A and B is

ans -- 0011000000 i,e; {3,4}

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.