exam in discrete math

RELATIONS.docx

A relation is a set of ordered pairs.

(x, y) = (p, q) (x = p) Λ (y = q)

EX: {a, b: N | a + b = 4 • (a, b)}

Defines the relation {(0, 4), (1, 3), (2, 2), (3, 1), (4, 0)}

Relations are usually named and can be written a number of ways:

EX: eqless = {a, b: N | a = b Λ a < 4} -- constructive specification

OR eqless = {(0, 0), (1, 1), (2, 2), (3, 3)} -- enumeration

If (x, y) is contained in a relation, then say:

(x, y) ∈ R OR R(x, y)

Can say the relation is defined over N x N

Relations describe a relationship between the elements; elements can be ordered pairs whose elements are sets.

EX: files = {new, old, archive, summary, tax}

And users = {Jones, Roberts, Wilson}

The relation CanAccess is a relation over users x P files which describe the files which a particular user can access.

This could contain:

{(Jones, {new}), (Roberts, {new, old, summary}), (Wilson, {tax})}

There are a number of operators defined for relations.

1. Domain operator: dom has one operand; its value is the set whose members are the left-hand elements of the pairs in a relation.

EX: Given CanAccess as defined above, then

dom CanAccess = {Jones, Roberts, Wilson}

2. Range operator: ran has one operand; its value is the set whose members are the right-hand elements of the pairs in a relation.

EX: Given UsesComputer is a relation defined over users x computers and

computers = {VAX780, Sequent, DRS800}

and the current value of UsesComputer is

{(Jones, VAX780), (Roberts, Sequent), (Wilson, VAX780)}

then ran UsesComputer =

{VAX780, Sequent}

3. Inverse operator: written as -1 as superscript; has one operand which is a relation; it reverses the elements of the pairs of the relation it operates on

EX: Given UsesComputer is a relation defined over users x computers and

computers = { VAX780, Sequent, DRS800}

and the current value of UsesComputer is

{(Jones, VAX780), (Roberts, Sequent), (Wilson, VAX780)}

then UsesComputer1 =

{(VAX780, Jones), (Sequent, Roberts), (VAX780, Wilson,)}

Example:

OS users are classified by means of sets NormalUsers and PrivilegedUsers. The association between users and the files they own is modelled by a relation owns over users and files. What expression represents the set of files owned by privileged users?

Answer: We’re looking for a specification that forms the relation which contains privileged users and files. So?

ran{u : users; f : files | u ∈ PrivilegedUsers Λ (u, f) ∈ owns }