Diskretne strukture (FiM) - vaje 26.11.2020

--- tags: vaje, ds, relacije hackmd: https://hackmd.io/Css03TaGQReBfuO4V6fX7Q plugins: mathjax, mermaid --- # 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: 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 * 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} $$ 1. Določi relaciji $R^{-1}$ in $R*S$. 2. Katere od naslednjih lastnosti ima relacija $R$: refleksivnost, irefleksivnost, simetričnost, asimetričnost, antisimetričnost, tranzitivnost, sovisnost, strogo sovisnost? ---- 1. * $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$ 2. * refleksivna: ne * irefleksivna: ja * simetrična: ne * asimetrična: ne * antisimetrična: ne * tranzitivna: ne * sovisna: ne * strogo sovisna: ne ```mermaid 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. $$ 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? ---- 1. * $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$ 2. * 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}. $$ 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. ---- 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$ ---- 1. * 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}$) 2. * $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]$ - $12 = 2^2 \cdot 3$ 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). $$ 1. Pokaži, da je $R$ ekvivalenčna relacija. 2. Določi ekvivalenčne razrede relacije $R$. 3. 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: 1. $(R * S)^{-1}=S^{-1} * R^{-1}$, 2. $R * (S\cup T) = (R * S)\cup (R * T)$, 3. $R * (S\cap T) \subseteq (R * S)\cap (R * T)$. Poišči še primere relacij $R,S,T$, za katere enakost ne velja. ---- 1. * 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$.

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.