domingo, 7 de diciembre de 2008

Función Booleana

Se denomina función lógica o booleana a aquella función matemática cuyas variables son binarias y están unidas mediante los operadores del álgebra de Boole suma lógica (+), producto lógico (•) o negación(').

Modos de representación

Existen distintas formas de representar una función lógica, entre las que podemos destacar las siguientes:

* Algebraica
* Por tabla de verdad
* Numérica
* Gráfica

El uso de una u otra, como veremos, dependerá de las necesidades concretas en cada caso.

Algebraica

Se utiliza cuando se realizan operaciones algebraicas. A continuación se ofrece un ejemplo con distintas formas en las que se puede expresar algebraicamente una misma función de tres variables.

a) F = [(A + BC’)’ + ABC]’ + AB’C
b) F = A’BC’ + AB’C’ + AB’C + ABC’
c) F = (A + B + C)(A + B + C’)(A + B’ + C’)(A’ + B’ + C’)
d) F = BC’ + AB’
e) F = (A + B)(B’ + C’)
f) F = [(BC’)’ • (AB’)’]’
g) F = [(A + B)’ + (B’ + C’)’]’

La expresión a) puede proceder de un problema lógico planteado o del paso de unas especificaciones a lenguaje algebraico. Las formas b) y c) reciben el nombre expresiones canónicas de suma de productos (sum-of-products, SOP, en inglés), la b), y de productos de sumas (product-of-sums, POS, en inglés), la c); su característica principal es la aparición de cada una de las variables (A, B y C) en cada uno de los sumandos o productos. Las d) y e) son funciones simplificadas, esto es, reducidas a su mínima expresión. Las dos últimas expresiones tienen la particularidad de que exclusivamente utiliza funciones NO-Y, la f), o funciones NO-O, la g).

Por tabla de verdad

Una tabla de verdad contiene todos los valores posibles de una función lógica dependiendo del valor de sus variables. El número de combinaciones posibles para una función de n variables vendrá dado por 2n. Una función lógica puede representarse algebraicamente de distintas formas como acabamos de ver, pero sólo tiene una tabla de verdad. La siguiente tabla corresponde a la función lógica del punto anterior.



La forma más cómodo para ver la equivalencia entre una tabla de verdad y una expresión algebraica es cuando esta última se da en su forma canónica. Así, la función canónica de suma de productos

F = A’BC’ + AB’C’ + AB’C + ABC’

nos indica que será 1 cuando lo sea uno de sus sumandos, lo que significa que tendrá por lo tanto cuatro combinaciones que lo serán (010 para A’BC’, 100 para AB’C’, 101 para AB’C y 110 para ABC’) siendo el resto de combiaciones 0. Con la función canónica de producto de sumas se puede razonar de forma análoga, pero en este caso observando que la función será 0 cuando lo sea uno de sus productos.

También es fácil obtener la tabla de verdad a partir de la función simplificada, pero no así a la inversa.

Numérica

La representación numérica es una forma simplificada de representar las expresiones canónicas. Si consideramos el criterio de sustituir una variable sin negar por un 1 y una negada por un 0, podremos representar el término, ya sea una suma o un producto, por un número decimal equivalente al valor binario de la combinación. Por ejemplo, los siguientes términos canónicos se representarán del siguiente modo (observe que se toma el orden de A a D como de mayor a menor peso):

AB’CD = 10112 = 1110
A’ + B + C’ + D’ = 01002 = 410

Para representar una función canónica en suma de productos utilizaremos el símbolo Σn (sigma) y en producto de sumas Πn (pi), donde n indicará el número de variables. Así, la representación numérica correspondiente a la tabla de verdad del punto anterior quedará como:

F = Σ3(2, 4, 5, 6) = Π3(0, 1, 3, 7)

Matemáticamente se demuestra, que para todo término i de una función, se cumple la siguiente ecuación:

F = [Σn(i)]' = Πn(2n-1-i )

A modo de ejemplo se puede utilizar esta igualdad para obtener el producto de sumas a partir de la suma de productos del ejemplo anterior:

F = Σ3(2, 4, 5, 6) = [Σ3(2, 4, 5, 6)]' ' = [Σ3(0, 1, 3, 7)]' = Π3(0, 4, 6, 7)

Gráfica


La representación gráfica es la que se utiliza en circuitos y esquemas electrónicos. En la siguiente figura se representan gráficamente dos funciones algebraicas, una con símbolos no normalizados, superior, y la otra con normalizados, inferior (véanse los símbolos de las puertas lógicas)



Métodos de simplificación

Por simplificación de una función lógica se entiende la obtención de su mínima expresión. A la hora de implementar físicamente una función lógica se suele simplificar para reducir así la compejidad del circuiuto.

A continuación se indican los modos más usuales de simplificar una función lógica.

Algebraico

Para la simplificación por este método no sólo bastará con conocer todas las propiedades y teoremas del álgebra de Boole, además se debe desarrollar una cierta habilidad lógico-matemática que se adquiere fundamentalmente con la experiencia.

Como ejemplo se simplificará la siguiente función:

F = A’C’ + ABC + BC’ + A’B’C + A’BC

Observando cada uno de los sumando podemos ver que hay factores comunes en los sumandos 2º con 5º y 4 con 5º que conllevan simplificación:

F = A’C’ + BC’ + BC(A + A’) + A’C(B + B’)

Note que el término 5º se ha tomado dos veces, de acuerdo con la propiedad que diceque A + A´ = 1. Aplicando las propiedades del álgebra de Boole, queda

F = A’C’ + BC’ + BC + A’C

Repitiendo nuevamente el proceso,

F = A’( C’ + C) + B( C’ + C) = A’ + B

No siempre las funciones son tan fáciles de simplificar como la anterior. El método algebraico, por lo general, no resulta cómodo para los no expertos, a los cuales, una vez simplificada una ecuación le pueden quedar serias dudas de haber conseguido la máxima simplificación.

Gráfico de Karnaugh

Este método consiste en formar diagramas de 2n cuadros, siendo n el número de variables. Cada cuadro representa una de las diferentes combinaciones posibles y se disponen de tal forma que se puede pasar de un cuadro a otro en las direcciones horizontal o vertical, cambiando únicamente una variable, ya sea en forma negada o directa.

Este método se emplea fundamentalmente para simplificar funciones de hasta cuatro variables. Para un número superior utilizan otros métodos como el numérico. A continuación pueden observarse los diagramas, también llamados mapas de Karnaugh, para dos, tres y cuatro variables.

Es una práctica común numerar cada celda con el número decimal correspondiente al término canónico que albergue, para facilitar el trabajo a la hora de plasmar una función canónica.

Para simplificar una función lógica por el método de Karnaugh se seguirán los siguientes pasos:

1º) Se dibuja el diagrama correspondiente al número de variables de la función a simplificar.

2º) Se coloca un 1 en los cuadros correspondientes a los términos canónicos que forman parte de la función.

3º) Se agrupan mediante lazos los unos de casillas adyacentes siguiendo estrictamente las siguientes reglas:

a) Dos casillas son adyacentes cuando se diferencian únicamente en el estado de una sola variable.

b) Cada lazo debe contener el mayor número de unos posible, siempre que dicho número sea potencia de dos (1, 2, 4, etc.)

c) Los lazos pueden quedar superpuestos y no importa que haya cuadrículas que pertenezcan a dos o más lazos diferentes.

d) Se debe tratar de conseguir el menor número de lazos con el mayor número de unos posible.

4º) La función simplificada tendrá tantos términos como lazos posea el diagrama. Cada término se obtiene eliminando la o las variables que cambien de estado en el mismo lazo.

A modo de ejemplo se realizan dos simplificaciones de una misma función a partir de sus dos formas canónicas:

F = Σ3(0,2,3,4,7) = Π3(1,2,6)

De acuerdo con los pasos vistos anteriormente, el diagrama de cada función quedará del siguiente modo:

Algebra Booleana

Álgebra de Boole en informática y matemática, es una estructura algebraica que rigorizan las operaciones lógicas AND, OR y NOT, así como el conjunto de operaciones unión, intersección y complemento.

Se denomina así en honor a George Boole, (2 de noviembre de 1815 a 8 de diciembre de 1864), matemático inglés que fue el primero en definirla como parte de un sistema lógico a mediados del siglo XIX. Específicamente, el álgebra de Boole fue un intento de utilizar las técnicas algebraicas para tratar expresiones de la lógica proposicional. En la actualidad, el álgebra de Boole se aplica de forma generalizada en el ámbito del diseño electrónico.

El resultado de aplicar cualquiera de las tres operaciones definidas a variables del sistema booleano resulta en otra variable del sistema, y este resultado es único.

Leyes fundamentales

Codificación

La codificación consiste en transformar la formulación de un mensaje mediante una serie de reglas dispuestas según un plan metódico y sistemático. Al conjunto de estas reglas metódicas que definen la codificación se les denomina código.

En la arquitectuda de computadoras, el código más utilizado es en código binario ya que a la máquina (en este caso, una computadora) le es más fácil tranformar esta información a niario que a cualquiero otro código por el siemple heche de solo manejar 2 números, u ejepemplo de este es:



Características del código binario

Ponderación.-La mayoría de los sistemas de numeración actuales son ponderados, es decir, cada posición de una secuencia de dígitos tiene asociado un peso. El sistema binario es, de hecho, un sistema de numeración posicional ponderado. Sin embargo, algunos códigos binarios, como el código Gray, no son ponderados, es decir, no tienen un peso asociado a cada posición. Otros, como el mismo código binario natural o el BCD natural sí lo son.

Distancia.- La distancia es una característica sólo aplicable a las combinaciones binarias. La distancia entre dos combinaciones es el número de bits que cambian de una a otra. Por ejemplo, si se tienen las combinaciones de cuatro bits 0010 y 0111, correspondientes al 2 y al 7 en binario natural, se dirá que la distancia entre ellas es igual a dos (ya que de una a otra cambian dos bits). Además, con el concepto de distancia se puede definir la distancia mínima de un código. Ésta no es más que la distancia menor que haya entre dos de las combinaciones de ese código.

Adyacencia.- La adyacencia es una característica que consiste en que de una combinación binaria a la siguiente sólo varía un bit (distancia igual a uno). Esta propiedad es aplicable únicamente a las combinaciones binarias de un código, no al código en sí mismo.

Continuidad.- La continuidad es una característica de los códigos binarios que cumplen que todas las posibles combinaciones del código son adyacentes, es decir, que de cualquier combinación del código a la siguiente cambia un sólo bit. En este caso se dice que el código es continuo. Cuando la última combinación del código es, a su vez, adyacente a la primera, se trata de un código cíclico.

Autocomplementariedad.- Se dice que un código binario es autocomplementario cuando el complemento a nueve del equivalente decimal de cualquier combinación del código puede hallarse invirtiendo los valores de cada uno de los bits (operación lógica unaria de negación) y el resultado sigue siendo una combinación válida en ese código. Esta característica se observa en algunos códigos BCD, como el código Aiken o el código BCD exceso 3. Los códigos autocomplementarios facilitan las operaciones aritméticas.

Sistéma numérico

En matemáticas, varios sistemas de notación que se han usado o se usan para representar cantidades abstractas denominadas números. Un sistema numérico está definido por la base que utiliza. La base de un sistema numérico es el número de símbolos diferentes o guarismos, necesarios para representar un número cualquiera de los infinitos posibles en el sistema.

Definición


Un conjunto S es un sistema numérico si en él están definidas dos operaciones binarias asociativas y conmutativas, denominadas adición y multiplicación, y si además se cumple que la multiplicación es distributiva con respecto a la adición. Para a, b y c elementos de S:

Propiedad asociativa de la adición: (a + b) + c = a + (b + c)

Propiedad conmutativa de la adición: a + b = b + a

Propiedad asociativa de la multiplicación: (a.b).c = a.(b.c)

Propiedad conmutativa de la multiplicación: a.b = b.a

Propiedad distributiva de la multiplicación sobre la adición: a.(b + c) = a.b + a.c

La adición y la multiplicación no necesariamente deben ser las de la aritmética elemental.

Es una práctica didáctica que los maestros utilicen objetos como manzanas o naranjas y la noción de conjunto para enseñar a sumar. Esta práctica podrá ser útil a la hora de enseñar, pero descansa en ideas no demasiado meditadas. Para las consideraciones que siguen utilizaremos la convención de asimilar la suma a la unión de conjuntos y el producto a la intersección, como en el título anterior:

* La unión de conjuntos es asimilable a la suma ordinaria solamente si los conjuntos son disjuntos:

En una primera aproximación tenemos que dos conjuntos que tengan tres y cuatro elementos, respectivamente, y que no contengan elementos comunes, darán por unión un conjunto de siete elementos, conforme a la intención del docente para lo que desea lograr en el alumno. Pero si esos conjuntos tuvieran dos elementos comunes la unión daría por resultado un conjunto de tres elementos.


* Se ve afectado el papel del elemento identidad para la adición o elemento nulo de la suma.

Podríamos asimilar al conjunto vacío como el elemento identidad para la suma, ya que: 0 U A = A U 0; pero también A U A = A y si B c A tenemos el mismo resultado, con lo que cada conjunto y todos los conjuntos incluidos en él lo dejan idéntico con respecto a la unión. Pero el conjunto vacío es el único que lo hace con todos los conjuntos.


* La intersección es más chocante en cuanto a su paralelismo con el producto.

La intersección de dos conjuntos disjuntos distintos del conjunto vacío darán por resultado el conjunto vacío. Esto equivale a decir que en el sistema numérico que forman los conjuntos hay divisores de cero. La intersección de conjuntos con elementos comunes dejará un conjunto con menos elementos que el menor de ellos. A lo sumo igual al menor de ellos, si está incluido dentro del conjunto mayor.


* La unidad o elemento identidad para la multiplicación.

Si adoptamos el uso intuitivo o hasta la formulación formal de los conjuntos, el sistema carecerá de unidad, puesto que no habrá ningún conjunto cuya intersección con otro cualquiera deje a ese idéntico. En el caso que se definiera un conjunto universal, referencial o de referencia, éste sería la unidad. Al estar cualquier conjunto definido a partir de él, la intersección de cualquier conjunto con el de referencia daría por resultado el conjunto menor. Pero esta unidad es un poco diferente de la idea intuitiva que se tiene a partir de la aritmética.

Arquitectura de computadoras

La arquitectura de computadoras es el diseño conceptual y la estructura operacional fundamental de un sistema de computadora. Es decir, es un modelo y una descripción funcional de los requerimientos y las implementaciones de diseño para varias partes de una computadora, con especial interés en la forma en que la unidad central de proceso (CPU) trabaja internamente y accede a las direcciones de memoria.


También suele definirse como la forma de seleccionar e interconectar componentes de hardware para crear computadoras según los requerimientos de funcionalidad, rendimiento y costo.

La segmentación de instrucciones es similar al uso de una cadena de montaje en una fábrica de manufacturación. En las cadenas de montaje, el producto pasa a través de varias etapas de producción antes de tener el producto terminado. Cada etapa o segmento de la cadena está especializada en un área específica de la línea de producción y lleva a cabo siempre la misma actividad. Esta tecnología es aplicada en el diseño de procesadores eficientes.

A estos procesadores se les conoce como pipeline processors. Estos están compuestos por una lista de segmentos lineales y secuenciales en donde cada segmento lleva a cabo una tarea o un grupo de tareas computacionales. Los datos que provienen del exterior se introducen en el sistema para ser procesados. La computadora realiza operaciones con los datos que tiene almacenados en memoria, produce nuevos datos o información para uso externo.

Las arquitecturas y los conjuntos de instrucciones se pueden clasificar considerando los siguientes aspectos:

  • Almacenamiento de operandos en la CPU: dónde se ubican los operandos aparte de la memoria.
  • Número de operandos explícitos por instrucción: cuántos operandos se expresan en forma explícita en una instrucción típica. Normalmente son 0, 1, 2 y 3.
  • Posición del operando: ¿Puede cualquier operando estar en memoria?, o deben estar algunos o todos en los registros internos de la CPU. Cómo se especifica la dirección de memoria (modos de direccionamiento disponibles).
  • Operaciones: Qué operaciones están disponibles en el conjunto de instrucciones.
  • Tipo y tamaño de operandos y cómo se especifican.