« nazaj
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:
- refleksivnost: $\forall a \in A: a \, R \, a$
- irefleksivnost: $\forall a \in A: \lnot (a \, R \, a)$
- simetričnost: $\forall a, b \in A: (a \, R \, b \Rightarrow b \, R \, a)$
- asimetričnost: $\forall a, b \in A: (a \, R \, b \Rightarrow \lnot (b \, R \, a))$
- antisimetričnost: $\forall a, b \in A: (a \, R \, b \land b \, R \, a \Rightarrow a = b)$
- tranzitivnost: $\forall a, b, c \in A: (a \, R \, b \land b \, R \, c \Rightarrow a \, R \, c)$
- intranzitivnost: $\forall a, b, c \in A: (a \, R \, b \land b \, R \, c \Rightarrow \lnot (a \, R \, c))$
- sovisnost: $\forall a, b \in A: (a \ne b \Rightarrow a \, R \, b \lor b \, R \, a)$
- stroga sovisnost: $\forall a, b \in A: (a \, R \, b \lor b \, R \, a)$
- 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}\]
- Določi relaciji $R^{-1}$ in $R \circ S$.
- 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.\]
- Kateri pari števil so med sabo v relaciji $Q$: $72,75,82,85$?
- 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}.\]
- Pokaži, da je $R$ ekvivalenčna relacija.
- Poišči $R[30]$ in $R[12]$.
- 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$.