Algebra Booleana Introduccion

Algebra Booleana Introduccion

A CONTINUACION SE MUESTRAN TODOS LOS TEMAS DE LA UNIDAD 3 ESPERO Y LE SIRVA DE ALGO

Algebra Booleana

3.1 Introducción

Las álgebras booleanas, estudiadas por primera vez en detalle por George Boole, constituyen un área de las matemáticas que ha pasado a ocupar un lugar prominente con el advenimiento de la computadora digital. Son usadas ampliamente en el diseño de circuitos de distribución y computadoras, y sus aplicaciones van en aumento en muchas otras áreas.

En el nivel de lógica digital de una computadora, lo que comúnmente se llama hardware, y que está formado por los componentes electrónicos de la máquina, se trabaja con diferencias de tensión, las cuales generan funciones que son calculadas por los circuitos que forman el nivel. Éstas funciones, en la etapa de diseña del hardware, son interpretadas como funciones de boole.

Álgebra de Boole (también llamada Retículas booleanas) en matemáticas y computación, son estructuras algebraicas que “capturan la esencia” de las operaciones lógicas Y, O y NO, así como el conjunto de operaciones unión, intersección y complemento.

Se denomina así en honor a George Boole, 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 preposicional. En la actualidad el álgebra de Boole se aplica de forma generalizada en diseño electrónico. Se aplicó por primera vez en circuitos de conmutación eléctrica biestables por Claude Shannon en 1938.

Los operadores del álgebra de Boole pueden representarse de varias formas. A menudo se representan simplemente como AND (Y), OR (O) y NOT (NO). En electrónica digital también se emplean la X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y X-NOR (equivalencia) . En matemáticas a menudo se utiliza + en lugar de OR y - en lugar de AND, debido a que estas operaciones son de alguna manera análogas a la suma y el producto en otras estructuras algebraicas, y NOT se representa como una línea o una comilla sobre la expresión que se pretende negar (NO A sería Ā o A’).

No se puede comenzar el estudio del Algebra de Boole sin conocer el concepto de clase. Se define como clase el total de los elementos que cumplen las características definidas por un criterio de pertenencia. En general, una subclase S de una clase dada C, es una clase cuyos elementos pertenecen a la clase C. A su vez, la clase C podría ser una subclase de una clase más amplia que contuviera todos los elementos de C juntos con otros elementos distintos. E inversamente, la clase S puede contener sus propias subclases.

Una clase especialmente importante es la denominada clase de referencia o clase universal, que es aquella que comprende a todos los elementos bajo estudio. Una vez definida la clase universal, se puede definir la clase complementaria de una clase cualquiera A perteneciente a la universal, como la clase que encierra a todos los elementos de la clase universal excepto aquellos que están contenidos en la clase A. Finalmente, se definir la clase vacía como la clase complementaria de la clase universal. De acuerdo con la definición de clase universal, la clase vacía es aquella que no contiene ningún elemento.

En este artículo se empleará la notación común con para el operador AND, para el operador OR y (o ~) para el operador NOT.

3.2 Expresiones booleanas

Las expresiones booleanas se usan para determinar si un conjunto de una o más condiciones es verdadero o falso, y el resultado de su evaluación es un valor de verdad. Los operandos de una expresión booleana pueden ser cualquiera de los siguientes:

Expresiones relacionales: que comparan dos valores y determinan si existe o no una cierta relación entre ellos.

Funciones booleanas: tal como p(v24), que regresa un valor de verdad.

Las expresiones relacionales permiten determinar si una relación dada se verifica entre dos valores. La forma general de una expresión relacional es:

Expresión-1 operador-de-relación expresión-2

Donde:

expresión-1 es una expresión numérica o de cadena

operador-de-relación es uno de los siguientes:

o = Igual

o<> No igual (diferente de)

o< Menor que

o<= Menor o igual que

o> Mayor que

o>= Mayor o igual que

o: Contiene (puede ser usado sólo en expresiones de cadena)

•expresión-2 es una expresión del mismo tipo que expresión-1, o sea, expresión-1 y expresión-2 deben ser ambas expresiones numéricas o ambas expresiones de cadena.

Los operadores de relación = <> < <= > >= tienen su significado convencional cuando se aplican a expresiones numéricas (dentro de los límites de precisión de los valores numéricos definidos bajo “Expresiones numéricas”). Cuando se comparan expresiones de cadena, se aplican las siguientes reglas:

•Excepto por el operador “:” (contiene), las cadenas se comparan exactamente en la forma en que ocurren, o sea, las letras mayúsculas y minúsculas se comparan de acuerdo con el código ASCII que les corresponde (p.ej. A será considerada menor que a);

•Dos expresiones de cadena no son consideradas iguales, a menos que tengan la misma longitud. Si dos expresiones generan cadenas de diferente longitud que son idénticas, carácter por carácter, hasta el total de la longitud de la más corta, entonces, la más corta será considerada menor que la más larga.

El operador “:” (contiene), busca una cadena de caracteres (definida por expresión-2) en otra cadena (definida por expresión-1). Si el segundo operando existe en cualquier parte del segundo operando, el resultado es Verdadero (TRUE). Este operador es insensible al hecho de que los caracteres se hallen en mayúsculas o minúsculas: por lo que las letras minúsculas se consideran iguales a su letra mayúscula correspondiente. Por ejemplo, el resultado de:

v10 : ‘química’

será Verdadero (True) si, y sólo si, el campo 10 contiene la cadena química. En caso contrario, el resultado será Falso (False). Nótese que el segundo operando puede ser cualquier cadena o carácter, y no necesita ser una palabra como tal. Por lo tanto, en este ejemplo, el resultado será Verdadero no sólo si el campo 10 contiene la palabra química, sino también si contuviera bioquímica, fotoquímicas, químicamente, etc.

Los operandos de una expresión booleana pueden combinarse con los operadores siguientes:

•NOT (NO) Este operador produce el valor Verdadero, si su operando es Falso; y el valor Falso, si su operando es Verdadero. El operador NOT sólo puede usarse como operador signo +, o sea, siempre se aplica a la expresión booleana que le sigue;

•AND (Y) Este operador produce el valor Verdadero si ambos operandos son Verdadero. Si cualquiera de los dos operandos es Falso, entonces el resultado será Falso;

•OR (O) Este operador realiza una operación O-inclusivo. El resultado es Verdadero si cualquiera de los dos operandos, o ambos son Verdadero. En caso contrario, es Falso.

Al evaluar expresiones booleanas, y en ausencia de paréntesis, CDS/ISIS ejecutará las operaciones NOT en primer lugar, después las operaciones AND, y finalmente las OR. Las series de dos o más operadores del mismo nivel, se ejecutan de izquierda a derecha. Se pueden usar paréntesis para alterar el orden de evaluación: las expresiones dentro de paréntesis se evalúan antes, y las expresiones entre paréntesis internos a otros, son evaluadas antes que las expresiones externas a los paréntesis.

Expresiones booleanas simples

Las expresiones booleanas simples pueden ser:

constantes y variables booleanas;

referencias a funciones booleanas;

expresiones de la forma

Expresiones booleanas compuestas

Las expresiones booleanas compuestas se forman combinando expresiones booleanas usando los operadores booleanos NOT, AND y OR.

3.3 Propiedades de expresiones Booleanas

Se dice que es un Álgebra de Boole si se cumplen las siguientes propiedades axiomáticas:

A1. Conmutativa: para todo a y b que son elementos del conjunto A; la suma de a + b es igual

Que b + a de la misma manera que el producto de a • b es igual a b • a.

 A, a + b = b + a y a • b = b • a

A2. Identidad: Los elementos neutros de ( + ) y ( ● ) son, respectivamente, el elemento cero (0) y el elemento (1).

 A, a + 0 = a y a • 1 = a

3. Distributiva: a, b, c A, a + (b • c) = (a + b) • (a + c) y a • (b + c) = (a • b) + (a • c)

a ∈ A, a + ∼a = 1 y a • ∼a = 0

3.4 Optimización de expresiones Booleanas

Para obtener una optimización de una expresión booleana podemos considerar dos formas para realizarlo.

El número de variables de una expresión booleana es el número de letras distintas que aparezcan en la expresión, sin tener en cuenta si están o no complementadas.

Forma normal disyuntiva. Una expresión booleana está en forma normal disyuntiva en n variables x1, x2,… xn, si la expresión es una suma de términos del tipo E1 (x1) x E2( x2) x … x En(xn), donde Ei(xi) = xi o xi’ para i = 1, 2,…, n, y ningún par de términos son idénticos. Además se dice que 0 y 1 están en F.N.D en una variable para todo n  0.

Teorema. Toda expresión booleana que no contiene constantes es igual a una función en forma normal disyuntiva.

Definición. La forma normal disyuntiva en n variable, que contiene 2n términos se llama forma normal disyuntiva completa en n variable. .

Teorema. Si a cada una de las n variables de una expresión booleana en la F.N.D se le asigna el valor 0 o 1 de una forma arbitraria pero fija, entonces exactamente un término de la F.N.D completa tendrá el valor 1, todos los demás términos tendrán el valor 0. .

Teorema. Dos expresiones booleanas son iguales si y sólo si sus respectivas F.N.D son iguales. .

Teorema. Para establecer cualquier Identidad en álgebra booleana, es suficiente verificar el valor de cada función para todas las combinaciones de 0 y 1 que pueden asignarse a las variables.

Se concluye entonces, que una expresión booleana está completamente determinada por los valores que toma para cada asignación posible de 0 y 1 a las variables respectivas. Luego las funciones se pueden especificar completamente dando una tabla que represente estas propiedades. .

En el diseño de circuitos, esta es precisamente la manera como las expresiones booleanas son construidas. Si tal tabla ha sido dada, entonces la expresión booleana en F.N.D puede escribirse por inspección. A cada conjunto de condiciones para los cuales la expresión booleana sea 1, corresponderá un término en la F.N.D escogida. La suma de estos términos da la función aunque no necesariamente en la forma más simple. . Forma normal conjuntiva. En esta forma cada función se representa como un producto de sumas, en lugar de una suma de productos. .

Definición. Una función booleana está en F.N.C en n variables x1, x2,… xn, para n  0, si la función en un producto de factores del tipo E1 (x1)  E2(x2) …  En (xn), donde Ei(xi) = xi o xi’ para i = 1, 2, …, n, y ningún par de factores son idénticos. Se dice también que 0 y 1 están en F.N.C en n variables para n  0.

Teorema. Toda función en un álgebra booleana que no contiene constantes es igual a una función en forma normal conjuntiva.

Definición. La forma normal conjuntiva en n variable que contienen 2n factores se llama forma normal conjuntiva completa en n variable. .

 Teorema. Si a cada una de las n variables de una F.N.C se le asigna el 0 o 1 de una manera arbitraria, pero fija, entonces exactamente un factor de la F.N.C en las n variables tendrá el valor 0 y todos los demás factores tendrán el valor 1. 

Teorema. Dos funciones, cada una expresada en la forma normal conjuntiva en n variables, son iguales si y sólo si contienen idénticos factores.

3.5 Compuertas lógicas (como una aplicación)

COMPUERTAS LOGICAS

Una compuerta lógica es un dispositivo que nos permite obtener resultados, dependiendo de los valores que le ingresemos.

Es necesario aclarar entonces que las compuertas lógicas se comunican entre si, incluidos los microprocesadores, que son nada más que muchas compuertas agrupadas entre sí, usando el sistema BINARIO el cual consta de solo 2 indicadores, 0 y 1, que se representan como BIT, y ya que en electrónica solo hay 2 valores equivalentes 0=0volt 1=5volt, (conectado-desconectado), es decir cuando conectamos una compuerta a el negativo equivale a introducir un cero (0), y por el contrario si derivamos la entrada a 5v le estamos enviando un uno (1). Ahora para que comprendan como se comporta cada compuerta se debe ver su TABLA DE VERDAD, la que muestra todas las combinaciones lógicas posibles y su resultado.

COMPUERTA NOT

La compuerta NOT es todo lo contrario al Buffer, invierte el valor que se le entrega, también tiene la utilidad de ajustar niveles pero tomando en cuenta que invierte la señal.

COMPUERTA BUFFER

La compuerta BUFFER es la más básica de todas, simplemente toma el valor que se le entrega y lo deja pasar tal cual, esto sirve para ajustar y aislar niveles lógicos, ya que no se pueden conectar infinita cantidad de compuertas a una misma señal, ya que el voltaje del nivel 1 empieza a decaer y el sistema falla.

COMPUERTA AND

La compuerta AND hace la función de multiplicación, es decir toma los valores que le aplicamos a sus entradas y los multiplica.

COMPUERTA NAND

La compuerta NAND también hace la función de multiplicación, es decir toma los valores que le aplicamos a sus entradas y los multiplica. Pero entrega el valor negado, esto es muy util, por que por ejemplo si estuviéramos usando una AND normal, tendríamos que usar otro chip con un NOT para negar el resultado.

COMPUERTA OR

La compuerta OR realiza la función de suma, cuando se le aplica un uno a cualquiera de sus entradas el resultado será uno, independiente del valor de la otra entrada. Excepto cuando las dos entradas estén en 0 la salida será 0.

COMPUERTA NOR

La compuerta NOR realiza la función de suma, pero entrega el resultado invertido, ahorrándonos un NOT, su salida será 1 solo si las dos entradas son 0.

COMPUERTA X-OR

Esta compuerta XOR o OR-exclusiva, se comporta de una manera especial y se usa muy poco, su característica especial es que el resultado de salida será 1 si las dos entradas son distintas, osean 0–1 ó 1–0.

El álgebra de Boole tiene muchas aplicaciones prácticas en las ciencias físicas, especialmente en la informática y en la electrónica. A continuación se expone un ejemplo del uso del álgebra de Boole en la teoría de circuitos electrónicos. Sean p y q dos proposiciones, es decir, oraciones afirmativas que son o verdaderas o falsas (pero no las dos cosas al mismo tiempo). Si cada una de las proposiciones p y q se asocia con un interruptor que está cerrado si la afirmación es verdadera y abierto si es falsa, entonces la proposición p ^ q se representa en el circuito conectando los interruptores en serie. La corriente circulará por este circuito si y sólo si ambos interruptores están cerrados, esto es, si ambas p y q son verdaderas. De la misma manera, otro circuito se puede usar para representar p Ú q. En este caso los interruptores tienen que estar conectados en paralelo, con lo que la corriente circula si o p o q o ambas son verdaderas (interruptores cerrados). Proposiciones más complejas darán lugar a circuitos más complicados.

NOTA CHEQUEN LOS SIMBOLOS QUE AL CAMBIARLE LA LETRA SE MODIFICARON

REALIZADO POR: JESUS ALBERTO CORTES CARREON


Mis sitios nuevos:
Emprendedores
Politica de Privacidad