1. Discrete Mathematics

Examples of discrete objects

Sets, graphs, elements, functions, relations

Why?

• Foundation for mathematics approaches to software and hardware
• Software engineering and software testing

Sets

A set is a collection of unordered objects/elements/members, where there are no duplicates.

Set Conventions

Names: Set names are upper case with a single letter (e.g. $A={ \dots }$). Elements/members: Lower case single letters (e.g. $a, b, c, \dots$).

Set membership

If an element belongs to a certain set, we write:

\(\text{Given } \mathbb{N}=\{1, 2, 3, \dots \}\) \(1 \in \mathbb{N},\) meaning: “$1$ is an element of $\mathbb{N}$”.

Conversely,

\[0 \not \in \mathbb{N},\]

means: “$0$ us not an element of $\mathbb{N}$”.

So in summary,

\[\{1, 2, 3\} \equiv \{2, 1, 3\}\]

as sets are unordered, and

\[\{1, 2, 2, 3, 4\} \text{ should instead be written as: } \{1, 2, 3, 4\}\]

as sets do not contain duplicates.

Defining larger sets

If we want to define a set $A$ of every object $x$ such that $x$ is an integer greater than $0$, we can write:

\[A = \{x \mid x \text{ is an integer, and } x > 0\}\]

Set Operations

Union

The union of two sets, is the set containing all of the elements from either set. It forms a new set consisting of all the elements from either of the original sets. (Similar to logical $OR$) If we have sets $A$ and $B$, the union of both sets ($U$) is:

\[U = A \cup B = \{x \mid x \in A \text{ or } x \in B\}\]

Intersection

The intersection of two sets, is the set consisting of all of the elements which the original sets have in common. (Similar to logical $AND$) If we have sets $A$ and $B$, the intersection of both sets ($I$) is:

\[I = A \cap B = \{x \mid x \in A \text{ or } x \in B\}\]

Difference

The difference between two sets, is the resultant set consisting of all the elements from the first set, that are not in the second.

\[D = A - B = \{x \mid x \in A \text{ and } x \not \in B\}\]

Cartesian Product

Ordered pair

An ordered pair, is a pair of objects which order associated with them.

By convention, if objects are represented by $x$ and $y$, then they can be written as an ordered pair: $\langle x, y \rangle$

Note: $\langle a, b \rangle \equiv \langle c, d \rangle \iff a \equiv c, \text{ and } b \equiv d$

$\underline{\text{Example:}}$ Let: \(A=\{a_1, a_2, a_3\}\) \(B=\{b_1, b_2\}\)

The cartesian product $A \times B$ is given as:

\[\{\langle a_1, b_1 \rangle, \langle a_1, b_2 \rangle, \langle a_2, b_1 \rangle, \langle a_2, b_2 \rangle, \langle a_3, b_1 \rangle, \langle a_3, b_2 \rangle \}\]

So in general,

\[A \times B = \{\langle a,b \rangle \mid a \in A, b \in B \}\]

Operator Precedence for Set Operations

• Union, intersection, difference, and the Cartesian product all have the same precedence
• Anything in parentheses always comes first

Note: $A \cap B - C$ does not make sense, but $(A \cap B) - C$ does.