An introduction to Discrete Mathematics

Introduction

Discrete maths is the foundation of computer science. It is particularly important for algorithm and compiler design.

N0 = {0, 1, 2, …}	Natural numbers with 0
Z = {…, –2, –1, 0, 1, 2, …}	Integers
Q	(Rational) Fractions
R	Real numbers
Ų = {}	The empty set
x ? X	x is an element of the set X
X ? Y N ? N0 ? Z ? Q ? R.	One set, X, is a subset of another set, Y, if every element of X is also an element of Y. We write this with a rounded less-than-or-equal sign
N = {x ? Z \| x > 0}	The set of integers that satisfy the predicate x>0

Injective: Each y, y=f(x), can only come from one unique x. Eg; f(x)=2+1 is, x² is not.

Surjective: Each y in the codomain is defined by at least one x. Eg; x² for R isn't (x²=-1)

Bijective: One-one: injective and bijective. Eg; Identity function,g(x) = x² isn't: not injective

Relations: A relation R on A is defined to be R ? A x A. Note (a,b) ?R can be written aRb

Reflexive:A relation where ?a?A (a,a)?R,ie where ?x, x->x (all x relate to x) Eg;=,<,?,|

Antisymmetric: If a relates to b,and b relates to a then a=b Eg; a₁< a₂,a₂< a₁so a₁=a₂

Symmetric: If f(x)=y, then f(y)=x, eg; equals, “... is married to ...”

Transitive: If aRb and bRc then aRc Eg; Divisibility: a|b and b|c => a|c

Preorder - a transitive relation that is also reflexive.

Partial order - a preorder that is antisymmetric.

Equivalence relation - a relation that is a preorder and symmetric.

Email to a friend | Printer friendly version | Link to this page | Terms of Use | Contact Unless otherwise noted, content on this site is licensed under Creative Commons Attribution 2.5
Discrete_Maths/Summary.htm was last modified on 2007-01-02 12:51:41