Lecture 12 - Relations

These flashcards cover key vocabulary and concepts related to Logic and Algorithms as outlined in the lecture notes.

Ordered n-tuple

An ordered collection of elements enclosed by (), where the order matters.

Cartesian Product

The Cartesian Product of sets A and B is A × B = {(a, b) : a ∈ A and b ∈ B}.

Binary String

A string whose alphabet is {0, 1}.

Concatenation

The operation of joining two strings together.

Binary Relation

A relation defined between two sets, represented by a subset of A x B.

N-ary Relation

A relation involving more than two sets, represented by A1 × … × An.

In-degree of a vertex

The number of edges pointing into a vertex in a directed graph.

Out-degree of a vertex

The number of edges pointing out of a vertex in a directed graph.

Composition of Relations

The relation combining relations R from set A to B and S from B to C, producing ordered pairs (a, c).

Empty String (λ)

The unique string that has no characters.

Alphabet

The set of symbols or characters from which strings are formed.

Ordered Pair

A pair of elements (a, b) where order matters; (a, b) ≠ (b, a).

Domain

The set from which the elements of a binary relation are taken.

Directed Graph (Digraph)

A graph with a set of vertices and a set of directed edges.

Relation

A structure used to represent relationships between sets.

Example of Binary Relation

For cities A and countries B, R is a relation if (a, b) ∈ R means city a is in country b.