owned this note
owned this note
Published
Linked with GitHub
---
tags: vaje, ds, relacije
hackmd: https://hackmd.io/9ie2EG-DRv2i35o01bkVig
plugins: mathjax
---
# 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: <i>$\forall a \in A: a \, R \, a$</i>
2. irefleksivnost: <i>$\forall a \in A: \lnot (a \, R \, a)$</i>
3. simetričnost: <i>$\forall a, b \in A: (a \, R \, b \Rightarrow b \, R \, a)$</i>
4. asimetričnost: <i>$\forall a, b \in A: (a \, R \, b \Rightarrow \lnot (b \, R \, a))$</i>
5. antisimetričnost: <i>$\forall a, b \in A: (a \, R \, b \land b \, R \, a \Rightarrow a = b)$</i>
6. tranzitivnost: <i>$\forall a, b, c \in A: (a \, R \, b \land b \, R \, c \Rightarrow a \, R \, c)$</i>
7. intranzitivnost: <i>$\forall a, b, c \in A: (a \, R \, b \land b \, R \, c \Rightarrow \lnot (a \, R \, c))$</i>
8. sovisnost: <i>$\forall a, b \in A: (a \ne b \Rightarrow a \, R \, b \lor b \, R \, a)$</i>
9. stroga sovisnost: <i>$\forall a, b \in A: (a \, R \, b \lor b \, R \, a)$</i>
10. enoličnost: <i>$\forall a, b, c \in A: (a \, R \, b \land a \, R \, c \Rightarrow b = c)$</i>
Operacije z relacijami:
* <i>$a \, (R \cup S) \, b \iff a \, R \, b \lor a \, S \, b$</i>
* <i>$a \, (R \cap S) \, b \iff a \, R \, b \land a \, S \, b$</i>
* <i>$a \, (R \setminus S) \, b \iff a \, R \, b \land \lnot (a \, S \, b)$</i>
* <i>$a \, (R \circ S) \, b \iff \exists c \in A: (a \, R \, c \land c \, S \, b)$</i>
* <i>$a \, R^{-1} \, b \iff b \, R \, a$</i>
* <i>$R^k = R \circ R \circ \cdots \circ R$</i> (<i>$k > 0$</i> krat)
* <i>$R^{-k} = (R^k)^{-1}$</i>
* <i>$R^0 = Id_A = \lbrace (a, a) \mid a \in A \rbrace$</i>
---
### Naloga 1
Dani sta relaciji <i>$R,S$</i> na množici <i>$A=\lbrace 1,2,3,4,5,6 \rbrace$</i>:
$$
\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 <i>$R^{-1}$</i> in <i>$R \circ S$</i>.
2. Katere od naslednjih lastnosti ima relacija <i>$R$</i>: refleksivnost, irefleksivnost, simetričnost, asimetričnost, antisimetričnost, tranzitivnost, sovisnost, strogo sovisnost?
---
### Naloga 2
Na množici dvomestnih naravnih števil definiramo relacijo <i>$Q$</i> 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 <i>$Q$</i>: <i>$72,75,82,85$</i>?
2. Katere od naslednjih lastnosti ima relacija <i>$Q$</i>: 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* <i>$R[a] = \lbrace b \in A \mid a \, R \, b \rbrace$</i>
- *Faktorska množica* <i>$A/R = \lbrace R[a] \mid a \in A \rbrace$</i>
---
### Naloga 3
Na <i>$\mathbb{N}$</i> definiramo naslednjo relacijo:
$$
m \, R \, n \ \Leftrightarrow \ mn \text{ je kvadrat naravnega števila}.
$$
1. Pokaži, da je <i>$R$</i> ekvivalenčna relacija.
2. Poišči <i>$R[30]$</i> in <i>$R[12]$</i>.
3. Poišči tako množico <i>$A\subseteq\mathbb{N}$</i>, ki bo vsebovala natanko en element iz vsakega ekvivalenčnega razreda.
---
### Naloga 4
Naj bosta <i>$R, S$</i> relaciji na množici <i>$A$</i>. Pokaži, da velja <i>$(R \circ S)^{-1}=S^{-1} \circ R^{-1}$</i>.
---
### Naloga 5
Vsako naravno število <i>$n$</i> lahko enolično zapišemo kot produkt potenc različnih praštevil. Definirajmo funkcijo <i>$f: \mathbb{N} \to \mathbb{N}$</i> 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 <i>$\mathbb{N}$</i> potem definiramo relacijo <i>$R$</i> takole:
$$
n \, R \, m \ \Leftrightarrow \ f(n) = f(m).
$$
Pokaži, da je relacija <i>$R$</i> ekvivalenčna relacija. Določi ekvivalenčni razred, v katerem je število <i>$25$</i>.