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. You can use **red** symbols to input into the Inference Checker.
However, it does not accept the purple symbols.

**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**

**A**_{i} , \cup(i=1 to n) A_i : **union of n sets**

, **\cap :** **set intersection**

**A**_{i} , **\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**

**A**_{i} , ** X(i=1 to n) A_i :** **cartesian product of n sets**

**Relation:**

**< a, b > :** **ordered pair **

**< a**_{1}, a_{2}, ..., a_{n} > : **ordered n-tuple **

** , ****<= :** **precedes (partial order)**

**Functions:**

**x**_{i} , **Sum(i=1 to n) x_i :** **sum of n x**_{i}'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 **