Lenguajes Formales

ISC. Erivan Martínez Ovando

TEORIA DE CONJUNTOS

• DEFINICIÓN:

Un conjunto es una colección de objetos, los objetos que conforman un conjunto son llamados elementos o miembros.

La notación común para representar un conjunto es a través de letras mayúsculas y sus elementos con letras minúsculas.

Ejemplo: A = {a,b,c,0,1}

Si un objeto x es un elemento de X, se dice que x pertenece a X o que X contiene a x, lo cual se denota como:

x ∈ X

Si un objeto y no es un elemento de X, se emplea la notación:

y ∉ X

• CONJUNTO UNIVERSAL. Los elementos de todos los conjuntos en consideración pertenecen usualmente a un gran conjunto llamado universal, representado con la letra U.

• CONJUNTO VACIO. El conjunto que no contiene elementos y se representa por ∅.

Ejemplos de conjuntos:A = {a,e,i,o,u}Nombres = {Juan, Pedro, Sonia, Karen}

CARACTERÍSTICAS DE LOS CONJUNTOS

• Un conjunto no distingue la repetición de objetos.

• El orden dentro de los elementos de un conjunto, matemáticamente es irrelevante.

• Un conjunto cuando tiene un número infinito de elementos, se dice que es un conjunto infinito y la notación para representarlo es la elipsis “…”.

PRINCIPIO DE EXTENSIÓN

• Definir a un conjunto mediante sus elementos se le conoce como principio de extensión.

PRINCIPIO DE INTENCIÓN

• Definir a un conjunto por sus características o a través de una proposición se le conoce como principio de intención.

EJEMPLOS

EXTENSIONALEXTENSIONAL INTENCIONALINTENCIONAL

X={1,2,3,4,…}X={1,2,3,4,…} X={x:x es positivo}X={x:x es positivo}

X={2,4,6,8,10,…}X={2,4,6,8,10,…} X={x:x es positivo y X={x:x es positivo y par}par}

X={a,e,i,o,u}X={a,e,i,o,u} X={x:x es vocal}X={x:x es vocal}

SUBCONJUNTO

• Un conjunto A se dice que es un subconjunto del conjunto B, si cada elemento de A es también elemento de B, la notación matemática es la siguiente:

A ⊂ B

B={a,e,i,o,u}A={e,i,o}

CONJUNTO DISJUNTO

• Dos conjuntos A y B se dice que son disjuntos si no tiene elementos comunes, esto es:

A ∩ B = ∅

Por ejemplo:X={x:x es par}; Y={y:y es impar}

son disjuntos

CONJUNTOS COMO OBJETOS• Los conjuntos también son objetos y por ello

pueden ser elementos de otros conjuntos. El conjunto {{1,2},{1,3},{2},{3}} tiene 4

elementos.

{∅} es un conjunto con un elemento, mientras que ∅ no contiene elementos, así que {∅} y ∅ son conjuntos distintos, por lo tanto:

∅ ∈ {∅} ∅ ⊂ ∅ ∅ ∉ ∅

CONJUNTO POTENCIA

• El conjunto cuyos elementos son todos los subconjuntos del conjunto A, se denomina conjunto potencia de A y se denota por:

Ejemplo: A = {1,2,3}

2A={∅,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}

PARTICIÓN DE UN CONJUNTO• Una partición de un conjunto A (no vacío) es un

nuevo conjunto formado por subconjuntos definidos por Π de 2A tal que: cada elemento de Π es un conjunto no vacío.los elementos de Π son disjuntos entre sí.la unión de los elementos de la partición, es el mismo conjunto A.

Ejemplo:A = {1,2,a,b} algunas particiones posibles de AA Π=[{1},{2},{a},{b}]A Π=[{1,2,a},{b}]A Π=[{1,2},{a,b}]

CARDINALIDAD

• De manera intuitiva, la cardinalidad de un conjunto es el número de elementos que contiene, por ejemplo:

CONJUNTOCONJUNTO CARDINALIDADCARDINALIDAD

A={1,2,3}A={1,2,3} |A|=3|A|=3

B={a,b}B={a,b} |B|=2|B|=2

C={{a,d},{2,3}}C={{a,d},{2,3}} |C|=2|C|=2

D={{D={{∅∅},{},{∅∅},{},{∅∅}}}} |D|=3|D|=3

E={1,2,3,4,5,…}E={1,2,3,4,5,…} No es posible establecer la No es posible establecer la cardinalidad en conjuntos infinitos o su cardinalidad en conjuntos infinitos o su cardinalidad es simplemente infinita.cardinalidad es simplemente infinita.

OPERACIONES SOBRE CONJUNTOS

En la teoría de conjuntos se tienen operaciones básicas como la unión, intersección y diferencia que se definen de la siguiente manera:

UNIÓN: la unión de dos conjuntos A y B es un tercer conjunto cuyos elementos son también elementos de A o B o ambos.

A∪B={x: x ∈ A ó x ∈ B}

INTERSECCIÓN: La intersección de dos conjuntos A y B es el conjunto cuyos elementos son comunes a A y B.

A∩B={x: x ∈ A y x ∈B}

DIFERENCIA: La diferencia de A con respecto a B, es el conjunto cuyos elementos están en A pero no en B.

A-B={x: x∈A y x∉B}

COMPLEMENTO ABSOLUTO: El complemento absoluto o simplemente complemento, es el conjunto de elementos que pertenecen a U pero no pertenecen a A.

Ac={x: x∈U y x∉A}

EJEMPLOS

A={1,2,3,4}; B={3,4,5,6}; U={1,2,3,…,9}

A∪B={1,2,3,4,5,6}A∩B={3,4}A-B={1,2}Ac={5,6,7,8,9}

DIFERENCIA SIMÉTRICA

• La diferencia simétrica entre dos conjuntos A y B, es el conjunto que contiene exactamente todos los elementos que están en A o en B pero no en ambos.

A⊕B=(A∪B)-(A∩B)

Ejemplos:

{a,b}⊕{a,c}={b,c}

{a,b}⊕{a,b}=∅

DIAGRAMA DE VENN• Un diagrama de Venn es una representación

gráfica de conjuntos. El conjunto universal se representa por el interior de un rectángulo y los otros conjuntos se representan por círculos incluidos en el rectángulo. Ejemplos:

UB

A

UB

A

U

BA

(a) A⊂B (b) A y B son disjuntos (c)

REPRESENTACIÓN DE OPERACIONES DE CONJUNTOS A TRAVÉS DE DIAGRAMAS DE VENN

U

BA

U

BA

A∪B A∩B

A-B Ac

U

BAA

U

BA

LEYES DE CONJUNTOS

• Leyes de ComplementoA∪Ac=UUc =∅A∩Ac=∅∅c =U• Leyes de Morgan(A∪B)c=Ac∩Bc

(A∩B)c=Ac∪Bc