ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
PORTAFOLIO
MATERIA: ESTRUCTURAS DISCRETAS
DOCENTE:
ESTUDIANTE: ALEXANDER MARTINEZ MORODIAS
CARRERA: ING. DE SISTEMAS
TURNO: MAÑANA
SANTA CRUZ - BOLIVIA
1
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
TEMARIO
UNIDAD I
TEMA: LOGICA MATEMATICA
1.-Introduccion
2.- Proposición
3.- Notación
4.- Conectivos Lógicos
5.- Operaciones Proposicionales
6.- Formulas Proposicionales
6.1.- Clasificación de las Formulas Proposicionales
6.2 Contradicción de tablas de verdad
8.- Circuitos Lógicos
BIBLIOGRAFIA:
ALGEBRA MODERNA “Sebastián Lazo”
ALGEBRA I “Pedro A. Gutiérrez”
ALGEBRA I “Armando Rojo”
2
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
UNIDAD I LOGICA MATEMATICA
1.-Introduccion:
La lógica es una disciplina que trata de los métodos, modos formas del razonamiento humano, ofreciendo reglas y técnicas para determinar si un argumento es válido o no; Una de las metas fundamentales de la lógica es eliminar las ambigüedades del lenguaje común introduciendo símbolos o conectivos lógicos en la construcción de proposiciones.
Lógica = Analizar el comportamiento humano.
Ambigüedades = los elementos que no están definidos claramente.
2.- Proposición:
Es todo enunciado u oración respecto de la cual se puede decir si es verdadero o falso, pero no ambos a la vez, es decir que toda proposición tienes los valores de verdad 1 verdadero u el otro falso.
a) Los siguientes enunciados son proposiciones:
“Carlos estudia estructuras discretas el mes de abril” V“El cuadrado tiene 3 lados” F“Un partido de futbol dura 90 minutos” V“Los gatos ladran” F“15 es múltiplo de 3” V“ −√4+2≥2 “ F
Los siguientes enunciados no son proposiciones:
Todos los que son interrogación o admiración, no son proposiciones:
“Viva Bolivia!!!”
“¿Hola como estas?”
“2 – 4+5”
3.- Notación:
Las proposiciones simples o numéricas se acostumbran a demostrar con letras minúsculas del alfabeto.
p, q, r, s, t…etc.
3
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
Ejemplo:
p: “El sol es cuadrado”
q: “El hombre es arquitecto de su propio destino”
r: “- 2 + 5 = 3”
s: “Los elefantes vuelan”
4.- Conectivos Lógicos:
Son símbolos que aparte de proposiciones simples nos permiten generar estas proposiciones simples o complejas.
Estos conectivos lógicos representan operaciones lógicas definidas.
5.- Operaciones Proposicionales:
Dada una o más proposiciones cuyos valores de verdad se conoce, las operaciones proposicionales tratan de generar otras proposiciones para caracterizar las proposiciones resultantes a través de su valor de verdad utilizando las siguientes operaciones lógicas.
a) Negación: ()
pp
V FF V
Cuando la proposición simple de “p” es antecedido por la el símbolo de negación “˜”, su
valor de verdad cambia al valor contrario.
4
CONECTIVOS OPERACIÓN ASICIADA SIGNIFICADO ˜ Negación No p : no es cierto que p ˄ Conjunción p˄ q ˅ Disyunción p ˅ q (sentido inclusivo)
=> Implicación (condicional)
Si p entonces q
<=> Doble Implicación p si y solo si q
VDisyunción Exclusiva P o q (sentido exclusivo)
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
b) Conjunción (˄ = n)
P q p ˄ q
V F VV V FF F FF V F
Regla.- La conjunción de 2 proposiciones es verdadera cuando ambos valores de verdad son verdades, en otro caso son falso.
c) Disyunción:
P q p ˅ q
V F VV V VF F FF V V
Regla.- La disyunción de 2 proposiciones es falsa cuando ambos valores de verdad son falso, en otro caso son verdaderos.
d) Implicación:
p q p => qV F VV V FF F VF V V
Regla.- La implicación de 2 proposiciones es falsa cuando el antecedente es verdadero o y el consecuente es falso,en otro caso son verdaderos.
e) Doble Implicación:
P q p <=> qV F VV V FF F FF V V
5
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
Regla.- La doble implicación de 2 proposiciones es verdadera cuando ambos valores de verdad son iguales,en otro caso es falso.
f) Disyunción Exclusiva:
P qp V q
V F FV V VF F VF V F
Regla.- La disyunción exclusiva de 2 proposiciones es verdadera cuando ambos valores de verdad son diferentes,en otro caso es falso.
Formula de recurrencia:
2ⁿ = Número de combinaciones al valor de verdad.n = Número de proposiciones simples (diferente de)n = 1 => 2^1 = 2 combinatoria (diferente de)n = 2 => 2^2 = 4 combinatoria (diferente de)
6.- Formulas Proposicionales:
Es una combinación de proposiciones y conectivos lógicos que simbolizan a una proposición compuesta.
Ejemplo:
˜p =>q ; ˜ (˜r v t) <=> ˜p ;( ˜q ^ r) =>[(p v s) v (t <=>q)]
a) ”Si la planta no crece, entonces necesita mas agua o necesita mejor abono”
˜p: “La planta no crece”
q: “La planta necesita más agua”
6
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
r: “La planta necesita mejor abono”
˜p=> (q v r)
b) “La decisión depende del juicio o la intuición, y no de quien pago más”
p: “La decisión depende del juicio”q: “La decisión depende de la intuición”r: “La decisión depende de quién pago más”
(p v q) ^ ˜ r
c) “21 es divisible entre 3 y por 7, pero no por 5”
p: “21 es divisible entre 3”q: “21 es divisible entre 7”r: “21 es divisible entre 5”
(p ^ q)^˜ r
6.1.- Clasificación de las Formulas Proposicionales”
Las formulas proposicionales se dividen según sus valores en:
a) Tautología:
Se presenta cuando todos los valores de verdad resultante son verdaderas.
b) Contradicción:
Se presenta cuando todos los valores de verdad resultante son falsos, se reconoce también como anti-tautología.
c) Contingencia:
Se presenta cuando todos los valores de verdad resultante son verdaderos y falsos.
6.2 Contradicción de tablas de verdad.
7
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
Se deben analizar todas las posibles combinaciones de valores de verdad de las proposiciones que conforman la formula proposicional; para determinar dichas combinaciones se utiliza las siguientes formula de recurrencia.
2^n = Numero de combinaciones diferente del valor de verdad.
n = Numero de proposiciones simples diferentes.
Ejemplo: Clasifique mediante tablas de verdad, las siguientes formulas proposicionales.
1).- [˜q^( ˜P=>Q)]=>P
p q [˜q^( ˜P = > Q ) ]=>PV F F F F V V V V
V V V V F V F V V
F F F F V V V V F
F V V F V F F V F
RESULTADO: TAUTOLOGIA.
2).-˜(p v q) <=> (˜ p => q)
p q ˜(p v q) <=> (˜ p => q)V F F F V V F V V
V V F V V V F V F
F F F F V V F V V
F V V F F F F F F
RESULTADO: CONTRADICCION.
3).-[q =>(r^ ˜q) <=>[(q v ˜p) => r]
p q r ˜(p v q) <=> (˜ p => q)V V V V F V F F V V V F V VV V F V F F F F F V V F F FV F V F V V V V F F F F V VV F F F V F F V F F F F V FF V V V F V F F V V V V V VF V F V F F F F F V V V F FF F V F V V V V F F V V V V
8
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
F F F F V F F V V F V V F F
RESULTADO: CONTINGENCIA.
4).- Son p y r, proposiciones con valores de verdad f y v respectivamente; q y s proposiciones y tales que la formula proposicional ˜ (˜q ^ s) es falsa. Con esta información determine el valor de verdad de las siguientes formulas proposicionales:
[(p ^ ˜q) ^ s] => ˜ (˜r v s)
Solución:
˜ (˜q ^ s) = F [(F ^ V) ^ V] =>˜(F v V)
(˜q ^ s) = V (F ^ V) =>˜ V
˜q = V F => F
s = V V
5)- Son q y r proposiciones con valores de verdad F, F, p y s proposiciones tales que la formula proposicional ˜ (p v ˜s) = V; Determine el valor de verdad de la formula proposicional.
Datos:
q = F [F =>(F ^ V) V (V => F)
r = F
(p ^ s) =˜ (p v ˜s) = V
˜ (p v ˜s) = V
p = F
˜s = F
6).- Determinar el valor de verdad d las proposiciones p, q, r, s, sabiendo que:
9
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
a) La fórmula proposicional es falso: ˜(r =>˜p) =>( ˜q v s) = F
b) La fórmula proposicional es verdadero: ˜(p v ˜r) ^ ˜(q =>˜ s) = V
a) ˜(r =>˜p) =>( ˜q v s) = FV F˜(r =>˜p) = V˜q v s = Fr = V˜p = F˜q = FS = F
Entonces:
p = V; q = V; r = V; s = F;
b) ˜(p v ˜r) ^ ˜ (q => ˜s) = V
˜(p v ˜r) = V
8.- Circuitos Lógicos:
Un circuito lógico es una red de conmutación que está formada por cables e interruptores que conectan 2 terminales entre si.
Si una red de conmutación asociamos a un circuito lógico; entonces tenemos:
A--------------.---.----------B
A--------------./ .-----------B
8.2.- Circuitos lógicos:
Se tienen 2 tipos de circuitos básicos:
a) Circuito en serie:
10
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
Un circuito representado en serie representa a la operación lógica de conjunción es decir:
A----------.∕ .-----------.∕ .--------->B = p ^ q
b) Circuito en paralelo: Un circuito representado en paralelo representa a la operación lógica de disyunción es decir:
|------p.∕ .-------|A ---| |----B = p v q
|-------q.∕ .------|
Ejemplo:1.- Representar por medio de circuitos lógicos las siguientes formulas proposicionales:
a): q ⇒pb): p q
c): p V q
2.- Dada la formula proposicional siguiente, represente el circuito lógico correspondiente y simplifique la formula proposicional.
{[p ^(q v r)] v (p ^ ˜r)} ^ (˜p v ˜q)
9.- Inferencia Lógica:
Se entiende por inferencia lógica el razonamiento o deducción de concusiones, a partir de un conjunto de proposiciones llamadas premisas.
Toda demostración de inferencia lógica tiene el objetivo fundamental de verificar si un razonamiento es válido o no.
P1P2 Permisos :pn-------
Q Conclusión
11
p q
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
Si P1 ^ P2 ^. . Pn => Q
Entonces es una Tautología
9.1.- Reglas de Inferencia Lógica: enlazar
9.2.- Métodos de demostración:
En inferencia lógica generalmente se utiliza 3 métodos de demostración, que son:
a) Método Directo: Consiste en asumir la verdad de las premisas y probar la verdad de la conclusión.Ejemplo: por el método directo determine si son válidos o no los siguientes razonamientos:
1).- Demostrarr2).- Demostrar ˜q3).- Demostrar ˜(p ^ r)4).- Demostrar P ^ U5).- Demostrar (x != 3) v (y != 1)6).- Demostrar ˜p v ˜q
b) Método Indirecto: Consiste en asumir la falsedad de la conclusión estableciendo la verdad de su negación, es decir que se demuestra que la negación de q es ˜q, lo cual nos lleva a una contradicción de la forma r ^ ˜r que dará como resultado una falsedad. Este método se conoce también como demostración por contradicción o demostración de lo absurdo.Ejemplo: Aplicando el método indirecto demostrar los siguientes razonamientos:1).- Demostrar r2).- Demostrar p3).- Demostrar r v z4).- Demostrar ˜p ^ q5).- Demostrar p ^ U
7).- Si q != V:
Determine los valores de verdad de p, r,s sabiendo que:
12
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
{[(˜p ^ r) v s] =>˜ q} [(q =>˜r) ^ ˜s] = F
UNIDAD II
TEORIA DE CONJUNTOS
1. Definición y Notación:
Un conjunto es una relación cualquiera de objetos, números o símbolos, la cual puede ser finito o infinito. Los conjuntos generalmente se representan con letras mayúsculas del alfabeto.
Ejemplo:
Conjunto de valores {a, e, i, o, u} = Conjunto Finito.
Conjunto de números {1, 2, 3,. . . . .} = Conjunto infinito
2. Pertenencia:
Es un símbolo que nos permite relacionar los elementos con un conjunto y se representa por: “∈” (pertenece)
Ejemplo:
u∈ A (u pertenece a: A)
u∉ A (u no pertenece a: A)
Otros símbolos de uso frecuente son:
/ Para expresar “Tal que”.
¿ Para expresar “Mayor que”.
13
CR
QZN I
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
¿ Para expresar “Menor que”.
3. Notación de conjuntos numéricos:
Las notaciones usuales para caracterizar conjuntos numéricos son las siguientes:
a) Conjunto de números Naturales: N= {0, 1, 2, 3…..}.
b) Conjunto de números Enteros: Z = {…,-2, -1, 0, 1, 2…..}.
c) Conjunto de números Racionales: Q = {…,- 38 , 23 ,0, 1, 2…..}.
d) Conjunto de números Irracionales: I ={…, √2, e, √3,1, 2…..}.
El conjunto de números reales se denota con la letra “R” y está formado por la unión de los números racionales e irracionales.
R = {N∪ Z ∪ Q, Qc}
R = {Q ∪ I}e) Conjunto de números Imaginarios i = {…, √−1, √−2,…..}.
f) Conjunto de números complejos C = {…a, a+bi,…..}.
4. Diagrama de Euler:
14
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
5. Determinación de un conjunto:
Puede ser determinado de 2 maneras:
a) Por Extensión.- Se dice que un conjunto está determinado por extensión si y solo si se nombran todos los elementos que los constituyen. En este caso se escriben sus elementos entre 2 llaves, por ejemplo:
A ={2, 4, 6, 8, 10} conjunto de pares de 1 a 10.Está escrito en extensión ya que se pueden enumerar uno a uno sus elementos del conjunto.
b) Se dice que un conjuntos está determinado por comprensión si y solo si se da la propiedad o propiedades que caracterizan a todos los elementos del conjunto.Ejemplo:El conjunto de los números naturales menores a 5, definido por comprensión puede escribirse:
B={x∈N /x<5 }∴B={0 ,1 ,2 ,3 , 4 }
Ejemplo:C={x∈Z /x2=3 x }∴B={0 ,3 }
15
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
Ejercicios:E-1) Dado los siguientes conjuntos:
U={x∈ R ,N /x ≤9}
A={2 ,4 ,5 ,6 ,8 ,9}
Realice las siguientes operaciones:a. A∪B
b. B−Ac. A−B
d. Ace. A∆ B
f. ( A c−B )∪ (Bc∩A )
E-2) Dado los siguientes conjuntos:U={a ,b , c , d , e , f , g , h , i}
A={a ,b ,d , e , g ,i }
B={a ,d , f , g , h , i}
Realizar las siguientes Operaciones:a. A−B
b. B−Ac. A∪B
16
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
d. A∩Be. Ac
f. Bc
g. B∩ Ac
Respuestas:E-1)
a. A∪B={1 ,2 ,3 , 4 ,5 ,6 ,7 ,8 ,9 }
b. B−A={2 ,6 }
c. A−B={1 ,3 }
d. Ac={1 ,3 ,7 }
e. A∆ B={1 ,2 ,2 ,6 }
f. ( A c−B )∪ (Bc∩A )={2 ,6 ,7 }
E-2)a. A−B={b , e }
b. B−A={ f , h }
c. A∪B={a ,b ,d , e , f , g , h , i}
d. A∩B={a ,d , g , i}
17
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
e. Ac={c , f , h}
f. Bc={b , c , e }
g. B∩ A c={f , h }
UNIDAD III
RELACIONES Y GRAFOS
1. Producto Cartesiano: (x, y)
A x B={(x , y)/ x∈ A ; y∈B }
Ejemplo:A={1 ,2,3 }
B={a ,b , c }
Determine:A x B
A x B={(1 , a } , (1 , b ) , (1, c ) , (2, a ) , (2 , b ) , (2, c ) , (3 , a ) , (3 , b ) , (3 , c )}
Bx A
Bx A={(a ,1 ) , (a ,2 ) , (a ,3 ) , (b ,1 ) , (b ,2 ) , (b ,3 ) , (c ,1 ) , (c ,2 ) , (c ,3 ) , }
18
123
A
B
cba
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
1.1.Representación Gráfica.
Ejemplo:Dado los conjuntos
A={x∈ R/−1≤x ≤1 }
B={ y∈ R/−2≤x≤2 }
A={x∈ R /−1≤x ≤1 }A={−1 ,0 ,1 }
B={ y∈ R/−2≤x≤2 }B={2 ,−1 ,0 ,1 ,2}
Determine:A x B
Bx A
Respuesta:
19
-1-2
1 2
A
B
21
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
A x B = {(−1 ,−2 ) (−1 ,−1 ) (−1 ,0 ) (−1,1 ) (−1 ,2 ) (0 ,−2 ) (0 ,−1 ) (0 ,0 ) (0 ,1 ) (0 ,2 ) (−1 ,−2 ) (−1 ,−1 ) (−1 ,0 ) (−1,1 ) (−1 ,2 ) (1 ,−2 ) (1,−1 ) (1 ,0 ) (1 ,1 ) (1 ,2 )}B x A = {(−2 ,−1 ) (−2 ,0 ) (−2 ,1 ) (−1 ,−1 ) (−1 ,0 ) (−1 ,1 ) (0 ,−1 ) (0 ,0 ) (0 ,1 ) (1 ,−1 ) (1,0 ) (1 ,1 ) (2 ,−1 ) (2 ,0 ) (2 ,1 )}
Gráficos:A x B
20
-2 -1
-1-2
1 2
A
B
21
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
B x A
2. Relación: Una relación r de A en B, es cualquier subconjunto del producto cartesiano A x B, es decir:R es una relación de A en B si y solo si R es subconjunto d A x B, también se puede representar como x R y si y solo si el par (x, y) ∊ R.Se lee: “x” está relacionado con “y” por R, si y solo si en par x, y pertenece a la relación R.
Ejemplo:Sean los conjuntos:
A={1 ,2,3 }
B={a ,b }
Halle el producto cartesiano A x B =? y utilizando el subconjunto R = {(1, a)(2, b)(3, a)}
21
123
A
B
ba
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
Producto cartesiano:AxB = {(1, a) (1, b) (2, a) (2, b) (3, a) (3, b)}Determine si R es una relación de A en B (GRAFICAMENTE).
= AxB
R pertenece a la relación A en B.Ejemplo:Sean A y B los mismos conjuntos anteriores y la relación R sea:R2 = {(1, b) (2, b)(4, a)}Determine si R2 es una relación de A en B (GRAFICAMENTE).
22
123
A
B
ba
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
R2 no pertenece a la relación A en B.Análisis
1 R2 b (1, b) ∊ A x B pertenece2 R2 b (2, b) ∊ A x B pertenece4 R2 b (4, a) ∉ A x B no pertenece
3. Grafos: Sea A y se pueda representar su grafo destinoTrace un pequeño círculo para cada elemento del conjunto A y enlazar con su relación en R con el circulo de A a esto se denomina arco.Ejemplo: Sean:
23
1 2
4 3
1 2
4 3
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
A = {1, 2, 3, 4}R = {(1, 1)(1, 2)(2, 1)(2, 2)(2, 4)(3, 4)(4, 1)}
Represente el grafo:
Ejemplo:Determina por extensión la relación R representado por el siguiente dígrafo:
R = {(4, 1)(4, 2)(4, 3)(4, 4)(3, 3)}
4. Grados de un dígrafo:Se representa dos tipos de grafos, grafo idéntico y Morgan, el grafo interno de un numero.Ejemplo:Dado el siguiente grafo:
24
1
2
4
3
ESTRUCTURAS DISCRETAS WWW.WEBSISBLOG.WORDPRESS.COM
A = {(1, 1) (1, 2) (1, 4) (2, 3) (3, 3)(3, 4)(4, 1)}Determinar:
a. La relación R por Extensión.b. Los grafos internos externos del dígrafo.c. La matriz de R.A. La relación R por ExtensiónR = {(1, 1)(1, 2)(2, 1)(2, 2)(2, 4)(3, 4)(4, 1)}B. Los grafos internos externos del dígrafo.
V1 = 1 V2 = 2 V3 = 3 V4 = 4GRADOS INTERNOS 2 1 3 2GRADOS EXTERNOS 4 1 2 1
C. La matriz de R. (4x4)Me =
1 2 3 41 1 1 1 12 0 0 1 03 0 0 1 14 1 0 0 0
25