Problema 1 · Álgebra UDL 2022

Tema: Relacions binàries: equivalència, ordre i diagrames de Hasse · Del examen Primer parcial novembre 2022 (2022)

Enunciado

Problema 1 (5 punts). Relació d'ordre en seqüències binàries

Sigui el conjunt de totes les cadenes finites binàries:

A={s=a1a2…an:ai∈{0,1}}A = \{s = a_1 a_2 \dots a_n: a_i \in \{0, 1\}\}

Sobre aquest conjunt es defineix la relació binària RR mitjançant la condició:

a1a2…anRb1b2…bm  ⟺  n≤miai≤bi,∀i≤na_1 a_2 \dots a_n R b_1 b_2 \dots b_m \iff n \le m \quad\text{i}\quad a_i \le b_i, \quad \forall i \le n

a.

[1 punt] Trobeu els elements del conjunt B={s∈A:s̸ ⁣R01 i sR10001}B = \{s \in A: s \not\! R 01 \text{ i } s R 10001\}.

b.

[0,75 punts] Demostreu formalment que RR compleix la propietat antisimètrica.

c.

[0,75 punts] Raoneu si RR és un ordre total o parcial sobre AA.

d.

[2,5 punts] Considereu el subconjunt S={001,010,1000,01001,11000,000100,111000}⊆AS = \{001, 010, 1000, 01001, 11000, 000100, 111000\} \subseteq A.

Representeu el diagrama de Hasse de SS i determineu, en cas que existeixin, el suprem, l'ínfim, el màxim, el mínim, així com els elements maximals i minimals.

Enunciado: Problema 1 · Álgebra UDL 2022

Solución

Según los criterios oficiales de corrección

a. (1 punt) Trobeu els elements del conjunt B = {s ∈ A : s ̸R 01 i s R 10001}.

Solución: 1, 10, 000, 100, 0000, 1000, 00000, 00001, 10000, 10001

b. (0,75 punts) Demostreu formalment que R compleix la propietat antisimètrica.

Solución: Siguin u = a_1...a_n i v = b_1...b_m tals que u R v i v R u. De u R v tenim n <= m i a_i <= b_i per a tot i <= n. De v R u tenim m <= n i b_i <= a_i per a tot i <= m. Per tant n = m i a_i = b_i per a tot i, d'on u = v.

c. (0,75 punts) Raoneu si R és un ordre total o parcial sobre A.

Solución: Ordre parcial

d. Representació del diagrama de Hasse de S

Solución: Diagrama de Hasse amb nivells: - Nivell inferior (minimals): 001, 010, 1000, 000100 (aquest últim aïllat) - Nivell intermedi: 11000 (connectat des de 010 i 1000) - Nivell superior (maximals): 01001 (connectat des de 010), 111000 (connectat des de 001 i 11000), i 000100 (aïllat)

d. Elements minimals de S:

Solución: 001, 010, 1000, 000100

d. Elements maximals de S:

Solución: 01001, 111000, 000100

d. Mínim de S:

Solución: No existeix

d. Màxim de S:

Solución: No existeix

d. Ínfim de S:

Solución: No existeix

d. Suprem de S:

Solución: No existeix

La explicación paso a paso, hecha con IA, es Premium. Premium

Resuélvelo aquí mismo: corrección automática, pistas y solución paso a paso.

Problema 1 - Relacions binàries i d'equivalència · 2017 ›

Más ejercicios de Relacions binàries: equivalència, ordre i diagrames de Hasse