CSC 2303

Discrete Structure

Dr. A. A. Mu’azu

Course Outline
 Basic Set Theory:
 Basic definitions,
 Relations, Equivalence Relations Partition,
 Ordered Sets.
 Boolean Algebra & Logic,
 Graph theory: Directed and Undirected graphs, Graph
Isomorphism, Basic Graph Theorems,
 Matrices;
 Integer and Real matrices,
 Boolean Matrices,
 Matrices med m, Path matrices. Adjacency Vectors/Matrices:
Path adjacency matrix, Numerical & Boolean Adjacency
matrices.
 Applications to counting, Discrete Probability
Generating Functions,
2

1
Introduction to Discrete Mathematics

 What Is Discrete Mathematics?

 Discrete Math is needed to see mathematical
structures in the object you work with, and
understand their properties.

 This ability is important for software

engineers, data scientists, security and
financial analysts

What Is Discrete Mathematics?

 What it isn’t: continuous

 Discrete: consisting of distinct or
unconnected elements
 Countably Infinite
 Definition Discrete Mathematics
 Discrete Mathematics is a collection of
mathematical topics that examine and
use finite or countably infinite
mathematical objects.

2
 What Is Discrete Mathematics?

 Much of discrete mathematics is

devoted to the study of discrete
structures, used to represent
discrete objects.
 Many important discrete structures
are built using sets, which are
collections of objects.

What is Discrete Structure?

 Discrete Objects
 Separated from each other (Opposite of
continuous)
 e.g., integers, people, house,
 Vs. Continuous objects: e.g., real number

 Discrete Structures
 The abstract mathematical structures used to
represent discrete objects and relationships
between the objects e.g. sets, relations, graphs

3
Why do we study Discrete Structures?

 Information is stored and manipulated by

computers in a discrete fashion. 0101101…
 As a student in computer science major, you
need to know the basic language and conceptual
foundation for all of the computer science, i.e.,
Discrete Structures!
 Discrete structure concepts are also widely
used throughout math, science, engineering,
economics, biology, etc., …
 Get training for rational thought!

Why do we need to study discrete

structures?

 Concepts and notations from discrete

mathematics are useful in studying and
describing objects and problems in all
branches of computer science,
 such as computer algorithms, programming
languages, cryptography, automated theorem
proving, and software development

4
Uses of Discrete Structures in Computer
Science
 Networking
 Database
 Image Processing
 Programming Languages
 Compilers & Interpreters
 Software Engineering
 Artificial Intelligence
 Computer Architecture
 Operating Systems
 Security & Cryptography
 Advanced Algorithms & Data Structures
 Graphics & Animation
 ……
9

Outline
 Introduction
 Sets
 Logic & Boolean Algebra
 Proof Techniques
 Counting Principles
 Combinatorics
 Relations,Functions
 Graphs/Trees
 Boolean Functions, Circuits

10

5
 SET
Sets: Learning Objectives
 Learn about sets

 Explore various operations on sets

 Become familiar with Venn diagrams

 CS:
 Learn how to represent sets in computer
memory

 Learn how to implement set operations in

programs 11

Sets
 Definition: Well-defined collection of distinct objects
 Members or Elements: part of the collection
 Roster Method: Description of a set by listing the
elements, enclosed with braces
 Examples:
 Vowels = {a,e,i,o,u}

 Primary colors = {red, blue, yellow}

 Membership examples
 “a belongs to the set of Vowels” is written as:
a  Vowels
 “j does not belong to the set of Vowels:
j  Vowels
12

6
 Set notations
 The notation of {...} describes a set. Each
member or element is separated by a
comma.
 E.g., S = {apple, pear, grape}
 S is a set
 The members of S are: apple, pear, grape
 Order and repetition do not matter in a
set.
 The following expressions are equivalent:
 {1, 3, 9}
 {9, 1, 3}
3/3/2023
 {1, 1, 3, 3, 9} 13

Sets
 Set-builder method

 A = { x | x  S, P(x) } or A = { x  S | P(x) }

 A is the set of all elements x of S, such that x

satisfies the property P

 Example:

 If X = {2,4,6,8,10}, then in set-builder

notation, X can be described as

X = {n  Z | n is even and 2  n  10}

14

7
 Sets
 Standard Symbols which denote sets of numbers
 N : The set of all natural numbers (i.e.,all positive integers)
 Z : The set of all integers
 Z+ : The set of all positive integers
 Z* : The set of all nonzero integers
 E : The set of all even integers
 Q : The set of all rational numbers
 Q* : The set of all nonzero rational numbers
 Q+ : The set of all positive rational numbers
 R : The set of all real numbers
 R* : The set of all nonzero real numbers
 R+ : The set of all positive real numbers
 C : The set of all complex numbers
 C* : The set of all nonzero complex numbers

15

Sets
 Subsets

 “X is a subset of Y” is written as X  Y

 “X is not a subset of Y” is written as X Y

 Example:

 X = {a,e,i,o,u}, Y = {a, i, u} and

Z= {b,c,d,f,g}

 Y  X, since every element of Y is an element of X

 Y Z, since a  Y, but a  Z

16

8
Sets
 Superset
 X and Y are sets. If X  Y, then “X is contained in
Y” or “Y contains X” or Y is a superset of X,
written Y  X
 Proper Subset
 X and Y are sets. X is a proper subset of Y if X 
Y and there exists at least one element in Y that
is not in X. This is written X  Y.
 Example:
 X = {a,e,i,o,u}, Y = {a,e,i,o,u,y}

 X  Y , since y  Y, but y  X

17

Sets

 Set Equality
 X and Y are sets. They are said to be equal if every
element of X is an element of Y and every element of Y is
an element of X, i.e. X  Y and Y  X
 Examples:

 {1,2,3} = {2,3,1}

 X = {red, blue, yellow} and Y = {c | c is a primary

color} Therefore, X=Y
 Empty (Null) Set
 A Set is Empty (Null) if it contains no elements.

 The Empty Set is written as 

 The Empty Set is a subset of every set

18

9
Sets

 Finite and Infinite Sets

 X is a set. If there exists a nonnegative integer n such
that X has n elements, then X is called a finite set with n
elements.
 If a set is not finite, then it is an infinite set.
 Examples:
 Y = {1,2,3} is a finite set
 P = {red, blue, yellow} is a finite set
 E , the set of all even integers, is an infinite set
  , the Empty Set, is a finite set with 0 elements

19

Sets
 Cardinality of Sets
 Let S be a finite set with n distinct elements,
where n ≥ 0. Then |S| = n , where the
cardinality (number of elements) of S is n
 Example:
 If P = {red, blue, yellow}, then |P| = 3
 Singleton
 A set with only one element is a singleton
 Example:

 H = { 4 }, |H| = 1, H is a singleton

20

10
Sets
 Power Set
 For any set X ,the power set of X ,written P(X),is
the set of all subsets of X
 Example:
 If X = {red, blue, yellow}, then P(X) = {  ,
{red}, {blue}, {yellow}, {red,blue}, {red,
yellow}, {blue, yellow}, {red, blue, yellow} }

 Universal Set
 An arbitrarily chosen, but fixed set

21

Sets
 Venn Diagrams
 Abstract visualization
of a Universal set, U
as a rectangle, with all
subsets of U shown as
circles.
 Shaded portion
represents the
corresponding set
 Example:
 In Figure 1, Set X,
shaded, is a subset
of the Universal set,
U

22

11
 Set Operations and Venn
Diagrams
 Union of Sets

Example: If X = {1,2,3,4,5} and Y = {5,6,7,8,9}, then

XUY = {1,2,3,4,5,6,7,8,9}

23

Sets
 Intersection of Sets

Example: If X = {1,2,3,4,5} and Y = {5,6,7,8,9}, then X ∩ Y = {5}

24

12
 Sets
 Disjoint Sets

Example: If X = {1,2,3,4,} and Y = {6,7,8,9}, then X ∩ Y = 

25

Sets
 Difference

• Example: If X = {a,b,c,d} and Y =

{c,d,e,f}, then X – Y = {a,b} and Y – X =
{e,f}

26

13
 Sets

 Complement

The complement of a set X with respect to a universal set U,

denoted by X, is defined to be X = {x |x  U, but x  X}

Example: If U = {a,b,c,d,e,f} and X = {c,d,e,f}, then X = {a,b}

27

Sets

28

14
Sets
 Ordered Pair
 X and Y are sets. If x  X and y  Y, then an
ordered pair is written (x,y)
 Order of elements is important. (x,y) is not
necessarily equal to (y,x)
 Cartesian Product
 The Cartesian product of two sets X and Y ,written X
× Y ,is the set
 X × Y ={(x,y)|x ∈ X , y ∈ Y}
 For any set X, X ×  =  =  × X
 Example:
 X = {a,b}, Y = {c,d}
 X × Y = {(a,c), (a,d), (b,c), (b,d)}
 Y × X = {(c,a), (d,a), (c,b), (d,b)}

29

30

15
 Computer Representation of Sets

 A Set may be stored in a computer in an array as an

unordered list
 Problem: Difficult to perform operations on the set.

 Linked List
 Solution: use Bit Strings (Bit Map)
 A Bit String is a sequence of 0s and 1s
 Length of a Bit String is the number of digits in the
string
 Elements appear in order in the bit string
 A 0 indicates an element is absent, a 1 indicates
that the element is present
 A set may be implemented as a file

31

Computer Implementation of Set

Operations

 Bit Map
 File
 Operations
 Intersection
 Union
 Element of
 Difference
 Complement
 Power Set

32

16
Special “Sets” in CS

 Multiset
 Ordered Set

33

Outline

 Introduction
 Sets
 Logic & Boolean Algebra
 Proof Techniques
 Counting Principles
 Combinatorics
 Relations,Functions
 Graphs/Trees
 Boolean Functions, Circuits

34

17
 Logic: Learning Objectives
 Learn about statements (propositions)

 Learn how to use logical connectives to combine statements

 Explore how to draw conclusions using various argument

forms

 Become familiar with quantifiers and predicates

 CS

 Boolean data type

 If statement

 Impact of negations

 Implementation of quantifiers
35

Mathematical Logic
 Definition: Methods of reasoning, provides rules
and techniques to determine whether an
argument is valid
 Theorem: a statement that can be shown to be
true (under certain conditions)
 Example: If x is an even integer, then x + 1 is an
odd integer
 This statement is true under the condition that x is an
integer is true

36

18
 Mathematical Logic
 A statement, or a proposition, is a declarative sentence
that is either true or false, but not both
 Uppercase letters denote propositions
 Examples:
 P: 2 is an even number (true)
 Q: 7 is an even number (false)
 R: A is a vowel (true)
 The following are not propositions:
 P: My cat is beautiful
 Q: My house is big

37

Propositional Logic
 Proposition: A proposition is a declarative statement
( a statement that declares a fact) that is either
TRUE or FALSE, but not both.
 The area of logic that deals with propositions is
called propositional logic.

Propositions Not Propositions

1. Riyadh is the capital 1. How many students in
of Saudi Arabia this class?
2. Every cow has 4 legs. 2. Bring me coffee!
3. 3 + 2 = 32 3. X + 2 = 3
4. 4 + 3 = 7 4. Y + Z = X
38

19
 Propositional Logic - Applications
 We are using propositional logic as a foundation for
formal proofs.

 Propositional logic is also the key to writing good

code…you can’t do any kind of conditional (if)
statement without understanding the condition
you’re testing.

 All the logical connectives we will discuss are also

found in hardware and are called “gates.”

39

Mathematical Logic
 Truth value
 One of the values “truth” (T) or “falsity” (F)
assigned to a statement
 Negation
 The negation of P, written P, is the statement
obtained by negating statement P
 Example:

 P: A is a consonant
 P: it is the case that A is not a consonant
 Truth Table
P P
T F
F T

40

20
 Mathematical Logic
 Conjunction
 Let P and Q be statements. The conjunction of P and
Q, written P ^ Q , is the statement formed by joining
statements P and Q using the word “and”
The statement P ^ Q is true if both p and q are true;

otherwise P ^ Q is false
 Example: p: “Today is Friday”
q: “It is raining today”
p  q: “Today is Friday and it is raining today”
 Truth table for conjunction:
p q pq
F F F
F T F
T F F
T T T
41

Mathematical Logic
 Disjunction
 Let P and Q be statements. The disjunction of P and
Q, written P v Q , is the statement formed by joining
statements P and Q using the word “or”
 The statement P v Q is true if at least one of the
statements P and Q is true; otherwise P v Q is false
 The symbol v is read “or”

 Truth Table for Disjunction:

 Example: p: “Today is Friday”
q: “It is raining today”
p  q: “Today is Friday or it is raining today”
 Truth table for disjunction: p q pq
F F F
F T T
T F T
T T T 42

21
 Propositional Logic – Exclusive Or
 Exclusive Or: Let p and q be two propositions. The
exclusive or of p and q, denoted by p ⊕ q, is the
proposition that is true when exactly one of p and q
is true, otherwise false.
 Truth table for Exclusive Or: p q p⊕q
F F F
F T T
T F T
T T F

43

Mathematical Logic
 Implication
 Let P and Q be statements. The statement “if P then Q”
is called an implication or condition.
 The implication “if P then Q” is written P  Q
 P is called the hypothesis, Q is called the conclusion
 Truth Table for Implication:

44

22
 Mathematical Logic
 Implication
 Let P: Today is Sunday and Q: I will wash the car.
 PQ:
If today is Sunday, then I will wash the car
 The converse of this implication is written Q  P
If I wash the car, then today is Sunday
 The inverse of this implication is P  Q
If today is not Sunday, then I will not wash the car
Q  P
 The contrapositive of this implication is
If I do not wash the car, then today is not Sunday

45

Mathematical Logic
 Biimplication
 Let P and Q be statements. The statement “P if and only if
Q” is called the biimplication or biconditional of P and Q
 The biconditional “P if and only if Q” is written P  Q
 “P if and only if Q”
 Truth Table for the Biconditional:

46

23
 Propositional Logic – Conditional
Statement
 It corresponds to English “if p then q” or “p implies q.”
 Conditional: Let p and q be two propositions. The
conditional statement (implication) p  q is the
proposition “if p, then q”. The conditional statement
p  q is false when p is true and q is false, otherwise
true.
 Example: If it is raining, then it is cloudy.
 If I am elected, then I will lower taxes.
 If you get 100% in the final, then you will get
Grade A+. p q pq
 Truth table for implication: F F T
F T T
T F F
T T T 47

Propositional Logic - Special

Definitions
 Converse: q  p is converse of p  q.
Ex.: p  q: “If it is noon, then I am hungry.”
q  p: “If I am hungry, then it is noon.”
 Contrapositive: q  p is contapositive of p  q.
Ex.: p  q: “If it is noon, then I am hungry.”
q  p: “If I am not hungry, then it is
not noon.”
 Inverse: p  q is inverse of p  q.
Ex.: p  q: “If it is noon, then I am hungry.”
p  q: “If it is not noon, then I am not
hungry.”
p  q has same truth values as q  p
48

24
 Propositional Logic - Questions
 Q1: Give some examples of p  q, then tell what is
 qp
 q  p
 p  q

 Q2: State the converse, contrapositive, and inverse

of each of them
 If it rains today, then I will stay at home
 I come to class whenever there is going to be a examination
 A positive integer is prime only if it has no divisors other
than 1 and itself.

49

Propositional Logic – Biconditional

Statement
 It corresponds to English “p if and only if q”.
 Biconditional: Let p and q be two propositions. The
biconditional statement (bi-implication) p ↔ q is
the proposition “p if and only if q”. The
biconditional statement p ↔ q is true when p and
q have the same truth values, otherwise false.
 p ↔ q has same truth value as (p q)  (q  p).
 Example: p: “You can take the flight”
q : “You buy a ticket” p q p↔q
p↔q : “You can take the F F T
flight if and only if F T F
you buy a ticket” T F F
T T T
50

25
 Mathematical Logic
 Precedence of logical
connectives is:

  highest


^ second highest
 v third highest

 → fourth highest

 ↔ fifth highest

51

Propositional Logic – Precedence

 Precedence of Logical Operators: Operator Precedence
¬ 1
p p p  p p  p Λ 2
ν 3
F T T F
→ 4
T F T F
↔ 5
 A compound proposition that is:
(1) always true is called a tautology
(2) always false is called a contradiction
(3) neither a tautology nor a contradiction is called
contingency or satisfiable.

52

26
 Mathematical Logic
 Tautology
 A statement formula A is said to be a tautology
if the truth value of A is T for any assignment of
the truth values T and F to the statement
variables occurring in A
 Contradiction
 A statement formula A is said to be a
contradiction if the truth value of A is F for any
assignment of the truth values T and F to the
statement variables occurring in A

53

Mathematical Logic
 Logically Implies
 A statement formula A is said to logically imply a
statement formula B if the statement formula A → B is a
tautology. If A logically implies B, then symbolically we
write A → B
 Logically Equivalent
 A statement formula A is said to be logically equivalent
to a statement formula B if the statement formula
A ↔ B is a tautology. If A is logically equivalent to B ,
then symbolically we write A B

54

27
 Two-Element Boolean Algebra

The Boolean Algebra on B= {0, 1} is defined as follows:

+01 · 01 ¯
0 01 0 00 0 1
1 11 1 01 1 0

55

Duality and the Fundamental

Boolean Algebra Properties
 Duality
 The dual of any Boolean theorem is also a theorem.

 Parentheses must be used to preserve operator

precedence.

© Dr. Eric Gossett 56

28
 Logic and CS
 Logic is basis of ALU (Boolean Algebra)
 Logic is crucial to IF statements
 AND
 OR
 NOT
 Implementation of quantifiers
 Looping
 Database Query Languages
 Relational Algebra
 Relational Calculus
 SQL

57

29