# 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.