MatDiscreta Semana12

Vista previa del material en texto

TEMA: ESTRUCTURAS MATEMÁTICAS
Semana 12
FACULTAD DE INGENIERÍA INDUSTRIAL Y 
SISTEMAS
ESTRUCTURAS MATEMÁTICAS
Una estructura matemática es una serie de objetos matemáticos con la definición de 
las operaciones que se realizan con estos y las propiedades que las acompañan, 
también llamado un sistema matemático, para matemática discreta se estudian 
únicamente las estructuras matemáticas discretas.
Ejemplos
La colección de los conjuntos con las operaciones, unión, intersección y 
complemento, y las operaciones relacionadas, es una estructura matemática 
discreta. Se denota esta estructura por
𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜𝑠,∪,∩,
−
.
La colección de matrices de orden 3x3 con las operaciones de adición, 
multiplicación y transpuesta es una estructura matemática que se denota por 
𝑚𝑎𝑡𝑟𝑖𝑐𝑒𝑠 3𝑥3,+,∗,
𝑇
FIIS - UNI
PROPIEDADES DE UNA ESTRUCTURA 
MATEMÁTICA
Cerradura 
Una estructura es cerrada con respecto de una operación si esa operación produce 
otro elemento de la colección de objetos.
Ejemplo 
▪ La estructura de los números enteros impares con las operaciones suma y 
multiplicación 𝑒𝑛𝑡𝑒𝑟𝑜𝑠 𝑖𝑚𝑝𝑎𝑟𝑒𝑠, +,∗
▪ La estructura no es cerrada con respecto a la adición, dado que la suma de dos 
enteros impares es un entero par.
▪ La estructura es cerrada con respecto a la multiplicación, dado que el producto de 
dos enteros impares es un número impar.
FIIS - UNI
PROPIEDADES DE UNA ESTRUCTURA MATEMÁTICA
Conmutativa
La propiedad conmutativa es el orden de los objetos que no cambia el resultado de la 
operación.
Ejemplo
i) La unión y la conjunción para las matices booleanas son operaciones conmutativas, es 
decir 
𝐴 ∨ 𝐵 = 𝐵 ∨ 𝐴 𝑦 𝐴 ∧ 𝐵 = 𝐵 ∧ 𝐴
ii) La multiplicación ordinaria de matrices no es una operación conmutativa, decir 𝐴𝐵 ≠
𝐵𝐴
Asociativa 
La propiedad asociativa es aquella donde los objetos matemáticos se pueden asociar sin 
que cambie el resultado
Ejemplo
La unión de conjuntos es una operación asociativa dado que 𝐴 ∪ 𝐵 ∪ 𝐶 = 𝐴 ∪ (𝐵 ∪ 𝐶)
FIIS - UNI
PROPIEDADES DE UNA ESTRUCTURA MATEMÁTICA
Distributiva 
Si una estructura matemática tiene dos operaciones binarias entonces la 
distribución de los objetos matemáticos no cambia el resultado.
Ejemplo
En el álgebra de Boole tenemos, si a, b y c pertenecen a B entonces 
a + b. c = a + b (a + c)
a. b + c = a. b + (a. c)
Nótese que en la distribución para la suma en el producto, la expresión a la derecha 
es diferente de la empleada habitualmente para números reales y enteros.
Observación
▪ Una operación que combina dos objetos matemáticos es una operación binaria
▪ Una operación que requiere solo un objeto matemático en una operación unaria 
FIIS - UNI
PROPIEDADES DE UNA ESTRUCTURA MATEMÁTICA
Leyes de Morgan 
Las leyes son aplicables para algunas estructuras matemáticas pero no en general.
▪ Ejemplo
i) La estructura 𝑐𝑜𝑛𝑗𝑢𝑛𝑡𝑜 𝑏𝑜𝑜𝑙𝑒𝑎𝑛𝑜,+,∗ , 𝑐𝑜𝑚𝑝𝑙𝑒𝑚𝑒𝑛𝑡𝑜
Si a y b elementos del conjunto booleano B entonces
𝑎 + 𝑏 = ഥ𝑎. ത𝑏
𝑎𝑏 = ത𝑎 + ത𝑏
ii) La estructura 𝑛𝑢𝑚𝑒𝑟𝑜𝑠 𝑟𝑒𝑎𝑙𝑒𝑠, +,∗ , , no satisface las leyes de Morgan, ya que 
𝑥 + 𝑦 ≠ 𝑥 ∗ 𝑦
FIIS - UNI
OPERACIÓN BINARIA
Definición:
Es una aplicación o función definida en un conjunto no vacío A, es decir
∗ ∶ 𝐴𝑥𝐴 → 𝐴
𝑎1, 𝑎2 → 𝑎1 ∗ 𝑎2
Donde como una operación binaria es una función entonces solo se le asigna un 
elemento de A a cada pareja ordenada.
Ejemplos 
La operación binaria de suma en 𝑍 es conmutativa es decir
▪ 𝑎 ∗ 𝑏 = 𝑎 + 𝑏 = 𝑏 + 𝑎 = 𝑏 ∗ 𝑎
La operación binaria de resta en 𝑍 no es conmutativa es decir
▪ 2 − 3 ≠ 3 − 2
FIIS - UNI
SEMIGRUPO
Definición
Un semigrupo es un subconjunto no vacío A con una operación binaria asociativa (*) 
definida en A. Se denota el semigrupo como (S,*).
Por otro lado el semigrupo (S,*) es conmutativo si (*) es una operación conmutativa.
Ejemplo 
La operación binaria de suma en 𝑍 es asociativa por lo tanto 𝑍,+ es un semigrupo
Elemento identidad en un semigrupo
Un elemento 𝑒 de un semigrupo (𝑆;∗), es un elemento identidad si se cumple
𝑒 ∗ 𝑎 = 𝑎 ∗ 𝑒 = 𝑎
Ejemplo: Los semigrupos 𝑍, . , y 𝑍,+ tienen elemento identidad 
FIIS - UNI
MONOIDE E ISOMORFISMO
▪ Monoide
Un monoide es un semigrupo (𝑆;∗) que tiene elemento identidad 
Ejemplo 
Los siguientes semigrupos 𝑍, . , y 𝑍,+ son monoides.
Isomorfismo 
Sean (𝑆;∗) y (𝑇;∘), dos semigrupos, una función 𝑓: 𝑆 → 𝑇es un isomorfismo de (𝑆;∗) a 
(𝑇;∘) si es una correspondencia biyectiva de S a T y si 
𝑓 𝑎 ∗ 𝑏 = 𝑓 𝑎 ∘ 𝑓 𝑏 , ∀𝑎, 𝑏 ∈ 𝑆
FIIS - UNI
ISOMORFISMO
Ejemplo
Sea T el conjunto de todos los enteros pares, probar que los semigrupos (𝑍;+) y (𝑇;+) son 
isomorfos.
Prueba
Definimos la función 𝑓: 𝑍 → 𝑇 donde para cada 𝑎 ∈ 𝑍 le corresponde 𝑓 𝑎 = 2𝑎
i) Probaremos que la función f es biyectiva 
a) Inyectividad
Si 𝑓 𝑎 = 𝑓(𝑏) entonces 2𝑎 = 2𝑏 implicando 𝑎 = 𝑏 por lo tanto f es inyectiva
b) suryectividad
Sea b un entero par 𝑏 ∈ 𝑇, entonces consideremos 𝑎 =
𝑏
2
∈ 𝑍 entonces
𝑓 𝑎 = 2𝑎 = 2
𝑏
2
= 𝑏, por lo tanto f es sobreyectiva
Ahora de a) y b) la función f es biyectiva 
ii) si 𝑓 𝑎 + 𝑏 = 2 𝑎 + 𝑏 = 2𝑎 + 2𝑏 = 𝑓 𝑎 + 𝑓(𝑏)
Finalmente de i) y ii) los semigrupos (𝑍;+) y (𝑇;+) son isomorfos
FIIS - UNI
HOMOMORFISMO
Homomorfismo
Sean (𝑆;∗) y (𝑇;∘) dos semigrupos, una función 𝑓: 𝑆 → 𝑇 definida para todo punto, es un homomorfismo de (𝑆;∗) a (𝑇;∘)
si 
𝑓 𝑎 ∗ 𝑏 = 𝑓 𝑎 ∘ 𝑓 𝑏 , ∀𝑎, 𝑏 ∈ 𝑆
Teorema
Sean (𝑆;∗) y (𝑇;∘) monoides con identidades 𝑒, 𝑒!, respectivamente. Sea 𝑓: 𝑆 → 𝑇 un isomorfismo. Entonces 𝑓 𝑒 = 𝑒!
Demostración
Sea 𝑏 un elemento cualesquiera de 𝑇. Como 𝑓 es sobreyectiva existe 𝑎 ∈ 𝑆 talque 𝑓 𝑎 = 𝑏, entonces 𝑎 = 𝑎 ∗ 𝑒
▪ 𝑏 = 𝑓 𝑎 = 𝑓 𝑎 ∗ 𝑒 = 𝑓 𝑎 ∘ 𝑓(𝑒)
▪ 𝑏 = 𝑏 ∘ 𝑓(𝑒)…….𝛼
De manera análoga si 𝑎 = 𝑒 ∗ 𝑎
𝑏 = 𝑓 𝑎 = 𝑓 𝑒 ∗ 𝑎 = 𝑓 𝑒 ∘ 𝑓(𝑎)
𝑏 = 𝑓 𝑒 ∘ 𝑏………𝛽
▪ Así para cualquier 𝑏 ∈ 𝑇 y de 𝛼 𝑦 𝛽, tenemos
▪ 𝑏 = 𝑏 ∘ 𝑓 𝑒 = 𝑓 𝑒 ∘ 𝑏
▪ Lo que significa que 𝑓(𝑒) es una identidad para 𝑇. Esto implica que 𝑓 𝑒 = 𝑒!∎
FIIS - UNI
HOMOMORFISMO
Ejercicio
Sean (𝑆;∗) y (𝑇;∘) monoides con identidades 𝑒, 𝑒!, respectivamente. Sea 𝑓: 𝑆 → 𝑇 un 
homomorfismo de (𝑆;∗) sobre (𝑇;∘) . Entonces 𝑓 𝑒 = 𝑒!
FIIS - UNI
HOMOMORFISMO
Teorema 
Si 𝑓 es un homomorfismo de un semigrupo conmutativo (𝑆;∗), sobre un semigrupo 
(𝑇;∘), entonces (𝑇;∘) también es conmutativo.
Demostración
Sea 𝑓: 𝑆 → 𝑇; si 𝑥1; 𝑥2 ∈ 𝑇, entonces existen 𝑦1; 𝑦2 ∈ 𝑆 tal que 𝑥1 = 𝑓 𝑦1 ; 𝑦 𝑥2 = 𝑓(𝑦2)
por lo tanto 
𝑥1 ∘ 𝑥2 = 𝑓 𝑦1 ∘ 𝑓(𝑦2), ahora dado que 𝑓 es un homomorfismo y 𝑆 es conmutativo 
entonces se cumple que:
▪ 𝑥1 ∘ 𝑥2 = 𝑓 𝑦1 ∘ 𝑓 𝑦2 = 𝑓 𝑦1 ∗ 𝑦2 = 𝑓 𝑦2 ∗ 𝑦1 = 𝑓 𝑦2 ∘ 𝑓 𝑦1 = 𝑥2 ∘ 𝑥1
▪ 𝑥1 ∘ 𝑥2 = 𝑥2 ∘ 𝑥1
▪ Finalmente concluimos que (𝑇;∘) es conmutativo.
FIIS - UNI
TEORIA DE GRUPOS
Grupo 
Definición.- Sea (𝐺;∗), un monoide entonces (𝐺;∗) es un grupo si cumple las 
siguientes condiciones.
1.- ∀ 𝑎, 𝑏 ∈ 𝐺 , 𝑎 ∗ 𝑏 ∈ 𝐺 (cerradura)
2.- ∀ 𝑎, 𝑏, 𝑐 ∈ 𝐺 , 𝑎 ∗ 𝑏 ∗ 𝑐 = 𝑎 ∗ 𝑏 ∗ 𝑐 (asociatividad)
3.- Existe un elemento 𝑒 ∈ 𝐺 talque 
𝑒 ∗ 𝑎 = 𝑎 ∗ 𝑒 = 𝑎, ∀𝑎 ∈ 𝐺
4.- Para todo elemento en 𝐺 tiene un inverso en 𝐺, respecto al operador (∗)
Además si (𝐺;∗), cumple las cuatro condiciones mencionadas anteriormente y es 
conmutativo entonces se llama grupo abeliano.
FIIS - UNI
TEORIA DE GRUPOS
Ejemplo
Sea (𝑅;∗), donde 𝑅 es el conjunto de los números reales diferentes de cero, y 
definimos la operación ∗ como 
𝑎 ∗ 𝑏 =
𝑎𝑏
2
Verificar si (𝑅;∗), cumple con las condiciones de grupo.
FIIS - UNI
TEORIA DE GRUPOS
Teorema
Si (𝐺,∗) es un grupo entonces cada elemento 𝑎 ∈ 𝐺 tiene un único elemento inverso 
en 𝐺.
Prueba 
Sean ഥ𝑎, ധ𝑎 , inversos de 𝑎, entonces 𝑎. ത𝑎 = 𝑒, 𝑎. ധ𝑎 = 𝑒
▪ ത𝑎 𝑎. ധ𝑎 = ത𝑎𝑒 = ത𝑎 ………………(𝛼)
▪ ത𝑎 𝑎. ധ𝑎 = ത𝑎. 𝑎 ധ𝑎 = 𝑒ധ𝑎 = ധ𝑎……(𝛽)
Ahora de 𝛼 y 𝛽 concluimos que ത𝑎 = ധ𝑎
FIIS - UNI
TEORIA DE GRUPOS 
Teorema 
Si (𝐺,∗) esun grupo y sean 𝑎, 𝑏, 𝑐 elementos de 𝐺entonces.
a) Si 𝑎𝑏 = 𝑎𝑐 entonces 𝑏 = 𝑐
b) Si 𝑏𝑎 = 𝑐𝑎 entonces 𝑏 = 𝑐
Prueba 
a)Si 𝑎𝑏 = 𝑎𝑐 y dado que (𝐺,∗) es un grupo tiene elemento inverso 𝑎−1, luego
𝑎−1 𝑎𝑏 = 𝑎−1 𝑎𝑐 → 𝑎. 𝑎−1 𝑏 = 𝑎. 𝑎−1 𝑐 → 𝑒. 𝑏 = 𝑒. 𝑐 → 𝑏 = 𝑐
Para el caso b) de manera análoga
FIIS - UNI
TEORIA DE GRUPOS
Teorema 
Si (𝐺,∗) es un grupo y sean 𝑎, 𝑏 elementos de 𝐺 entonces.
a) La ecuación 𝑎𝑥 = 𝑏 tiene una única solución en 𝐺
b) La ecuación 𝑦𝑎 = 𝑏 tiene una única solución en 𝐺
Prueba 
a) Dado que (𝐺,∗) es un grupo, si 𝑎−1, 𝑏 ∈ 𝐺 → 𝑎−1. 𝑏 ∈ 𝐺, luego 𝑥 = 𝑎−1. 𝑏 es una 
solución de la ecuación 𝑎𝑥 = 𝑏, es decir 𝑎 𝑎−1𝑏 = 𝑎𝑎−1 𝑏 = 𝑏
Ahora supongamos que 𝑥1, 𝑦 𝑥2 son dos soluciones de la ecuación 𝑎𝑥 = 𝑏, entonces
𝑎𝑥1 = 𝑏 𝑦 𝑎𝑥2 = 𝑏 → 𝑎𝑥1 = 𝑎𝑥2 → 𝑎
−1𝑎𝑥1 = 𝑎
−1𝑎𝑥2 → 𝑒𝑥1 = 𝑒𝑥2 → 𝑥1 = 𝑥2∎
De manera análoga para el caso b)
FIIS - UNI
SUBGRUPO
A continuación presentaremos dos definiciones de subgrupo
Definición.-Sea (𝐺,∗) un grupo y 𝐻 ≠ 0 subconjunto de 𝐺 𝐻 ⊆ 𝐺 , se dice que 𝐻 es 
un subgrupo de 𝐺, si 𝐻 con la operación definida sobre 𝐺 verifica las siguientes 
propiedades.
1.- El elemento identidad 𝑒 de 𝐺 es un elemento de 𝐻
2.- Si 𝑎, 𝑏 ∈ 𝐻 entonces 𝑎 ∗ 𝑏 ∈ 𝐻
3.-Si ℎ ∈ 𝐻, entonces ℎ−1 ∈ 𝐻
Definición.-Sea (𝐺,∗) un grupo, el conjunto 𝐻 es un subgrupo de 𝐺 si cumple las 
siguientes condiciones.
1.-𝐻 ≠ ∅
2.-𝐻 ⊆ 𝐺
3.-∀ 𝑎, 𝑏 ∈ 𝐻 → 𝑎 ∗ 𝑏 ∈ 𝐻
FIIS - UNI
EJEMPLO
Ejemplo
Dados dos subgrupos (𝐻1,*),(𝐻2*) e un mismo grupo 𝐺,∗ , entonces la intersección 
de los subgrupos 𝐻 = 𝐻1 ∩ 𝐻2, es también otro subgrupo del mismo grupo 𝐺,∗ . 
Demostración
FIIS - UNI
GRUPOS PRODUCTOS Y COCIENTES
Teorema
Sean 𝐺1,∗1 y 𝐺2,∗2 dos grupos con elementos identidad 𝑒1, 𝑒2, respectivamente.
En el conjunto 𝐺1𝑥𝐺2 se define la operación ∗ talque:
𝑎, 𝑏 ∗ 𝑐, 𝑑 = 𝑎 ∗1 𝑐; 𝑏 ∗2 𝑑 , entonces 𝐺1𝑥𝐺2;∗ es un grupo y se denomina grupo
producto.
FIIS - UNI