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} \]

  1. Pokaži, da je \(\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\).
    • 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} \]

  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 < 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)\).

  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)\).
Select a repo