UNIDAD I TEORIA DE CONJUNTOS

 

 

INTRODUCCION

 

INTRODUCCION Y FUNDAMENTOS

 

LOGICA ELEMENTAL

 

LOGICA PROPOSICIONAL

 

PROPOSICIONES

 

CONECTIVOS LOGICOS

 

FORMULAS BIEN FORMADAS

 

JERRARQUIA DE CONECTIVAS 

 

INTERPRETACION DE FORMULAS (tautología, contradicción)

 

FORMULAS EQUIVALENTES

 

FORMAS NORMALES

 

CONJUNTOS

 

NOTACION DE CONJUNTOS

 

SUBCONJUNTOS

 

CONGUNTOS EQUIVALENTES

 

CONJUNTOS FINITOS E INFINITOS

 

ALFABETO

 

PROPIEDADES DE STRING

1.- LONGITUD

2.- CONCANETACION

3.- LENGUAJE

 

RELACIONES

 

 

 

 

INTRODUCCION

En este trabajo se hablara de los conceptos más básicos en lenguajes y autómatas como son: lógica elemental, lógica proposicional, las proposiciones, los conjuntos y las relaciones los elementos que lo conforman y los principales puntos de cada uno de estos significados que se darán a continuación

 

La lógica elemental trata del estudio de la composición de enunciados mediante conectores (y, o, si...entonces, etc.) y se fundamenta en el principio de bivalencia, según el cual, todo enunciado es verdadero o falso, pero nunca ambas cosas a la vez.

 

Se presentan conceptos asociados a la lógica proposicional, cuyos elementos fundamentales son sentencias, que pueden ser evaluadas como falsas o verdaderas; se introduce el concepto de fórmula bien formada y de su deducción a partir de expresiones en lenguaje natural, así como la construcción de fórmulas en sus formas normales. También se muestra la forma de construir circuitos lógicos equivalentes a fórmulas de la lógica proposicional.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

UNIDAD No. 1  TEORIA DE CONJUNTOS

 

 

INTRODUCCION Y FUNDAMENTOS

 

La Teoría de Conjuntos es una teoría matemática, que estudia básicamente a un cierto tipo de objetos llamados conjuntos y algunas veces, a otros objetos denominados no conjuntos, así como a los problemas relacionados con estos.

Intuitiva e informalmente los objetos de estudio de la Teoría de Conjuntos quedan descritos así:

  1. Si x no tiene elementos, entonces x es un objeto de la Teoría de Conjuntos.
  2. Si x es un conjunto, entonces x es un objeto de la Teoría de Conjuntos.
  3. Los únicos objetos de la Teoría de Conjuntos son los descritos en 1 y 2.

La importancia de la Teoría de Conjuntos radica en que a partir de ella se puede reconstruir toda la matemática, salvo la Teoría de Categorías.
Por ejemplo, con la Teoría de Conjuntos se pueden definir los siguientes conceptos y probar todas sus propiedades: par ordenado, relación, función, partición, orden, estructuras algebraicas, los naturales, los enteros, los racionales, los reales, los complejos, etc.

LOGICA ELEMENTAL

La lógica elemental se divide en:

lógica de enunciados

lógica de predicados

Ambas utilizan un lenguaje propio artificial o formalización de un lenguaje natural que permite analizar las proposiciones del lenguaje natural.

El cometido de la lógica clásica elemental es determinar si nuestros razonamientos, independientemente de su contenido, son correctos o incorrectos.

Por razonamientos (o argumentos) se entiende un conjunto de proposiciones de tal manera que, una de las cuales, denominada conclusión del razonamiento, pueda presentarse como consecuencia de las demás proposiciones, llamadas premisas del razonamiento.

En la lógica de enunciados la unidad mínima es el enunciado, es decir, un segmento lingüístico que tiene sentido completo por sí mismo:

 

Esta fiesta es muy divertida

Esta fiesta es muy divertida y la música es muy buena

Para que un enunciado sea tal, tiene que poder atribuírsele valores de verdad o falsedad.

En el caso de las dos oraciones anteriores, la verdad o falsedad habrá de determinarse empíricamente, comprobando si, de hecho, la fiesta es divertida y buena la música. En este caso, además, la dificultad es aún mayor ya que se trata de una afirmación subjetiva.

La lógica de enunciados (o lógica proposicional), trata del estudio de la composición de enunciados mediante conectores (y, o, si...entonces, etc.) y se fundamenta en el principio de bivalencia, según el cual, todo enunciado es verdadero o falso, pero nunca ambas cosas a la vez..

Podemos decir, por lo tanto, que la lógica de enunciados se dedica a formalizar las proposiciones del lenguaje natural en un lenguaje simbólico y a definir los conectores, estudiando las leyes de combinación o deducción de los enunciados que las contienen.

 Los enunciados pueden ser:

1. Simples o atómicos: no tienen conectores de ninguna clase

Ejemplos: El Tajo es un río.

En esta fiesta hay 20 personas

2. Compuestos o moleculares: utilizan conectores que unen varios segmentos lingüísticos:

Ejemplo: En esta fiesta hay 20 personas y poca cerveza

LOS CONECTORES de los enunciados moleculares son:

 

 

 

LOGICA PROPOSICIONAL

 

La lógica proposicional trabaja con sentencias u oraciones a las cuales se les puede asociar un valor de verdad (cierto o falso); estas sentencias se conocen como sentencias declarativas o, simplemente, proposiciones. Existen proposiciones que son simples, así como proposiciones que están construidas por otras proposiciones usando elementos (conectivas lógicas) que las asocian. Al construir una proposición, se debe garantizar que esta puede ser evaluada (fórmula bien formada); de la misma forma, podemos construir proposiciones usando solo un grupo de conectivas, produciendo fórmulas que se dice están en su forma normal. Las formas normales son importantes por el hecho que permiten definir esquemas generales para el tratamiento de estas fórmulas (GSAT, por ejemplo).

Otro aspecto importante es el de determinar si una proposición esta construida (o puede ser deducida) a partir de un conjunto de proposiciones, es decir, si es una consecuencia lógica de dicho conjunto.

Finalmente, existen varias formas de representar una fórmula de la lógica proposicional; aquí se introduce el concepto de circuitos lógicos, donde se asocia a las conectivas lógicas un símbolo gráfico.

Simples o atómicas: constituye la unidad mínima de la cual se puede decir que es V ó F. Se simbolizan con p, q, r, s, t, etc., y se denominan variables proposicionales.

 

Compuestas o moleculares: están compuestas por dos o más proposiciones atómicas (su valor de verdad depende del de las proposiciones que la componen). Los valores de verdad dados  como  posibilidades  de  combinación  entre  proposiciones atómicas  corresponden a los valores que pueden tener una o varias proposiciones combinadas

 

Sólo la comprobación empírica confirmará su valor real o fáctico. Basta con que una sea falsa, para que la molecular sea falsa.

Los objetivos que se persiguen dentro de este módulo son los siguientes:

  1. El alumno distinguirá fórmulas bien formadas a partir de oraciones en lenguaje natural para especificar y definir formalmente un conjunto de sentencias.
  2. El alumno probará consecuencias lógicas (CL) para un conjunto de fórmulas bien formadas, a partir de los teoremas 1 y 2 para distinguir cuando un enunciado es verdadero ante un conjunto de axiomas, o sigue de ellos.

 

PROPOSICIONES

Al escuchar algo como La rosa es una flor o El cocodrilo es un mamífero, fácilmente se puede determinar si estas sentencias son ciertas o falsas; sin embargo, al escuchar No seas flojo! o Quién ganará las elecciones?, no es posible asociar a ellas un valor de verdad. Sentencias como las primeras dos son los elementos fundamentales con los que trabaja la lógica proposicional.

La lógica proposicional (o cálculo proposicional) tiene el propósito de simbolizar cualquier tipo de razonamiento para su análisis y tratamiento. Específicamente, para simbolizar razonamiento, la lógica proposicional usa sentencias declarativas a las que se puede asociar un valor de verdad (cierto o falso); es decir, usa proposiciones.

No existe una notación generalmente utilizada para representar proposiciones, pero en este curso se identifica a cada una de ellas con una letra mayúscula (o una cadena de letras mayúsculas).

Ejemplo: P y Q son proposiciones:

P : La rosa es una flor

Q : El cocodrilo es un mamífero

La asociación de proposiciones produce otras proposiciones conocidas como compuestas, por lo que es posible diferenciar a las proposiciones simples llamándolas fórmulas atómicas o, simplemente átomos y a las compuestas llamándolas fórmulas compuestas. Del ejemplo, P y Q son átomos.

CONECTIVAS LOGICAS

La construcción de fórmulas compuestas requiere del uso de elementos que permitan establecer una relación entre los átomos que la forman; estos elementos se conocen como conectivas lógicas. En la proposición ''El agua esta fría y el calentador está descompuesto''

se tienen dos átomos (El agua esta fria, el calentador está descompuesto), unidos por la partícula ''y'' la cual se dice que es una conectiva lógica. Otro ejemplo sería ''Si Luis es ingeniero, entonces Luis es inteligente'', donde la conectiva lógica es ''Si ... entonces''.

Las conectivas lógicas usadas en la lógica proposicional son cinco y son representadas simbólicamente de varias formas, como se muestra en la tabla 1.

Conectiva

Símbolos asociados

Negación (No)

~, ¬ , -

Conjunción (Y)

Ù, &, *

Disyunción (O)

Ú, |, +

Condicional (Si ... entonces)

®

Bicondicional (Si y solo si)

« , =

Tabla 1: Conectivas Lógicas.

Así, para los ejemplos mencionados, se tendría la siguiente representación:

Ejemplo: C: ''El agua esta fría y el calentador está descompuesto'', se representa por AÙB.

donde:

       A: El agua esta fría.

       B: El calentador esta descompuesto.

Ejemplo: R: ''Si Luis es ingeniero, entonces Luis es inteligente'', se representa por  P®  Q.

donde:

       P: Luis es ingeniero.

       Q: Luis es inteligente.

Como es posible determinar si una proposición es cierta o falsa, al encontrarse con proposiciones unidas por conectivas lógicas, es necesario conocer cuales son las reglas que se aplican para determinar si la proposición completa es cierta o falsa. La tabla 2 señala los valores resultantes para la evaluación de proposiciones compuestas a partir de las diferentes combinaciones de valores de verdad de sus átomos. En esta tabla P y Q son los átomos y se utiliza V para un valor cierto y F para uno falso.

 

 

 

P

Q

¬ P

PÙQ

PÚQ

P® Q

P« Q

V

V

F

V

V

V

V

V

F

F

F

V

F

F

F

V

V

F

V

V

F

F

F

V

F

F

V

V

 

Tabla 2: Valores de verdad de proposiciones compuestas.

Ejemplo: Si P tiene un valor V, Q tiene un valor F y R es V, el valor de P® R es V y el valor de P® Q es F.

FORMULAS BIEN FORMADAS

Como se ha explicado, las proposiciones compuestas son agrupaciones de átomos unidos por conectivas lógicas; es importante aclarar que al construir proposiciones, se requiere seguir una serie de reglas que establecen si una fórmula esta bien formada. De acuerdo a lo anterior, una formula bien formada (fbf) es aquella que cumple los siguientes cuatro puntos:

  1. Un átomo es una fórmula bien formada.
  2. Si P es una fórmula bien formada, ¬ P también es una fórmula bien formada.
  3. Si P y Q son fórmulas bien formadas, PÙQ, PÚQ, P® Q y P« Q son fórmulas bien formadas.
  4. Todas las fórmulas bien formadas se obtienen aplicando las reglas 1, 2 y 3.

De lo anterior, se puede decir que fórmulas están bien formadas y que fórmulas no lo están:

Ejemplo: Las siguientes son fórmulas bien formadas:

PÚ¬ Q

PÚ¬ Q® S

Ejemplo: Las siguientes no son fórmulas bien formadas:

® S

ÚP¬

P¬ R

 

JERARQUIA DE CONECTIVAS

Como se estableció anteriormente, para determinar el valor de verdad de una proposición compuesta, es necesario conocer cuales son las reglas que se aplican para determinar si la proposición completa es cierta o falsa; asimismo, al tener fórmulas con dos o más conectivas, se deben conocer las reglas de precedencia y asociatividad de las conectivas para asegurar que la evaluación es correcta. Aún cuando existen algunas diferencias en la determinación de una jerarquía de conectivas, en este texto se utilizará el siguiente orden:

¬ , Ù, Ú, ® , «

donde ¬ (negación) es el operador con mayor jerarquía en la secuencia y « (bicondicional) es el operador con el menor peso.

Ejemplo: El orden de evaluación de ¬PÚQÙR es, utilizando paréntesis, ( (¬ P) Ú( QÙR) ) ; es decir, primero se evalúa ¬ P, posteriormente QÙR, y finalmente se aplica  al resultado de ambas evaluaciones.

Al tener una fórmula con la presencia de dos o mas conectivas iguales, el orden de asociatividad siempre es de izquierda a derecha.

Ejemplo: El orden de evaluación de P® Q® R es ( ( P® Q) ® R) .

INTERPRETACION DE FORMULAS

Una interpretación de una fórmula es una asignación de valores de verdad a un conjunto de átomos; para una fórmula con dos átomos se tienen dos posibles interpretaciones, para una con tres se tienen ocho interpretaciones, y en general para una fórmula con n átomos de tienen 2n interpretaciones.

Considerando las condiciones discutidas anteriormente, es posible determinar el valor de verdad cualquier una fórmula de la lógica proposicional.

Ejemplo: Teniendo que P es V, Q es F, R es V y S es V, la interpretación para la fórmula ¬ ( P® Q) ® ( RÙS) es:

P

Q

R

S

P® Q

¬ ( P® Q)

RÙS

¬ ( P® Q) ® ( RÙS)

V

F

V

V

F

V

V

V

En general, para evaluar una fórmula, se deben considerar todas sus posibles interpretaciones.

Ejemplo: La evaluación de ¬ ( P® Q) ® ( RÙS) es:

 

 

 

 

 

 

CP

Q

R

S

P® Q

¬ ( P® Q)

RÙS

¬ ( P® Q) ® ( RÙS)

V

V

V

V

V

F

V

V

V

V

V

F

V

F

F

V

V

V

F

V

V

F

F

V

V

V

F

F

V

F

F

V

V

F

V

V

F

V

V

V

V

F

V

F

F

V

F

F

V

F

F

V

F

V

F

F

V

F

F

F

F

V

F

F

F

V

V

V

V

F

V

V

F

V

V

F

V

F

F

V

F

V

F

V

V

F

F

V

F

V

F

F

V

F

F

V

F

F

V

V

V

F

V

V

F

F

V

F

V

F

F

V

F

F

F

V

V

F

F

V

F

F

F

F

V

F

F

V

 

 

De la evaluación de una fórmula, se pueden definir los siguientes conceptos:

Tautología o fórmula válida: Una fórmula es una tautología si es verdadera para todas sus posibles interpretaciones. Una tautología también se conoce como una fórmula válida.

Contradicción, fórmula inconsistente o fórmula insatisfactible: Una fórmula es una contradicción si es falsa para todas sus posibles interpretaciones. Una contradicción también se conoce como una fórmula inconsistente o una fórmula insatisfactible.

Fórmula consistente o fórmula satisfactible: Una fórmula que al menos tiene una interpretación verdadera se conoce como una fórmula consistente o satisfactible.

Fórmula inválida: Una fórmula es inválida si es falsa para al menos una interpretación.

Ejemplo: La fórmula ( P® Q) ÚP es una tautología, ya que todas sus interpretaciones son verdaderas.

 

 

 

 

P

Q

P® Q

( P® Q) ÚP

V

V

V

V

V

F

F

V

F

V

V

V

F

F

V

V

 

Ejemplo: La fórmula ( P® Q) Ù¬ P es consistente, ya que de sus interpretaciones, dos son verdaderas.

P

Q

¬ P

P® Q

( P® Q) Ù¬ P

V

V

F

V

F

V

F

F

F

F

F

V

V

V

V

F

F

V

V

V

Como consecuencia de las definiciones anteriores, se tiene que:

 

 

 

FORMULAS EQUIVALENTES

Al evaluar las fórmulas P® Q y ¬ PÚQ se observa que todas sus interpretaciones son iguales, por lo que se dice que ambas fórmulas son equivalentes.

Ejemplo: P® Q y ¬ PÚQ son fórmulas equivalentes:

P

Q

¬ P

P® Q

¬ PÚQ

V

V

F

V

V

V

F

F

F

F

F

V

V

V

V

F

F

V

V

V

 

La tabla 3 muestra estas leyes. Se utiliza el símbolo Tautología para indicar una tautología y el símbolo Contradicción para indicar una contradicción.

Ley de equivalencia

Fórmula

Doble Implicación

F«G = (F® G)Ù(G® H)

Implicación

F® G = ¬ FÚG

Distribución

FÚ(GÙH) = (FÚG)Ù(FÚH)

 

FÙ(GÚH) = (FÙG)Ú(FÙH)

Asociación

(FÚG)ÚH = FÚ(GÚH)

 

(FÙG)ÙH = FÙ(GÙH)

Complementación

FÙ¬ F = Contradicción

 

FÚ¬ F = Tautología

 

¬ ¬ F = F

Conmutación

FÚG = GÚF

 

FÙG = GÙF

Cero

FÚTautología = Tautología

 

FÙContradicción = Contradicción

Identidad

FÚContradicción = F

 

FÙTautología = F

Idempotencia

FÚF = F

 

FÙF = F

Absorción

FÚFÙQ = F

 

FÙ(FÚQ) = F

 

FÚ¬ FÙQ = FÚQ

Leyes de Morgan

¬ (FÚQÚH) = ¬ FÙ¬ QÙ¬ H

 

¬ (FÙQÙH) = ¬ FÚ¬ QÚ¬ H

Tabla 3: Leyes de equivalencias para fórmulas lógicas.

 

FORMAS NORMALES

Las leyes de equivalencia permiten transformar fórmulas de la lógica proposicional en otras fórmulas más simples de evaluar o que estén escritas en alguna forma que sea útil para su manipulación. En lógica proposicional existen dos formas para presentar fórmulas que son importantes ya que permiten definir métodos genéricos de evaluación y análisis; estas formas se conocen como formas normales, y en particular: forma normal conjuntiva y forma normal disyuntiva.

Forma Normal Conjuntiva: Una fórmula está en su forma normal conjuntiva (FNC) si es una conjunción de disyunciones, es decir, tiene la forma: F1ÙF2Ù...ÙFn, en la cual Fn es una fórmula construida por una agrupación de átomos unidos por disyunciones; esto es Fn es P1ÚP2Ú...ÚPm. En ambos casos n y m pueden ser mayores o iguales a 1.

Forma Normal Disyuntiva: Una fórmula está en su forma normal disyuntiva (FND) si es una disyunción de conjunciones, es decir, tiene la forma: F1ÚF2Ú...ÚFn , en la cual Fn es una fórmula construida por una agrupación de átomos unidos por conjunciones; esto es Fn es P1ÙP2Ù...ÙPm.

Ejemplo: La fórmula ( PÚQÚR) Ù( ¬ PÚR)ÙR está en su forma normal conjuntiva construida de tres funciones F1:PÚQÚR, F2:¬ PÚR y F3:R. Cada función es una agrupación de átomos unidos por disyunciones.

Para poder transformar cualquier fórmula a su forma normal (conjuntiva o disyuntiva), es necesario aplicar la siguiente secuencia de operaciones de equivalencia sobre la fórmula original:

  1. Sustituir todas las ocurrencias de conectivas ® y « en la fórmula usando las correspondientes leyes de equivalencia.
  2. Asegurarse que las negaciones afecten solo a átomos, usando las leyes de Morgan y la eliminación de dobles negaciones.
  3. Aplicar las otras leyes para encontrar la forma normal (las principales leyes que se aplican son las distributivas).

Ejemplo: La forma normal conjuntiva de P® Q® S es ( PÚS) Ù( ¬ QÚS)  ya que aplicando las reglas anteriores:

Se eliminan las condicionales P® Q por ¬ PÚQ y ( ¬ PÚQ) ® S por ¬ ( ¬ PÚQ) ÚS.

Se pasan las negaciones a los átomos usando leyes de Morgan produciendo ¬ ¬ PÙ¬ QÚS.

Se elimina la doble negación resultando PÙ¬ QÚS.

Como la conjunción tiene mayor prioridad, se distribuye la disyunción, quedando ( PÚS) Ù( ¬ QÚS) , que ya esta en la forma normal conjuntiva.

Ejemplo: La forma normal disyuntiva de P® Q® S es PÙ¬ QÚS.

CONJUNTOS

Conceptos básicos teoría de conjuntos

Un Conjunto es cualquier colección de objetos el cual pueden ser tratado como una entidad, y un objeto de la colección se dice que es un elemento o miembro del conjunto. Dado un objeto x  y un conjunto S, si x es un elemento del conjunto S, lo podemos escribir como x Î S; si x no es un elemento del conjunto S, podemos escribirlo como Ø(x Î S) o también x Ï S. Los términos conjunto, colección y clase son usados como sinónimos, así como también los términos elemento o miembro.

Hay que hacer notar que no hemos dado una definición formal de conjuntos ni una base para decidir cuando un objeto es un miembro de un conjunto. Como en cualquier otra teoría matemática, no siempre se hace énfasis en los conceptos básicos o en las nociones indefinidas (como por ejemplo, punto o línea en geometría); la definición de conjunto y la relación es un elemento de son conceptos fundamentales de la teoría de conjuntos. Como consecuencia de no tener definiciones para estos conceptos, no tenemos una prueba para determinar cuando algo es un conjunto o cuando, un objeto dado, es un elemento de un conjunto especificado. Por no tener una prueba, debemos de confiar en un sentido común del significado de los términos.

Casi cualquier cosa puede ser puede ser tratada como conjunto, viéndola desde un punto de vista muy matemático, lo que trataremos de ilustrar con los siguientes ejemplos.

El conjunto de enteros no negativos menores que 4. Éste es un conjunto finito con cuatro miembros: 0, 1, 2 y 3.

El conjunto de libros en la biblioteca del ITQ en este momento. Éste también es un conjunto finito. Un conjunto que tal vez sea difícil de listar dado que en éste momento pueden estar prestando y devolviendo libros, es decir hay flujo constante.

El conjunto de nombres de las personas que hablaron a Tombuctú el 15 de febrero del año810 a. C. Éste es un conjunto finito que seguramente tendrá por lo menos un elemento. Aunque éste tiene una característica que tal vez no concuerde con la realidad por la cual será difícil determinar los miembros del conjunto, muchos matemáticos dicen que no hay porque no considerarlo un conjunto.

El conjunto de dinosaurios vivos en el Museo Británico. Asumiendo que no se están realizando experimentos siniestros en dicho museo, éste conjunto tiene la propiedad de no tener ningún elemento, a lo que llamamos conjunto nulo o vacío.

El conjunto de enteros mayores que 3. Como es de suponerse, éste se trata de un conjunto infinito y no hay ninguna dificultad para definir cualquiera de los miembros de éste conjunto.

Desde que un conjunto es caracterizado por sus miembros, un conjunto puede ser especificado por declaración cuando un objeto está en el conjunto. Un conjunto finito puede ser especificado explícitamente por una lista de sus elementos. Los elementos de la lista deben ser separados por comas y la lista encerrada en llaves ( { } ), como lo muestran los siguientes ejemplos:

El conjunto que contiene los elementos A, B y C está denotado por { A, B, C }.

El conjunto que contiene todos los enteros pares no negativos menores que 10 es especificado por { 0, 2, 4, 6, 8 }.

Los elementos de un conjunto infinito no pueden ser listados explícitamente; en consecuencia, necesitamos una forma para describirlos implícitamente. La especificación implícita frecuentemente es hecha por el significado de predicados con una variable libre. El conjunto es definido de manera que los elementos del universo establecido por el conjunto hagan el predicado verdadero. De aquí, si P (x) es un predicado con una variable libre, el conjunto { x | P(x) } denota el conjunto S tal que  c ÎS si y sólo si P (c) es verdadero.

Los siguientes ejemplos son de especificaciones implícitas de conjuntos. Las dos primeras son de conjuntos infinitos; la tercera es un conjunto finito.

El conjunto de enteros mayores que 10 es especificado por

{ x | x Î I Ù x >10 }

El conjunto de enteros pares puede ser especificado como

{ x | $y [ y Î I Ù x = 2y ] }

El conjunto { 1, 2, 3, 4, 5 } puede ser especificado como

{ x | x Î I Ù 1 £ x £ 5 }

Significados menos formales son usados frecuentemente para describir conjuntos. Una técnica es colocar las especificaciones del conjunto a la izquierda de una barra vertical, como lo muestran los siguientes ejemplos:

El conjunto de enteros múltiplos de 3 puede ser especificado por

{ 3x | x Î I } en lugar de

{ x | $y [ y Î I Ù x = 3y ] }.

 

El conjunto de números racionales puede ser especificado por

{ x / y | x, y Î I Ù y ¹ 0 }.

Si un conjunto es finito pero muy largo como para listarse fácilmente o si es un conjunto infinito, las elipses suelen ser usadas para especificar implícitamente un conjunto. Las siguientes especificaciones usan elipses para caracterizar una lista de los elementos de un conjunto.

El conjunto de enteros del 1 al 50 es especificado por

{ 1, 2, 3, …, 50 }

El conjunto de enteros pares no negativos es especificado por

{ 0, 2, 4, 6, … }

Todas éstas técnicas informales de especificaciones de conjuntos son convenientes por lo cual podemos usarlas libremente.

En un desarrollo más formal de la teoría de conjuntos, el siguiente axioma es usado para establecer que los conjuntos son completamente especificados por sus elementos. El axioma nos sirve como una definición de igualdad de conjuntos.

Axioma de Extensión: Dos conjuntos A y B son iguales si y sólo si tienen los mismos elementos.

El axioma de extensión puede ser expresado en notación lógica de dos maneras:

A = B Û "x [ x Î A Û x Î B ]

A = B Û { "x [ x Î A Þ x Î B ]  Ù "x [ x Î B Þ x Î A ]}

El axioma de extensión declara que si dos conjuntos tienen los mismos elementos, aún sin considerar como están especificados, son iguales. Es decir, si un conjunto es especificado explícitamente con una lista, el orden en el que esté listado es irrelevante. Por ejemplo: el conjunto denotado por { A, B, C } es el mismo que (igual a) el conjunto denotado por { C, B, A } y { B, C, A }. Además, no importa el número de veces que aparezca un elemento en el conjunto,

{ A, B, A }, { A, B} y { A, A, A, B, B }

 

 

Son diferentes especificaciones de un mismo conjunto. Un conjunto finito puede ser caracterizado implícita o explícitamente, como lo demuestran los conjuntos { 1, 2, 3, 4, 5 } y { x | x Î I Ù 1 £ x £ 5 }que son el mismo conjunto. También, el mismo conjunto puede ser especificado implícitamente con diferentes predicados, por ejemplo: el conjunto { x | x =0 } y { x | x Î I Ù -1 < x < 1 } son iguales.

Notación de conjuntos

Notación:

Ordinariamente usaremos letras mayúsculas para representar los conjuntos que incluiremos sus elementos dentro de llaves separados por comas, {}.

El símbolo elementoÎsignifica (es elemento de). Análogamente,Ïsignifica (no es elemento de). Ejemplo: Sea S la letra que designa el conjunto descrito precisamente como [a,b,c,d].

Por tanto, S es el conjunto cuyos elementos son las primeras cuatro letras minusculas del alfabeto. Podemos entonces escribir a ÎS, b ÎS, c ÎS y d ÎS. Similarmente fÏ S, 3 Ï S, etc.

Conuntos Iguales:

Usamos el signo de igualdad para indicar que dos símbolos representan al mismo conjunto.

Definición: se dice que dos conjuntos S y T  son iguales si cada elemento de S es elemento de T y viceversa. Se escribe S=T.

Ejemplo: en el ejemplo anterior pusimos S = [a,b,c,d]; puesto que [a.b.c.d] es un símbolo para representar al mismo conjunto que representa S.

Debe notarse que, según esta definición, no importa el orden en que se expresan los elementos. Por lo tanto [a,b,c,d] =[b.d,c.a].

Conjuntos Vacios :

Es útil tener el concepto de un conjunto sin elemento.

Definición: un conjunto sin elementos recibe el nombre de conjuntos vacios o conjunto  nulo y se representa por [ ] o por Æ. Ejemplo: considérese el conjunto S de todos los elementos que los son tanto [a,b,c] como de [d,e,f]. El conjunto S no tiene elementos,; luego, S = [ ].

 

 

Subconjuntos:

Definición: se dice que un conjunto S es subconjunto T, si todos los elementos de S los son T. El símboloÍ se lee (es subconjunto de).

Así, (SÍ T ) se lee (S es subconjunto de T). Decir que S no es subconjunto de T significa que algun elemento de S no lo es de T. En tal caso escribimos S Ë T. Ejemplo: sea S = (a.b.c.d) y T=(a.b.c.d.e). Vemos que S Í T. Sin embargo si  H={a.b.c.f}, notamos que f Ï T, de modo que HËT.

Entenderemos que el conjunto vacío, Æ, siempre es subconjunto de cualquier conjunto T. Si no fuese así ellos significaría que algún elemento de  Æ, no sería miembro de T, pero como Æ, no tiene elementos esto resultaría imposible.

Definición: se dice que S es un subconjunto propio de T, si S Í T, y además existe algún elemento de T que no esta en S. Esto lo escribimos  S Ì T.

Conjuntos Equivalentes:

Cuando los elementos de un conjunto se corresponden con los de un segundo conjunto de  modo que cada elemento de cada conjunto tenga uno, y solo uno, asociado en el otro conjunto, decimos que hay una correspondencia uno a uno entre ambos conjuntos.

Definición: dos conjuntos que se pueden poner en correspondencia uno a uno entre sí, se dice que son equivalentes. Si A es equivalente a B, se escribe A~B. Ejemplo: sean  S = {a.b.c.d} y T = {Ù,?,0,+}. Estos dos conjuntos son  equivalentes puesto que podemos hacer corresponder en forma uno a uno los elementos de un conjunto con los del otro.

Cardinalidad De Un Conjunto

Todos estamos familiarizados con el conjunto ordenado de los números naturales, N = {1,2,3,4..} y el conjunto ordenado de los número enteros no negativos W = {0,1,2,3,4...}.

Contar es el proceso por el cual podemos en correspondencia los elementos de un conjunto con algún subconjunto propio de N, comenzando con 1 y usando los elementos de N en orden y sin saltar ninguno. Un subconjunto así se llama subconjunto estándar de N. Ejemplo: es decir, el subconjunto estándar de N, {1,2,3,4} es equivalente a {a,b,c,d}decimos entonces que S tiene cuatro elementos. Estos lleva a la definición siguiente:

Definición: cuando un conjunto S se equipara con un subconjunto estándar de N, el ultimo elemento de N usado se llama   cardinalidad  del conjunto S y se denota por  n (S). Ejemplo: en el ejemplo anterior, n(S)= 4.

 

 

 

Definición: la cardinalidad Æ, el conjunto vacío es cero.

Tenemos que construir esta definición por separado, puesto que 0ÏN  y, por tanto, no tiene sentido hablar de equiparar elementos que no existen.

La claridad del conjunto {3} es 1, ya que {3} se puede equiparar con {1}. Es decir que el conjunto {3} tiene un miembro. Similarmente, la claridad del conjunto {0} es 1. hay que estar seguro de que entendemos la diferencia entre {} y {0}.

Dos números enteros no negativos m y n, son iguales si ambos son la cardinalidad del mismo conjunto o de conjuntos equivalentes. En tal caso, escribimos m=n..

Definición: si m y n son números entero no negativos, decir que m es  menor que n significa que n es la cardinalidad de un conjunto que se puede equipar con un subconjunto propio de un conjunto de cardinalidad n. Escribiremos entonces m < n. Si m < n podemos decir también que n > m. Ejemplo: S = {a.b.c} y T ={d,e,f,g,h}. Vemos que hay una correspondencia uno a uno entre S y el subconjunto propio de T, {d,e,f}. Por tanto, n (S) < n  (T), o bien puesto que n (S) =3 y  n (T)=5, ponemos 3 < 5.

Conjuntos Finitos E Infinitos:

Si es posible encontrar un subconjunto estándar  de N que se puede hacer corresponder uno a uno  con un conjunto dado S, o si S es el conjunto vacío,  decimos que S es finito. Si no, decimos que infinitos. Ejemplos:

T = {a,b,c..., x,y,z} es conjunto finito, puesto que es equivalente  {1,2,3,4,5...,25,26}.

El conjunto N = {1,2,3...} es infinito, puesto que no es posible equiparar con ningún subconjunto estándar de N.

Notese que, sin embargo si hay un equiparamiento  de N con uno de sus subconjuntos que no es un subconjunto estándar: como el conjunto de los números pares. Vemos que N se puede poner en correspondencia con un subconjunto propio de si mismo. Esto solo se puede hacer en un conjunto infinito.

 

 

 

 

 

ALFABETO

Un alfabeto es un conjunto finito y no vacío, cuyos elementos suelen escribirse con un solo carácter y a los cuales llamaremos letras. De ahora en adelante, emplearemos la letra  para denotar a un alfabeto cualquiera, pero que en nuestras definiciones y teoremas permanece fijo. Una palabra sobre un alfabeto  es una nada (n _ 0) de elementos de.

 En el caso n = 0, tenemos la palabra vacía, a la que denotaremos con la letra.

 

Por ejemplo, consideremos 1 = {a, b}, las siguientes son palabras sobre:

 (a, a, a, b)

(b)

(b, a, a)

() = _

Dado que hemos convenido en que los elementos de un alfabeto requieren de un solo carácter para escribirse, podemos omitir el uso de las comas y de los paréntesis para escribir las palabras de . De esta manera, las palabras anteriores

 

aaab

b

baa

 

Al conjunto de todas las palabras sobre un alfabeto, le llamaremos. Si es una nada de elementos de, entonces a n se le llama la longitud de  y se escribe |'|.

 

 

 

PROPIEDADES DE STRING

 

1.-LONGITUD

Si b es una cadena sobre cualquier alfabeto, su longitud se denota mediante el símbolo |b|. La longitud de b es el número de símbolos que tiene la cadena. Así que, si b = 121 sobre el alfabeto ∑ = {1,2}, entonces |b| = 3.     La cadena vacía e, no tiene símbolos con lo que |b| = 0

 

2.-CONCANETACION

La concatenación de la palabra vacía e con cualquier otra palabra a no modifica a a. Por esta razón, e se comporta como la identidad con respecto a la operación de concatenación.

 

Si A y B son cadenas, la concatenación de w con z es la cadena que se obtiene al añadir a la cadena w la palabra z. Por ejemplo si a = “pera” y b = “arbol”, la concatenación de a con b es la cadena “peraarbol”. La concatenación de las palabras a y b se denota como ab o a·b. Obsérvese que se tiene que:

 

|ab| = |a| + |b|

 

 

3.-LENGUAJES

 

Un lenguaje es un conjunto de palabras. Por tanto el conjunto {1,12,123,1234,12345,123456} es un lenguaje sobre el alfabeto compuesto por dígitos. De forma similar, la colección de palabras inglesas “correctas” es un lenguaje sobre el alfabeto ingles. Obsérvese que si ∑ es un alfabeto, también es un lenguaje, el formado por todas las cadenas con un único símbolo.

 

Los lenguajes pueden ser bastante grandes, como es el caso de todas las palabras inglesas “correctas” o el lenguaje {1,11,111,1111,1111,…} formado por todas las cadenas finitas de unos. Obsérvese que este lenguaje es infinito (aunque cada cadena formada por este lenguaje tenga longitud infinita). Cuando un lenguaje tiene un tamaño muy grande es difícil especificar que palabras le pertenecen.

 

Dado que un lenguaje es un conjunto de cadenas, se puede tener el lenguaje compuesto por ninguna cadena, esto es, un lenguaje vacío. Este no es el mismo lenguaje que el que consta de la cadena vacía {e}. El lenguaje vacío se denota de la misma forma que el conjunto vacío.

 

Supongamos que ∑ es un alfabeto y w una cadena sobre ∑. Si L es el lenguaje formado por algunas de las cadenas sobre ∑ y si w esta en L, entonces se tiene que wÎL y se dice que w es un elemento de L, w es un miembro de L.

 

Por tanto:

 

121 Î {1,12,121,1212,12121}

 

Es necesario tener en cuenta que el lenguaje compuesto por todas las cadenas sobre el alfabeto ∑, se conoce como cerradura de ∑ o lenguaje universal sobre ∑ y se denota por ∑*. Por ejemplo, si se tiene el alfabeto ∑ = {1}, entonces

 

∑* = {e,1,11,111,1111,…}

 

Para cualquier alfabeto, ∑* es infinito (ya que los alfabetos no son vacíos).

 

 

 

 

 

 

 

RELACIONES

 

Una relación del conjunto A con el conjunto B es un subconjunto de A x B.     por tanto si R      A x B y (a, b) Є R. se dice que a esta relación con b bajo la relación con R. por ejemplo, si A ={2,3,4,5} y B ={1,3,5,7,9}, entonces R= {(2,1),(2,3).(5,3),(5,5)}es una relación y 2 esta relacionado con 1 bajo esta relación.

Si A y B son el mismo conjunto se dice que la relación es una relación sobre A. por ejemplo sea R     N x N definida por (x,y) Є R si y solo si x ≤ y. R es la relación “menor o igual que “ sobre N.

La relación R    A x B define dos subconjuntos, uno de A y otro de B. estos son:

Dom (R) ={a \ a Є A y (a, x) Є R para algún x Є B}

Im (R) ={b \ b Є B y (y, b) Є R para algún y Є A}

 

Y se conoce como el dominio y la imagen de R respectivamente por ejemplo si A ={a, b, c d ,e} y B = {1,2,3,4,5,} con R= {(a,1),(a,2),(b,5),(c,4) se tiene que

 

Dom (R) = {a, b, c,} e Im (R) = {1,2,4.5}

 

Si R     A x B es una relación de A con B entonces el conjunto R-1 = {(b, a) |(a, b) Є R} es un subconjunto de B x A por consiguiente ella es una relación misma de B x A. llamaremos a R-1 inversa de la relación R. sea A un conjunto no vacío. Una colección A de subconjuntos no vacíos de A es una partición de A si se cumple con lo siguiente

 

1.- si B y C son conjuntos en A, entonces o bien  B = C o B ∩ C = 0

2.- A =    B Є A B

 

Intuitivamente, una partición de A divide a A en partes no vacías disjuntas por ejemplo sea A = {x\x Є N y x ≤ 10} y sea

 

A = {{0, 2 ,4},{1,3,5},{6,8,10},{7,9}}

 

Una partición de A. por otro lado

 

B ={{0,2,4,6},{1,2,3,5,7,},{9,10},0}

No es una partición

 

En resumen, para la relación

R= {(x, y)\ x e y están en el mismo conjunto de A

 

Tendremos lo siguiente:

 

1.-(a, a) Є R para todo a Є X (propiedad reflexiva)

2.- Si (a, b) Є R entonces (b, a) Є R (propiedad simétrica)

3.- Si (a, b) y (b, c) están en R, entonces (a, c) Є R (propiedad transitiva)

Toda relación que tenga 3 propiedades se dice que es una relación de equivalencia supongamos que R es una relación de equivalencia sobre el conjunto x. para cada x Є X, se

 

define como el conjunto [x]= {y Є X | (x, y) Є R}. El conjunto {x} se llama clase de equivalencia de x.

 

PAGINA PRINCIPAL