【DiscreteStructuresClassNotes · Ⅱ】Sets, Functions, Sequences, Sums and Matrices

由 MisakaStone 发布

Chapter Summary

  • Sets

    • The Language of Sets, Set Operations
  • Functions

    • Types of Functions, Operations on Functions
  • Sequences and Summations

    • Types of Sequences, Summation Formulae
  • Matrices

    • Matrix Arithmetic

Sets

Introduction

Sets are one of the basic building blocks for the types of objects considered in discrete mathematics.

  • Important for counting.
  • Programming languages have set operations.

Set theory is an important branch of mathematics.

  • Many different systems of axioms have been used to develop set theory
  • Here we are not concerned with a formal set of axioms for set theory. Instead, we will use what is called naïve set theory

Definition

A set is an unordered collection of objects.

The notation a ∈ A denotes that a is an element of the set A.

If a is not a member of A, write a ∉ A.

Describing a Set: Roster Method

  • S = {a,b,c,d}
  • Order not important.

    • S = {a,b,c,d} = {b,c,a,d}
  • Each distinct object is either a member or not; listing more than once does not change the set

    • S = {a,b,c,d} = {a,b,c,b,c,d}
  • Ellipses (…) may be used to describe a set without listing all of the members when the pattern is clear.

    • S = {a,b,c,d, ……,z }

Some Important Sets

N = natural numbers = {0,1,2,3….}

Z = integers = {…,-3,-2,-1,0,1,2,3,…}

$Z^{+}$ = positive integers = {1,2,3,…..}

R = set of real numbers

$R^{+}$ = set of positive real numbers

C = set of complex numbers

Q = set of rational numbers

Describing a Set: Set-Builder Notation

Specify the property or properties that all members must satisfy :

S = {x | x is a positive integer less than 100}

O = {x | x is an odd positive integer less than 10}

O = {x ∈ Z⁺ | x is odd and x < 10}

A predicate may be used :

S = {x | P(x)}

Interval Notation

[a,b] = {x | a ≤ x ≤ b}

[a,b) = {x | a ≤ x < b}

(a,b] = {x | a < x ≤ b}

(a,b) = {x | a < x < b}

closed interval [a,b]

open interval (a,b)

Universal Set and Empty Set

The universal set U is the set containing everything currently under consideration.

The empty set(null set)is the set with no elements. Symbolized ∅, but {} also used.

Some things to remember

Sets can be elements of sets.

{{1,2,3},a, {b,c}}

{N,Z,Q,R}

The empty set is different from a set containing the empty set.

∅ ≠ { ∅ }

Set Equality

Definition: Two sets are equal if and only if they have the same elements.

Therefore if A and B are sets, then A and B are equal if and only if $ \forall x (x \in A \leftrightarrow x \in B ) $

Venn Diagrams

Sets can be represented graphically using Venn iagrams, named after the English mathematician John Venn, who introduced their use in 1881.

John Venn

In Venn diagrams the universal set U, which contains all the objects under consideration, is represented by a rectangle.

Venn Diagram

Subsets

Definition: The set A is a subset of B, if and only if every element of A is also an element of B.

The notation A ⊆ B is used to indicate that A is a subset of the set B.

A ⊆ B holds if and only if $ \forall x (x \in A \rightarrow x \in B) $ is true.

Another look at Equality of Sets

Recall that two sets A and B are equal, denoted by A = B, iff

$$ \forall x (x \in A \leftrightarrow x \in B) $$

Using logical equivalences we have that A = B iff

$$ \forall x [(x \in A \rightarrow x \in B) \wedge (x \in B \rightarrow x \in A)] $$

This is equivalent to

$$ A \subseteq B \ and \ B \subseteq A $$

Proper Subsets

Definition: If A ⊆ B, but A ≠ B, then we say A is a proper subset of B, denoted by A ⊂ B. If A ⊂ B, then

$$ \forall x (x \in A \rightarrow x \in B) \wedge \exist x (x \in B \wedge x \notin A) $$

is ture.

Venn Diagram

Set Cardinality

Definition : If there are exactly n distinct elements in S where n is a nonnegative integer, we say that S is finite. Otherwise it is infinite.

Definition: The cardinality of a finite set A, denoted by |A|, is the number of (distinct) elements of A.

Examples:

  1. |ø| = 0
  2. Let S be the letters of the English alphabet. Then |S| = 26
  3. |{1,2,3}| = 3
  4. |{ø}| = 1
  5. The set of integers is infinite.

Power Sets

Definition: The set of all subsets of a set A, denoted $ \mathcal{P} (A) $, is called the power set of A.

Example: If A = {a,b} then

$$ \mathcal{P} (A) = \{ \varnothing, \{ a \}, \{ b \}, \{ a, b \} \} $$

If a set has n elements, then the cardinality of the power set is $ 2^{n} $.

Let’ s look at the same example in another way

Example: If A = {a,b} then $ \mathcal{P} (A) $ = {ø, {a},{b},{a,b}}
Use binary digit 1 to indicate an element is contained in a subset; use binary digit 0 to indicate an element is not contained in a subset.

00 – neither a nor b is contained in a subset. ø

01 – b, not a, is contained in a subset. {b}

10 – a, not b, is contained in a subset. {a}

11 – both a or b is contained in a subset. {a,b}

Ordered n-Tuples

The ordered n-tuple $ (a_{1}, a_{2}, ..., a_{n}) $ is the ordered collection that has $a_{1}$ as its first element and $a_{2}$ as its second element and so on until an as its last element.

2-tuples are called ordered pairs.

The ordered pairs (a,b) and (c,d) are equal if and only if a = c and b = d.

Cartesian Product

Definition: The Cartesian Product of two sets A and B, denoted by A × B is the set of ordered pairs (a,b) where a ∈ A and b ∈ B .

$$ A \times B = \{(a,b) | a \in A \wedge b \in B\} $$

Example :

A = {a,b} B = {1,2,3}

A × B = {(a,1), (a,2), (a,3), (b,1), (b,2), (b,3)}

Definition: The cartesian products of the sets $ A_{1}, A_{2}, …, A_{n} $, denoted by $ A_{1} \times A_{2} \times … \times A_{n} $, is the set of ordered n-tuples $ (a_{1}, a_{2}, …, a_{n}) $ where $a_{i}$ belongs to $A_{i}$ for i = 1, … n.

$$ A_{1} \times A_{2} \times ··· \times A_{n} = \{ (a_{1}, a_{2}, ···, a_{n}) | a_{i} \in A_{i} for \ i = 1, 2, ···, n \} $$


Set Operations

Boolean Algebra

Propositional calculus and set theory are both instances of an algebraic system called a Boolean Algebra.

The operators in set theory are analogous to the corresponding operator in propositional calculus.

As always there must be a universal set U. All sets are assumed to be subsets of U.

Union

Union: ∪ ∨ OR +

Definition: Let A and B be sets. The union of the sets A and B, denoted by A ∪ B, is the set:

$$ \{ x | x \in A \vee x \in B \} $$

Venn Diagram for A ∪ B

Intersection

Intersection: ∩ ∧ AND

Definition: The intersection of sets A and B, denoted by A ∩ B, is

$$ \{ x | x \in A \wedge x \in B \} $$

Note if the intersection is empty, then A and B are said to be disjoint.

Venn Diagram for A ∩ B

Complement

Complement: ¯ ¬ NOT

Definition: If A is a set, then the complement of the A (with respect to U), denoted by Ā is the set U - A

$$ \bar{x} = \{x \in U \ | \ x \notin A\} $$

(The complement of A is sometimes denoted by $A^{c}$.)

Venn Diagram for Complement

Difference

Definition: Let A and B be sets. The difference of A and B, denoted by A – B, is the set containing the elements of A that are not in B. The difference of A and B is also called the complement of B with respect to A.

$$ A - B = \{ x \ | \ x \in A \wedge x \notin B \} = A \cap \bar{B} $$

Venn Diagram for A − B

Example: If U = {1,2,3,4,5} A = {1,2, 4}, and B ={4,5}, what is A – B and B – A ?

Solution:

A – B = {1,2}

B – A = {5}

Review Questions

Example: U = {0,1,2,3,4,5,6,7,8,9,10} A = {1,2,3,4,5} B ={4,5,6,7,8}

  1. $A \cup B$

Solution: {1,2,3,4,5,6,7,8}

  1. $A \cap B$

Solution: {4,5}

  1. $\overline{A}$

Solution: {0,6,7,8,9,10}

  1. $\overline{B}$

Solution: {0,1,2,3,9,10}

  1. A – B

Solution: {1,2,3}

  1. B – A

Solution: {6,7,8}

The Cardinality of the Union of Two Sets

Inclusion-Exclusion

|A ∪ B| = |A| + |B| − |A ∩ B|

Set Identities

  • Identity laws

$$ A \cup \varnothing = A \\ A \cap U = A $$

  • Domination laws

$$ A \cup U = A \\ A \cap \varnothing = \varnothing $$

  • Idempotent laws

$$ A \cup A = A \\ A \cap A = A $$

  • Complementation law

$$ \overline{(\overline{A})} = A $$

  • Commutative laws

$$ A \cup B = B \cup A \\ A \cap B = B \cap B $$

  • Associative laws

$$ A \cup (B \cup C) = (A \cup B) \cup C \\ A \cap (B \cap C) = (A \cap B) \cap C $$

  • Distributive laws

$$ A \cap (B \cup C) = (A \cap B) \cup (A \cap C) \\ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) $$

  • De Morgan’s laws

$$ \overline{A \cup B} = \overline{A} \cap \overline{B} \\ \overline{A \cap B} = \overline{A} \cup \overline{B} $$

  • Absorption laws

$$ A \cup (A \cap B) = A \\ A \cap (A \cup B) = A $$

  • Complement laws

$$ A \cup \overline{A} = U \\ A \cap \overline{A} = \varnothing $$

Membership Table

Example: Construct a membership table to show that the distributive law holds.

$$ A \cup (B \cap C) = (A \cup B) \cap (A \cup C) $$

Solution:

ABC$ B \cap C $$ A \cup (B \cap C) $$ A \cup B $$ A \cup C $$ (A \cup B) \cap (A \cup C) $
11111111
11001111
10101111
10001111
01111111
01000100
00100010
00000000

Generalized Unions and Intersections

Let $ A_{1}, A_{2}, ..., A_{n} $ be an indexed collection of sets.

We define:

$$ \bigcup_{i = 1}^{n} A_{i} = A_{1} \cup A_{2} \cup ... \cup A_{n} \\ \bigcap_{i = 1}^{n} A_{i} = A_{1} \cap A_{2} \cap ... \cap A_{n} $$

Computer Representation of Sets

First, specify an arbitrary ordering of the elements of U, for instance $a_{1}, a_{2}, ..., a_{n}$. Represent a subset A of U with the bit string of length n, where the ith bit in this string is 1 if ai belongs to A and is 0 if ai does not belong to A.

Example: Let U = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}, and the ordering of elements of U has the elements in increasing order.

What bit strings represent the subset of all odd integers in U?

10 1010 1010

What bit strings represent the subset of all even integers in U?

01 0101 0101

What bit strings represent the subset of integers not exceeding 5 in U?

11 1110 0000


Functions

Definition: Let A and B be nonempty sets. A function $f$ from A to B, denoted $f: A \rightarrow B$ is an assignment of each element of A to exactly one element of B. We write $f(a) = b$ if b is the unique element of B assigned by the function $f$ to the element a of A.

Functions are sometimes called mappings or transformations.

Function

Given a function $f: A \rightarrow B$

We say $f$ maps A to B or $f$ is a mapping from A to B.

A is called the domain of $f$

B is called the codomain of $f$

If $f (a) = b$,

  • then b is called the image of a under $f$
  • a is called the preimage of b

Two functions are equal when they have the same domain, the same codomain and map each element of the domain to the same element of the codomain.

Questions

Example

$ f (a) = ? $ z

The image of d is ? z

The domain of $f$ is ? A

The codomain of $f$ is ? B

The preimage of y is ? b

$ f (A) = ? $ {y,z}

The preimage(s) of z is (are) ? {a,c,d}

Injections ( one-to-one mapping)

A function that never assigns the same value to two different domain elements is said to be one-to-one.

Injections

Definition: A function $f$ is said to be one-to-one, or injective, if and only if $f (a) = f (b)$ implies that a = b for all a and b in the domain of $f$. A function is said to be an injection if it is one-to-one.

Surjections

Surjections

Definition: A function $f$ from A to B is called onto or surjective, if and only if for every element $b \in B$ there is an element $a \in A$ with $f (a) = b$. A function $f$ is called a surjection if it is onto.

Bijections

Bijections

Definition: A function $f$ is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto(surjective and injective).

Different Types of Correspondences

Examples

Inverse Functions

Definition: Let $f$ be a bijection from A to B. Then the inverse of $f$, denoted $ f^{-1} $ , is the function from B to A defined as

$$ f^{-1} (y) = x \iff f(x) = y $$

Inverse

Composition

Definition: Let $ g: A \rightarrow B $, $ f: B \rightarrow C $. The composition of $f$ with $g$, denoted $ f \circ g $ is the function from A to C defined by

$$ f \circ g(x) = f(g(x)) $$

Composition

Note that the composition $f \circ g$ cannot be defined unless the range of $g$ is a subset of the domain of $f$.

Some Important Functions

  • The floor function, denoted

$$ f(x) = \lfloor x \rfloor $$

is the largest integer less than or equal to x.

  • The ceiling function, denoted

$$ f(x) = \lceil x \rceil $$

is the smallest integer greater than or equal to x.

Examples:

$$ \lfloor 3.5 \rfloor = 3 \;\;\;\; \lceil 3.5 \rceil = 4 \\ \lfloor -1.5 \rfloor = -2 \;\;\;\; \lceil -1.5 \rceil = -1 $$

Graphs


Sequences and Summations

Introduction

Sequences are ordered lists of elements.

Sequences arise throughout mathematics, computer science, and in many other disciplines, ranging from botany to music.

Definition

A sequence is a function from a subset of the integers A (usually the set {0, 1, 2, 3, 4, …..}) to a set S. The notation $a_{n}$ is used to denote the image of the integer n. We can think of $a_{n}$ as the equivalent of $f(n)$ where $f$ is a function from {0, 1, 2, …} to S. We call $a_{n}$ a term of the sequence.

Geometric Progression

Definition: A geometric progression is a sequence of the form:

$$ a, ar, ar^{2}, ..., ar^{n}, ... $$

where the initial term a and the common ratio r are real numbers.

Arithmetic Progression

Definition: A arithmetic progression is a sequence of the form:

$$ a, a + d, a + 2d , ... a + nd, ... $$

where the initial term a and the common difference d are real numbers.

Strings

Definition: A string is a finite sequence of characters from a finite set (an alphabet).

Sequences of characters or bits are important in computer science.

The empty string is represented by $\lambda$.

The string abcde has length 5.

Recurrence Relations

Definition: A recurrence relation for the sequence {$a_{n}$} is an equation that expresses $a_{n}$ in terms of one or more of the previous terms of the sequence, namely, $a_{0}, a_{1}, …, a_{n-1}$, for all integers n with $n \geq n_{0} $, where $n_{0}$ is a nonnegative integer.

A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect.

Fibonacci Sequence

Definition: Define the Fibonacci sequence, $f_{0}, f_{1}, f_{2}, …,$ by:

  • Initial Conditions: $ f_{0} = 0, \ f_{1} = 1 $
  • Recurrence Relation: $ f_{n} = f_{n-1} + f_{n - 2} $

Solving Recurrence Relations

Finding a formula for the nth term of the sequence generated by a recurrence relation is called solving the recurrence relation.

Such a formula is called a closed formula.

Many methods have been developed for solving recurrence relations.

A straightforward method is known as iteration.

An iteration method can be executed using

  • Forward substitution (Working upward)
  • Backward substitution(Working downward)

Summations

Sum of the terms $a_{m}, a_{m + 1}, ..., a_{n}$ from the sequence {$a_{n}$}

The notation:

$$ \sum_{j = m}^{n} a_{j} \;\;\;\; \textstyle\sum_{j = m}^{n} a_{j} \;\;\;\; \textstyle\sum_{m \leq j \leq n} a_{j} $$

represents $a_{m} + a_{m + 1} + ... + a_{n}$

The variable j is called the index of summation. It runs through all the integers starting with its lower limit m and ending with its upper limit n.

Geometric Series

Sums of terms of geometric progressions:

$$ \sum_{j = 0}^{n} ar^{j} = \left \{ \begin{array}{l} \frac{a(1-r^{n+1})}{1-r} \;\;\;\; r \neq 1 \\ (n+1)a \;\;\;\; r = 1 \end{array} \right. $$

Some useful summation formulae:

SumClosed Form
$ \sum_{k=1}^{n} k $$ \frac{n(n+1)}{2} $
$ \sum_{k=1}^{n} k^{2} $$ \frac{n(n+1)(2n+1)}{6} $
$ \sum_{k=1}^{n} k^{3} $$ \frac{n^{2}(n+1)^{2}}{4} $
$ \sum_{k=0}^{\infty} x^{k} $ , IxI < 1$ \frac{1}{1-x} $
$ \sum_{k=0}^{\infty} kx^{k-1} $ , IxI < 1$ \frac{1}{(1-x)^{2}} $

Double Summations

As in the analysis of nested loop in computer program.

$$ \sum_{i=1}^{4} \sum_{j=1}^{3} ij $$

To evaluate the double sum, first expand the inner summation and then continue by computing the outer summation:

$$ \sum_{i=1}^{4} \sum_{j=1}^{3} ij = \sum_{i=1}^{4} (i + 2i + 3i) \\ = \sum_{i=1}^{4} 6i \\ \;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\;\; = 6 +12 +18 +24 \\ = 60 \;\;\;\;\; $$


Matrices

Introduction

Matrices, useful discrete structures, can be used to:

  • Describe certain types of functions known as linear transformations.
  • Express which vertices of a graph are connected by edge.

Matrices are used to build models of transportation systems and communication networks.

Definition

A matrix is a rectangular array of numbers.

A matrix with m rows and n columns is called an $m \times n$ matrix.

  • The plural of matrix is matrices or matrixes.
  • A matrix with the same number of rows as columns is called square.
  • Two matrices are equal if they have the same number of rows and the same number of columns and the corresponding entries in every position are equal.

Notation

Let m and n be positive integers and let

$$ A = \begin{bmatrix} a_{11}&a_{12}&\cdots&a_{1n} \\ a_{21}&a_{22}&\cdots&a_{2n} \\ \vdots&\vdots&&\vdots \\ a_{m1}&a_{m2}&\cdots&a_{mn} \end{bmatrix} $$

The ith row of A is the $1 \times n$ matrix: $[a_{i1}, a_{i2}, …, a_{in}]$.

The jth column of A is the $m \times 1$ matrix: $ \begin{bmatrix} a_{1j} \\ a_{2j} \\ \vdots \\ a_{mj} \end{bmatrix} $.

The (i,j)th element or entry of A is the element $a_{ij}$. We can use $A = [a_{ij}]$ to denote the matrix with its (i,j)th element equal to $a_{ij}$.

Matrix Arithmetic

Addition

Definition: Let $A = [a_{ij}]$ and $B = [b_{ij}]$ be $m \times n$ matrices. The sum of A and B, denoted by A + B, is the $m \times n$ matrix that has $a_{ij} + b_{ij}$ as its (i,j)th element. In other words, $ A + B = [a_{ij} + b_{ij}] $.

Example:

$$ \begin{bmatrix} 1&0&-1 \\ 2&2&-3 \\ 3&4&0 \end{bmatrix} + \begin{bmatrix} 3&4&-1 \\ 1&-3&0 \\ -1&1&2 \end{bmatrix} = \begin{bmatrix} 4&4&-2 \\ 3&-1&-3 \\ 2&5&2 \end{bmatrix} $$

Multiplication

Definition: Let A be an $m \times k$ matrix and B be a $k \times n$ matrix. The product of A and B, denoted by AB, is the $m \times n$ matrix that has its (i,j)th element equal to the sum of the products of the corresponding elements from the ith row of A and the jth column of B. In other words, if $AB = [c_{ij}]$ then $c_{ij} = a_{i1}b_{1j} + a_{i2}b_{2j} + … + a_{ik}b_{kj}$.

Example:

$$ \begin{bmatrix} 1&0&4 \\ 2&1&1 \\ 3&1&0 \\ 0&2&2 \end{bmatrix} \begin{bmatrix} 2&4 \\ 1&1 \\ 3&0 \end{bmatrix} = \begin{bmatrix} 14&4 \\ 8&9 \\ 7&13 \\8&2 \end{bmatrix} $$

The product of two matrices is undefined when the number of columns in the first matrix is not the same as the number of rows in the second.

Identity Matrix and Powers of Matrices

Definition: The identity matrix of order n is the $m \times n$ matrix $I_{n} = [δ_{ij}]$, where $δ_{ij} = 1$ if i = j and $δ_{ij} = 0$ if $i \ne j$.

$$ I_{n} = \begin{bmatrix} 1&0&0&\cdots&0 \\ 0&1&0&\cdots&0 \\ 0&0&1&\cdots&0 \\ \vdots&\vdots&\vdots&&\vdots \\ 0&0&0&\cdots&1 \end{bmatrix} $$

$ AI_{n} = I_{m}A = A $ when A is an $m \times n$ matrix.

Transposes of Matrices

Definition: Let $A = [a_{ij}]$ be an $m \times n$ matrix. The transpose of A, denoted by $A^{t}$ ,is the $n \times m$ matrix obtained by interchanging the rows and columns of A.

Definition: A square matrix A is called symmetric if $A = A^{t}$. Thus $A = [a_{ij}]$ is symmetric if $a_{ij} = a_{ji}$ for i and j with $1 \leq i \leq n$ and $1 \leq j \leq n$.

Zero-One Matrices

Definition: A matrix all of whose entries are either 0 or 1 is called a zero-one matrix.

Algorithms operating on discrete structures represented by zero-one matrices are based on Boolean arithmetic defined by the following Boolean operations:

$$ b_{1} \wedge b_{2} = \left \{ \begin{array}{l} 1 \;\;\;\; if \ b_{1}=b_{2}=1 \\ 0 \;\;\;\; otherwise \end{array} \right. \;\;\;\;\;\;\; \\ b_{1} \vee b_{2} = \left \{ \begin{array}{l} 1 \;\;\;\; if \ b_{1}= 1 \ or \ b_{2}=1 \\ 0 \;\;\;\; otherwise \end{array} \right. $$

Definition: Let $A = [a_{ij}]$ and $B = [b_{ij}]$ be an $m \times n$ zero-one matrices.

  • The join of A and B is the zero-one matrix with (i,j)th entry $a_{ij} \vee b_{ij}$. The join of A and B is denoted by $A \vee B$.
  • The meet of of A and B is the zero-one matrix with (i,j)th entry $a_{ij} \wedge b_{ij}$. The meet of A and B is denoted by $A \wedge B$.

Boolean Product of Zero-One Matrices

Definition: Let $A = [a_{ij}]$ be an $m \times k$ zero-one matrix and $B = [b_{ij}]$ be a $k \times n$ zero-one matrix. The Boolean product of A and B, denoted by $A \odot B$, is the $m \times n$ zero-one matrix with (i,j)th entry.

$$ c_{ij} = (a_{i1} \wedge b_{1j}) \vee (a_{i2} \wedge b_{2j}) \ \vee ... \vee \ (a_{ik} \wedge b_{kj}) $$

Identity Matrix

Example:

$$ I \times A = A \times I = A $$


Thanks for the learning resource provided by Qi Wang from University at Albany!


暂无评论

发表评论