Discrete Mathematics Assignment on Set Theory and Deductive Reasoning

This document presents a comprehensive solution to a Discrete Mathematics assignment focusing on set theory and deductive reasoning. The assignment includes multiple-choice questions and deductive problems. The solution covers fundamental concepts such as set operations (intersection, union, and complement), DeMorgan's theorem, and the principle of inclusion and exclusion. It also addresses the concept of closed functions within the context of real numbers and square roots. Each question is thoroughly explained, providing step-by-step solutions and justifications. The assignment covers topics such as set cardinality, the relationship between set operations and logical operators, and the application of these concepts to problem-solving scenarios. The document is a valuable resource for students studying discrete mathematics, offering detailed explanations and worked examples to enhance understanding and improve problem-solving skills.

Discrete Mathematics

TABLE OF CONTENT
SET THEORY.................................................................................................................................3
1 MCQ.............................................................................................................................................3
1.1 Q1......................................................................................................................................3
1.2 Q2......................................................................................................................................3
1.3 Q3......................................................................................................................................3
1.4 Q4..........................................................................................................................................3
1.5 Q5..........................................................................................................................................4
2. DEDUCTIVE..............................................................................................................................4
2.1 Q1..........................................................................................................................................4
2.2 Q2..........................................................................................................................................5
2.3 Q3..........................................................................................................................................5
2.4 Q4..........................................................................................................................................6
2.5 Q5..........................................................................................................................................6

SET THEORY
1 MCQ
1.1 Q1
Solution:
D. NOTA
W = set of number of days in a week = {7}
R= set of number of colors in a rainbow = {7}
|W X R|. |W ∩ R| + |W ∪ R|
|W ∩ R| = {7}
|W ∪ R| = {7}
|W X R| = 49
On substituting values we have: 49 . 7 + 7 = 350
1.2 2Q
Solution
b. Intersection operation
P = {1, 2, 3, 5, 7}
N = {2, 4, 6, 8}
If we are supposed to choose for filtering even prime number, then result will be 2 only. It is also
the only common number between both sets. Hence using intersection operation will give desire
result.
1.3 Q3
Solution
A. 10

A group may consist of maximum of 10 students. Since some students may also choose to take
tutorial from home it is possible that tutor may see 10 unique groups. Since each and every
student will be part of group either of home tutorial or of campus tutorial it is evident that total
number of elements will be equivalent to unique combination of the participants. The size of
group may vary up to a maximum of 10 and thus even a group of 2 or 3 students will also be
unique for teacher.
1.4 Q4
Solution
D. 100
In the given question total number of students = n = 90+60 = 150
Since each of the student knows either algebra or calculus or both none of the student falls in
category of neither situation. Thus here n = n (A U C) = 150
n(A): number of students who knows only algebra = ?
n(C): number of students who knows only calculus = 80
n (A ∪ C): number of students who knows either of calculus or algebra = 150
n (A ∩ C): number of students who knows both calculus and algebra = 30
Using the formula: n (A ∪ C) = n(A) + n(C) - n (A ∩ C)
150 = n(A) + 80 – 30
n(A) = 100
Thus number of students who studied only algebra is 100.
1.4 Q5
Solution
C. 26
If there are total 130 students in class and 5 sets of question papers then there will be 26
questions in paper. It is assumed that each paper has equal probability to be distributed among

students. A student will get same set of paper as obtained by other student only once all 5 types
are distributed. Thus (130/5) students will receive identical test set and the same number denotes
the number of questions in each paper.
2. DEDUCTIVE
2.1 Q1
Solution
Intersection operator cannot be considered as fundamental operator because it can be easily
expressed with the help of difference (-), union (U) and complementary operator (‘).
In terms of difference operator, we can write:
P ∩ Q = P – (P -Q)
Similarly, DeMorgan theorem can be used to convert union and complementary theorem into
intersection operator. The theorem states that
(P ∩ Q)’ = P’ U Q’
Thus in order to find intersection function we can write: (P ∩ Q) = [ P’ U Q’]’
2.2 Q2
Solution
|{ϕ}| = 0 is WRONG STATEMENT; instead |{ϕ}| = 1 is correct.
Φ is known as the empty set which does not have any element. Thus number of element in null
or empty set = | Φ | = 0. However, in the given question it is asked to find |{ϕ}| which denotes
number of elements in a set which consist of one element and that element is null set. Thus the
answer must be one; not zero.
2.3 Q3
Solution

DeMorgan’s theorem has two parts. The first one states that for NOR operation of n variables
(altogether) is equals to AND operation of each variable complemented individually. For 3
variables it can be demonstrated as: (A +B +C)’ = A’.B’.C’
Similarly, the second theorem of DeMorgan states that for n number of variables when NAND
operation is performed altogether then their resultant is equivalent to OR operation of inverted or
complemented variable.
(A.B.C)’ = A’ + B’ + C’
Proving DeMorgan’s law for 3 variables:
Let A; B and C are three Boolean variables. Thus the truth table for various terms in DeMorgan’s
law is as follows:
A B C A’ B’ C’ (A +B +C) (A +B +C)’ (A’.B’.C’) (A.B.C)’ (A’ + B’ + C’)
0 0 0 1 1 1 0 1 1 1 1
0 0 1 1 1 0 1 0 0 1 1
0 1 0 1 0 1 1 0 0 1 1
0 1 1 1 0 0 1 0 0 1 1
1 0 0 0 1 1 1 0 0 1 1
1 0 1 0 1 0 1 0 0 1 1
1 1 0 0 0 1 1 0 0 1 1
1 1 1 0 0 0 1 0 0 0 0
From the above truth table DeMorgan’s law for three variables is verified. On this basis the law
for n variable can be stated as:
(A +B +C +D……….up to n variables )’ = A’.B’.C’…………n’
(A.B.C. D……..n)’ = A’ + B’ + C’ +D’ ………..+ n’
2.4 Q4
Solution

Principle of inclusion and exclusion (PIE) is employed for computing cardinality of union set.
This technique helps to determine the number of values which satisfy at least one characteristics
among several while ensuring that elements are not counted twice in cases when they satisfy
more than one characteristics. For the three variables PIE can be formulated as:
|A ∪ B ∪ B| = |A| + |B| + |C| - | A ∩ B | - | A ∩ C | - | B ∩ C | + | A ∩ B ∩ C |
The principle is greatly helpful in avoiding the problem of double counting.
2.5 Q5
Solution
No; f is not closed under R. When X and Y both are equal then function f: X → Y is closed. For
real numbers R the radical symbol represents principle square root so that for all values of
positive x result is positive. However, for both positive and negative numbers the square root
result is positive. Thus it can be concluding that when all values of x are real then function of x is
also real and result will be only positive value which results in open function instead of closed f
(x). Due to this reason when f = √ x ∈ R the resultant function cannot be considered as close.