Web viewLa 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

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


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


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


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)


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


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


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


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


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


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


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


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


{[(˜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


¿ 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


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


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


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


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


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


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


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


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


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


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


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

Documents

Web viewLa 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