CS381 Introduction to Discrete Structures
Legend
Color Code
Bold red indicates a term being defined or important item.
Underlined bold italic blue or
underlined blue indicates a link. If it is a terminology, it has already been introduced earlier.
Bold green indicates a term to be defined later or a heading
Bold black is used for emphasis, and section headings.
Organization of Contents Page
Each contents page consists of three or four items: Subjects to be Learned, Contents,
in many cases, Test, and Links to Next subject, to Schedule, and to Table of Contents.
Symbols
Red and purple symbols below
show text symbols you can use
in your e-mail, MS Word file, with NetMeeting to communicate with your
instructor.
Language, Automata:
, \alpha : usually denotes a string in this course.
, \beta : usually denotes a string in this course.
, \delta : usually denotes a transition function in this course.
, \sigma : usually denotes a symbol in an alphabet in this course.
, \Delta : usually denotes a blank space in this course.
, \Gamma : usually denotes a set of stack symbols in this course.
, \Lambda : usually denotes an empty string in this course.
, \Pi : usually denotes a partition in this course.
, \Sigma : usually denotes an alphabet in this course.
, \goto : usually denotes a (one step) transition in this course.
Logic:
, ~ : logical not
, ^ : logical and
, V : logical or
, -> : logical imply
, <-> : logical if and only if (equivalent)
, => : logical tautologically imply
, <=> : logical tautologically equivalent
, \A : logical for all
, \E : logical for some (there exists)
Sets:
, \in : belongs to
,
\not\in : does not belong to
, @ : empty set
U , : universal set
, \subset : proper subset
, \not\subset : not a proper subset
, \subseteq : subset
,
\not\subseteq : not a subset
, \cup : set union
Ai , \cup(i=1 to n) A_i : union of n sets
, \cap : set intersection
Ai , \cap(i=1 to n) A_i : intersection of n sets
, \bar A : complement of set A
(A) , P(A) : power set of set A
, X : Cartesian product
Ai , X(i=1 to n) A_i : cartesian product of n sets
Relation:
< a, b > : ordered pair
< a1, a2, ..., an > : ordered n-tuple
, <= : precedes (partial order)
Functions:
xi , Sum(i=1 to n) x_i : sum of n xi's
O(f) , O(f) : of order smaller than or equal to f
o(f) , o(f) : of order smaller than f
(f) , Omega : of order greater than or equal to f
(f) , omega : of order greater than f
(f) , Theta : of the same order as f
f(x) , lim(x -> inf) f(x) : limit of f as x goes to infinity