Examen de Álgebra UDL 2017 · parcial novembre 2017

Sigui el conjunt $A = \{(a_1, a_2, a_3, a_4): a_i \in \{0, 1\}\}$. En aquest conjunt es defineixen dues relacions, $R_1$ d'equivalència i $R_2$ d'ordre:

$$(a_1, a_2, a_3, a_4) R_1 (b_1, b_2, b_3, b_4) \iff \sum_{i=1}^4 a_i = \sum_{i=1}^4 b_i$$

$$(a_1, a_2, a_3, a_4) R_2 (b_1, b_2, b_3, b_4) \iff a_i \le b_i, \quad \forall i \in \{1, 2, 3, 4\}$$

a.

Trobeu tots els elements $(a_1, a_2, a_3, a_4) \in A$ tals que $(a_1, a_2, a_3, a_4) R_1 (0, 1, 0, 1)$ i $(a_1, a_2, a_3, a_4) R_2 (0, 1, 0, 1)$. [0,3 punts]

b.

Doneu la classe d'equivalència de $(1, 1, 0, 0)$ per la relació $R_1$. [0,3 punts]

c.

Determineu totes les classes d'equivalència de $R_1$ i el conjunt quocient $A / R_1$. [0,4 punts]

f.

En el mateix conjunt $A$ es defineix la relació $R_3$ mitjançant:

$$a R_3 b \iff \exists c \in A \text{ tal que } a R_1 c \text{ i } c R_2 b$$

on $a = (a_1, a_2, a_3, a_4)$, $b = (b_1, b_2, b_3, b_4)$ i $c = (c_1, c_2, c_3, c_4)$. Determineu si $R_3$ és o no una relació simètrica. [0,3 punts]

Sigui el conjunt $A = \{(a_1, a_2, a_3, a_4): a_i \in \{0, 1\}\}$. En aquest conjunt es defineixen dues relacions, $R_1$ d'equivalència i $R_2$ d'ordre:

$$(a_1, a_2, a_3, a_4) R_1 (b_1, b_2, b_3, b_4) \iff \sum_{i=1}^4 a_i = \sum_{i=1}^4 b_i$$

$$(a_1, a_2, a_3, a_4) R_2 (b_1, b_2, b_3, b_4) \iff a_i \le b_i, \quad \forall i \in \{1, 2, 3, 4\}$$

d.

Determineu si $R_2$ és una relació d'ordre total o d'ordre parcial. [0,2 punts]

Ordre total

Ordre parcial

e.

Considereu el subconjunt $S = \{(1, 0, 0, 0), (0, 1, 0, 0), (1, 1, 0, 0), (0, 1, 1, 1), (1, 1, 1, 0)\} \subseteq A$.

Representeu el diagrama de Hasse de $S$ explicant el procediment seguit. Indiqueu, si existeixen en $S$ o respecte a $A$, el suprem, l'ínfim, el màxim, el mínim, així com els elements maximals i minimals. [0,5 punts]

Problema 2 (2 punts). Aplicacions i combinatòria d'assignacions

Disposem d'un clúster amb quatre nodes $N = \{a, b, c, d\}$ i una llista de sis tasques a executar $T = \{1, 2, 3, 4, 5, 6\}$. Considerem el conjunt $\mathcal{F} = \{f: T \to N\}$ de totes les possibles assignacions de tasques a nodes. Considerem l'aplicació:

$$\mathcal{G}: \mathcal{F} \longrightarrow L, \quad f \longmapsto (f(1), f(2), \ldots, f(6))$$

on $L = \{(a_1, a_2, \ldots, a_6): a_i \in N\}$.

a)

Considereu l'aplicació $f \in \mathcal{F}$ definida per:

$$f(1) = b, \quad f(2) = d, \quad f(3) = a, \quad f(4) = c, \quad f(5) = a, \quad f(6) = c$$

Determineu si $f$ és una aplicació injectiva o exhaustiva. Determineu també el valor de $\mathcal{G}(f)$. [0,4 punts]

b)

Doneu un exemple d'aplicació $f \in \mathcal{F}$ que no sigui ni injectiva ni exhaustiva. [0,4 punts]

c)

Determineu l'antiimatge $\mathcal{G}^{-1}(a, a, c, b, c, b)$. Indiqueu quines tasques ha d'executar el node $b$. [0,4 punts]

d)

Demostreu formalment que $\mathcal{G}$ és una aplicació bijectiva. [0,4 punts]

e)

Determineu quants elements té $L$. Quina relació guarda amb el cardinal de $\mathcal{F}$? [0,4 punts]