Web viewLa lógica es una disciplina que trata de los métodos, modos formas del...
Transcript of Web viewLa lógica es una disciplina que trata de los métodos, modos formas del...
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