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

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