Department of Computer Science and Engineering (CSE)

UNIT- 1
DISCRETE MATHEMATICS
CST-253

University Institute of Engineering

1

Campus: Gharuan, Mohali

 Department of Computer Science and Engineering (CSE)

Course Objectives

• Identify and apply basic concepts of set theory, arithmetic,

logic, proof techniques, binary relations, graphs and trees.

• Apply the knowledge and skills obtained to investigate and

solve a variety of discrete mathematical problems

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

Course Outcome

• some fundamental mathematical concepts and terminology.

• how to count some different types of discrete structures.

• Techniques for constructing mathematical proofs,

illustrated by discrete mathematics examples.

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)

SETS

University Institute of Engineering (UIE)

 Department of Computer Science and Engineering (CSE)
Defining Sets
Definition: A set is an unordered collection of objects.
Definition: A set is an unordered collection of well defined objects.

The objects in a set are called the elements or members

of the set S, and we say S contains its elements.

We can define a set by directly listing all its elements.

e.g. S = {2, 3, 5, 7, 11, 13, 17, 19},

S = {CSC1130, CSC2110, ERG2020, MAT2510}

After we define a set, the set is a single mathematical object,

and it can be an element of another set.

University Institute of Engineering

e.g. S = {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}
 Department of Computer Science and Engineering (CSE)
Examples of Sets

Well known sets: • the set of all real numbers,

• the set of all complex numbers,
• the set of all integers,
• the set of all positive integers
• empty set, , the set with no elements.

Other examples:

The set of all polynomials with degree at most three: {1, x, x2, x3, 2x+3x2,…}.

The set of all n-bit strings: {000…0, 000…1, …, 111…1}

The set of all triangles without an obtuse angle: { , ,… }

The set ofInstitute

University all graphs with four nodes: {
of Engineering , , , ,…}
 Department of Computer Science and Engineering (CSE)
Size of a Set

In this course we mostly focus on finite sets.

Definition: The size of a set S, denoted by |S|,

is defined as the number of elements contained in S.

e.g. if S = {2, 3, 5, 7, 11, 13, 17, 19}, then |S|=8.

if S = {CSC1130, CSC2110, ERG2020, MAT2510}, then |S|=4.
if S = {{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}}, then |S|=6.

University Institute of Engineering

 Department of Computer Science and Engineering (CSE)
Subset

Definition: Given two sets A and B, we say A is a subset of B,

denoted by , if every element of A is also an element of B.

A B
not a subset

• If A={4, 8, 12, 16} and B={2, 4, 6, 8, 10, 12, 14, 16}, then but

• because every element in A is an element of A.

• for any A because the empty set has no elements.

• If A is the set of prime numbers and B is the set of odd numbers, then

University Institute of Engineering

Fact: If , then |A| <= |B|.
 Department of Computer Science and Engineering (CSE)
Proper Subset, Equality

Definition: Given two sets A and B, we say A is a proper subset of B,

denoted by , if every element of A is an element of B,
But there is an element in B that is not contained in A.

B Fact: If , then |A| < |B|.

A

Definition: Given two sets A and B, we say A = B if and .

A B
Fact: If A = B, then |A| = |B|.

University Institute of Engineering

 Department of Computer Science and Engineering (CSE)
Exercises

1. ?

2. {3} {5,7,3}?

3.  every set?

4. {1,2} {{1,2}, {2,3}, {3,1}}?

5. {a} = {{a}}?

6. If A B and B C, then A C?

7. If A B and B C, then A C?

University Institute of Engineering

 Department of Computer Science and Engineering (CSE)
Basic Operations on Sets

Let A, B be two subsets of a universal set U

(depending on the context U could be R, Z, or other sets).

intersection:

Defintion: Two sets are said to be disjoint if

their intersection is an empty set.

e.g. Let A be the set of odd numbers, and B be the set of even numbers.
Then A and B are disjoint.

union:

University
Fact: Institute of Engineering
 Department of Computer Science and Engineering (CSE)
Basic Operations on Sets

difference:

Fact:

complement:

e.g. Let U = Z and A be the set of odd numbers.

Then is the set of even numbers.

Fact: If , then
University Institute of Engineering
 Department of Computer Science and Engineering (CSE)
Examples

A = {1, 3, 6, 8, 10} B = {2, 4, 6, 7, 10}

A B = {6, 10}, A B = {1, 2, 3, 4, 6, 7, 8, 10} A-B = {1, 3, 8}

Let U = { x Z | 1 <= x <= 100}.

A={x U | x is divisible by 3}, B = { x U | x is divisible by 5}

A B={x U | x is divisible by 15}

A B={x U | x is divisible by 3 or is divisible by 5 (or both)}

A–B={x U | x is divisible by 3 but is not divisible by 5 }

Exercise:
University compute
Institute |A|, |B|, |A B|, |A
of Engineering B|, |A – B|.
 Department of Computer Science and Engineering (CSE)
Partitions of Sets

Two sets are disjoint if their intersection is empty.

A collection of nonempty sets {A1, A2, …, An} is a partition of a set A

if and only if

A1, A2, …, An are mutually disjoint (or pairwise disjoint).

e.g. Let A be the set of integers.

A1 = {x A | x = 3k+1 for some integer k}
A2 = {x A | x = 3k+2 for some integer k}
A3 = {x A | x = 3k for some integer k}
University Institute of Engineering
Then {A1, A2, A3} is a partition of A
 Department of Computer Science and Engineering (CSE)
Power Sets

power set: pow ( A) :: {S | S  A}

In words, the power set pow(A) of a set A
contains all the subsets of A as members.

pow({a,b}) = {, {a}, {b}, {a,b}}

pow({a,b,c}) = {, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c}}

pow({a,b,c,d}) = {, {a}, {b}, {c}, {d},

{a,b}, {a,c}, {b,c}, {a,d}, {b,d}, {c,d},
{a,b,c}, {a,b,d}, {a,c,d}, {b,c,d}, {a,b,c,d}}

University Institute of Engineering

Fact (to be explained later): If A has n elements, then pow(A) has 2n elements.
 Department of Computer Science and Engineering (CSE)
Cartesian Products

Definition: Given two sets A and B, the Cartesian product A x B is the

set of all ordered pairs (a,b), where a is in A and b is in B. Formally,

Ordered pairs means the ordering is important, e.g. (1,2) ≠ (2,1)

e.g. Let A be the set of letters, i.e. {a,b,c,…,x,y,z}.

Let B be the set of digits, i.e. {0,1,…,9}.

AxA is just the set of strings with two letters.

BxB is just the set of strings with two digits.

AxB is the set of strings where the first character is a letter

University Institute of Engineering
and the second character is a digit.
 Department of Computer Science and Engineering (CSE)
Cartesian Products

The definition can be generalized to any number of sets, e.g.

Using the above examples, AxAxA is the set of strings with three letters.

Our ID card number has one letter and then six digits,
so the set of ID card numbers is the set AxBxBxBxBxBxB.

Fact: If |A| = n and |B| = m, then |AxB| = nm.

Fact: If |A| = n and |B| = m and |C| = l, then |AxBxC| = nml.

Fact: |AInstitute
University 1xA2x…xA | = |A1|x|A2|x…x|Ak|.
of kEngineering
 Department of Computer Science and Engineering (CSE)
Exercises

1. Let A be the set of prime numbers, and let B be the set of even numbers.
What is A B and |A B|?

2. Is |A B| > |A| > |A B| always true?

3. Let A be the set of all n-bit binary strings, Ai be the set of all n-bit
binary strings with i ones. Is (A1, A2, …, Ai, …, An) a partition of A?

4. Why the name Cartesian product?

5. Let A = {x,y}. What is pow(A)xpow(A) and |pow(A)xpow(A)|?

University Institute of Engineering
 Department of Computer Science and Engineering (CSE)
Set Identities

Some basic properties of sets, which are true for all sets.

University Institute of Engineering

 Department of Computer Science and Engineering (CSE)
Set Identities

Distributive Law: (1)

(2)

A B A B

C C
University Institute of Engineering
(1) (2)
 Department of Computer Science and Engineering (CSE)
Set Identities

Distributive Law:

We can also verify this law more carefully

L.H.S

S1 S2
S3
A B
S4
S5 S6
R.H.S.
S7

C
University Institute of Engineering
 Department of Computer Science and Engineering (CSE)
Set Identities

De Morgan’s Law:

University Institute of Engineering

 Department of Computer Science and Engineering (CSE)
Set Identities

De Morgan’s Law:

University Institute of Engineering

 Department of Computer Science and Engineering (CSE)
Disproof

1 2 3 1 2 3
A B A B
4 5 6 4 5 6

7 7

C C

We can easily construct a counterexample to the equality,

by putting a number in each region in the figure.
Let A = {1,2,4,5}, B = {2,3,5,6}, C = {4,5,6,7}.
University Institute of Engineering
Then we see that L.H.S = {1,2,3,4} and R.H.S = {1,2}.
 Department of Computer Science and Engineering (CSE)
Algebraic Proof

Sometimes when we know some rules, we can use them to prove

new rules without drawing figures.

e.g. we can prove without drawing figures.

by using DeMorgan’s rule on A and B

University Institute of Engineering