proyecto matematicas discretas

7/31/2019 proyecto matematicas discretas

1/106


2/106

Lo mas valioso no es lo que tienen en susvidas, si no a quin tienen en sus vidas

annimo


3/106

GRUPO 2

Integrantes:Santiago PearretaDiego Celi

Roberto ParedesOscar Muoz

Anderson JimnezMariuxi Granda

Jorge UlloaJorge Medina

Amparo Collaguazo


4/106

PROYECTOMATEMTICAS

DISCRETAS


5/106

TEMASCAPITULO 1.- LOGICA PROPOSICIONAL

EJERCICIOSCAPITULO 2.- LOGICA DE PREDICADOS

APLICACIONESCAPITULO 3.- ALGEBRA BOOLEANA

TEORIACAPITULO 4.- SISTEMAS NUMERICOS

EJERCICIOSCAPITULO 5.- TEORIA DE GRAFOS

APLICACIONESCAPITULO 6.- ARBOLES

TEORIACAPITULO 7.- MODELOS DE REDES

EJERCICIOS


6/106

Siempre habr alguien mejor o peor

que t NO RENIEGES DE TU VIDA Annimo


7/106


8/106


9/106


10/106


11/106


12/106

()


13/106

1. x = 4 y 6 < z

2. Franco lee pero Juan escribe

3. 4 < 7 no obstante 9>4

4. Hace frio sin embargo Jackeline estudia

5. El fuego calienta e ilumina


14/106

DISYUNCIN(o", "al menos ,como mnimo, u, o bien)

1. Estudias o pierdes el ao

2. Miguel lee, al menos escribe

3. hace sol, como mnimo hace frio

4. Marcos tiene una empresa u organizacin

5. A es una vocal o bien es una letra mayscula


15/106

Si hace frio entonces llueve

Hace frio solo si llueve

Hace frio si llueve

Hace frio si es necesario para que llueva

Hace frio implica que llueve

Cada vez que hace frio llueve

Llueve siempre que hace frio

Hace frio cuando llueve

CONDICIONAL(Sientonces, .solo si.,.si.,

es necesario para que,.implica.,cada vez que, siempre

que,.cuando.)


16/106

Marcos trabaja si y solo si Juan estudia

Marcos trabaja solo y cuando Juan estudia

Marcos trabaja cuando y solo cuando Juan estudia

BICONDICIONAL(si y solo si, solo y cuando,cuando y solo cuando)


17/106

SIMBOLIZACINY

TABLAS DE VERDAD


18/106

NEGACIN()

1. Laura no estudia (p)2. 5 no es un numero par (q)

3. No es cierto que 4 > 1(r)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Negacion1.jpg


19/106

CONJUNCIN ( ^ ) 1.Juan canta y estudia (p ^ q)2.Carlos y Kevin son hermanos (q ^ r)3.Lorena sonre y x + 2 = 7 (r ^ s )
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Conjuncion1.jpg


20/106

DISYUNCIN (V)

1.Maana llueve o hace sol (p v q)2.Maria sonre o bien Luis es amigo de Rosa (q V r)

3.Marcos canta o Pedro trabaja (r V s)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Disyuncion1.jpg


21/106

CONDICIONAL( ) 1. Si x + 2 = 7, entonces z > 9 (p r)2. Si llueve entonces es una ciudad (s t)3. 6 es numero para, entonces 6 < 9 cuando 9 es un nmero

impar ( p q) r
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:C.jpg


22/106

BICONDICIONAL()

1. Z > 9 si y solo si Z > 9 (p q)2. si nieva cuando y solo cuando llueve (s t)

3. 2 + 3 = 5 si y solo si 2 < 10 (p q)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Bicondicional01.jpg


23/106

TAUTOLOGIA

[(P V q ) ^ ( q V p)] p
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Contingencia2.jpg


24/106

CONTINGENCIA

(P V P) ^ (q V p)
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Contingencia2.jpg


25/106

CONTRADICCIN

q ^ q
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Contradiccion1.jpg


26/106

EQUIVALENCIA

(pVq)pq Si se escriben las tablas de verdad para P=(pVq) y Q=, se puedeverificar que ; a partir de cualesquiera valores de verdad para p yq, P y Q son ambas verdaderas o P y Q son ambas falsas.

Entonces P y Q son equivalentes lgicos
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Equivalencia1.jpg


27/106

SIMPLIFICACION de PROPOSICIONES

PASO1.- Aplicamos [ Morgan] ^ [( ) ^Morgan] ^ [condicional]

PASO2.- Aplicamos conmutativa ^ [ complemento] [asociativ a]

PASO3.- Aplicamos 1 ^ [ qvr] ^ [idenpotencia v p vq]

PASO4.- Aplicamos 1 ^ [ qvr] ^ [asociativa v q]

PASO5.- Aplicamos 1 ^ [ qvr] ^ [Morgan v q ]

PASO6.- Aplicamos 1 ^ [ qvr] ^ [conmutativa]

PASO7.- Aplicamos [ asociativa] complemento

PASO8.- Aplicamos [ conmutativa ]^1

PASO9.- Aplicamos (complemento) 1

PASO10.-- Aplicamos (complemento ) y esto

es el mnimo es decir el resultado
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Simplificacion1.jpghttp://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:Simplificacion1.jpg


28/106

Qu sentido tiene corrercuando estamos en lacarretera equivocada?

Annimo


29/106

2.- LOGICA DE PREDICADOS _APLICACIONES

1.- A nivel profesional; se lo aplica en un programa llamado LISP, elcual sirve como constructor de sistemas expertos.


30/106

La primera regla para poder amar es tenercario por uno mismo

Annimo


31/106

2.- La lgica tambin es aplicada para ensear a programar en losdiferentes lenguajes de programacin. Por ejemplo java, c++, etc.


32/106

Nunca es tarde para bien hacer; has lo queno hiciste ayer

Annimo


33/106

ALGEBRA BOOLEANAS Y CIRCUITOSCOMBINATORIOS

Constituyen un rea de las matemticas que hapasado a ocupar un lugar prominente con eladvenimiento de la computadora digital.

Son usadas ampliamente en el diseo de circuitos dedistribucin y computadoras, y sus aplicaciones vanen aumento en muchas otras reas. En el nivel delgica digital de una computadora, lo quecomnmente se llama hardware, y que est formadopor los componentes electrnicos de la mquina, setrabaja con diferencias de tensin, las cualesgeneran funciones que son calculadas por loscircuitos que forman el nivel.


34/106

CIRCUITOS COMBINATORIOS

En una computadora digital solo hay dos posibilidades, quese escriben como 0 y 1, para el objeto indivisible mspequeo. En ltima instancia, todos los programas y datosse pueden reducir a combinaciones de bits.

A travs de los aos se ha usado una variedad dedispositivos en las computadoras digitales para almacenarbits. Los circuitos electrnicos permiten que estosdispositivos de almacenamientos se comuniquen entre si.Un bit en una parte del circuito es trasmitido a otra partedel circuito como un voltaje. Entonces se necesitan dosniveles de voltajes; por ejemplo, un voltaje alto puedecomunicar un 1 y un voltaje bajo, un 0.


35/106

DEFINICIN 1:

Una compuerta AND recibe entradas X1 y X2,donde X1 y X2 son bits, y produce una salidadenotada X1 X2, donde

1 si X1= 1 y X2=1X1 X2 = 0 de otra manera

Una compuerta AND se dibuja como se indicaen la figura 1


36/106

X1 X2


37/106

DEFINICIN 2:

Una compuerta OR recibe entradas X1 y X2,donde X1 y X2 son bits, y produce una salidadenotada X1 X2, donde

X1 X2 = 1 si X1= 1 o X2=10 de otra manera.

Una compuerta OR se dibuja como se indicaen la figura 2.


38/106

X1 X2


39/106

DEFINICIN 3:

Una compuerta NOT (o inverso) recibe unaentrada X, donde X es un bits, y produce unasalida denotada por

= 1 si X = 00 si X = 1.

Una compuerta NOT se dibuja como se indicaen la figura 3


40/106


41/106

Tabla lgica

La tabla lgica de un circuito combinatorio lista todas lasentradas posibles junto con las salidas posibles.

ANDX1 X2 X1 X21 1 11 0 00 1 00 0 0


42/106

X1 X2 X1 X2

1

1

0

0

1

0

1

0

1

1

1

0

X

1

O

0

1

OR

NOT


43/106

Aprende de quienes puedanensearte

Annimo


44/106

4.- SISEMAS DE NUMERACIN_

EJERCICIOS DECIMALES A BINARIOS En esta conversin se tiene un nmero enforma decimal dicho numero se lo dividirpara 2 tantas veces como sea posible y setomara como numero binario el residuo quedeje este y se lo tomara en cuenta desde

abajo hasta arriba, teniendo en cuenta que elnumero siempre se dividir para el numero 2nicamente.


45/106


46/106

DECIMALES A OCTALES En esta conversin se tiene un nmero enforma decimal dicho numero se lo dividirpara 8 tantas veces como sea posible y setomara como numero octal el residuo quedeje este y se lo tomara en cuenta desde

abajo hasta arriba, teniendo en cuenta que elnumero siempre se dividir para el numero 8nicamente.


47/106


48/106

DECIMALES A HEXAGESIMALES En esta conversin se tiene un nmero enforma decimal dicho numero se lo dividirpara 16 tantas veces como sea posible y setomara como numero hexagesimal el residuoque deje este y se lo tomara en cuenta desdeabajo hasta arriba, teniendo en cuenta que elnumero siempre se dividir para el numero 16nicamente y se remplazara los nmerosmayores a 9 con sus respectivas letras.


49/106


50/106

RESTA


51/106

Divisin


52/106

DECIMALES:0 al 9

BINARIOS:1 al 0

OCTAL:0 al 7

HEXADECIMAL:0 al 9 y del alfabeto de la A a

la F

EQUIVALENCIAS DEESTOS ENUNCIADOS


53/106

Convertir binarios a decimales

Convertir decimales a binarios

Convertir decimales a octales

Convertir decimales a hexadecimales

Convertir binarios a octales

Convertir octales a binarios

Convertir binarios a hexadecimales

Convertir hexadecimales a binarios

TABLA DE NUME RACION: TABLA DE NUME RACION: TABLA DE NUME RACION:


54/106

TABLA DE NUMERACIN:


55/106


56/106

En esta tabla yo descubr una forma de aprender masrpido los nmeros binarios la clave esta en darse cuentasimplemente en los 3 primeros nmeros que son 01 10

11 y en que la tabla los nmeros mas altos son el 100 y el1000 y el resto simplemente se le sustituye los dos ltimosnmeros por los nmeros de las tres primeras filas es decirpor ejemplo con el 100 dense cuenta que el numero que lesigue es 101 y hay ya contiene al primer numero que es 01el numero que le sigue es 110 hay ya contiene al 10 y el otroque le sigue es 111 y hay ya contiene al 11. En la del 1000 esigual hasta el 1011 despus de este numero esta 1100simplemente hacemos de cuenta como si fuera 100 y elproceso es el mismo.


57/106

BINARIOS A OCTALES


58/106

En esta conversin los nmeros tienen que seragrupados de 3 en 3 desde la derecha y en casode que no hubiese como agrupar al ultimogrupo de tres por circunstancia de que faltasenmeros se le debe aumentar los ceros quesean necesarios para completar la agrupacin.Luego de esto a los nmeros agrupados de tresen tres se los va sustituyendo por los nmerosque representen segn la tabla con el ejemplose entender mejor.


59/106

EJERCICIOS:


60/106

Como pueden darse cuenta es similar al anterior solo queahora los nmeros de azul son remplazados a ceros yunos y ese cero que esta de rojo en el segundo ejercicio lopuse de ese color para explicarles que tambin alremplazar esos nmeros pro binarios siempre tienen quequedar conformados de 3 nmeros y en caso de alpasarlo a binario solo quede de 2 nmeros tenemos queaumentar un cero para que quede conformado de tres

nmeros


61/106

BINARIO A HEXADECIMA


62/106

Antes de empezar tengo de decirles que este es igual debinario a octal simplemente lo nico que cambia es que

aqu se agrupa de 4 en 4


63/106

EJERCICIOS:


64/106

Como podemos darnos cuenta solo lo nico quecambio fue el numero de agrupacin y nada maslo ceros en rojo son los que tuve que agregar

para completar la agrupacin. Y tambin nospodemos dar cuenta que aqu esos nmerosbinarios a sido una letra es lo nico que tambincambia que aqu aparecen letras.


65/106

HEXADECIMAL A BINARIO


66/106

Es similar al de octal a binario lo nico quecambia es que aparecen letras y las letrastambin son sustituidas por nmeros binarios


67/106

EJERCICIOS:


68/106

COMVERTIR UNA BASE DE CUALQUIER TIPO A DECIMAL


69/106

Ahora les explicare mejor los nmeros de colorazul son los nmeros que nos fueron dados los

verdes son las posiciones de los azules segn laenumeracin que les di empezando desde laderecha y comenzando desde cero los nmeros deamarillo son el procedimiento ya explicado hay

vemos que el tres que es el numero ya dado se lomultiplica por la base y la base es elevada segn laposicin del numero que en este caso seriaelevada a dos


70/106

OPERACIONES BINARIAS

Las operaciones que veremos sern las cuatrooperaciones que son las siguientes:


71/106

SUMA:

Las reglas a cumplir sern las siguientes:


72/106

NOTA: (En este caso en la respuesta no secolocara el 10 en si solo se colocara el 0 y eluno se le sumara al nmero de alado pero

siguiendo las reglas solo se colocara el 10 encaso de ser ya el ltimo nmero sumado). Parasu mejor entendimiento aqu les dejo unosejercicios resueltos y explicados:


73/106

EJERCICIOS:

Para las siguientes sumas de este tamao tenemos que sumar lasfilas de 2 en 2 para no confundirnos es decir la fila 1 y 2 y se saca elresultado luego la fila 3 y 4 y se saca el resultado y as sucesivamenteluego de la misma forma se suma los resultados es decir el resultado

de la fila 1 y 2 con el resultado de la fila 3 y 4 y se saca un resultado yese resultado con la fila 5 como seria en el caso del ejercicio a realizarque esta debajo


74/106

MULTIPLICACION:Las reglas a cumplir sern las


75/106

g psiguientes:


76/106

En la multiplicacin de estas operacionesbinarias no cambien en nada su metodologacomn es decir que estas se multiplican tal ycomo si se estuviera multiplicando en unaoperacin normal pero siguiendo las reglasplanteadas. Y para multiplicar con decimales esigual simplemente se cuenta cuantos nmeroshay despus de la coma tanto de multiplicadorcomo del multiplicando y segn la cantidad dedichos nmeros en el resultado final se comienzaa contar los nmeros desde la derecha y secoloca la coma a continuacin unos ejercicios:


77/106

EJERCICIOS:

NOTA: En este ejercicio voy a explicar mejor lo de los decimalescuenten cuantos nmeros hay despus de la coma del multiplicadory multiplicando smenlos, les da un total de 4 y ahora en el resultadofinal cuenten desde la derecha los nmeros que fueron encontradosdespus de la coma del multiplicando y multiplicador y coloquen lacoma tal y como esta en el ejemplo


78/106


79/106

LAS FORMAS COMPLEMENTARIAS Y ESIGNO

Para hacer estos ejercicios primero el numero quenos den tenemos que convertirlo a binario luegohacer que queden en 7 dgitos en caso de no ser assimplemente se le aumenta los ceros que sean

necesarios y luego de eso si dichos nmeros estn ennegativo o alguno de ellos esta dado en negativoutilizamos el complemento 1 que consiste encambiar todos los 1 por 0 y viceversa y luegoutilizamos el complemento2 el cual consiste en; al

complemento 1 sumarle 1 y despus de todo esto sisumar los binarios y en caso de no existir ningnnmero en negativo simplemente convertir a binarioy sumar


80/106

EJERCICIOS:


81/106

Ahora voy a explicarles para convertir esto a binariostenemos que dividir manualmente el numero dado para 2hasta ya no poder luego el residuo es lo que pasara a serlos nmeros binarios empezando desde el ultimo nmerohasta el primero para mejor entendimiento e puesto enun circulo rojo los nmeros que pasaron a ser binarios

pero los dgitos de este tienen que constar de 7 dgitosas que la regla ser igual en todas simplementeaumentar los ceros necesarios que los e colocado enrojo. Uno vez hecho esto se pasa a sumarlos como ya lese enseado.


82/106


83/106

En este ejercicio estamos aplicando lo que les dije si esque un nmero es negativo pero como el nmero fue el

13 y ya tenamos convertido a binario pero en positivonos ahorramos el volver a sacar el binario y solo nos tocoaplicar los complementos pero si el numero dadohubiese sido por decir el 36 pero en negativo hubiramostenido que hacer lo mismo que hicimos con el 36 positivopara encontrar el binario y luego de eso aplicar loscomplementos y luego si la operacin


84/106


85/106

En este ejercicio lo que hemos hecho es la respuesta finalque nos dio negativa pasarla a positivo utilizando loscomplementos estos nos sirven para pasar nmerospositivos a negativos o viceversa este ultimo ejercicio erapara demostrar esto


86/106

ACEPTA LA VIDA TAL CUALES.

ALEGRATE SI RAZONALGUNA

Giroux Andr


87/106

TEORIA DE GRAFOSAPLICACIONES

CABLEADO ESTRUCTURADO


88/106

CABLEADO ESTRUCTURADO

GPS PARA AUTOS
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:EDIFICIO.jpg


89/106

GPS PARA AUTOS
http://www.utpl.edu.ec/wikis/matematicas_discretas/index.php/Imagen:CARRETERA.jpg


90/106

Antes de juzgar a alguien, respira un poco ypiensa si vale la pena

Annimo


91/106

TEORIA DE ARBOLES


92/106

Un rbol es un grafo simple en el cual existe un nico camino entre cada par de vrtice.

Un rbol con raz, es un rbol que tiene un vrtice particular designado como raz.Ejemplo de rbol raz:


93/106

Existen cuatro tipos de rbol binario:. b l Bi i Di i


94/106

rbol Binario Distinto.rbol Binario Similares.rbol Binario Equivalentes.rbol Binario Completos.A continuacin se har una breve descripcin de los diferentes tiporbol binario as como un ejemplo de cada uno de ellos.

Se dice que dos rboles binarios son distintos cuando sus estructurdiferentes.

Dos arboles binarios son similares cuando sus estructuras son idnpero la informacin que contienen sus nodos es diferente.

Son aquellos arboles que son similares y que adems los nodos conla misma informacin.

Son aquellos arboles en los que todos sus nodos excepto los del lt

nivel, tiene dos hijos; el subrbol izquierdo y el subrbol derecho.

Los rboles binarios se utilizan frecuentemente para represen


95/106

Los rboles binarios se utilizan frecuentemente para represenconjuntos de datos cuyos elementos se identifican por una clanica. Si el rbol est organizado de tal manera que la clave dnodo es mayor que todas las claves su subarbol izquierdo, y mque todas las claves del subarbol derecho se dice que este rbrbol binario de bsqueda.


96/106

Una tarea muy comn a realizar con un rbol es ejecutar unadeterminada operacin con cada uno de los elementos del rbEsta operacin se considera entonces como un parmetro de tarea ms general que es la visita de todos los nodos o, como denomina usualmente, del recorrido del rbol.Si se considera la tarea como un proceso secuencial, entoncenodos individuales se visitan en un orden especfico, y puedeconsiderarse como organizados segn una estructura lineal. Dhecho, se simplifica considerablemente la descripcin de mu

algoritmos si puede hablarse del proceso del siguiente elemenel rbol, segn un cierto orden subyacente.Hay dos formas bsicas de recorrer un rbol: El recorrido en

y el recorrido en

Es aquel recorrido que recorre el rbol por niveles, en el ltimo ejemplo sera:


97/106

q q p , j p

Recorre el rbol por subrboles.Hay tres .Hay tres formas: en . Cada una de ellas tiene una secuenciadistinta para analizar el rbol como se puede ver a continuacin:

Recorrer el subarbol izquierdo en enorden.

Examinar la raz.Recorrer el subarbol derecho en enorden.

Examinar la raz.Recorrer el subarbol izquierdo en preorden.recorrer el subarbol derecho en preorden.

Recorrer el subarbol izquierdo en postorden.Recorrer el subarbol derecho en postorden.Examinar la raz.

A continuacin se muestra un ejemplo de los diferentes recorridos en un rbol binario

Una de las operaciones mas importantes a realizar en un rbol binario es el recorrido de los mismos, reco


98/106

Una de las operaciones mas importantes a realizar en un rbol binario es el recorrido de los mismos, recosignifica visitar los nodos del rbol en forma sistemtica, de tal manera que todos los nodos del mismo svisitados una sola vez.$Existen 3 formas diferentes de efectuar el recorrido y todas ellas de naturaleza recursiva, estas son:

En el que se procesa el nodo y despus se procesan recursivamente sus hijos.Donde el nodo dado se procesa despus de haber procesado recursivamente

hijos.En este se procesa recursivamente el hijo izquierdo, luego se procesa el nodo ac

finalmente se procesa recursivamente el hijo derecho.Hay un ltimo recorrido que implementa a estos 3.


99/106

RECORRIDO POR NIVELES

Concluimos implementando el recorrido porniveles. este recorrido procesa los nodoscomenzando en la raz y avanzando en formadescendente y de izquierda a derecha.

El nombre se deriva del hecho de que primerovisitamos:

los nodos del nivel 0 (la raz),despus los del nivel 1 (los hijos de la raz),los del nivel 2 (los nietos de la raz),y as sucesivamente.

Un o es un grafoG(V, E) , en el que a cada arista se le asigna un valor real no


100/106

g ( , ) , q gnegativo o Sobre el conjunto de aristas se introduce una funcin peso .El de un subgrafo de un grafo ponderado es la suma de los pesos de todas sus aristas.Dado el grafo con pesos:

El peso total del grafo es


101/106

RBOLES BINARIOS ISOMORFOS : Dos rboles binarios son isomorfos si tiemisma estructura, aunque el contenido de cada uno de los nodos sea diferente .


102/106

El sabio no ensea con palabras si no conActos

Annimo


103/106

EJERCICIOSMODELO DE REDES

Hallar los flujos faltantes y el peso de


104/106

Hallar los flujos faltantes y el peso deentrada (a) y de salida(b)

Hallar los flujos faltantes y el peso de entrada(a) y de


105/106

y ysalida(b)

Hallar los flujos faltantes y el peso de


106/106

Hallar los flujos faltantes y el peso deentrada(a) y de salida(b)

Documents

proyecto matematicas discretas