SCC121: Fundamentals of Computer Science Study Notes

SCC121: Fundamentals of Computer Science

Overview of Preliminary Concepts

• Ordered Pairs

  • An ordered pair is defined as a pair of objects in which the sequence matters.

  • Written notation:

• Cartesian Product

  • The Cartesian product of two sets A and B is the set of all possible ordered pairs , where a belongs to set A and b belongs to set B.

  • Written notation: A x B

• Binary and n-ary Relations

  • Defines relations in terms of pairs, triples, or n-tuples of objects.

• Definitions

  • Establishing consistent meanings for terms used within the context of relations.

• Representing Relations

  • Various methods of illustrating or utilizing relations such as tables and directed graphs.

• Operations on Relations

  • Discusses potential operations that can be performed on relations (not elaborated in transcript).

• Properties of Relations

  • Characteristics that describe relations, likely including reflexivity, symmetry, transitivity (not elaborated in transcript).

Objectives

• Understand the basic concepts surrounding relations.

• Develop the ability to accurately represent relations in different forms.

Detailed Concepts

Ordered Pairs

• Definition: An ordered pair is a mathematical concept that consists of two elements with a defined order. Thus, is different from .

Cartesian Product

• Definition: The Cartesian product of two sets A and B includes all ordered pairs where a is an element of A and b is an element of B.

• Mathematical representation: given sets A and B, we can write it as:
  $A imes B = \begin{Bmatrix} (a<em>1,b</em>1),(a<em>1,b</em>2),…,(a<em>n,b</em>m) \ \text{for all } a<em>i \in A, b</em>j \in B \ ext{ and } \ a<em>i,a</em>j \text{ are unique elements of the respective sets.} \end{Bmatrix}$

• Example:

  • Let S = {Helen, Jim, John, Mary} and C = {course1, course2, course3}.

  • This produces ordered pairs:

  • , , , , , , , , , , , .

  • Count of pairs: 4 (from S) * 3 (from C) = 12 pairs.

Binary Relation

• Definition: A binary relation R is a relation that connects elements of one set A to elements of another set B through ordered pairs .

• Mathematical representation: R is defined as R ⊆ A x B,

  • Where R contains pairs that signify a relationship between members of A and B, thus encapsulating all meaningful interactions between them.

• Example Relation T:

  • Let us exemplify relations through students taking courses, such as satisfies the relation R: ∈ T meaning John takes course1.

  • The relation T is then a subset of the Cartesian product of students and courses.

Equality of Binary Relations

• Differences among binary relations are expressed through equality:

  • If R1 ⊆ A1 x A2 and R2 ⊆ B1 x B2, then R1 = R2 if:

  • Sets A1 and B1 are equal; and

  • Corresponding pairs in R1 and R2 are also equivalent sets.

Ordered n-tuples

• Definition: An ordered n-tuple expressed as represents a sequence of n objects where each xi belongs to set A_i. For example, ordered pairs can extend into ordered triplets or even larger sets.

• Equality: Two ordered n-tuples = are considered equal if each respective element of the tuples is identical

  • Written notation: xi = yi for all i, 1 ≤ i ≤ n.

n-ary Relation

• Definition: An n-ary relation generalizes binary relations to n sets. It involves n elements and can be defined through a set of n-tuples.

• Mathematical representation: $R \subseteq A<em>1 \times A</em>2 \times … \times A_n$

  • Example: Let S = {John, Jim, Helen, Mary}, C = {course1, course2, course3}, M = {65, 41, 55, 72, 63} the relation T can be illustrated as:
    T = {, , , , } indicating the scores each student received in their respective courses.

Representing Relations

• 
  

• Tables: Relations can be represented using a tabular format where columns denote distinct attributes such as Student, Course, and Marks.

  • E.g., a table representation of T would consist of students, courses, and their respective scores.

  • 
    

  • Example:
    

    Student	Course	Marks
    John	course1	65
    Jim	course1	41
    Mary	course3	55
    Helen	course2	72
    Helen	course3	63
    Diagraphs: Relationships can be visualized in diagrams involving vertices and arcs to connect pairs.
    A directed graph is denoted as G = (P, A) where P represents the point set and A the arcs (ordered pairs) connecting the points.
    Examples of Diagraph Representation

    • Diagraph Setting:

      • Set P = {1, 2, 3}, arcs A = {<1, 1>, <1, 2>, <1, 3>, <2, 3>} form a relational graph G1 where each arc signifies a relation between points.

    • To indicate bi-directional relationships, mirrored pairs such as <3, 2> would be added.

    Summary of Key Notations and Definitions

    • Binary Relations:

      • Ordered pair: representing the relationship between elements.

      • Binary Relation R defined over A x B as a subset.

    • N-ary Relations:

      • n-tuple: showcasing ordered relationships with defined orderings.

      • Cartesian Product: A1 x A2 x … x An connecting potential elements from all participating sets.

    ---