Concepts of Computer
Science Theory
CECS 329
Book chapter
• 0.2 Mathematical Notions and Terminology
• 0.3 Definitions, Theorems, and Proofs
Overview
• Sets
• Sequences and tuples
• Functions and relations
• Graphs
• Undirected graph
• Directed graph
• Subgraph
• Path
• Simple cycle
• Strings and languages
• Boolean logic
Image credit: google
Regarding notation
•1+1=2
•*#*@~
Python
List
How to describe this
process in English?
Sets
• A set is a group of objects represented as a unit.
• Sets may contain any type of object, including numbers, symbols,
and even other sets.
• The objects in a set are called its elements or members.
• Sets may be described formally in several ways
• One way is by listing a set’s elements inside braces.
• describe a set containing elements according to some rule
the set of perfect squares
M. Sipser, “Introduction to the theory of computation”
c
a d
b
https://slideplayer.com/slide/4697375/
D. Nickovic, X. et al, “Shape Expressions for Specifying and Extracting Signal Features”
Sets
• The symbols and denote set
membership and nonmembership.
• An infinite set contains infinitely
many elements
Image credit: google
Venn diagram
Overlapping circles indicate common elements
Image credit: google
Power set
• The power set of A is the set of all subsets of A.
Sequences and Tuples
• A sequence of objects is a list of these objects in some
order.
• The order matters in a sequence.
is not the same as
• Repetition matters in a sequence.
is not the same as
(1 , 2)
(2 , 1)
Sequences and Tuples
• Finite sequences often are called tuples. A
sequence with elements is a -tuple.
is a -tuple
• A -tuple is also called an ordered pair.
• Cartesian product or cross product
• If A and B are two sets, the Cartesian
product or cross product of A and B, written ,
is the set of all ordered pairs wherein the
first element is a member of A and the
second element is a member of B.
If we have the Cartesian product of a set with
itself, we use the shorthand
Functions and relations
• A function is an object that sets up an input–output
relationship.
• A function takes an input and produces an output.
Input: Coin, ItemID
Output: food
Functions and relations
• A function (mapping) is an object that sets up an
input–output relationship.
• A function takes an input and produces an output.
If is a function whose
Input: Coin, ItemID output value is when the
input value is , we write
Output: food
We say that maps a to b
The notation for saying that is a
function with domain and range
• The set of possible inputs to the function is called its
domain.
• The outputs of a function come from a set called its
range.
…
Equivalence relation
• Friend(C,D)
Graphs
• An undirected graph, or simply a graph, is a set of
points with lines connecting some of the points.
• The points are called nodes or vertices, and the lines
are called edges.
• The number of edges at a particular node is the degree
of that node.
𝐺 =(𝑉 , 𝐸 )
• In a graph that contains nodes and , the pairrepresents
the edge that connects and.
• If is the set of nodes of and is the set of edges
we say
({1 ,2 , 3 , 4 },{(1 , 2),(1 , 3), (1 , 4),(2 , 3),(2 , 4 ),(3 , 4 )})
https://rekep-robot.github.io/
Subgraph
• We say that graph is a subgraph of graph if the nodes
of are a subset of the nodes of , and the edges of are
the edges of on the corresponding nodes.
Path, cycle, tree
Directed graph
• A directed graph has arrows instead of lines, as shown
in the following figure. The number of arrows pointing
from a particular node is the outdegree of that node,
and the number of arrows pointing to a particular node
is the indegree.
(1,2), (1,5), (2,1), (2,4)
(5,4), (5,6), (6,1), (6,3)
In class practice
{ 1 , 10,100
{𝑥 ∈ ℤ ∣ 𝑥> 5 }
{𝑥 ∈ ℤ ∣ 𝑥< 5 }
{ aba
{ 𝜖 }
{ }𝑜𝑟 Ø
𝑁𝑜
𝑌𝑒𝑠
{𝑥 , 𝑦 , 𝑧
{𝑥 , 𝑦
{(x , x),(x , y),( y , x),( y, y),(z , x),(z , y)
P( B)={∅ , {x },{ y },{ x , y }
