matematica disccreta

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 como por 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 podemos mostrar 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)  CRelación de pertenencia:
Se define de elemento a conjunto. A la izquierda del signo  (pertenece) debe haber un elemento y a la derecha 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 poseeun conjunto.












Inclusión: Igualdad:

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











CONJUNTO DE PARTES
Dado un conjunto 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 subconjuntoimpropio 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 el conjunto 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 vezconjuntos 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 el conjunto 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...