Mate

www.monografias.com

Apuntes de Matemática Discreta

1. Preposición, Tablas de verdad, Tautología y Contradicción
2. Relación de pertenencia
3. Conjunto de partes
4. Partición
5. Inducción matemática
6. Sucesiones por recurrencia
7. Reglas de divisibilidad
8. Cambio de base
9. Producto cartesiano
10. Relaciones
11. Funciones
12. Relaciones definidas de un conjunto en si mismo
13.Clausura de una relación
14. Composición de funciones
15. Relación de equivalencia
16. Conjunto cociente
17. Operaciones binarias
18. Conjuntos ordenados
19. Grupos
20. Subgrupos
21. Redes, subredes, átomos
22. Lenguajes
23. Autómatas finitos

LÓGICA Y CÁLCULO PROPORCIONAL:
Preposición: Cualquier frase susceptible de adquirir un valor de verdad. En general se compone de la siguientemanera: (SUJETO + VERBO + PREDICADO)

Tablas de verdad:
P Q PQ PQ PQ PQ PQ

V V V V F V V
V F F V V F F
F V F V V F V
F F F F F V V


Tautología: El valor de verdad de toda la columna es Verdadero.
Contradicción: El valor de verdad de toda la columna es Falso.
-----------------------------------------------
Tautología: ~Contradicción.
Contradicción:~Tautología.
Si el antecedente de una implicación es Falso, el valor de verdad es Verdadero

Leyes de De Morgan:

P Q ~ (PQ)  ~P  ~Q

V V F V V F F F
V F F V V F F V
F V F V V V F F
F F V F V V V V


Cuantificadores:
Hay dos tipos:
El cuantificador Universal  (“Para todo”) y el cuantificador existencial  (“Existe”).
Hay proposiciones comopor ejemplo: “5 > 2”; “X toma el mismo valor que Y”; “5²=20”; a las que podemos adjudicarle un valor de verdad (Verdadero o Falso), y hay expresiones que incluyen variables como x²+2x-3 = 0 que no podemos decir que sean proposiciones, puesto que si x=1 resulta verdadero, pero su x=0 entonces resulta falso.
Si decimos “ x: x²+2x-3= 0”, ahora si es una proposición y es falsa, puesto que podemosmostrar el contraejemplo, dándole a x el valor “0”.
La expresión: “ x / x²+2x-3 = 0” es también una proposición y en este caso es verdadera.

Negación de los cuantificadores:

~ ( x: P(x) )   x: ~ P(x)
~ ( x: P(x) )  x: ~ P(x)

(p1, ^ p2 ^ p3 ^ p4)  C

Relación de pertenencia:
Se define de elemento a conjunto. A la izquierda del signo  (pertenece) debe haber un elemento y a laderecha del signo un conjunto. Para que la expresión sea verdadera el elemento de la izquierda debe ser alguno de los elementos del conjunto de la derecha.
El  (conjunto vacío) es el que no contiene ningún elemento.
 (cardinal) es la cantidad de elementos que posee un conjunto.

Inclusión: Igualdad:

A  B  x  A  x  B A = B  (A  B ^ B  A )

CONJUNTO DE PARTES
Dado unconjunto A, llamamos P(A) (partes de A), a un conjunto cuyos elementos son todos los subconjuntos posibles del conjunto A.
El conjunto vacío es subconjunto trivial de cualquier conjunto, y el mismo conjunto A es subconjunto impropio de si mismo. Todos los otros subconjuntos se llaman propios. En nuestro caso:

 A = 3  P(A) = 8
A
En general:  P(A) = 2

Por este motivo elconjunto de partes se llama también Conjunto Potencia.
A =   = 0
P(A) {0;A}  = 2º = 1
A = {a}  = 1
P(A) {0;A}  = 2¹ = 2

Partición:
Dado un conjunto “A ” y otro conjunto “P”, cuyos elementos son a su vez conjuntos a los cuales llamamos Pi.

P = {P1, P2, P3, … Pn}

Decimos que P es una partición de A si se cumple que la intersección de dos elementos cualquiera de P es siempre elconjunto vacío; la unión de todos los elementos de P es el conjunto A. Por último, ningún elemento de P es el conjunto vacío.

Condiciones:
1º) Pi ^ Pj =  si i  j
n
2º) U Pi = A
i = 1
3º) Pi  0  i

Ejemplificación:
Sea A = {1,2,3,4,5,6}

P1 = {1,2,3,4; 5,6} Es partición
P2 = {2,4; 1,6; 3,5} Es partición

P3 = {1,3,5; 1,2,4,6}
No...