8.- Grafos dirigidos

 Grafos dirigidos y no dirigidos. Hasta ahora hemos supuesto que un arco conecta dos nodos en ambos sentidos igualmente. Un grafo dirigido es aquel en el que los arcos tienen un único sentido. En este caso, un arco se dirige desde el nodo origen hasta el nodo destino. Se dice que el nodo origen precede al nodo destino, y que éste sucede al origen. Los arcos de un grafo dirigido se representan gráficamente con flechas. Un grafo no dirigido es un grafo donde los arcos conectan a los nodos en ambos sentidos. Un grafo dirigido se podría usar para representar bloques de un programa mediante los nodos y la transferencia del flujo de control mediante los arcos. Un grafo que representara el sentido del tráfico entre diferentes plazas podría ser:

7.- Mapas de Karnaugh

 Un mapa de Karnaugh24 (también conocido como tabla de Karnaugh o diagrama de Veitch) es un diagrama utilizado para la simplificación de funciones algebraicas en forma canónica. A partir de la tabla de Karnaugh se puede obtener una forma canónica mínima (con el mínimo número de términos). En este texto emplearemos indistintamente los términos “mapa” y “tabla” de Karnaugh.

Nota.- Observe que siempre existirán dos formas canónicas mínimas, una DNF y otra CNF.

La tabla de Karnaugh consiste en una representación bidimensional de la función que se quiere simplificar. Si la función viene expresada como una tabla de verdad, entonces la tabla de Karnaugh puede verse como una forma alternativa de representación 2D. Puesto que la tabla de verdad de una función de n variables posee 2n filas, la tabla de Karnaugh correspondiente debe poseer también 2n celdas. La construcción de la tabla de Karnaugh pasa por codificar cada celda en código binario reflejado (o código Gray) de manera que celdas adyacentes tengan un código que difiere en un solo dígito.

Figura 3.1: Descripción del mapa de Karnaugh

En la Fig. 3.1 puede verse un ejemplo de codificación Gray para el caso de funciones lógicas de 4 variables. Cada variable lógica (A, B, C, D en la figura) se corresponde con un bit del código Gray.

En la práctica, no es necesario explicitar el código de cada celda; basta con expresar las cabeceras de las filas y columnas en código Gray (el código de la celda se construye combinando la fila y columna correspondiente), según se desprende de la figura.

Definida la codificación Gray para la tabla, las celdas se rellenan asignando el valor ‘1’ para el caso que exista el término canónico correspondiente en la función objeto de análisis, y el valor ‘0’ en caso contrario. Si la función lógica viene expresada como tabla de verdad, se puede elegir la forma canónica para expresar la función. El criterio más lógico es elegir aquella forma que contenga inicialmente el menor número de términos. Para ello basta con contar el número de interpretaciones que satisfacen la fórmula lógica (filas de la tabla de verdad con resultado ‘1’). Cuando el número de interpretaciones que satisfacen la fórmula lógica es menor que el número de interpretaciones que no la satisfacen, se elige la forma canónica DNF. En caso contrario la CNF.

Nota.- Las tablas de Karnaugh se pueden realizar fácilmente a mano con funciones de hasta 6 variables. Para funciones de mayor cantidad de variables es más eficiente el uso de software especializado.

Una vez construida la tabla de Karnaugh se procede a la reducción del número de términos (si es posible) mediante la agrupación de celdas adyacentes en la tabla con valor ‘1’25.

Las dos secciones siguientes describen el algoritmo de simplificación en detalle para las formas canónicas DNF y CNF.

6.- Algebra de Boole

 El álgebra de Boole está formada por un conjunto de variables booleanas, 

$x\in \{0,1\}$. Es decir variables que sólo pueden tomar dos valores: 0 ó 1, verdadero o falso, abierto o cerrado, encendido o apagado, etc.

Un literal l es una variable o su negada. Existen dos tipos: literales con signo positivo cuando representan el valor ‘1’ de la variable ($l=x$), y con signo negativo cuando representa el valor ‘0’ ($l=\overline{x}$).

Una cláusula (o término C) está formada por un conjunto de literales enlazados mediante conectivas lógicas.

Una fórmula lógica $\varphi$ está formada por conjuntos de cláusulas enlazadas mediante conectivas lógicas. Matemáticamente, toda fórmula lógica $\varphi$ de n variables puede verse también como una función multivariable, esto es $\varphi :\{0,1{\}}^n\to \{0,1\}$. En este texto emplearemos indistintamente los términos de función y fórmula.

Una interpretación de una fórmula lógica $\varphi$ es el valor lógico de la fórmula cuando se le asignan valores de verdad (TRUE / FALSE) a sus variables. En consecuencia, existirán tantas interpretaciones como combinaciones de asignaciones posibles.

Se dice que una fórmula lógica es satisfacible cuando existe al menos una interpretación que la hace verdadera.

Una tabla de verdad, o tabla de valores de verdades, es una tabla que muestra el valor de verdad de una cláusula o fórmula lógica, para cada combinación de verdad que se pueda asignar a sus literales

5. Lógica de bits (not, and, or, xor)

 

Compuertas Lógicas

Las compuertas lógicas son circuitos electrónicos diseñados para obtener resultados booleanos (0,1), los cuales se obtienen de operaciones lógicas binarias (suma, multiplicación). Dichas compuertas son AND, OR, NOT, NAND, NOR, XOR, XNOR. Además se pueden conectar entre sí para obtener nuevas funciones.A continuación se describirá  las características de las compuertas. Este tipo de dispositivos lógicos se encuentran implementados con transistores y diodos en un semiconductor y actualmente podemos encontrarlas en formas de circuitos integrados lógicos. Al mismo tiempo, puedes tu programar el comportamiento de otra manera, con circuitos reconfigurables o programable, como microcontroladores o FPGAs. Sin embargo, en este tutorial veremos las compuertas implementadas en circuitos independientes y su comportamiento.

                                    Compuerta AND

Compuerta OR

Compuerta NOT

Compuerta NAND 

Compuerta XOR

4. Potencia Booleana r-ésima

 Potencia booleana r-esima

La potencia r-ésima de una matriz cuadrada A es el producto booleano de r (entero positivo) factores iguales. Esta potencia booleano r-ésima se denota por A[r].

3.- Producto Booleano

 

2.- Operaciones Unión e Interjección

                                                                Unión:

Interjección:

1.- Matrices Booleanas