« nazaj
Diskretne strukture (FiM) - vaje 26.11.2020
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 * 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 * R * \cdots * 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*S$.
- Katere od naslednjih lastnosti ima relacija $R$: refleksivnost, irefleksivnost, simetričnost, asimetričnost, antisimetričnost, tranzitivnost, sovisnost, strogo sovisnost?
-
- $R^{-1} = \lbrace (2, 1), (4, 1), (6, 1), (1, 2), (4, 3), (6, 3), (6, 5) \rbrace$
- $R * S = \lbrace (1, 4), (1, 6), (3, 4), (3, 6), (5, 6) \rbrace$
-
- refleksivna: ne
- irefleksivna: ja
- simetrična: ne
- asimetrična: ne
- antisimetrična: ne
- tranzitivna: ne
- sovisna: ne
- strogo sovisna: ne
graph LR
1 --> 2
1 --> 4
1 --> 6
2 --> 1
3 --> 4
3 --> 6
5 --> 6
2 ==> 4
2 ==> 6
4 ==> 4
6 ==> 6
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?
-
- $72 \, Q \, 72$, $72 \, Q \, 75$, $\lnot (72 \, Q \, 82)$, $\lnot (72 \, Q \, 85)$
- $75 \, Q \, 72$, $75 \, Q \, 75$, $75 \, Q \, 82$, $\lnot (75 \, Q \, 85)$
- $82 \, Q \, 72$, $82 \, Q \, 75$, $82 \, Q \, 82$, $82 \, Q \, 85$
- $85 \, Q \, 72$, $85 \, Q \, 75$, $85 \, Q \, 82$, $85 \, Q \, 85$
-
- refleksivnost: ja
- irefleksivnost: ne
- simetričnost: ne
- asimetričnost: ne
- antisimetričnost: ne
- tranzitivnost: ne
- sovisnost: ja
- stroga sovisnost: ja
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.
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$
-
- refleksivnost:
- vzamemo $n \in \mathbb{N}$
- dokazujemo $n \, R \, n \iff n^2$ je kvadrat naravnega števila, očitno res
- QED
- simetričnost:
- vzamemo $m, n \in \mathbb{N}$
- predpostavimo $m \, R \, n$, dokazujemo $n \, R \, m$
- $m \, R \, n \Rightarrow mn = nm$ je kvadrat $\Rightarrow n \, R \, m$
- QED
- tranzitivnost:
- vzamemo $m, n, k \in \mathbb{N}$
- predpostavimo $m \, R \, n$, $n \, R \, k$, dokazujemo $m \, R \, k$
- $m \, R \, n \land n \, R \, k \Rightarrow mn, nk$ sta kvadrata $\Rightarrow mn^2k$ je kvadrat $\Rightarrow mk$ je kvadrat $\Rightarrow m \, R \, k$
- QED
- torej je $R$ ekvivalenčna relacija (če $0 \not\in \mathbb{N}$)
-
- $R[30] = \lbrace 30m^2 \mid m \in \mathbb{N} \rbrace$
- $30 \, R \, n \iff 30n$ je kvadrat $\iff n = 2 \cdot 3 \cdot 5 \cdot m^2$
- $30 = 2 \cdot 3 \cdot 5$
- $R[12] = \lbrace 3m^2 \mid m \in \mathbb{N} \rbrace = R[3]$
- $A = \lbrace \prod_{p \in P} p \mid P \subset \mathbb{P} \text{ končna}\rbrace$ (kjer je $\mathbb{P}$ množica vseh praštevil)
Naloga 4
Na $\mathbb{N}$ definiramo naslednjo relacijo:
\[a \, R \, b \ \Leftrightarrow \ 7 \,|\, (5a+2b).\]
- Pokaži, da je $R$ ekvivalenčna relacija.
- Določi ekvivalenčne razrede relacije $R$.
- Poišči še faktorsko množico $\mathbb{N}/R$.
Naloga 5
Naj bodo $R, S, T$ relacije na množici $A$. Pokaži, da velja:
- $(R * S)^{-1}=S^{-1} * R^{-1}$,
- $R * (S\cup T) = (R * S)\cup (R * T)$,
- $R * (S\cap T) \subseteq (R * S)\cap (R * T)$. Poišči še primere relacij $R,S,T$, za katere enakost ne velja.
-
- Dokazujemo $\forall a, b \in A: (a \, (R * S)^{-1} \, b \iff a \, (S^{-1} * R^{-1}) \, b)$
- Vzamemo poljubna $a, b \in A$, dokazujemo ekvivalenco
-
\[\begin{aligned}
a \, (R * S)^{-1} \, b
&\iff b \, (R * S) \, a \\
&\iff \exists c \in A: (b \, R \, c \land c \, S \, a) \\
&\iff \exists c \in A: (a \, S^{-1} \, c \land c \, R^{-1} \, b) \\
&\iff a \, (S^{-1} * R^{-1}) \, b
\end{aligned}\]
Naloga 6
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$.