Diskretne strukture (FiM) - vaje 27.11.2024

Relacije

• Množice: model predikatnega računa s predikatom \(\in\)
• (\(n\)-mestna) relacija \(R \subseteq A_1 \times A_2 \times \cdots \times A_n\)
• (Dvojiška) relacija na množici \(A\): \(R \subseteq A \times A = A^2\)
• Pišemo \(a \, R \, b \iff (a, b) \in R\)

Lastnosti:

1. refleksivnost: \(\forall a \in A: a \, R \, a\)
2. irefleksivnost: \(\forall a \in A: \lnot (a \, R \, a)\)
3. simetričnost: \(\forall a, b \in A: (a \, R \, b \Rightarrow b \, R \, a)\)
4. asimetričnost: \(\forall a, b \in A: (a \, R \, b \Rightarrow \lnot (b \, R \, a))\)
5. antisimetričnost: \(\forall a, b \in A: (a \, R \, b \land b \, R \, a \Rightarrow a = b)\)
6. tranzitivnost: \(\forall a, b, c \in A: (a \, R \, b \land b \, R \, c \Rightarrow a \, R \, c)\)
7. intranzitivnost: \(\forall a, b, c \in A: (a \, R \, b \land b \, R \, c \Rightarrow \lnot (a \, R \, c))\)
8. sovisnost: \(\forall a, b \in A: (a \ne b \Rightarrow a \, R \, b \lor b \, R \, a)\)
9. stroga sovisnost: \(\forall a, b \in A: (a \, R \, b \lor b \, R \, a)\)
10. enoličnost: \(\forall a, b, c \in A: (a \, R \, b \land a \, R \, c \Rightarrow b = c)\)

Operacije z relacijami:

• \(a \, (R \cup S) \, b \iff a \, R \, b \lor a \, S \, b\)
• \(a \, (R \cap S) \, b \iff a \, R \, b \land a \, S \, b\)
• \(a \, (R \setminus S) \, b \iff a \, R \, b \land \lnot (a \, S \, b)\)
• \(a \, (R \circ S) \, b \iff \exists c \in A: (a \, R \, c \land c \, S \, b)\)
• \(a \, R^{-1} \, b \iff b \, R \, a\)
• \(R^k = R \circ R \circ \cdots \circ R\) (\(k > 0\) krat)
• \(R^{-k} = (R^k)^{-1}\)
• \(R^0 = Id_A = \lbrace (a, a) \mid a \in A \rbrace\)

Naloga 1

Dani sta relaciji \(R,S\) na množici \(A=\lbrace 1,2,3,4,5,6 \rbrace\):

\[ \begin{aligned} R &= \{(1,2),(1,4),(1,6),(2,1),(3,4),(3,6),(5,6)\} \\ \text{in} \quad S &= \{(2,4),(2,6),(4,4),(6,6)\}. \end{aligned} \]

1. Določi relaciji \(R^{-1}\) in \(R \circ S\).
2. Katere od naslednjih lastnosti ima relacija \(R\): refleksivnost, irefleksivnost, simetričnost, asimetričnost, antisimetričnost, tranzitivnost, sovisnost, strogo sovisnost?

Naloga 2

Na množici dvomestnih naravnih števil definiramo relacijo \(Q\) takole:

\[ x_1x_2 \ Q \ y_1y_2 \ \Leftrightarrow \ x_1 \ge y_1 \ \mbox{ali} \ x_2 > y_2. \]

1. Kateri pari števil so med sabo v relaciji \(Q\): \(72,75,82,85\)?
2. Katere od naslednjih lastnosti ima relacija \(Q\): refleksivnost, irefleksivnost, simetričnost, asimetričnost, antisimetričnost, tranzitivnost, sovisnost, strogo sovisnost?

Ekvivalenčne relacije

Relacija \(R\) je ekvivalenčna, če je

• refleksivna,
• simetrična,
• tranzitivna.

• Ekvivalenčni razred \(R[a] = \lbrace b \in A \mid a \, R \, b \rbrace\)
• Faktorska množica \(A/R = \lbrace R[a] \mid a \in A \rbrace\)

Naloga 3

Na \(\mathbb{N}\) definiramo naslednjo relacijo:

\[ m \, R \, n \ \Leftrightarrow \ mn \text{ je kvadrat naravnega števila}. \]

1. Pokaži, da je \(R\) ekvivalenčna relacija.
2. Poišči \(R[30]\) in \(R[12]\).
3. Poišči tako množico \(A\subseteq\mathbb{N}\), ki bo vsebovala natanko en element iz vsakega ekvivalenčnega razreda.

Naloga 4

Naj bosta \(R, S\) relaciji na množici \(A\). Pokaži, da velja \((R \circ S)^{-1}=S^{-1} \circ R^{-1}\).

Naloga 5

Vsako naravno število \(n\) lahko enolično zapišemo kot produkt potenc različnih praštevil. Definirajmo funkcijo \(f: \mathbb{N} \to \mathbb{N}\) s predpisom

\[ f(p_1^{\alpha_1} \dots p_k^{\alpha_k}) = p_1\cdot \alpha_1 + \dots + p_k \cdot \alpha_k. \]

Na množici \(\mathbb{N}\) potem definiramo relacijo \(R\) takole:

\[ n \, R \, m \ \Leftrightarrow \ f(n) = f(m). \]

Pokaži, da je relacija \(R\) ekvivalenčna relacija. Določi ekvivalenčni razred, v katerem je število \(25\).