# 2. Methodical guidelines / Методичні вказівки

This section is **self-contained**: it collects all the theory of the work's
theme — finite sets and their operations — together with practical guidance for
carrying out the tasks in [4task.md](4task.md). No outside material is required.

## 2.1 Sets: basic notions

A **set** is an unordered collection of **distinct** objects, called its
*elements*. We write $x \in A$ if $x$ is an element of $A$, and $x \notin A$
otherwise. A finite set may be written by listing its elements in braces, e.g.
$A = \{1, 2, 3\}$.

![Membership: element x belongs to set A while y lies outside it](img/membership.png)

Two conventions define what a set *is*:

- **Distinctness (no duplicates).** An element is either in the set or not;
  repeating it changes nothing: $\{1, 2, 2, 3\} = \{1, 2, 3\}$.
- **No order.** The elements have no positions: $\{1, 2, 3\} = \{3, 1, 2\}$.

**Equality.** $A = B$ means they have exactly the same elements — every element
of $A$ is in $B$ and every element of $B$ is in $A$. Equality is therefore
decided by **membership, not by position**. This is the rule you must use to
compare two sets that are stored as lists in an arbitrary order.

**Cardinality.** $|A|$ is the number of distinct elements of $A$. The **empty
set** $\varnothing$ contains nothing, so $|\varnothing| = 0$.

**Subset.** $A \subseteq B$ ("A is a subset of B") means every element of $A$ is
also in $B$. Note $A = B$ exactly when $A \subseteq B$ and $B \subseteq A$.

**Universal set.** Many problems fix in advance a set $U$ of *all* elements under
consideration — the **universe**. It is the reference domain against which the
*complement* of a set is taken (see below).

## 2.2 The operations of this work

Let $A$ and $B$ be sets and $U$ a universal set with $A \subseteq U$.

| Operation | Notation | Definition | Example ($A=\{1,2,3\}$, $B=\{3,4,5\}$) |
|---|:--:|---|---|
| **Union** | $A \cup B$ | $\{x : x \in A \ \text{or}\ x \in B\}$ | $\{1,2,3,4,5\}$ |
| **Intersection** | $A \cap B$ | $\{x : x \in A \ \text{and}\ x \in B\}$ | $\{3\}$ |
| **Difference** | $A \setminus B$ | $\{x : x \in A \ \text{and}\ x \notin B\}$ | $\{1,2\}$ |
| **Complement** | $\overline{A}$ | $U \setminus A = \{x \in U : x \notin A\}$ | $\{4,5\}$ if $U=\{1,\dots,5\}$ |

![Venn diagram of the union A ∪ B, with both circles shaded](img/venn_union.png)

Two remarks that matter for the implementation:

- **Complement is relative.** $\overline{A}$ has no meaning without a universe;
  outside $U$ there is no notion of "everything not in $A$." Your `complement`
  function therefore takes the universal set as an explicit argument.
- **Difference is directed.** $A \setminus B$ and $B \setminus A$ are different in
  general: for the sets above, $A \setminus B = \{1,2\}$ but
  $B \setminus A = \{4,5\}$. Sets with $A \cap B = \varnothing$ are called
  **disjoint**.

## 2.3 The algebra of sets

The operations obey algebraic laws. You do not need to prove them for this work,
but they explain *why* your functions should behave as they do, and they let you
check results by hand (see [6questions.md](6questions.md)).

| Law | Statement |
|---|---|
| Commutativity | $A \cup B = B \cup A$, $\quad A \cap B = B \cap A$ |
| Associativity | $(A \cup B) \cup C = A \cup (B \cup C)$, and likewise for $\cap$ |
| Distributivity | $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$ |
| Identity | $A \cup \varnothing = A$, $\quad A \cap U = A$ |
| Domination | $A \cup U = U$, $\quad A \cap \varnothing = \varnothing$ |
| Complement | $A \cup \overline{A} = U$, $\quad A \cap \overline{A} = \varnothing$, $\quad \overline{\overline{A}} = A$ |
| De Morgan | $\overline{A \cup B} = \overline{A} \cap \overline{B}$, $\quad \overline{A \cap B} = \overline{A} \cup \overline{B}$ |

![De Morgan's law: the complement of A ∪ B equals A-complement intersected with B-complement](img/demorgan.png)

Note in particular the identity $A \setminus B = A \cap \overline{B}$ (relative to
a universe $U$): difference can be expressed through intersection and complement.
Union and intersection are commutative; **difference is not**.

## 2.4 Implementing a set without a built-in set type

The rules forbid the language's own set type (`HashSet`, `set()`, `Set`, …). Use
a plain **array/list** and maintain the *distinctness* invariant yourself. Every
operation reduces to one primitive — the **membership test**:

- **membership** ($x \in A$) — scan the list and compare elements (this is
  `containsElement`);
- **insertion** — append $x$ only if `containsElement(A, x)` is false;
- **construction** from a raw list — insert elements one by one, so duplicates
  drop out automatically.

## 2.5 Reference algorithms

```text
function contains(A, x):
    for y in A:
        if y == x: return true
    return false

function union(A, B):
    R ← copy of A
    for x in B:
        if not contains(R, x): append x to R
    return R

function intersection(A, B):
    R ← empty list
    for x in A:
        if contains(B, x): append x to R
    return R

function difference(A, B):        # A \ B
    R ← empty list
    for x in A:
        if not contains(B, x): append x to R
    return R

function complement(A, U):        # elements of U not in A
    return difference(U, A)
```

## 2.6 Complexity

With a list representation, `contains` is $O(|A|)$, so `union`, `intersection`,
and `difference` cost $O(|A| \cdot |B|)$. This is acceptable for the work. A
hash-based or sorted representation would reduce membership to $O(1)$ or
$O(\log n)$ respectively — which is precisely what the forbidden built-in set
types do internally, and the reason for implementing the mechanism by hand here.

## 2.7 The expression evaluator (Tier 3)

The final tier evaluates a string such as `"A intersection B union C"` given a
dictionary that maps names to sets. A workable approach:

1. **tokenise** the string into names (`A`, `B`, `C`) and operator words
   (`union`, `intersection`, `difference`, `complement`);
2. **look up** each name in the dictionary to obtain its set;
3. **fold** the operators over the operands, applying them **left to right**.

Left-to-right evaluation reproduces the expected output of the example:
`A intersection B union C` gives $(A \cap B) \cup C = \{3,5,6,7\}$ (see
[4task.md](4task.md)). Reuse the Tier 1–2 functions inside the evaluator — do not
re-implement the operations.