Discreate Mathematics

 Proposition and Connectives

Satisfiable, Valid Questions

converse, inverse, contra-positive

Predicates and Quantifiers

Statements into Symbolic forms

Semigroup, monoid, group, abelian 

Poset, Hasse diagram

lattice

=========================================================================

Practice Questions

=========================================================================

1Q. Let A be a set with six elements. Which of the following cannot exist?
 (a) A subset of the power set of A with six elements.
 (b) An element of the power set of A with six elements.
 (c) An element of A containing six elements.
 (d) Any of the above can exists, for suitable sets A

Solution: 

(a) A subset of the power set of A with six elements:

• The power set of A contains all the subsets of A. The number of subsets in the power set of A is 26=642^6 = 6426=64. It's possible to form a subset of the power set containing six elements, so this option can exist.

(b) An element of the power set of A with six elements:

• The power set of A contains subsets of A, but the subsets must have between 0 and 6 elements, since A itself has 6 elements. A subset of A with six elements is just the set A itself. Therefore, this option can exist.

 (c) An element of A containing six elements:

• This cannot exist because the elements of A are not sets; they are individual elements. The set A has 6 elements, but no single element of A can contain 6 elements. So, this option cannot exist.

(d) Any of the above can exist, for suitable sets A:

• This is false because (c) cannot exist as discussed

========================================================================

2Q. Two finite sets have „m‟ and „n‟ elements respectively. The total number of subsets of „m‟ is 56 more than the total number of subsets of „n‟. The product of„m‟ and „n‟ is? _____

Solution:

According to the given information, the total number of subsets of the set with $m$ elements is 56 more than the total number of subsets of the set with $n$ elements. This gives the equation:

$$2^m = 2^n + 56$$=========================================================================

3Q. How many positive integers are there that are not larger than 1500 and are neither perfect squares nor perfect cubes? ________

Solution:

Step 1: Count the perfect squares

The number of perfect squares less than or equal to 1500 is the number of integers $n$ such that $n^2 \leq 1500$. The largest such $n$ is $\lfloor \sqrt{1500} \rfloor = 38$, because $38^2 = 1444$ and $39^2 = 1521$ exceeds 1500.

Thus, there are 38 perfect squares.

Step 2: Count the perfect cubes

The number of perfect cubes less than or equal to 1500 is the number of integers $n$ such that $n^3 \leq 1500$. The largest such $n$ is $\lfloor \sqrt[3]{1500} \rfloor = 11$, because $11^3 = 1331$ and $12^3 = 1728$ exceeds 1500.

Thus, there are 11 perfect cubes.

Step 3: Count the perfect sixth powers (numbers that are both squares and cubes)

A number that is both a perfect square and a perfect cube is a perfect sixth power. The number of perfect sixth powers less than or equal to 1500 is the number of integers $n$ such that $n^6 \leq 1500$. The largest such $n$ is $\lfloor \sqrt[6]{1500} \rfloor = 3$, because $3^6 = 729$ and $4^6 = 4096$ exceeds 1500.

Thus, there are 3 perfect sixth powers.

Step 4: Apply the principle of inclusion and exclusion

The number of integers up to 1500 that are either perfect squares or perfect cubes can be found using inclusion and exclusion:

$$\text{Number of squares or cubes} = (\text{Number of squares}) + (\text{Number of cubes}) - (\text{Number of sixth powers})$$ $$= 38 + 11 - 3 = 46$$

Step 5: Subtract from total numbers

The total number of positive integers up to 1500 is 1500. The number of integers that are neither perfect squares nor perfect cubes is:

$$1500 - 46 = 1454$$=========================================================================

5Q. Two finite sets have p and q elements given that p and q are consecutive prime numbers the total number of subsets of 1st set is 24 less than the total number of subsets of 2nd set. Find p + q. _______?

Solution:

According to the given information, the total number of subsets of the first set is 24 less than the total number of subsets of the second set. This gives the equation:

$$2^q - 2^p = 24$$=========================================================================

6Q. A set of mn objects can be partitioned into `m` sets of size `n` in _____different ways.

Solution:

The number of ways to partition $mn$ objects into $m$ sets of size $n$ is:

$$\frac{(mn)!}{(n!)^m \cdot m!}$$

• $(mn)!\; accounts\; for\; all\; possible\; permutations\; of\; the$$mn$ objects.
• $(n!)^m$ accounts for the fact that the elements within each subset can be arranged in $n!$ ways, but since the order of elements in each subset does not matter, we divide by $n!$ for each subset.
• $m!$ accounts for the fact that the order of the $m$ subsets does not matter, so we divide by $m!$.

=========================================================================

7Q. What will be expected cardinally of the subset of A, if cardinality of A= 10? __________

Solution:

Step 1: Number of Subsets

The total number of subsets of a set with $n$ elements is $2^n$. For $A$, with 10 elements, the total number of subsets is $2^{10} = 1024$.

Step 2: Expected Cardinality of a Subset

For each element of $A$, when forming a subset, there are two possibilities: either the element is included in the subset or it is not. Each element is included in a subset with a probability of $\frac{1}{2}$, because there are two equally likely outcomes for each element (in or out).

Therefore, the expected size (cardinality) of a randomly chosen subset of $A$ is:

$$\text{Expected cardinality} = \sum_{i=1}^{10} \mathbb{P}(\text{element } i \text{ is in the subset}) = 10 \times \frac{1}{2} = 5$$

$$==========================================================================$$

$$8Q.\; How\; many\; integers\; between\; 1\; and\; 1200\; inclusive\; do\; not\; share\; a\; common\; factor\; with\; 180,\; That\; is,\; are\; relative\; prime\; to\; other?\; \_\_\_\_\_\_\_\_$$

$$solution:$$

$$9Q.\; What\; is\; largest\; possible\; cardinality\; of\; A,\; if\; A\; is\; a\; collection\; of\; subsets\; of\; \{1,2,3---n\}such\; that\; no\; two\; elements\; of\; A\; are\; disjoint?\; (a)\; 2n-1\; (b)2n-1\; (c)\; 2n\; (d)2n/2$$

$$Solution:$$