PARTES DE UN GRAFO

Vértice o nodos:     V={a, b, c, d, e}

Aristas o lados:        E={1, 2, 3, 4, 5, 6, 7}

Lados paralelos:     P={ 4, 5}

Lazo:                 ={6}

Valencia o grado:    a(3)  b(4)  c(4)  d(2)  e(1)

Introducción a los grafos

La teoria de grafos

Es un campo de estudio de las matemáticas y las ciencias de la computación, que estudia las propiedades de los grafos y sus estructuras que constan de dos partes, el conjunto de vértices, nodos o puntos; y el conjunto de aristas, líneas o lados  que pueden ser orientados o no.

La teoría de grafos es una rama de la Matemática discreta y de las aplicadas, y es un tratado que usa diferentes conceptos de diversas áreas como Análisis combinatorio, Álgebra abstracta, probabilidad, geometría de polígonos, aritmética y topología.

                                       

302-B

UNIVERSIDAD INTERCULTURAL MAYA DE QUINTANA ROO

MAPA MENTAL

AUDIO INTRODUCTORIO A LAS MATEMÁTICAS DE BOOLE

ÁLGEBRA DE BOOLE

Se denomina así en honor a George Boole (2 de noviembre de 1815 a 8 de diciembre de 1864), matemático inglés autodidacta, que fue el primero en definirla como parte de un sistema lógico, inicialmente en un pequeño folleto: The Mathematical Analysis of Logic, publicado en 1847, en respuesta a una controversia en curso entre Augustus De Morgan y Sir William Hamilton. El álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. Más tarde como un libro más importante: The Laws of Thought, publicado en 1854.

En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico. Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación eléctrica biestables, en 1948. Esta lógica se puede aplicar a dos campos:

• Al análisis, porque es una forma concreta de describir como funcionan los circuitos.
• Al diseño, ya que teniendo una función aplicamos dicha álgebra, para poder desarrollar una implementación de la función

¿QUE ES EL ÁLGEBRA BOOLEANA?

El álgebra booleana es un sistema matemático deductivo centrado en los valores cero y uno (falso y verdadero). Un operador binario " 0 " definido en éste juego de valores acepta un par de entradas y produce un solo valor booleano, por ejemplo, el operador booleano AND acepta dos entradas booleanas y produce una sola salida booleana.

Leer más: http://www.monografias.com/trabajos14/algebra-booleana/algebra-booleana.shtml#al#ixzz2yakOq05K

Sea B un conjunto en el cual se definen dos operaciones binarias, + y *, y una

operación unitaria denotada ; sean 0 y 1 dos elementos diferentes de B. Entonces la

sextupla:

              〈B, +, *, , 0, 1〉

se denomina álgebra de Boole si se cumplen los siguientes axiomas para cualesquiera

elementos a, b, c del conjunto B:

[B1] Conmutatividad:

        (1a) a + b = b + a                                             (1b) a * b = b * a

[B2] Distributividad:

        (2a) a + (b * c) = (a + b) * (a + c)                     (2b) a * (b + c) = (a * b) + (a * c)

[B3] Identidad:

        (3a) a + 0 = a                                                     (3b) a * 1 = a

[B4] Complemento:

        (4a) a + a = 1                                                     (4b) a * a = 0

¿Para que se utiliza?

Para tratar expresiones de la lógica proposicional para así poder solucionar mas rápidamente problemas como lo son los que tiene que ver con el ámbito de diseño electrónico.Y hubo algunas personas las cuales usaban estas teorías para aplicarlas en el diseño de circuitos de conmutación eléctrica como fue “Claude Shannon”.

De la misma manera en nuestra actualidad se  le ha dado un uso directo: en la electrónica,durante el análisis de los circuitos electrónicos:

Lógica: la cual trabajan con señales electrónicas.

Digital: es mas usado en la computación ya que maneja señales electrónicas discretas.

Formas Canónicas

A partir de una tabla de verdad es posible obtener múltiples expresiones para la misma función, y todas estas expresiones son equivalentes entre ellas.

¿Que es un maxitermino?

Primera Forma Canónica

La primera forma canónica está formada por la suma de productos (minitérminos) y se desarrolla tomando la tabla de verdad y eligiendo las combinaciones de entradas en las que la salida se hace 1 y descartando las que son igual a 0.

¿Que es un minitermino?

Segunda Forma Canónica

La segunda forma canónica está formada por el producto de sumas (maxitérminos) y se desarrolla tomando la tabla de verdad y eligiendo las combinaciones de entradas en las que la salida se hace 0 y descartando las que son igual a 1.

¿Que es un circuito?

Un circuito lógico es un dispositivo que tienen una o más entradas y exactamente una salida. En cada instante cada entrada tiene un valor, 0 o 1; estos datos son procesados por el circuito para dar un valor en su salida, 0 o 1. Los valores 0 y 1 pueden representar ciertas situaciones físicas como, por ejemplo, un voltaje nulo y no nulo en un conductor.

Los circuitos lógicos se construyen a partir de ciertos circuitos elementales denominados compuertas lógicas, entre las cuales diferenciaremos:

• Compuertas lógicas básicas: OR, AND, NOT.

• Compuertas lógicas derivadas: NOR, NAND.

¿Que son las compuertas lógicas?

Los circuitos digitales (lógicos) operan en el modo binario donde cada voltaje de entrada y salida es un 0 o un 1; las designaciones 0 y 1 representan rangos de voltaje predefinidos.

Operación OR con compuertas OR

la operación OR es la primera de las tres operaciones booleanas básicas que se debe aprender.

La expresión booleana para la operación OR es:

                                X = A + B

En esta expresión, el signo + no representa la adición común, sino la operación OR (lógica), entonces tendríamos 1 + 1 = 1.

Operación AND con compuertas AND

La operación AND es la segunda operación básica booleana, la expresión booleana para la operación AND es:

                                 X = A . B

En esta expresión el signo (.) representa la operación booleana AND y no la multiplicación.

Operación NOT

La operación NOT difiere de las operaciones OR y AND en que se pueden realizar en una sola variable de entrada. Por ejemplo, si la variable A se somete a la operación NOT, el resultado X se puede expresar como:

                                  X= A.

OPERACIÓN ENTRE LAS RELACIONES

Álgebra relacional

Se llama álgebra relacional a un conjunto de operaciones simples sobre tablas relacionales, a partir de las cuales se definen operaciones más complejas mediante composición. Definen, por tanto, un pequeño lenguaje de manipulación de datos.

El elemento fundamental del modelo relacional de bases de datos es la tabla relacional. Una tabla relacional es una representación extensional de una relación definida sobre un cierto dominio.

Así, son ejemplos de tablas:  cuyos dominios son, respectivamente:  puede_asistir:ALUMNO  GRUPO,  gusta: ALUMNO  PROFESOR, y da_clase_en:PROFESOR  GRUPO.

Se llama tupla a cada ``fila'' de una tabla, y es por supuesto un elemento del producto cartesiano de los dominios que dan nombre a las columnas ( atributos).

http://algebrarelacional.awardspace.com/Algebra%20Relacional.htm

¶ ) PROYECCIÓN

Permite extraer columna de una relación, dando como resultado un  subconjunto vertical de atributos de la relación, señalada con la letra griega pi mayúscula (¶) Como subíndice de ¶ se coloca una lista de todos los atributos que se desea aparezcan en el resultado. La relación argumento se escribe después de¶ entre paréntesis.

Ejemplos :

EMPLEADOS
CLAVE	NOMBRE	DIRECCIÓN
001	Juan Carlos Torres Méndez	Atasta
002	Mónica Comes Pérez	Centro
003	Carmen Cruz Cruz	Tamute
004	Miguel Contreras León	Sabina

¶  Clave (Empleados)

CLAVE

001

002

003

004

σ) Selección

El operador de selección opta por tuplas que satisfagan cierto predicado, se utiliza la la letra griega sigma minúscula (σ) para señalar la selección. El predicado aparece como subíndice de σ. La Relación que constituye el argumento se da entre paréntesis después de la σ.
 

Ejemplos :

EMPLEADOS
CLAVE	NOMBRE	DIRECCIÓN
001	Juan Carlos Torres Méndez	Atasta
002	Mónica Comes Pérez	Centro
003	Carmen Cruz Cruz	Tamute
004	Miguel Contreras León	Sabina

¶  nombre σ nombre='Mónica Comes Pérez' (Empleados)

NOMBRE

Mónica Comes Pérez

(X) PRODUCTO CARTESIANO

El producto cartesiano de dos conjuntos A x B es el conjunto de todos los pares ordenados que se pueden formar con un elemento perteneciente al conjunto A y un elemento del conjunto B.

Los elementos de A x B son pares ordenados. Cada par que se forma con un elemento del conjunto A y uno del conjunto B, en ese orden y recibe el nombre de par ordenado. Sus elementos se colocan entre paréntesis, separados por coma.

Como ejemplo:

EMPLEADOS
CLAVE	NOMBRE	OFICIO
001	Juan Carlos Torres Méndez	Chofer
002	Mónica Comes Pérez	Enfermera
003	Carmen Cruz Cruz	Dentista
004	Miguel Contreras León	Ingeniero

COLONIAS
CLAVE	COLONIA	C.P.
001	Méndez	86003
002	Rovirosa	86105
003	Sabina	87100
004	Tamulte	85300

¶ Empleados.Nombre, Empleados.Oficio, Empleados.Colonia σ Empleados.Nombre='Miguel Contreras León' ^ Empleados.Clave = Colonia.Clave (Empleados x Colonias)

PRODUCTO CARTESIANO (EMPLEADOS  X COLONIAS)
CLAVE	NOMBRE	OFICIO	CLAVE	COLONIA	C.P.
001	Juan Carlos Torres Méndez	Chofer	001	Méndez	86003
001	Juan Carlos Torres Méndez	Chofer	002	Rovirosa	86105
001	Juan Carlos Torres Méndez	Chofer	003	Sabina	87100
001	Juan Carlos Torres Méndez	Chofer	004	Tamulte	85300
002	Mónica Comes Pérez	Enfermera	001	Méndez	86003
002	Mónica Comes Pérez	Enfermera	002	Rovirosa	86105
002	Mónica Comes Pérez	Enfermera	003	Sabina	87100
002	Mónica Comes Pérez	Enfermera	004	Tamulte	85300
003	Carmen Cruz Cruz	Dentista	001	Méndez	86003
003	Carmen Cruz Cruz	Dentista	002	Rovirosa	86105
003	Carmen Cruz Cruz	Dentista	003	Sabina	87100
003	Carmen Cruz Cruz	Dentista	004	Tamulte	85300
004	Miguel Contreras León	Ingeniero	002	Rovirosa	86105
004	Miguel Contreras León	Ingeniero	003	Sabina	87100
004	Miguel Contreras León	Ingeniero	001	Méndez	86003
004	Miguel Contreras León	Ingeniero	004	Tamulte	85300

RESULTADO
NOMBRE	OFICIO	COLONIA
Miguel Contreras León	Ingeniero	Tamulte

   

¿PARA QUE SIRVE EL ÁLGEBRA RELACIONAL?

El álgebra relacional permite escribir expresiones que sirven para diversos propósitos, como son;

• Recuperar información: definir datos que van a ser introducidos, modificados o borrados.
• Relaciones virtuales: definir datos que van a ser visibles por medio de vistas.
• Rhapshots: definen datos que van  a conservar en forma de relacion "shapshot" -(consultas rápidas aleatorias).
• Reglas de validación: define el dominio de los datos.