Diskretne strukture (FiM) - vaje 4.12.2020

--- tags: vaje, ds, urejenosti hackmd: https://hackmd.io/db8ZJIUIQm6hJ06sBYLjtw plugins: mathjax, mermaid --- # Diskretne strukture (FiM) - vaje 4.12.2020 --- ## Relacije * $R^k = R * R * \cdots * R$ ($k$ relacij) * $R^a * R^b = R^{a+b}$ če imata $a$ in $b$ enak predznak * $R * R^{-1} \subseteq Id_A$ * $R^+ = R \cup R^2 \cup R^3 \cup \ldots$ tranzitivna ovojnica * $R^* = R^0 \cup R \cup R^2 \cup R^3 \cup \ldots$ tranzitivno-refleksivna ovojnica --- ### Naloga 1 Naj bo $A = \lbrace 1, 2, 3, 4 \rbrace$ in $R = \lbrace (1, 2), (2, 3), (3, 1), (4, 3) \rbrace$. Ali je $R$ tranzitivna? Izračunaj $R^2$, $R^3$, $R^4$, $R^{2020}$, $R^+$ in $R^*$. ---- * $R$ ni tranzitivna relacija * $R^2 = \lbrace (1, 3), (2, 1), (3, 2), (4, 1) \rbrace = R^5$ * $R^3 = \lbrace (1, 1), (2, 2), (3, 3), (4, 2) \rbrace = R^6$ * $R^4 = \lbrace (1, 2), (2, 3), (3, 1), (4, 3) \rbrace = R = R^7$ * $R^{2020} = R^{3 \cdot 673 + 1} = R$ * $R^+ = \lbrace (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3) \rbrace$ * $R^* = \lbrace (1, 1), (1, 2), (1, 3), (2, 1), (2, 2), (2, 3), (3, 1), (3, 2), (3, 3), (4, 1), (4, 2), (4, 3), (4, 4) \rbrace$ ```mermaid graph LR 1 --> 2 --> 3 --> 1 4 --> 3 ``` --- ## Urejenosti * Delna urejenost $\le$: - refleksivna - antisimetričnost - tranzitivnost * Linearna urejenost: - delna urejenost - (strogo) sovisna + $a$ je minimalni element, če $\forall x: (x \le a \Rightarrow x = a)$ + $a$ je maksimalni element, če $\forall x: (a \le x \Rightarrow x = a)$ + $a$ je prvi element, če $\forall x: a \le x$ + $a$ je zadnji element, če $\forall x: x \le a$ --- ### Naloga 2 Na $\mathbb{R}^2$ definiramo relacijo $R$ takole: $$ (x,y) \, R \, (z,w) \ \Leftrightarrow \ y\leq w \text{ in } x-y\leq z-w. $$ Pokaži, da je $R$ delna urejenost. ---- * Refleksivnost: - $(x, y) \, R \, (x, y) \iff y \le y \land x-y \le x-y$ je res * Antisimetričnost: - $$ \begin{aligned} (x, y) \, R \, (z, w) \land (z, w) \, R \, (x, y) &\Rightarrow y \le w \land x-y \le z-w \land w \le y \land z-w \le x-y \\ &\Rightarrow y = w \land x-y = z-w \\ &\Rightarrow x = z \land y = w \\ &\Rightarrow (x, y) = (z, w) \end{aligned} $$ * Tranzitivnost: - $$ \begin{aligned} (x, y) \, R \, (z, w) \land (z, w) \, R \, (u, v) &\Rightarrow y \le w \land x-y \le z-w \land w \le v \land z-w \le u-v \\ &\Rightarrow y \le v \land x-y \le u-v \\ &\Rightarrow (x, y) \, R \, (u, v) \end{aligned} $$ --- ### Naloga 3 Dana je množica $A=\lbrace 1,2,\dots,14 \rbrace$. Nariši Hassejev diagram za delno urejenost $(A, \mid)$. Določi še minimalne, maksimalne, prve in zadnje elemente. ---- * prvi element, edini minmalni element: $1$ * zadnjega elementa ni * maksimalni elementi: $8, 12, 9, 10, 14, 11, 13$ ```mermaid graph TD 2 --- 1 3 --- 1 5 --- 1 7 --- 1 11 --- 1 13 --- 1 4 --- 2 6 --- 2 10 --- 2 14 --- 2 6 --- 3 9 --- 3 10 --- 5 14 --- 7 8 --- 4 12 --- 4 12 --- 6 ``` --- ### Naloga 4 Vsako naravno število $n \in \mathbb{N}$ lahko enolično zapišemo v obliki $n = 2^p(2q+1)$. V $\mathbb{N}$ vpeljemo urejenosti $\prec$ in $\preceq$ takole. Naj bo $n=2^p(2q+1)$ in $m = 2^u(2v+1)$. Potem je: $$ \begin{alignedat}{2} n &\prec m &\ &\Leftrightarrow \ p $\preceq$ delna urejenost. 2. Ali je $\preceq$ linearna urejenost? 3. Uredi množico $\lbrace 1,2,3,4,5,6,7,8,9 \rbrace$ glede na $\prec$. 4. Določi najmanjši element glede na $\preceq$ v množici $\lbrace n \in \mathbb{N} \mid 100 \leq n \leq 200 \rbrace$. 5. Določi neposrednega naslednika števila $96$ glede na $\preceq$. ---- 1. * Refleksivnost: - $n \preceq n \iff n = n \lor n \prec n$ velja * Antisimetričnost ($n = 2^p(2q+1)$, $m = 2^u(2v+1)$): - $$ \begin{aligned} n \preceq m \land m \preceq n &\Rightarrow (n = m \lor n \prec m) \land (m = n \lor m \prec n) \\ &\Rightarrow n = m \lor ((p $n = 2^p(2q+1)$, $m = 2^u(2v+1)$, $k = 2^a(2b+1)$): - $$ \begin{aligned} n \preceq m \land m \preceq k &\Rightarrow (n = m \lor n \prec m) \land (m = k \lor m \prec k) \\ &\Rightarrow ((n = m \lor m = k) \land n \preceq k) \lor (n \prec m \land m \prec k) \\ &\Rightarrow n \preceq k \\ n \prec m \land m \prec k &\Rightarrow (p < u \lor (p = u \land q < v)) \land (u < a \lor (u = a \land v < b)) \\ &\Rightarrow (p < u \land u < a) \lor (p < u \land u = a \land v < b) \lor \\ &\qquad \lor (p = u \land q < v \land u < a) \lor (p = u \land q < v \land u = a \land v < b) \\ &\Rightarrow p < a \lor (p = a \land q < b) \\ &\Rightarrow n \prec k \end{aligned} $$ 2. Stroga sovisnost ($n=2^p(2q+1)$, $m = 2^u(2v+1)$): * $$ \begin{aligned} n \preceq m \lor m \preceq n &\iff (n = m \lor n \prec m) \lor (m = n \lor m \prec n) \\ &\iff n = m \lor n \prec m \lor m \prec n \\ &\iff (p = u \land q = v) \lor p < u \lor (p = u \land q < v) \lor u < p \lor (u = p \land v < q) \\ &\iff (p = u \land (q = v \lor q < v \lor v < q)) \lor p $n$ imenujemo *razbitje* naravnega števila $n$. Razbitje $Z$ je pred razbitjem $S$, kar zapišemo $Z \leq S$, natanko takrat, ko lahko $S$ dobimo tako, da seštejemo nekaj členov zaporedja $Z$ (in jih po potrebi preuredimo). Na primer, $(2,2,1) \leq (3,2)$. Množico vseh razbitij števila $n$ označimo s $P(n)$. 1. Pokaži, da relacija $\leq$ delno ureja $P(n)$. 2. Primerjaj razbitje $(2,2,1)$ z ostalimi elementi iz $P(5)$. 3. Nariši Hassejev diagram za $P(5)$. 4. Naj bo $Q(n)$ množica vseh razbitij naravnega števila $n$, v katerih ne nastopa število $1$. Nariši Hassejev diagram za $Q(6)$. 5. Poišči prvi, zadnji, maksimalni in minimalni element v $Q(6)$.

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.