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