Tran Viet Dung

LECTURE ON MATHEMATICS I
For HEDSPI Students

Hanoi University 2008
1


COMTENTS
CHAPTER I.

SYMBOLIC LOGICS.............................................5

1.

Propositions ....................................................................................5

2.

Logical operations ..........................................................................6

2.

3.

1.1.

Negation operator NOT ............................................................6

1.2.

Conjunction operator AND (  )................................................6

1.3.

Disjunction operator OR (  ) ....................................................7

1.4.

Implication operator IMP (

1.5.

Equivalence operator IFF (  )................................................9

1.6.

Tautologies, contradictions ..................................................... 10

Generation of operators ............................................................... 11
4.1

Binary XOR operator ( ) ........................................................ 11

4.2

Binary operator NOR () ........................................................ 12

4.3


Binary Operator NAND () ....................................................13

Propositions with quantifiers ,. ...............................................13

CHAPTER II.
1.

2.

) ..................................................8

SETS........................................................................ 16

Sets and elements..........................................................................16
1.1

Some definitions and notations ...............................................16

1.2

The ways to determine a set ...................................................16

1.3

Subsets ...................................................................................18

Set operations................................................................................18
2.1.

Intersection and union of sets ..................................................18


2.2.

Difference of sets, compliment of a subset .............................. 19

2.3.

Properties................................................................................20
2


2.4.
3.

The Cartesian product of sets ..................................................21

Some properties of finite sets........................................................ 21

CHAPTER III.

MAPPINGS ........................................................... 23

1.

Basic concepts ...............................................................................23

2.

Injective,surjective, bijective mappings.......................................24


3.

Composition of maps, inverse maps.............................................25

4.

Restriction, characteristic functions ............................................26

5.

Substitutions .................................................................................27

6.

Collections..................................................................................... 29
6.1

Collection of sets ....................................................................29

6.2

Collection of maps ..................................................................30

CHAPTER IV.

RELATIONS ......................................................... 32

1.

On relation Concepts....................................................................32


2.

Order relation ...............................................................................33

3.

2.1.

Concepts on order relation ...................................................... 33

2.2.

Lexicographical order. ............................................................ 35

Equivalence relation .....................................................................36
3.1

Definitions and examples ........................................................ 36

3.2

Equivalence classes................................................................. 36

3.3

Partitions induced by maps ..................................................... 38

CHAPTER V.
1.


ALGEBRAIC STRUCTURES ................................. 39

3
Binary operators...........................................................................39


2.

3.

4.

1.1

Definitions and examples ....................................................... 40

1.2

Properties of binary operators .................................................41

Groups........................................................................................... 43
2.1

Semigroups.............................................................................43

2.2

Concepts on groups.................................................................43


2.3

Some properties ......................................................................44

Subgroups, normal subgroups ..................................................... 45
3.1.

Subgroups...............................................................................45

3.2.

Normal subgroups...................................................................46

Rings and fiels...............................................................................48
4.1

Rings ...................................................................................... 48

4.2

Fields...................................................................................... 48

4.3

Ring of integers ......................................................................50

4.4

Euclidean Algorithm............................................................... 51


4.5

Presentation of integers ........................................................... 54

CHAPTER VI. FIELD OF COMPLEX NUMBERS...................... 56
1.

2.

3.

Concepts on complex numbers..................................................... 56
1.1

Canonical form of complex numbers.......................................56

1.2

Operations in canonical form ............................................... 562

1.3

Modulus and conjucgate of complex numbers ...................... 562

Polar form of complex numbers..................................................59
2.1

Definitions and examples. ....................................................... 59

2.2


Some operations of complex numbers in the polar form ..........60

2.3

n-roots of a complex number...................................................62

Quadratic equations on C............................................................. 64
3.1

Quadratic equations of real coefficients...................................64
4


3.2
4.

Quadratic equations of complex

coefficients ........................ 65

Polynomials of complex variables ................................................66

Chapter I

SYMBOLIC LOGICS

1. Propositions
Definition 1.
A Proposition is a statement which is either true or false, although

we may not know which. Propositions are denoted by lower letters as p, q,
r… The truth or falsity is called truth value of the proposition. The truth
value of the proposition p is denoted by V(p).
If p is true then V(p) = 1 or T. If p is false then V(p) = 0 or F.
Example 1.
The proposition p is given by p = “ The sun rises in the east “ and
the proposition q is given by q = “ The sun rises in the west”. Then V(p) =
1 and V(q) = 0.
However, for several propositions we do not know the truth values.
Example 2.
The proposition r = “ There exists life outside the earth.” Up to now
we can not know the truth value of the statement r.

5


2. Logical operations
Negation operator NOT
Definition 2.1.
The negative proposition of a proposition p is the proposition
p defined by its truth table as follows

p

p

1

0


0

1

Table 1.NOT truth table



Note : For a proposition p we have V(p) = V p .

Example 3.
Given a proposition p = “ Hanoi is the capital of Vietnam “. Then NOT p
is the proposition p = “ Hanoi is not the capital of Vietnam”.
Example 4.
The proposition q is “ The equation f(x) = 0 has solutions ”, then the
negative proposition is “ The equation f(x) = 0 has no solution “.

Conjunction operator AND (  )
Definition 2.2.
6


Given two propositions p and q . The proposition p  q is true only
both p and q are true propositions. The AND operator is defined by a
truth table which lists of possible combinations of the truth values of p
andq :

p

q


pq

1

1

1

1

0

0

0

1

0

0

0

0

TABLE 2 . AND truth table

Example 5.

If p = “ Pigs are mammals” and q = “Pigs fly “ , then p  q is
interpreted as “ Pigs are flying mammals “.

Disjunction operator OR (  )
Definition 2.3.
For propositions p and q the proposition p  q is false only when
both p and q are false. The OR operator is defined by the following truth
table

p

Q

p q

1

1

1

1

0

1

0

1


1

0

0

0

Table 3. OR Truth Table

Theorem 1. ( De Morgan ’s Law )

7


For any two propositions p and q we have
1) V( p  q ) = V( p )  V( q ),
2) V( p  q ) = V( p )  V( q ),
Corollary 2.
The disjunction operator OR may be defined by NOT and AND
operators:
V( p  q ) = V ( p  q ).
Theorem 3.(Distributive Laws ).
For any three propositions p, q, r, we have
1) V(p(qr)) = V((pq)(pr))
2) V(p(qr ) = V(( pq)(pr))
Theorem 4.( commutative and associative Laws)
For propositions p, q, r, we have
1)


V(pq) = V(qp),

2)

V(pq) = V(qp),

3)

V((pq)r)=V(pq(r)),

4)

V((pq)r))= V(p(qr)).

Implication operator IMP (

)

Definition 2.4.
For two propositions p, q, the proposition p q is defined by its truth
table

p

q

P q

1

1
0
0

1
0
1
0

1
0
1
1

TABLE 4. IMP truth table
Thus, the proposition p q is false only when p is true and q is false.

8


Assertion 5.
If p, q are propositions then we have
1) the proposition p (pq) is true,
2) The proposition (pq) p is true.

Theorem 6.
The implication operator IMP may be built from the negation
operator NOT and the conjunction operator AND:
V(p q) = V( p  q ).


Equivalence operator IFF (  )

Definition 2.5.
Given two propositions p, q. The proposition pq is true only when
the truth values of p and q are the same.
p

q

Pq

1

1

1

1

0

0

0

1

0

0


0

1

TABLE 5. IFF Truth Table

Theorem 7.
For propositions p, q we have
V( pq) = V((p q)(q p)).

Theorem 8.

9


The equivalence operator may be built from the negation operator
NOT and the conjunction operator AND:
V(pq) = V(( p  q )( q  p )).

Tautologies, contradictions
Definition 3.1.
A proposition composite by atomic propositions is called a
tautology if it is always true regardless truth values of atomic components.
Example 5.
a)The proposition (pq) p is a tautology. Actually, we have the
truth table of this proposition

p


q

pq

(Pq) p

1

1

1

1

1

0

0

1

0

1

0

1


0

0

0

1

b)(( pq) p ) q is a tautology. The truth table is
p

q

pq

(Pq) p

((Pq) p ) q

1

1

1

0

1

1


0

1

0

1

0

1

1

1

1

0

0

0

0

1

Definition 3.2.

10


A proposition composite by atomic propositions is called a
contradiction if it’s values are always false regardless truth values of
atomic components.

Example 6.
a) The proposition p p is a contradiction. Actually, the
truth table of this proposition is

p

p

p p

1

0

0

0

1

0

b)The proposition (pq) p is a contradiction because the truth

values of this are always false:

p

q

p

q

p p

q q

1

1

0

0

1

0

1

0


0

0

1

0

0

0

1

1

1

1

0

0

0

0

1


1

1

0

0

(p p ) q q
0

2. Generation of operators
4.1 Binary operator XOR (  )
Definition 4.1.
For two propositions p and q, the proposition p q is defined by the
truth table

11


p

q

p q

1

1


0

1

0

1

0

1

1

0

0

0

Assertion 9.
The XOR operator is the negation of the IFF operator:
V(p  q) = V( p  q ).

4.2 Binary operator NOR ()
Definition 4.2.
Given two proposition p, q. The proposition pq is the proposition
defined by the truth table

p


q

pq

1

1

0

1

0

0

0

1

0

0

0

1

This means neither p nor q.

12


Assertion 10.
The operator NOR is negation of OR:
V(pq)= V ( p  q ).

4.3

Binary Operator NAND ()

Definition 4.3.
Given two propositions p and q. The proposition pq is defined by
the truth table

p

q

pq

1

1

0

1

0


1

0

1

1

0

0

1

Assertion 11.
The operator NAND is the negation of AND:
V(pq) = V( p  q ).

3. Propositions with quantifiers ,.
13


Definition 5.1.
Let p(x) is a statement for x X. Then
 xX,p(x) is a proposition that is true if for every x in the set X, p(x) is

true.  xX,p(x) is a proposition that is true if there is an element x in X
such that p(x) is true.
Analogously, we have propositions as  x  y,P(x,y);  x  y,P(x,y)

or  x  y,P(x,y).
In general, we have propositions containing  ,  and a statement
P(x1,...,xn).

Example 7.
a)The proposition “  xR , x2 +1  0.“ is true.
b)The proposition “  xR , x2 -1  0.“ is false.
c)The proposition “  xR , x2 -1  0“ is true.
d) The proposition “  xR,  yR, x + y  0“ is true
e)The proposition “  yR  xR, x + y  0“ is false.
Example 8.
The function f(x) is continuous at the point x0 if “ 

  0,   0,

 x,( (x-x0 ) f(x)–f(x0)   )“.

Note.
To receive the negation of a proposition containing qualifiers
 ,  and statement P(x1,..., xn ), we change  by  , change  by  and

change P(x1,..., xn ) by P (x1,..., xn ).
Example 9.
In Example 8, using the above note we have that a function
f(x) is not continuous at the point x0 if

14


“    0,   0,  x(((x-x0 ) (f(x)–f(x0)   )”.


15


Chapter II
SETS

1. Sets and elements
1.1 Some definitions and notations
Definition 1.
A set is a collection of elements. Let a be and element of a set A.
Then we say that the element a is be long to A and denote by a  A. If the
element a is not belong to A then denote by a  A.
Let a and b be two element of a set A. If a and b are the same then
denote by a  b.
The set containing no any element is called the empty set and
denoted by .
Definition 2.
The set A and the set B are called equal and denoted by A = B if an
element a  A  a  B.

1.2 The ways to determine a set
Method 1. Listing of all elements of the set.

Example 1.

16


a) A = { 1,2,3,4,5,6,7,8,9,10 }.

b) B = { 1, 3, 5, ..., 2n+1,...}
However in several cases we can not know exactly elements of a set or
can not list all elements of a set.
c) We usually use some number sets as follows:
N is the set of natural numbers,
Z is the set of integer numbers,
Q is the set of rational numbers,
R is the set of real numbers.

Example 2.
a) Let A be the set of real roots of the equation x9 – 3 x8 + 4 x3- 100
= 0. Then it is difficul to us to collect elements of A.
b) Let R be the set of real numbers. We can not list all elements of
R.
Hence a set is also defined by the following method.
Method 2.
Poiting out the characteristic properties of elements of the set.

Example 3.
In Example 2a) an element of A is a real root of given equation.
Then we can denote
A = { x R  x9 – 3 x8 + 4 x3- 100 = 0 }.
In Example 2b) an element of R is a real numbers.

Example 4.
a) A = { 1,2,3,4,5,6,7,8,9,10 } can be expressed as
A = { x N  1  x  10 }.
b) B = { 1, 3, 5, ...}

= { k  N  k = 2n +1, n  N }.

17


1.3

Subsets

Definition 3.
We say that a set A is a subset of a set B or that A is included in B
and denote by A  B if all elements of A are also belong to B. That is
A  B if and only if ( a  A

a  B ).

Example 5. a) { 1, 3, 5 }  { 1, 2, 3, 5, 8, 13 }.
b) N  Z, Z  Q , Q  R.
Note. a) A set is a subset of itself.
b) For two sets A, we have
A = B iff A  B and B  A.

2. Set operations
Intersection and union of sets
Definition 4.
The intersection of a set A and a set B is the set A  B given by
A  B = { x  x A  x B }.
Definition 5.
The union of a set A and a set B is the set A  B given by
A  B = { x  x A  x B }.
Example 6.
18



a)If A = {1,2,3,4.5,6 }, B = { 1,3,5,7,9 } then A  B = { 1,3,5}, A
 B = { 1,2,3,4,5,6,7,9 }.
b) A = { x  R  f(x)= 0 } B = { x R  g(x) = 0 }
then A  B = { x R  f(x) = 0  g(x) = 0 }.

If A  B =  then we say that A, B are disjoint .
Venn diagrams

AB

AB

Difference of sets, compliment of a subset

Definition 5.
The difference of a set A and a set B is the set A\B defined by
A\B ={ x  A  x  B }.
19


Let U be the universal set the compliment of a set A denoted by

A = U\A.

Example 7.
a) A = { 1,2,3,4,5 }, B = { 1,3,5,7,9 },

A\B = { 2,4 }.


b) A = { xR  f(x) = 0 }, B = { x R  g(x) = 0 }
The set { x R 

f (x)
 0 } is equal to A\B.
g(x)

Properties
Theorem 1.
For sets A, B, C, we have
1) A  B = B  A, A  B = B  A,
2) A ( B  C )) = (A  B) C ,

A  ( B  C )= ( A 

B) C,
3) A  ( B  C ) = (A  B)  ( A  C ),

A(BC)=

( A  B )  ( A  C ),
4)

  A = ,   A = A,

5)

AB AB=A


6)

AB  AB=B.
n

Notations :

A

i

= A1  A2  ... An,

i 1
n

A

i

= A1  A2  ... An

i 1

Theorem 2.

20


For sets X, A1,..., An, we have

n

1) X \

A

i

n

=

i 1

2) X \

n

n



i 1

i 1

 Ai =

A


4)

( X \ Ai ) ,

i 1

i

( X \ Ai ) ,

n

n

3)



=

A

,

i

i 1

i 1


n

n

 Ai =

A .

i 1

i 1

i

The Cartesian product of sets
Definition 6.
The cartesean product of a set A and a set B is the set AB of all
ordered pairs whose first coordinates in A and whose second coordinate is
in B, i.e AB = { (a, b)  a A, b  B }.
Example .
If A = { 1,2,3 }, B = {2,4 } then

AB = { (1,2 ), (1,4), (2,2),

(2,4), (3,2), (3,4)}.
In General
A1A2... An = {(x1,x2,...,xn) x1 A1...,xn An},
An = {(x1,x2,...,xn) x1 A...,xn A }.

3. Some properties of finite sets

21


Assume that the number of elements of a set X is finite. Denote by
N(X) the number of elements of X.
Theorem 3.
Let A and B be finite sets . Then we have
N(AB) = N(A).N(B).
Theorem 4.
a)For two disjoint sets A, B we have
N(AB) = N(A) + N(B).
b) For A, B are arbitrary , we have
N(AB) = N(A) + N(B) – N(AB).
Theorem 5.
For arbitrary finite sets A1, A2, ...Am , the number of elements of
their union is counted by the formula
N( A1...Am ) = N1 - N2 + N3 +... + (- 1)m-1Nm ,
where N1 = N(A1)+...+N(Am), ..., Nk =

 N(A

i1

 Ai 2  ... Aik )

1 i1 i 2  ... ik  m

Example .
N( A1  A2  A3 ) = N1 – N2 +N3, where
N1 = N(A1) + N(A2 ) + N(A3) ,

N2 = N(A1A2) + N(A1A3) + N(A2A3)
N3 = N(A1A2A3) .

22


Chapter III

MAPPINGS

1. Basic concepts
Definition 1.
Let X and Y be two sets. A mapping ( map or function) f from X to
Y is an assignment of every element in X to an unique element in Y.
Let f be a mapping from X to Y. If x  X, the element of Y to which
x assigned by f and denoted by f(x). Denote by
f: X  Y, x  f(x).
If f(x) = y, we say that x is mapped to y by f and y is the image of x
under f.
Definition 2.
Two mappings f, g from X to Y are called equal if they are the same
way on every element of X, i.e
f = g iff for all xX, f(x) = g(x).
Example 1.
a) A mapping f: X  R for a subset X in R is a real function.
b) The map IdX: X X given by IdX(x)= x for every x X is called
the identity on X.

Definition 3.
Let f: X Y be a map

23


a) For a set A  X, the set f(A) = { f(x) x A } is called the image
of A under f.
b) For B  Y the set f-1(B) = { xX f(x)  B } is called the
preimage of B under f.
If A = X, f(X) is denoted by Im(f). If B ={b}, we write

f-1{b}

instead of f-1({b}).

2. Injective,surjective, bijective mappings
Definition 4.
Let f: X Y be a map.
a) The map f is called injective if for x1, x2  X, f(x1) = f(x2)
implies x1 = x2.
b ) The map f is called surjective if for every y Y there exists an
element x  X such that f(x) = y.
c) The map f is called bijective if it is both injective and surjective.
Example 2.
a) f : RR , f(x) = 2x +1 is bijective.
b) g: RR , g(x) = ex is injective not surjective
c) h: R R, h(x) = x2 is neither injective nor surjective.
Remark.
X and Y are finite sets. We have
a) If f: X Y is injective then N(X) N(Y)
b) If f: X Y is surjective then N(X) N(Y)
c) If X Y is bijective then N(X) = N(Y).


24


3. Composition of maps, inverse maps
Definition 5.
Given three sets X, Y, Z and maps
f: XY, g: YZ.
The composition of f and g is the map
gof: XZ
given by (gof)(x) = g(f(x)) for x X.
Example 3.
If f,g: RR, f(x)= x2, g(x) = sin(x) then
(gof)(x)= sin(x2), (fog)(x)= sin2(x).

Proposition 1.
For maps f:XY, g:Y X, h:ZW, we have
a)

ho(gof) = (hog)of,

b)

foIdX = f ; IdYof= f.

Proposition 2.
Let f:XY, g: YZ be maps.
a)If f and g are injective then gof is injective
b)If f and g are surjective then gof is surjective
c) If f and g are bijective then gof is bijective.


Proposition 3.
Let f : X Y be a bijection. Then there is a map g: YX

g(y) =

x if f(x) = y.
25