Expresiones booleanas minimales

Expresiones booleanas minimales

Considérese una expresión E en un álgebra de Boole B. Como E puede representar un circuito lógico, es posible que pretendamos obtener una expresión F que, siendo equivalente a la expresión original, sea en algún sentido mínima; de esta forma, lograríamos minimizar la cantidad de compuertas lógicas utilizadas para implementar la operación buscada, con la consiguiente economía de recursos. Aquí nos concentraremos en la forma minimal de las expresiones booleanas que están en forma de suma de productos.

Si E es una expresión booleana en forma de suma de productos, EL denota el número de literales en E (contados con sus repeticiones) y ES denota el número de sumandos en E.

Por ejemplo, si E es la siguiente expresión:

Entonces EL=14 y ES=4.

Sea ahora F una expresión booleana de suma de productos equivalente a E. Decimos que E es más simple que F si se cumple que:

EL ≤ FL y ES ≤ FS

Y por lo menos una de las relaciones es una desigualdad estricta.

Definición: Una expresión booleana E está en forma minimal de suma de productos si está en forma de suma de productos y no hay ninguna otra expresión equivalente en forma de suma de productos que sea más simple que E.

Circuitos lógicos

Circuitos lógicos

Los circuitos lógicos se forman combinando compuertas lógicas. La salida de un circuito lógico se obtiene combinando las tablas correspondientes a sus compuertas componentes.

Por ejemplo:

Es fácil notar que las tablas correspondientes a las compuertas OR, AND y NOT son respectivamente idénticas a las tablas de verdad de la disyunción, la conjunción y la negación en la lógica de enunciados, donde sólo se ha cambiado V y F por 0 y 1. Por lo tanto, los circuitos lógicos, de los cuales tales compuertas son elementos, forman un álgebra de Boole al igual que los enunciados de la lógica de enunciados.

Adoptaremos, entonces, aquí las mismas convenciones adoptadas en el caso del álgebra de Boole:

• Omitimos el símbolo *, usándose en su lugar la yuxtaposición de variables.

• Establecemos que + es más fuerte que * y * es más fuerte que - .

Puesto que tanto el álgebra de Boole es la estructura algebraica tanto de los circuitos como de la lógica de enunciados, la salida de un circuito lógico también puede expresarse en el lenguaje de la lógica de enunciados. Por ejemplo, la salida del circuito anterior resulta:

Ejemplo: 

La salida de este circuito, expresada en el lenguaje de la lógica de enunciados, resulta: 

Compuertas lógicas derivadas: NOR, NAND, Separador (yes)

Compuerta Separador (yes):

Un símbolo triángulo por sí mismo designa un circuito separador, el cual no produce ninguna función lógica particular puesto que el valor binario de la salida es el mismo de la entrada. 
Este circuito se utiliza simplemente para amplificación de la señal. Por ejemplo, un separador que utiliza 5 volt para el binario 1, producirá una salida de 5 volt cuando la entrada es 5 volt. Sin embargo, la corriente producida a la salida es muy superior a la corriente suministrada a la entrada de la misma.
De ésta manera, un separador puede excitar muchas otras compuertas que requieren una cantidad mayor de corriente que de otra manera no se encontraría en la pequeña cantidad de corriente aplicada a la entrada del separador.

Compuerta NAND: 

Es el complemento de la función AND, como se indica por el símbolo gráfico, que consiste en una compuerta AND seguida por un pequeño círculo (quiere decir que invierte la señal).
La designación NAND se deriva de la abreviación NOT - AND. Una designación más adecuada habría sido AND invertido puesto que es la función AND la que se ha invertido.
Las compuertas NAND pueden tener más de dos entradas, y la salida es siempre el complemento de la función AND.

Compuerta NOR:   

La compuerta NOR es el complemento de la compuerta OR y utiliza el símbolo de la compuerta OR seguido de un círculo pequeño (quiere decir que invierte la señal). Las compuertas NOR pueden tener más de dos entradas, y la salida es siempre el complemento de la función OR.

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

Compuerta AND:  

Cada compuerta tiene dos variables de entrada designadas por A y B y una salida binaria designada por x. 
La compuerta AND produce la multiplicación lógica AND: esto es: la salida es 1 si la entrada A y la entrada B están ambas en el binario 1: de otra manera, la salida es 0. 
Estas condiciones también son especificadas en la tabla de verdad para la compuerta AND. La tabla muestra que la salida x es 1 solamente cuando ambas entradas A y B están en 1.
El símbolo de operación algebraico de la función AND es el mismo que el símbolo de la multiplicación de la aritmética ordinaria (*).
Las compuertas AND pueden tener más de dos entradas y por definición, la salida es 1 si todas las entradas son 1.

Compuerta OR:  

La compuerta OR produce la función sumadora, esto es, la salida es 1 si la entrada A o la entrada B o ambas entradas son 1; de otra manera, la salida es 0. 
El símbolo algebraico de la función OR (+), es igual a la operación de aritmética de suma. 
Las compuertas OR pueden tener más de dos entradas y por definición la salida es 1 si cualquier entrada es 1.

Compuerta NOT: 

El circuito NOT es un inversor que invierte el nivel lógico de una señal binaria. Produce el NOT, o función complementaria. El símbolo algebraico utilizado para el complemento es una barra sobra el símbolo de la variable binaria. 
Si la variable binaria posee un valor 0, la compuerta NOT cambia su estado al valor 1 y viceversa. 
El círculo pequeño en la salida de un símbolo gráfico de un inversor designa un inversor lógico. Es decir cambia los valores binarios 1 a 0 y viceversa.

 

Compuertas lógicas

Compuertas lógicas

Los circuitos lógicos se construyen a partir de ciertos circuitos elementales denominados compuertas lógicas

Las compuertas son bloques del hardware que producen señales en binario 1 ó 0 cuando se satisfacen los requisitos de entrada lógica. Las diversas compuertas lógicas se encuentran comúnmente en sistemas de computadoras digitales. Cada compuerta tiene un símbolo gráfico diferente y su operación puede describirse por medio de una función algebraica. Las relaciones entrada - salida de las variables binarias para cada compuerta pueden representarse en forma tabular en una tabla de verdad.

Entre las cuales diferenciaremos:

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

• Compuertas lógicas derivadas: NOR, NAND, Separador (yes)

¿Qué es un Circuito Lógico?

¿Qué es un Circuito Lógico?

Un Circuito Lógico es aquel que maneja la información en forma de "1" y "0", dos niveles lógicos de voltaje fijos. "1" nivel alto o "high" y "0" nivel bajo o "low". Puede ser cualquier circuito que se comporte de acuerdo con un conjunto de reglas lógicas.

Los circuitos lógicos, forman la base de cualquier dispositivo en el que se tengan que seleccionar o combinar señales de manera controlada. Entre los campos de aplicación de estos tipos de circuitos pueden mencionarse la conmutación telefónica, las transmisiones por satélite y el funcionamiento de las computadoras digitales.

 Los valores 0 y 1 pueden representar ciertas situaciones físicas como, por ejemplo, un  voltaje nulo y no nulo en un conductor.

Definición de álgebra de Boole

Definición de álgebra de Boole

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 séxtupla:

                        〈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