← Back to Home返回主页

Chapter 1第1章

Chapter Summary本章概述

This chapter introduces the fundamental concepts of Set Theory and Functions. We explore set notation, operations, relationships, and basic function concepts, laying the groundwork for more advanced discrete mathematics concepts. Key topics include set representations, Boolean algebra, Cartesian products, and function properties. 本章介绍集合论与函数的基础概念，包括集合的记号与运算、集合关系以及函数的基本概念，为后续离散数学内容打下基础。重点主题涵盖集合表示法、布尔代数、笛卡尔积以及函数性质。

Key Concepts:关键概念：
  • • Set Notation
  • • Set Operations
  • • Cartesian Products
  • • Functions
Learning Goals:学习目标：
  • • Understand sets
  • • Apply operations
  • • Work with functions
  • • Solve problems
Prerequisites:先修知识：
  • • Basic algebra
  • • Logic concepts
  • • Problem solving

1.1 Introduction to Sets1.1 集合导论

A set is a well-defined collection of distinct objects, called elements or members of the set. 集合是由一组彼此不同的对象构成的、定义明确的整体，这些对象称为该集合的元素或成员。

Basic Notation:基本记号：

  • A = {1, 2, 3, 4} - Roster notation列举法
  • B = {x | x is an even integer} - Set-builder notation描述法
  • x ∈ A - x is an element of set Ax 属于集合 A
  • y ∉ A - y is not an element of set Ay 不属于集合 A

Important Number Sets:常见数集：

  • Natural Numbers:自然数： ℕ = {0, 1, 2, 3, ...}
  • Integers:整数： ℤ = {..., -2, -1, 0, 1, 2, ...}
  • Positive Integers:正整数： ℤ⁺ = {1, 2, 3, ...}
  • Rational Numbers:有理数： ℚ
  • Real Numbers:实数： ℝ
  • Complex Numbers:复数： ℂ

1.2 Subsets and Power Sets1.2 子集与幂集

Subset Relationships子集关系

  • Subset:子集： A ⊆ B if every element of A is also in B若 A 的每个元素都属于 B
  • Proper Subset:真子集： A ⊂ B if若 A ⊆ B and且 A ≠ B
  • Set Equality:集合相等： A = B if当且仅当 A ⊆ B and且 B ⊆ A

Power Sets幂集

The power set P(A) is the set of all subsets of A.幂集 P(A) 是由 A 的所有子集组成的集合。

If |A| = n, then |P(A)| = 2^n.若 |A| = n，则 |P(A)| = 2^n。

Example:示例： If若 A = {1, 2}，then则 P(A) = {∅, {1}, {2}, {1,2}}

1.3 Set Operations1.3 集合运算

Basic Operations基本运算

  • Union:并集： A ∪ B = {x | x ∈ A or x ∈ B}
  • Intersection:交集： A ∩ B = {x | x ∈ A and x ∈ B}
  • Complement:补集： A^c = {x ∈ U | x ∉ A}
  • Difference:差集： A - B = {x | x ∈ A and x ∉ B}
  • Symmetric Difference:对称差： A ⊖ B = (A ∪ B) - (A ∩ B)

Inclusion-Exclusion Principle容斥原理

  • |A ∪ B| = |A| + |B| - |A ∩ B|
  • |A ∪ B ∪ C| = |A| + |B| + |C| - |A ∩ B| - |A ∩ C| - |B ∩ C| + |A ∩ B ∩ C|

1.4 Laws of Set Algebra1.4 集合代数定律

Commutative Laws交换律

A ∪ B = B ∪ A

A ∩ B = B ∩ A

Associative Laws结合律

A ∪ (B ∪ C) = (A ∪ B) ∪ C

A ∩ (B ∩ C) = (A ∩ B) ∩ C

Distributive Laws分配律

A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C)

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)

De Morgan's Laws德摩根律

(A ∪ B)^c = A^c ∩ B^c

(A ∩ B)^c = A^c ∪ B^c

1.5 Cartesian Products and Functions1.5 笛卡尔积与函数

Cartesian Product笛卡尔积

The Cartesian product of sets A and B is:集合 A 与 B 的笛卡尔积定义为：

A × B = {(a, b) | a ∈ A and b ∈ B}

Example:示例： If若 A = {1, 2} and且 B = {x, y}，then则 A × B = {(1,x), (1,y), (2,x), (2,y)}

Note:注意： |A × B| = |A| × |B|

Functions函数

A function f: X → Y is a rule that assigns to each element in X exactly one element in Y.函数 f: X → Y 是一种映射规则：为 X 中的每个元素唯一地对应 Y 中的一个元素。

  • Domain:定义域： The set X (input set)集合 X（输入集合）
  • Codomain:陪域： The set Y (possible output set)集合 Y（可能的输出集合）
  • Range/Image:值域： f(X) = {f(x) | x ∈ X} (actual outputs)（实际输出集合）

Function Properties函数性质

  • Injective (One-to-one):单射： If若 f(x₁) = f(x₂)，then则 x₁ = x₂
  • Surjective (Onto):满射： For every对任意 y ∈ Y，there exists存在 x ∈ X such that使得 f(x) = y
  • Bijective:双射： Both injective and surjective同时为单射与满射

Practice Problems练习题

Problem 1: Set Operations题目1：集合运算

Given:已知： A = {1, 2, 3, 4} and， B = {3, 4, 5, 6}

Find:求： A ∪ B、A ∩ B、A - B

Solution:解：
  • A ∪ B = {1, 2, 3, 4, 5, 6}
  • A ∩ B = {3, 4}
  • A - B = {1, 2}

Problem 2: Cartesian Product题目2：笛卡尔积

Given:已知： A = {a, b} and， B = {1, 2, 3}

Find:求： A × B and与 |A × B|

Solution:解：
  • A × B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}
  • |A × B| = |A| × |B| = 2 × 3 = 6