Answer:
Answer explained below
Explanation:
Credit to Jordan Johnson,
The set Bn contains all binary strings of size n. The number of strings in the set is equal to 2n since there are n positions to fill and each position can be filled with either 0 or 1.
Therefore, total number of strings = 2 * 2 * … * 2 = 2n
The set Pn that contains all the n-bit strings that are palindrome is a subset of the set Bn.
(c)
The set P7 contains 7-bit binary strings that are a palindrome. Each bit can either be 0 or 1 and hence there are 2 ways to fill each position of the binary string. The number of strings in P7can be computed as follows:
The first bit should be equal to the seventh bit. Number of ways to fill the first bit = 2 ways
The second bit should be equal to the sixth bit. Number of ways to fill the second bit = 2 ways
The third bit should be equal to the fifth bit. Number of ways to fill the third bit = 2 ways
The fourth bit could either be 0 or 1. Number of ways to fill the fourth bit = 2 ways
Therefore, the cardinality of P7 is equal to the total number of ways to fill the first 4 bits of the 7-bit strings = 2*2*2*2 = 16
To create a bijection function between P7 and Bn, compute the value of n as shown below:
Number of strings in P7 = Number of strings in Bn
16 = 2n
24 = 2n
Therefore, the value of n = 4.
The string in the set B4 are as follows:
{0000, 0001, 0010, 0011, 0100, 0101, 0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111}
Proof for bijection:
1. The above function P7 to B4 is one-one or injective, that is, if f(x) = f(y), then x = y where x, y belongs to the set P7.
For all x and y belonging to set P7, there are no two strings x and y for which f(x) = f (y), where x is not equal to y.
Hence, the function is one-one or injective.
2. The above function is onto or surjective, that is, for all y belonging to B4, there exist f(x) such that f(x) = y.
In other words, there is no y that belongs to B4 which is not mapped to an element of the set P7. None of the element in the set B4 is left un-mapped.
Hence, the function is onto or surjective.
Since the function is injective and surjective, the function P7 to B4 is bijective.
Hence, proved.
