Diskretne strukture (FiM)

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$

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$

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 < u \lor (p = u \land q < v) \quad \text{in} \\ n &\preceq m &\ &\Leftrightarrow \ n=m \lor n \prec m. \end{alignedat}\]

Pokaži, da je $\preceq$ delna urejenost.
Ali je $\preceq$ linearna urejenost?
Uredi množico $\lbrace 1,2,3,4,5,6,7,8,9 \rbrace$ glede na $\prec$.
Določi najmanjši element glede na $\preceq$ v množici $\lbrace n \in \mathbb{N} \mid 100 \leq n \leq 200 \rbrace$.
Določi neposrednega naslednika števila $96$ glede na $\preceq$.

- 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 < u \lor (p = u \land q < v)) \land (u < p \lor (u = p \land v < q))) \\ &\Rightarrow n = m \lor (p = u \land q < v \land v < q) \\ &\Rightarrow n = m \end{aligned}\]
- Tranzitivnost ($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}\]
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 < u \lor u < p \\ &\iff p = u \lor p < u \lor u < p \\ &\iff 1 \end{aligned}\]

Naloga 5

Vsako nenaraščajoče urejeno zaporedje pozitivnih naravnih števil z vsoto $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)$.

Pokaži, da relacija $\leq$ delno ureja $P(n)$.
Primerjaj razbitje $(2,2,1)$ z ostalimi elementi iz $P(5)$.
Nariši Hassejev diagram za $P(5)$.
Naj bo $Q(n)$ množica vseh razbitij naravnega števila $n$, v katerih ne nastopa število $1$. Nariši Hassejev diagram za $Q(6)$.
Poišči prvi, zadnji, maksimalni in minimalni element v $Q(6)$.

Ta stran je odprtokodna. Izboljšaj to stran.

Ta zapisek je dostopen tudi na HackMD.