01-离散数学基本原理-离散数学讲义-海南大学（共十一讲）

1.基础知识Fundamentals

1.1集合与子集Sets and Subsets 1.1.1集合的表示

1.

A?{x|P(x)} P(x)是谓词Predicate表示元素x具有某种属

例

性, 满足P(x), 即具有性质P的x , 是集合A的元素

A?{x|0?x?3?x是实数}

2.

A?{a,b,c,d} 元素不计次序

a?A, a is in A, a is an element of A.

1.1.2集合的例子

The set of positive integers and zero

N?{0,1,2,3,?}自然数集

The set of all integers(positive and negative integers and zero)

Z?{?,?2,?1,0,1,2?}整数集

the set of all positive integers

Z??{1,2,3,?}Z+=正整数集

The set of all rational numbers

Q?{n|n,m?Z}有理数集 mthe set of real number

R?{x|x是实数} 实数集

?={ } empty set空集.

1.1.3集合相等equal A?B

A?B if and only if for every x, x?A?x?B.

1.1.4子集 subset

A?B??x(x?A?x?B) .

A?B?A?B?B?A.

例For any set A, ??A，A?A,

{a,c}?{a,b,c}, {{a}}?{a,{a}}

Z??N?Z?Q?R

1.1.5真子集proper subset

A?B?A?B?A?B ?A?B??x(x?B?x?A)Z??N?Z?Q?R

1.1.6（有限）集合的基数

the cardinality of a finite set

If a set A has n distinct elements, n?N, n is called the cardinality of A , is denoted by |A|.

|{a,b,c,d}|=4, |{a, {a}}|=2 , | ? |=0.

1.1.7全集universe(论域)U

We always assume that for each discussion there is a universal set U , for any set A in the discussion , A?U, for any element x in the discussion x∈U

1.1.8幂集power set

P(A)?{B|B?A}

P({a})?{?,{a}}

P({a,b})?{?,{a},{b},{a,b}}

P({a,b,c})?{?,{a},{b},{c},{a,b},{a,c},{a,b,c}}P({a,{a}})?{?,{a},{{a}},{a,{a}}}

P(?)?{?}

If |A| = n , then |P(A)|=2n.

1.2集合的运算Operations on the Sets 1.2.1交intersection A?B?{x|x?A?x?B} 1.2.2并union A?B?{x|x?A?x?B}

1.2.3差difference A?B?{x|x?A?x?B} 1.2.4补complement A?U?A 1.2.5对称差symmetric difference

A?B?(A?B)?(B?A)?{x|x?A?B?x?B?A}

例U = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10}

A= {1, 2, 3, 4, 5}, B = {4, 5, 6, 7, 8}. Then A∪B = {1, 2, 3, 4, 5, 6, 7, 8} A∩B = {4, 5}

A = {0, 6, 7, 8, 9, 10}

B = {0, 1, 2, 3, 9, 10}

A - B = {1, 2, 3} B - A = {6, 7, 8} A

?B = {1, 2, 3, 6, 7, 8}

{x|x?A?x?B?x?C}

2

n

A∩B∩C=

n?A=A∩A∩?∩A={x|x?A1?x?A2???x?An}

i?1i1

A∪B∪C={xn|x?A?x?B?x?C}

2

n

?A=A∪A∪?∪A={x|x?A1?x?A2???x?An}

i?1i1

1.2.6Venn diagrams（文氏图）

Diagrams used to show relationships between sets after the British logician John Venn.

A useful geometric visualization tool (for 3 or less sets).

The Universe U is the rectangular box.

Each set is represented by a circle and its interior.

All possible combinations of the sets must be represented A A B B B A B A C