Discrete Mathematics 1-1 [Link].

in

1 Set and Propositions

Syllabus Course Code: PCC-252- COM (2024 Pattern) 09 Hours 14 Marks
Introduction and significance of Discrete Mathematics, Propositional Logic- logic, Propositional Equivalences,
Application of Propositional Logic- Translating English Sentences, Proof by Mathematical Induction and Strong
Mathematical Induction. Sets– Naïve Set Theory (Cantorian Set Theory), Axiomatic Set Theory, Set Operations, Cardinality
of set, Principle of inclusion and exclusion. Types of Sets – Bounded and Unbounded Sets, Diagonalization Argument,
Countable and Uncountable Sets, Finite and Infinite Sets, Countably Infinite and Uncountably Infinite Sets, Power set.

1.1. Introduction and significance of Discrete Mathematics

• Discrete Mathematics is a branch of mathematics that deals with discrete and distinct elements rather
than continuous values. The notion of a set is a fundamental concept in Discrete Mathematics.
• In fact, almost every branch of mathematics can be considered as the study of sets of objects of one kind
or another.

Significance of Discrete Mathematics:

▪ It forms the foundation of mathematical reasoning.
▪ It is used to study sets, relations, functions, and logic.
▪ It is essential in computer science applications such as algorithms and data structures.
▪ It helps in analyzing and solving computational problems systematically.

1.2. Propositional Logic

• Propositional logic is a branch of mathematical logic that deals with propositions and the logical
relationships between them.

1.2.1. Logic
Statements / Propositions
A statement is a declarative sentence which is either true or false but not both. The truth or falsity of a
statement is called its truth value. The truth value of a true statement is denoted by 'T' and the false statement
is denoted by 'F'. They are also denoted by 1 or 0. Statements are usually denoted by A, B, C, ....... or a, b, c

Laws of Formal Logic

Formal logic is based on fundamental laws that govern valid reasoning.
There are two main laws of formal logic.
1. Law of Contradiction
• Statement: A statement cannot be both true and false at the same time.
• Explanation: If a statement is true, its negation must be false.
• Symbolic Form: A statement p and ¬p cannot both be true.

2. Law of Excluded Middle

• Statement: For any proposition p, either p is true or p is false.
• Explanation: There is no middle or third possibility between true and false.
• Symbolic Form: p v ¬p is always true.

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-2 [Link]

Logical Connectives
Logical connectives are symbols used to combine or modify propositions to form compound statements.
1. Negation ( ~ )
Negation of a proposition p is a statement that reverses the truth value of p.
Truth Table:
p ~p
T F
F T

Example:
If p: “It is raining”
Then ~p: “It is not raining”

2. Conjunction ( ∧ )
Conjunction of two propositions p and q is true only when both p and q are true.
Truth Table:
p q p∧ q
T T T
T F F
F T F
F F F

Example:
p: “Student studied”
q: “Student attended exam”
p ∧ q: “Student studied and attended exam”

3. Disjunction ( ∨ )
Disjunction of two propositions p and q is true if at least one of them is true.
Truth Table:
p q p∨ q
T T T
T F T
F T T
F F F

Example:
p: “Student passed theory”
q: “Student passed practical”
p ∨ q: “Student passed theory or practical”

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-3 [Link]

4. Conditional ( → )
Conditional statement p → q means if p is true, then q must be true.

Truth Table:
p q p→q
T T T
T F F
F T T
F F T

Example:
p: “Student submits assignment”
q: “Student is allowed to appear for exam”
p → q: “If student submits assignment, then student is allowed to appear for exam”

5. Biconditional ( ↔ )
Biconditional statement p ↔ q is true when both p and q have the same truth value.
Truth Table:
p q p↔q
T T T
T F F
F T F
F F T

Example:
p: “Student passes exam”
q: “Student gets certificate”
p ↔ q: “Student passes exam if and only if student gets certificate”

Special Propositions
If p → q is a conditional statement, then
1. q → p is called its converse
2. ~p → q ~ is called its inverse
3. ~ q → ~p is called its contrapositive

The truth table of these propositions are as follows

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-4 [Link]

Compound Statements
A statement which is formed from primary statements by using logical connectives is called a compound
statement.
e.g. If p : I am studying in SE computer class
q : I am learning discrete structure subject

The compound statement is

I am studying in SE computer class and I am learning discrete structure subject

Example:
Let p denote the statement, "The material is interesting'. q denote the statement, "The exercises are
challenging", and r denote the statement, "The course is enjoyable".
Write the following statements in symbolic form:
i) The material is interesting and exercises are challenging.
ii) The material is interesting means the exercises are challenging and conversely.
iii) Either the material is interesting or the exercises are not challenging but not both.
iv) If the material is not interesting and exercises are not challenging, then the course is not enjoyable.
v) The material is uninteresting, the exercises are not challenging and the course is not enjoyable.
are challenging and course is not
the

Solution:

1.2.2. Propositional Equivalences

1. Statement Formula (Propositional Formula)
A statement formula is an expression that contains one or more statement variables and logical
connectives.
It is a string consisting of statement variables, parentheses, and logical connective symbols.
A statement formula is not a statement and does not have a truth value.
When definite statements are substituted for the variables, the formula becomes a statement and its
truth value depends on the truth values of the variables.

2. Well-Formed Formula (WFF)

A statement formula is called a well-formed formula if it can be generated using the following rules:
1. A statement variable p standing alone is a well-formed formula.
2. If p is a well-formed formula, then ~p is also a well-formed formula.
3. If p and q are well-formed formulas, then
p ∧ q, p ∨ q, p → q, q → p, and p ↔ q are well-formed formulas.
4. A string of symbols is a well-formed formula if and only if it is obtained by a finite number of
applications of rules (i), (ii), and (iii).

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-5 [Link]

3. Tautology
A statement formula that is true for all possible values of its propositional variables is called tautology.
Example: 𝑝 ∨ ~𝑝
Truth Table Proof:
p ~p p ∨ ~p
T F T
F T T

4. Contradiction
A statement formula that is false for all possible values of its variables is called a contradiction (or
absurdity).
Example: 𝑝 ∧ ~𝑝
Truth Table Proof:

p ~p p ∧ ~p
T F F
F T F

5. Contingency
A statement formula which is neither a tautology nor a contradiction is called a contingency.
Example: 𝑝 → 𝑞
Truth Table Proof:
p q p→q
T T T
T F F
F T T
F F T

6. Precedence Rule
When brackets are not present, logical connectives are applied in the following order:
1. Negation ~
2. Conjunction ∧
3. Disjunction ∨
4. Conditional →
5. Biconditional ↔

Remark:
• If ∨ and ⊕ (exclusive OR) appear together, apply the leftmost first.
• Same rule applies for → and ↔.

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-6 [Link]

7. Logical Equivalence
Two statement formulas P and Q are said to be logically equivalent if they have the same truth value for
all possible truth values of their variables.
If 𝑃 ↔ 𝑄is a tautology, then P and Q are logically equivalent.

Symbol
• 𝑃≡𝑄
• or 𝑃 ↔ 𝑄(as a tautology)

Examples
1. 𝑝 → 𝑞 ≡ ~𝑝 ∨ 𝑞
2. ~(𝑝 ∧ 𝑞) ≡ ~𝑝 ∨ ~𝑞

8. Logical Identities

Name Identity
Idempotent (∨) 𝑝∨𝑝 ≡𝑝
Idempotent (∧) 𝑝∧𝑝 ≡𝑝
Commutative (∨) 𝑝∨𝑞 ≡𝑞∨𝑝
Commutative (∧) 𝑝∧𝑞 ≡𝑞∧𝑝
Associative (∨) (𝑝 ∨ 𝑞) ∨ 𝑟 ≡ 𝑝 ∨ (𝑞 ∨ 𝑟)
Associative (∧) (𝑝 ∧ 𝑞) ∧ 𝑟 ≡ 𝑝 ∧ (𝑞 ∧ 𝑟)
Distributive (∧ over ∨) 𝑝 ∧ (𝑞 ∨ 𝑟) ≡ (𝑝 ∧ 𝑞) ∨ (𝑝 ∧ 𝑟)
Distributive (∨ over ∧) 𝑝 ∨ (𝑞 ∧ 𝑟) ≡ (𝑝 ∨ 𝑞) ∧ (𝑝 ∨ 𝑟)
De Morgan’s ~(𝑝 ∨ 𝑞) ≡ ~𝑝 ∧ ~𝑞
De Morgan’s ~(𝑝 ∧ 𝑞) ≡ ~𝑝 ∨ ~𝑞
Absorption 𝑝 ∨ (𝑝 ∧ 𝑞) ≡ 𝑝
Absorption 𝑝 ∧ (𝑝 ∨ 𝑞) ≡ 𝑝

9. Duality Principle
Two statement formulas are said to be duals of each other if one can be obtained from the other by
replacing:
o ∧↔∨
o 𝑇↔𝐹
(Variables and negations remain unchanged.)
Examples
1. Original: 𝑝 ∧ 𝑞
Dual: 𝑝∨𝑞

2. Original: 𝑝 ∨ 𝑇
Dual: 𝑝∧𝐹

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-7 [Link]

1.2.3. Applications of Propositional Logic

1. Translating English → Symbolic

Express following statement in propositional form :
i) There are many clouds in the sky but it did not rain.
ii) I will get first class if and only if I study well and score above 80 in mathematics.
iii) Computers are cheap but softwares are costly.
iv) It is very hot and humid or Ramesh is having heart problem.
v) In small restaurants the food is good and service is poor.
vi) If I finish my submission before 5.00 in the evening and it is not very hot I will go and play a
game of hockey

Solution:
i) p : There are many clouds in the sky
q : It rain
p ∧~q

ii) p : I will get first class

q : I study well
r : Score above 80 in mathematics
p↔( q ∧ r )

iii) p : Computers are cheap

q : Softwares are costly
p∧ q

iv) p : It is very hot

q : It is very humid
r : Ramesh is having heart problem
(p ∧ q )∨r

v) p : In small restaurant food in good

q : Service is poor
p∧q

vi) p : I finish my submission before 5:00 p.m.

q : It is very hot
r : I will go
s : I will play a game of hockey
(p ∧ ~ q ) →( r ∧ s )

2. Translating Symbolic → English

Use p : I will study discrete mathematics, q : I will go to a movie, r : I am in a good mood. Write the
following in English sentence :
a) ~ r → q
b) ~ q ∧ p
c) q → ~ p
d) ~ p → ~ r

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-8 [Link]

Solution:
a) ~ r → q
English sentence: If I am not in a good mood, then I will go to a movie.

b) ~ q ∧ p
English sentence: I will not go to a movie and I will study discrete mathematics.

c) q → ~ p
English sentence: If I go to a movie, then I will not study discrete mathematics.

d) ~ p → ~ r
English sentence: If I do not study discrete mathematics, then I am not in a good mood.

3. The Duality Principle

Write the duals of i) ~ ( p ∨ q) ii) p ∧ ( q ∨ r ) iii) p ∨ T
Solution:
The duals are i) ~ ( p ∧ q)
ii) p ∨ ( q ∧ r )
iii) p ∧ F

1.3. Mathematical Induction

• Mathematical Induction is a powerful method used to prove statements involving natural numbers.
• It is widely used in number theory and discrete mathematics to establish the truth of formulas and
properties defined for all natural numbers.
• This technique is also useful in computer science, particularly in verifying loop invariants in programs.
There are two principles of mathematical induction:
1. First Principle of Mathematical Induction
2. Second Principle of Mathematical Induction (Strong Induction)

1. First Principle of Mathematical Induction

Statement
Let 𝑃(𝑛)be a statement involving a natural number 𝑛 ≥ 𝑛0 , where 𝑛0 ∈ ℕ. If:
1. Basis Step: 𝑃(𝑛0 )is true, and
2. Induction Step: Assuming 𝑃(𝑘)is true for some 𝑘 ≥ 𝑛0 , then 𝑃(𝑘 + 1)is also true, then 𝑃(𝑛)is
true for all natural numbers 𝑛 ≥ 𝑛0 .
• Step 1 is called the basis of induction.
• Step 2 is called the induction step.

Example
Prove that:
𝑛(𝑛 + 1)
1 + 2 + 3 + ⋯+ 𝑛 = , for all 𝑛 ∈ ℕ
2

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1-9 [Link]

Solution
Let 𝑃(𝑛)be the statement
𝑛(𝑛 + 1)
1+ 2+ 3+ ⋯+ 𝑛 =
2

Step 1: Basis of Induction

For 𝑛 = 1:
L.H.S. = 1
1(1+1)
R.H.S. = =1
2
Since L.H.S. = R.H.S., 𝑃(1)is true.
Step 2: Induction Step
Assume that 𝑃(𝑘) is true for some 𝑘 ∈ ℕ, i.e.,
𝑘(𝑘 + 1)
1+ 2+ 3+ ⋯+ 𝑘 = ...(1)
2

Now consider:
1 + 2 + 3 + ⋯ + 𝑘 + (𝑘 + 1)

Using (1),
𝑘(𝑘 + 1)
= + (𝑘 + 1)
2
𝑘(𝑘 + 1) + 2(𝑘 + 1)
=
2
(𝑘 + 1)(𝑘 + 2)
=
2

Thus,
𝑃(𝑘 + 1) is true

Hence, by the First Principle of Mathematical Induction,

𝑃(𝑛) is true for all 𝑛 ∈ ℕ

2. Second Principle of Mathematical Induction (Strong Induction)

Statement
Let 𝑃(𝑛)be a statement involving a natural number 𝑛 ≥ 𝑛0 . If:
1. 𝑃(𝑛0 )is true, and
2. Assuming that 𝑃(𝑛0 ), 𝑃(𝑛0 + 1), … , 𝑃(𝑘) are all true, we prove that 𝑃(𝑘 + 1)is true, then 𝑃(𝑛) is
true for all 𝑛 ≥ 𝑛0 .
In strong induction, the induction hypothesis assumes the truth of all previous cases, not just one.

Example
Prove that:
𝑛5 − 𝑛 is divisible by 5 for all 𝑛 ∈ ℕ

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 10 [Link]

Solution
Let 𝑃(𝑛)be the statement that 𝑛5 − 𝑛is divisible by 5.
Step 1: Basis of Induction
For 𝑛 = 1:
15 − 1 = 0

which is divisible by 5.
Hence, 𝑃(1)is true.

Step 2: Induction Step

Assume that 𝑃(𝑘)is true, i.e.,
𝑘 5 − 𝑘 is divisible by 5

Now consider:
(𝑘 + 1)5 − (𝑘 + 1)
= 𝑘 5 + 5𝑘 4 + 10𝑘 3 + 10𝑘 2 + 5𝑘 + 1 − 𝑘 − 1
= (𝑘 5 − 𝑘) + 5(𝑘 4 + 2𝑘 3 + 2𝑘 2 + 𝑘)

By induction hypothesis, 𝑘 5 − 𝑘is divisible by 5, and the remaining term is also divisible by 5.
Hence,
(𝑘 + 1)5 − (𝑘 + 1) is divisible by 5

Therefore, 𝑃(𝑘 + 1)is true.

By the Second Principle of Mathematical Induction,
𝑛5 − 𝑛 is divisible by 5 for all 𝑛 ∈ ℕ

1.4. Theory of Sets

• The notion of a set is a fundamental concept in mathematics. Almost every branch of mathematics can be
considered as the study of collections of objects.
• The theory of sets was founded by the great mathematician Georg Cantor. Set theory provides the basic
language for describing mathematical structures and is widely used in discrete mathematics and
computer science.

1.4.1. Sets – Naïve Set Theory

A set is a well-defined collection of distinct objects. The objects in a set are called elements or members
of the set.
Notation:
• 𝐼𝑓 "x is an element of a set A" 𝑡ℎ𝑒𝑛 𝑤𝑒 𝑤𝑟𝑖𝑡𝑒 𝑥 ∈ 𝐴
• 𝐼𝑓 "𝑥 𝑖𝑠 𝑛𝑜𝑡 𝑎𝑛 𝑒𝑙𝑒𝑚𝑒𝑛𝑡 𝑜𝑓 𝑎 𝑠𝑒𝑡 𝐴" 𝑡ℎ𝑒𝑛 𝑤𝑒 𝑤𝑟𝑖𝑡𝑒 𝑎𝑠 𝑥 ∉ 𝐴

Examples:
1) The set of letters forming the word "MATHEMATICS"
2) The set of students in a class SE Computer Engineering
3) s = {1, 2, 3, 4, 5, 6}

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 11 [Link]

1.4.2. Methods of Describing Sets

A set can be described in different ways depending on the nature and size of the set.
1 Roster Method (Listing Method)
- A set is described by listing all its elements inside curly braces { }.
- Order of elements does not matter.
- This method is used for small sets.
Examples:
• 𝐴 = {1,2,3,4,5}
• 𝐵 = {𝑎, 𝑏, 𝑐, 𝑑, 𝑒, 𝑓, 𝑔}

2 Statement Form
- A set is described by stating a common property of its elements.
- Useful when elements have a clear common characteristic.
Examples:
1. The set of all even integers
2. The set of all Prime Ministers of India

3 Set Builder Notation

- Used when listing all elements is not possible or not convenient.
- The set is described by specifying a property satisfied by all elements.
General form:
𝐴 = {𝑥 ∣ property of 𝑥}
Examples:
• 𝐴 = {𝑥 ∣ 𝑥 is real and 𝑥 2 ≤ 100}
• 𝐵 = {𝑥 ∣ 𝑥 is real and − 10 ≤ 𝑥 ≤ 20}

1.4.3. Some Special Sets

Important sets used frequently in mathematics:
1. Natural Numbers
𝑁 = {1,2,3, … }

2. Integers
𝑍 = {… , −3, −2, −1,0,1,2,3, … }

3. Whole Numbers
𝑍 + = {0,1,2,3, … }

4. Rational Numbers

5. Real Numbers
𝑅

6. Complex Numbers
𝐶

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 12 [Link]

1.4.4. Subsets
• A set A is a subset of B if every element of A is also an element of B.
• Denoted by:
𝐴⊆𝐵
• If 𝐴 ⊆ 𝐵, then B is called the superset of A.

Empty (Null) Set

• A set with no elements.
• Denoted by:
∅ or {}
Possible Cases when 𝑨 ⊆ 𝑩
1. 𝐴 = 𝐵
2. 𝐴 ⊂ 𝐵and 𝐴 ≠ 𝐵

1. Proper Subset
A set A is a proper subset of B if:
1. 𝐴 ⊆ 𝐵
2. At least one element of B is not in A

Notation:
𝐴⊂𝐵
Example:
If 𝐴 = {1,2,3}, 𝐵 = {1,2,3,4,5}, then A is a proper subset of B.

2. Improper Subsets
• Every set is a subset of itself.
• The null set is a subset of every set.
• These are called improper subsets.

3. Equal Sets
• Two sets A and B are equal if:
𝐴 ⊆ 𝐵 and 𝐵 ⊆ 𝐴
• Denoted by:
𝐴=𝐵

1.4.4. Types of Sets

Depending upon some properties there are mainly following types of sets.
1) Universal Set
• A non-empty set containing all objects under discussion.
• Denoted by U.
• Universal set is not unique.

2) Singleton Set
• A set containing only one element.
Examples:
• {5}
• {∅}

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 13 [Link]

3) Finite Set
• A set having a finite number of elements.
• Number of elements is called cardinality, denoted by ∣ 𝐴 ∣.
Example:
• 𝐴 = {1,2,3,4,5}, then ∣ 𝐴 ∣= 5

4) Infinite Set
• A set having infinitely many elements.
Example:
• 𝑁(set of natural numbers)

5) Power Set
• The set of all subsets of a set A.
• Denoted by:
𝑃(𝐴)

• If ∣ 𝐴 ∣= 𝑛, then:
∣ 𝑃(𝐴) ∣= 2𝑛

Examples:
• If 𝐴 = {𝑎, 𝑏}
𝑃(𝐴) = {∅, {𝑎}, {𝑏}, {𝑎, 𝑏}}
• 𝑃(∅) = {∅}

6) Power Set of Power Set

• Denoted by:
𝑃(𝑃(𝐴))
• If ∣ 𝐴 ∣= 2, then:
▪ ∣ 𝑃(𝐴) ∣= 4
▪ ∣ 𝑃(𝑃(𝐴)) ∣= 16

7) Element vs Subset
Let 𝐴 = {𝑥, 𝑦}
• 𝑥 ∈ 𝐴→ True
• 𝑥 ⊆ 𝐴→ False
• {𝑥} ⊆ 𝐴→ True
• {𝑥} ∈ 𝐴→ False
• ∅ ⊆ 𝐴→ True

8) Countable Set
o A set is called countable if its elements can be put in one-to-one correspondence with a subset of
natural numbers.
Example:
The set {2, 4, 6, 8}is countable.

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 14 [Link]

9) Countably Infinite Set

o A set is called countably infinite if its elements can be put in one-to-one correspondence with the
set of natural numbers 𝑁
Example:
• Set of natural numbers 𝑁 = {1,2,3, … }
• Set of integers 𝑍 = {… , −2, −1,0,1,2, … }
• Set of rational numbers 𝑄

10) Uncountable Set

o A set is called uncountable if its elements cannot be put in one-to-one correspondence with natural
numbers.
Example:
• Set of natural numbers 𝑁 = {1,2,3, … }
• Set of integers 𝑍 = {… , −2, −1,0,1,2, … }
• Set of rational numbers 𝑄

11) Bounded Set

o A set is called bounded if all its elements lie between two fixed real numbers.
Example:
A = {x ∈ R | 0 ≤ x ≤ 5}

12) Unbounded Set

o A set whose elements are not restricted within any finite range.
Example:
N = {1,2,3,…}

13) Diagonalization Argument

o Cantor’s diagonalization argument is used to prove that the set of real numbers is uncountable.
o It shows that no matter how real numbers are listed, a new real number can always be constructed
that differs from each listed number in at least one decimal place.
o Hence, real numbers cannot be put into one-to-one correspondence with natural numbers.

Example:
▪ Consider a list of real numbers between 0 and 1.
▪ By changing the digits along the diagonal of the list, a new real number is obtained which
is not present in the list.
▪ Therefore, the set of real numbers is uncountable

1.4.5. Venn Diagrams

• Venn diagrams are used to represent relationships between sets visually.
• Introduced by John Venn.

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 15 [Link]

Rules:
1. Universal set is shown by a rectangle.
2. Subsets are shown by circles.
3. If 𝐴 ⊆ 𝐵, circle A lies inside circle B.
4. Disjoint sets have no common area.
5. Non-disjoint sets have overlapping regions.

1.4.6. Operations on Sets

• To define new sets by combining given sets, set operations are used.
• These operations are analogous to algebraic operations like + , − , × on numbers.

1. Union of Two Sets

Let A and B be two sets.
The union of A and B is the set of all elements which are in A or in B or in both.
Notation:
𝐴 ∪ 𝐵 = {𝑥 ∣ 𝑥 ∈ 𝐴 or 𝑥 ∈ 𝐵}

Venn diagram: By Venn diagram A ∪ B is represented as

Examples
1. A = {1, 2, 3, 4}, B = {x, y, z}
𝐴 ∪ 𝐵 = {1,2,3,4, 𝑥, 𝑦, 𝑧}
2. A = {1,2,3,4,5,6,7,8,9,10}, B = {2,3,5,7,11,13}
𝐴 ∪ 𝐵 = {1,2,3,4,5,6,7,8,9,10,11,13}

2. Intersection of Two Sets

The intersection of two sets A and B is the set of elements which are common to both A and B.
Notation:
𝐴 ∩ 𝐵 = {𝑥 ∣ 𝑥 ∈ 𝐴 and 𝑥 ∈ 𝐵}

Venn diagram: By Venn diagram A ∩ B is represented as

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 16 [Link]

Examples
1. A = {1,2,3,4,5}, B = {1,4}
𝐴 ∩ 𝐵 = {1,4}
2. 𝐴∩∅=∅
3. A = {a,b,c}, B = { x, y }
𝐴∩𝐵 =∅

3. Disjoint Sets
Two sets A and B are said to be disjoint if they have no common elements.
Condition:
𝐴∩𝐵 =∅
Example:
A = {1,2}, B = { x , y } are disjoint sets.

4. Complement of a Set
Let A be a subset of the universal set U.
The complement of A consists of all elements of U which are not in A.
Notation:
𝐴′ or 𝐴ˉ

Definition:
𝐴′ = {𝑥 ∣ 𝑥 ∈ 𝑈 and 𝑥 ∉ 𝐴}

Venn diagram: By Venn diagram ‘A’ is represented as

Examples
1. If A = set of even numbers and U = set of integers
Then A′ = set of odd numbers
2. U = {1,2,3,…,15}, A = {1,2,3,4,5,6,7}
𝐴′ = {8,9,10,11,12,13,14,15}

Properties of Complement
1. 𝑈 ′ = ∅, ∅′ = 𝑈
2. ( 𝐴′ )′ = 𝐴
3. 𝐴 ∪ 𝐴′ = 𝑈, 𝐴 ∩ 𝐴′ = ∅
4. 𝐴 ∪ 𝑈 = 𝑈, 𝐴 ∩ 𝑈 = 𝐴

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 17 [Link]

5. Difference of a Sets
Let A and B be two sets.
The difference A − B is the set of elements that are in A but not in B.
Definition:
𝐴 − 𝐵 = {𝑥 ∣ 𝑥 ∈ 𝐴 and 𝑥 ∉ 𝐵}
It is also called the relative complement of B in A.
Similarly,
𝐵 − 𝐴 = {𝑥 ∣ 𝑥 ∈ 𝐵 and 𝑥 ∉ 𝐴}

Venn diagram: By Venn diagram it is represented as

Examples
1. A = {1,2,3,4,5}, B = {3,4,5,6,7}
𝐴 − 𝐵 = {1,2}, 𝐵 − 𝐴 = {6,7}

2. A = set of prime numbers B = set of odd integers

𝐴 − 𝐵 = {2}

Properties of Difference
1. 𝐴′ = 𝑈 − 𝐴
2. 𝐴 − 𝐴 = ∅, ∅ − 𝐴 = ∅
3. 𝐴−∅=𝐴
4. 𝑈−∅=𝑈
5. 𝐴 − 𝐵 = 𝐴 ∩ 𝐵′
6. 𝐴−𝐵 =𝐵−𝐴 ⟺ 𝐴 =𝐵
7. 𝐴−𝐵 =∅ ⟺ 𝐴⊆𝐵

6. Symmetric Difference of Sets

The symmetric difference of two sets A and B consists of elements which are in either A or B but not
in both.
Notation:
𝐴 △ 𝐵 or 𝐴 ⊕ 𝐵
Definition:
𝐴 △ 𝐵 = (𝐴 − 𝐵) ∪ (𝐵 − 𝐴)

Venn diagram: By Venn diagram it is represented as

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 18 [Link]

Examples
1. A = {1,2,3,4,5,6}, B = {3,4,5,6,7,8}
𝐴 △ 𝐵 = {1,2,7,8}

2. 𝐴 △ ∅ = 𝐴

Properties of Symmetric Difference

1. 𝐴△𝐴 =∅
2. 𝐴△∅=𝐴
3. 𝐴 △ 𝑈 = 𝐴′
4. 𝐴 △ 𝐴′ = 𝑈
5. 𝐴 △ 𝐵 = (𝐴 ∪ 𝐵) − (𝐴 ∩ 𝐵)

1.4.6. Cardinality of set

In the analysis of computer algorithms, it is often required to count the number of operations performed.
This helps in estimating the cost and efficiency of an algorithm.

Let A be a finite set.

The number of elements in set A is called the cardinality of A.
Notation: ∣ 𝐴 ∣ or𝑛(𝐴)
Example:
If 𝐴 = {𝑥, 𝑦, 𝑧, 𝑝}, then ∣ 𝐴 ∣= 4

Theorem 1
If 𝐴 = ∅, then ∣ 𝐴 ∣= 0

Theorem 2
If 𝐴 ⊆ 𝐵, then ∣ 𝐴 ∣≤∣ 𝐵 ∣

Theorem 3 (Addition Principle)

If A and B are finite and disjoint sets, then ∣ 𝐴 ∪ 𝐵 ∣=∣ 𝐴 ∣ +∣ 𝐵 ∣
(Note: This theorem is valid only when A and B are disjoint, i.e. 𝐴 ∩ 𝐵 = ∅)

Theorem 4 (General Addition Principle)

If 𝐴1 , 𝐴2 , 𝐴3 , … , 𝐴𝑛 are mutually disjoint finite sets, then
∣ 𝐴1 ∪ 𝐴2 ∪ 𝐴3 ∪ ⋯ ∪ 𝐴𝑛 ∣=∣ 𝐴1 ∣ +∣ 𝐴2 ∣ +∣ 𝐴3 ∣ + ⋯ +∣ 𝐴𝑛 ∣

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 19 [Link]

Theorem 5 If A is a finite set and B is any set, then

∣ 𝐴 − 𝐵 ∣=∣ 𝐴 ∣ −∣ 𝐴 ∩ 𝐵 ∣
Reason: 𝐴 = (𝐴 − 𝐵) ∪ (𝐴 ∩ 𝐵) and these two sets are disjoint.

1.4.7. The Principle of Inclusion and Exclusion for Sets

Theorem 6: (Principle of Inclusion–Exclusion for Two Sets)
Let A and B be finite sets.
∣ 𝐴 ∪ 𝐵 ∣=∣ 𝐴 ∣ +∣ 𝐵 ∣ −∣ 𝐴 ∩ 𝐵 ∣
Explanation:
• Add elements of A
• Add elements of B
• Subtract common elements counted twice

Theorem 7: (Principle of Inclusion–Exclusion for Three Sets)

Let A, B, C be finite sets.
∣ 𝐴 ∪ 𝐵 ∪ 𝐶 ∣=∣ 𝐴 ∣ +∣ 𝐵 ∣ +∣ 𝐶 ∣ −∣ 𝐴 ∩ 𝐵 ∣ −∣ 𝐴 ∩ 𝐶 ∣ −∣ 𝐵 ∩ 𝐶 ∣ +∣ 𝐴 ∩ 𝐵 ∩ 𝐶 ∣
Key idea:
• Add single sets
• Subtract pairwise intersections
• Add triple intersection (removed too many times)

Theorem 8: Principle of Inclusion–Exclusion for Four Sets

Let A, B, C, D be finite sets.
∣ 𝐴 ∪ 𝐵 ∪ 𝐶 ∪ 𝐷 ∣= ∣ 𝐴 ∣ +∣ 𝐵 ∣ +∣ 𝐶 ∣ +∣ 𝐷 ∣
−(∣ 𝐴 ∩ 𝐵 ∣ +∣ 𝐴 ∩ 𝐶 ∣ +∣ 𝐴 ∩ 𝐷 ∣
+∣ 𝐵 ∩ 𝐶 ∣ +∣ 𝐵 ∩ 𝐷 ∣ +∣ 𝐶 ∩ 𝐷 ∣)
+(∣ 𝐴 ∩ 𝐵 ∩ 𝐶 ∣ +∣ 𝐴 ∩ 𝐵 ∩ 𝐷 ∣
+∣ 𝐴 ∩ 𝐶 ∩ 𝐷 ∣ +∣ 𝐵 ∩ 𝐶 ∩ 𝐷 ∣)
−∣ 𝐴 ∩ 𝐵 ∩ 𝐶 ∩ 𝐷 ∣

Example : Among the integers 1 to 300 find how many are not divisible by 3, not by 5. Find also how many
are divisible by 3 but not by 7.

Solution:
Let A denote the set of integers from 1 to 300 divisible by 3,
B denote the set of integers from 1 to 300 divisible by 5,
and C denote the set of integers from 1 to 300 divisible by 7.

300
∣ A ∣= ⌊ ⌋ = 100
3
300
∣ B ∣= ⌊ ⌋ = 60
5
300
∣ C ∣= ⌊ ⌋ = 42
7
300 300
∣ A ∩ B ∣= ⌊ ⌋=⌊ ⌋ = 20
3×5 15

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 20 [Link]

To find the number of integers not divisible by 3 and not divisible by 5

We have
A ∪ B = U − (A ∩ B)

Using Principle of Inclusion–Exclusion,

∣ A ∪ B ∣=∣ A ∣ +∣ B ∣ −∣ A ∩ B ∣
∣ A ∪ B ∣= 100 + 60 − 20 = 140
∣ U − (A ∪ B) ∣= 300 − 140 = 160

Hence, 160 integers between 1 and 300 are not divisible by 3 and not divisible by 5.

To find the number of integers divisible by 3 but not divisible by 7

∣ A − C ∣=∣ A ∣ −∣ A ∩ C ∣
300 300
∣ A ∩ C ∣= ⌊ ⌋=⌊ ⌋ = 14
3×7 21
∣ A − C ∣= 100 − 14 = 86

Hence, 86 integers between 1 and 300 are divisible by 3 but not divisible by 7.

1.5. Multiset
We know that a set is a collection of well-defined distinct objects.
However, in many practical situations, objects are not distinct. Such collections are called multisets.
Examples:
1. Collection of alphabets in the word “MISSISSIPPI”
𝑚, 𝑖, 𝑖, 𝑖, 𝑖, 𝑠, 𝑠, 𝑠, 𝑝, 𝑝
2. Birth months of students in a class.
Definition:
A collection of objects in which repetition of elements is allowed is called a multiset (or M-set).
To distinguish a set from a multiset, elements of a multiset are written in square brackets.
Example: 𝑎, 𝑎, 𝑏

Multiplicity of an Element
Let S be a multiset and 𝑥 ∈ 𝑆.
The multiplicity of x is the number of times x occurs in S.
It is denoted by 𝜇(𝑥).
Example:
S = 𝑎, 𝑏, 𝑐, 𝑑, 𝑑, 𝑑, 𝑒, 𝑒
μ(a)=1, μ(b)=1, μ(c)=1, μ(d)=3, μ(e)=2

Equality of Multisets
Two multisets A and B are said to be equal iff
𝜇𝐴 (𝑥) = 𝜇𝐵 (𝑥)for all elements x.
Example:
𝑎, 𝑏, 𝑎, 𝑏= 𝑎, 𝑎, 𝑏, 𝑏
but 𝑎, 𝑎≠ 𝑎

Join Community - https:/[Link]/community/ | @SPPU Engineers®

Discrete Mathematics 1 - 21 [Link]

Subset of Multisets
A multiset A is said to be a sub-multiset of B if the multiplicity of each element in A is less than or equal
to its multiplicity in B.
Example:
𝑎⊆ 𝑎, 𝑎
𝑎, 𝑏, 𝑎, 𝑏, 𝑎⊆ 𝑎, 𝑎, 𝑎, 𝑏, 𝑏, 𝑏

Union and Intersection of Multisets

Let A and B be multisets.
• Union (A ∪ B):
Multiplicity of x is the maximum of its multiplicities in A and B.
• Intersection (A ∩ B):
Multiplicity of x is the minimum of its multiplicities in A and B.
Example:
A = 𝑎, 𝑏, 𝑐, 𝑎, 𝑏, 𝑐, 𝑎, 𝑎, 𝑎
B = 𝑎, 𝑎, 𝑏, 𝑏, 𝑏, 𝑏
A ∪ B = 𝑎, 𝑎, 𝑎, 𝑎, 𝑎, 𝑏, 𝑏, 𝑏, 𝑏, 𝑐, 𝑐
A ∩ B = 𝑎, 𝑎, 𝑏

Difference of Multisets
Let A and B be multisets.
The difference A − B is a multiset where the multiplicity of x is
𝜇𝐴 (𝑥) − 𝜇𝐵 (𝑥), if this value is positive.
Examples:
1. A = 𝑎, 𝑎, 𝑏, 𝑎, B = 𝑎, 𝑏
A − B = 𝑎, 𝑎
2. A = 1,2,3,4,2,2,3,3
B = 1,1,1,2,2,2,3,3,3,3,4
A − B = [ \ ] (empty multiset)

Sum of Multisets
The sum of two multisets A and B is denoted by A + B.
Multiplicity of x in A + B is the sum of multiplicities of x in A and B.
Example:
A = 𝑎, 𝑏, 𝑐, 𝑐
B = 𝑎, 𝑎, 𝑏, 𝑏, 𝑐, 𝑐
A + B = 𝑎, 𝑎, 𝑎, 𝑏, 𝑏, 𝑏, 𝑐, 𝑐, 𝑐, 𝑐

Applications of Multisets
1. Used to represent roots of polynomial equations.
Example: Roots of 𝑥 3 + 1 = 0are −1, −1, −1
Multiset: −1, −1, −1
2. Used to represent prime factorization of numbers.
Example: Prime factors of 72 are 2 × 2 × 2 × 3 × 3
Multiset: 2,2,2,3,3
3. Used in computer science in searching and sorting applications.

Join Community - https:/[Link]/community/ | @SPPU Engineers®