Automata M1-M3 Flashcards
as a collection well defined objects, called elements having certain common property
Sets
represented by a CAPITAL letter, i.e. A, B, C
Sets
In sets, order of elements is _____
insignificant
In sets, it does not matter how often the same element is ________
listed (repetition doesn’t count)
Two types of Method of Set Notation:
Roster / Tabular / List Method
Set Builder / Rule Method
Venn Diagram
the set is represented by actually listing the elements which belong to it
Roster / Tabular / List Method
separated by comma (,) and enclosed between pair of curly brackets { }.
Roster / Tabular / List Method
The order of writing the elements of set is immaterial
Roster / Tabular / List Method
Roster method is used only when the number of elements in the set is _______
finite
sometimes a set is defined by stating property (P) which characterizes all the elements of the set.
Set Builder / Rule Method
the elements must satisfy a given rule or condition
Set Builder / Rule Method
It represents relation and operator using the plan geometrical figures such as rectangle, circle, ellipse
Venn Diagram
Types of Sets
Finite Set
Infinite Set
Empty Set
Unit Set
Subset (⊆)
Proper Subset
Family Set
Power Set
Universal Set
Complement
a set whose elements are countable
Finite Set
a set whose elements are not countable
Infinite Set
a set having no element.
Empty Set
Its also called as null set or void set
Empty Set
It is denoted by Ø or {}.
Empty Set
a set containing only one element.
Unit Set
It is also called a singleton.
Unit Set
If each element of the set A is also an element of set B.
Subset (⊆)
The set A ⊂ B and A ≠ B, then A is called a ______ of B
Proper Subset
or Set A is a ______ of set B if there is at least one element in B not contained in A.
proper subset
class of sets or the set of sets
Family Set
the set of all subsets of a given set.
Power Set
It is denoted by P(A) where number of subsets equal to 2^|A|.
Power Set
a set which contains all objects, including itself
Universal Set (U)
The ________ of set A, written as “A is the set containing everything that is not in A.”
Complement
N = {0, 1, 2, 3, …}
Natural Numbers
Z = {…, -2, -1, 0, 1, 2, …}
Integers
Z^+ = {1, 2, 3, 4, …}
Positive Integers
Q = {1.5, 2.6, -3.8, 15, …}
Rational Numbers
R = {47.3, -12, π, …}
Real Numbers
For numbers with decimal places, it must be ____
terminating or as recurring decimal digits for non-terminating type
Set Relations:
Equal Sets
Equivalent Sets
Disjoint Sets
two sets A and B consisting of the same elements and same cardinality
Equal Sets
two sets A and B having the same cardinality.
Equivalent Sets
the two sets having no common elements
Disjoint Set
Set Operations:
Union
Intersection
Sett Difference
A U B = {x | (x ∊ A) or (x ∊ B) }
Union
The ______ of sets A and B, written A ⋂ B, is a set that contains exactly those elements that are in both A and B
Intersection
A ⋂ B = {x | (x ∈ A) and (x ∈ B)}
Intersection
The _______ of set A and set B, written as A - B, is the set that contains everything that is in A but not in B.
Set Difference
A - B = {x | x ∈ A and x ∉ B}
Set Difference
–– is what
complement
A ____ on sets S and T is a set of ordered pairs (s, t),
relation
A relation on sets S and T is a set of ordered pairs (s, t), where:
s ∊ S (s is a member of S)
t ∊ T
S and T need not be different
The set of all first elements is the “domain” of the relation and
The set of all second elements is the “range” of the relation
R1 = {(a, b) | (a < b)} = {(1,2), (1,3), (2,3)}
R2 = {(a, b) | a = b)} = {(1,1), (2,2), (3,3)}
R3 = {(a, b) | b = 4a) = { }
R4 = {(1,1), (1,2), (1,3), (2,1), (2,2), (2,3), (3,1), (3,2), (3,3)}
R2 is called identity relation
R3 is called void relation
R4 is called universal relation
A subset R of A is called an equivalence relation on A if R satisfies the following conditions:
Equivalence Relation
A subset R of A is called an equivalence relation on A if R satisfies the following conditions:
(i) (a,a) ∊ R for all a ∊ A (R is reflexive)
(ii) If (a, b) ∊ R, then (b, a) ∊ R, then (a, b) ∊ R (R is symmetric)
(iii) If (a, b) ∊ R and (b, c) ∊ R, then (a, c) ∊ R (R is transitive)
A ______is a way of matching the members of a set “A” to a set “B”:
function
Each element of A should be associated to exactly one element of B, though more A may be associated in B.
Functions
Every element of A must be associated with unique element of B
Functions
May be some elements of set B which are not assigned to any element of set A
Functions
Every _____ is a ______
Not all _____ are _____
function, relation
relation. function
One-to-one (______) correspondence function
injective
if each element of B is f image of at least one element of A f(a) = b
Onto (surjective)
(if there is one element of B which is not f image of any element of A)
Into function
(mapped to the same single element of B)
Constant Function
With a constant function, for any two points in the interval, a change in x results in a zero change in f(x)
Constant Function
mapped into itself
Identity
Representations of Relations
Relation as arrow diagram
Relation as table
Relation as matrix
Relation as Directed Graph
Types of Function
One-to-one (injective) correspondence function
Onto (Surjective)
Into
Constant
Identity
Invertible Function
Inclusion Function
A function whose domain is a subset of its codomain, and for which all the elements in its domain are fixed points
Inclusion Function
A _____ is a bunch of vertices (Nodes) which are represented by circles and are connected by edges represented by lines
Graph
are undirected graphs
Trees
Any two vertices are connected by exactly one simple path.
Trees
A _____ also does not contain cycle
tree
A _____ G = (V, E)
simple graph
{set of all vertices} - not empty
V
{set of all edges} - not empty
E
{subsets of V with cardinality 2}
E
2 Types of Digraph
In-degree
Out-degree
a pair of vertices that determine an edge are ____ vertices
“adjacent”
in a graph G consists of a pair (V, E) of sequences
Path
is a path that begins and ends at the same vertex
Circuit
A path is called ______ if no vertex appears more than once in the vertex sequence
simple
a graph is called ______ if there is a path from any vertex to any other vertex in the graph, otherwise, the graph is “disconnected”.
Connected Graph
if the graph is ______, the various connected pieces are called the components of the graph
Component
