Software Reliability Methods Chap2

Basic knowledge of set theory, graph theory, complexity theory and computability.

2.1 Set Notation

Set

A set is a finite or infinite collection of elements.

• Insersection
• Union
• Difference: Prefer \(A /\ B\) to \(A - B\).
• Powerset: Prefer \(2^A\) to \(\mathcal{P}(A)\)

Other operations...

Relation

A relation of arity \(n\) is a set of \(n\)-tuples over some domain.

• Reverse \(R^{-1}\):

  \(R \subseteq D_1 \times D_2\)，\(R^{-1}\) is \(\{ \langle x,y \rangle | \langle y,x \rangle \in R \}\). Notice that \(R^{-1} \subseteq D_2 \times D_1\)

Properties

• Reflexive:
• Symmetric:
• Transitive

Notice transitive closure, \(R^{\*}\). Definition \((x,y) \in R^{\*}\) when there is a sequence \(z_0,z_1,\cdots,z_n\) such that \((z_i,z_{i+1}) \in R\) for \(0 \le i < n, z_0 = x\) and \(z_n = y\). (Attention! Different from the defination comes from closure as I learn in the Discrete Mathematics).

A function(mapping), can be viewed as a constrained (n+1)-tuples relation.The first n elements define the (n+1). (We cannot have two tuples with the first n elements in the same but different in the (n+1) ).

A function \(f: \mathcal{D}_1 \rightarrow \mathcal{D}_2\)

• one-one(or indective): if for every two elements \(d_1,d_2 \in \mathcal{D_1}\), \(d_1 \ne d_2\) we have \(f(d_1) \ne f(d_2)\).
• onto: if for each element \(c \in \mathcal{D}_2\) there is an element \(d \in \mathcal{D}_1\)

2.2 Strings and Languages

On predefined set alphabet.