un pekeña propuesta



Introducción


Para el estudio de la teoría de la computación se necesitan tres herramientas matemáticas básicas. Una de ellas es la notación teórica establecida, otra el dominio de los conceptos de funciones y relaciones, y la tercera son unos buenos conocimientos de inducción matemática. La capacidad para usar la notación teórica establecida depende, fundamentalmente, del conocimientode las definiciones básicas de símbolos y sus significados. Conocer las otras dos herramientas depende de la capacidad para entender razonamientos lógicos. Por tanto comenzaremos con una presentación de las ideas fundamentales de la lógica para pasar establecer los mecanismos matemáticos requeridos.

En lógica, una proposición o sentencia es una frase de la cual se puede determinar si esverdadera o falsa. La frase “2+1 es 5”, “3>2” y “17 es un número primo” son proposiciones, mientras que “ven a nuestra fiesta”, “¿Qué hora es?” y “esta proposición es falsa” no lo son. Si P y Q son proposiciones, se dice que P es equivalete a Q si para todos los casos tienen el mismo valor de verdad. Por eso las frases “3 0} describe el conjunto de los enteros positivos.

Un caso algo especial es elconjunto vacío, representado por {} y también por , que no contiene elementos. El símbolo  se lee como “es un elemento de”. Así, x  X significa que x es un elemento de X. Por otra parte,  se lee como “no es un lemento de”.

Los conjuntos A y B son iguales si contienen exactamente los mismos elementos. Por tanto, si A={1,2,3} y B={2,1,3}, se puede escribir que A=B. Fíjese que para A={a}, {a} ya no es lo mismo. Tenemos que a  A, pero a  {a}.

Si A y B son conjuntos y todos los elementos de A son también elementos de B, se escribe A  B y se dice que A es un subconjunto de B. Por ejemplo, si A={1,2,3} y B={0,1,2,3,4,5}, se tiene A  B. Por otro lado B no es un subconjunto de A, por que los elementos 0, 4 y 5 de B no lo son de A.

Obsérvese que si A  B y B  A simultáneamente,entonces todos los elementos de A estén en B. Por lo tanto si A  B y B  A, tenemos que A = B.

TEOREMA 3.
si A  B y B  C, entonces A  C

Demostración:
Sea x A. Entonces, si A  B se obtiene que x B. Además, puesto que B  C y x B, tenemos que x C. Por tanto, dado que x era un elemento arbitrario de A, resulta que AC.

Supongamos que A es un conjunto potencia. Definimos conjuntopotencia de A como 2A = {B | B A} . Por ejemplo, Sea A = {a,b,c} entonces 2A es el conjunto

{, {a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}

Obsérvese que   2A y A  2A


1.3.1 Operaciones con conjuntos.
En aritmética se puede sumar, restar o multiplicar dos números. En la teoría de conjuntos existen tres operaciones que son análogas a las anteriores. La Union de conjuntos A y B se denotapor A  B y es un conjunto formado por los elementos que aparecen en A, en B o en ambos. Por tanto A  B = {x| x A o x B }.
La intersección de A y B es el conjunto A  B = {x| x A y x B }. Observese que si x  A  B entonces se puede decir que x aparece simultáneamente en A y B.
Por ejemplo, si A ={0,1,2,3,4,5} y B={2,3,5,9} entonces A  B={0,1,2,3,4,5,9} y A  B = {2,3,5}.

Obsérveseque Z+  {0} = N, mientras que N  Z+ = Z+.
Se dice que los conjuntos A y B son disjuntos si A  B = ..


TEOREMA: Dado los conjuntos A y B , se tiene lo siguiente:
1.   A = A
2.   A = 
3. si A B, entonces A  B = A.
4. si A B, entonces A  B = B.
5. A  A = A = A  A
6. a) A  B = B  A
b) A  B = B  A
7. a) A  (B  C) = (A  B)  C
b) A  (B  C) = (A  B)  C8. a) A  (B  C) = (A  B)  (A  C)
b) A  (B  C) = (A  B)  (A  C)


Demostración: Dejaremos al profesor que realice algunas demostraciones y el resto será el alumno quien se encargue de demostrarlo.


Complemento Relativo.
Si A y B son dos conjuntos cualesquiera, el complemento de B con respecto a A (también llamado complemento relativo) es el conjunto.

A-B = {x|xA y...