Sistemas numéricos
Un sistema numérico son un conjunto de símbolos y reglas que se utilizan para representar datos numéricos o cantidades. Se caracterizan por su base que indican el número de símbolos distinto que utiliza y además es el coeficiente que determina cual es el valor de cada símbolo dependiendo de la posición que ocupe. Estas cantidades se caracterizan por tener dígitos enteros y fraccionarios.
Si aj indica cualquier dígito de la cifra, b la base del sistema de numeración y además de esto la cantidad de dígitos enteros y fraccionarios son n y k respectivamente, entonces el número representado en cualquier base se puede expresar de la siguiente forma:
Nb = [an-1.an-2.an-3..........a3.a2.a1.a0,a-1.a-2.a-3 .......a-k]b
Donde: j = {n-1, n-2,.........2, 1, 0,-1, -2, ......, -k} y n + k indica la cantidad de dígitos de la cifra.
Por ejemplo, el número 31221, 324 en base cuatro tiene n=5 y k=2 con la parte entera: an-1=a4=3; a3=1; a2=2; a1=2; a0=1 y parte fraccionaria a-1=3; a-2=2
SISTEMA DECIMAL.
Este es el sistema que manejamos cotidianamente, está formado por diez símbolos {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} por lo tanto la base del sistema es diez (10).
SISTEMA BINARIO.
Es el sistema que utiliza internamente el hardware de las computadoras actuales, se basa en la representación de cantidades utilizando los dígitos 1 y 0. Por tanto su base es 2 (número de dígitos del sistema). Cada dígito de un número en este sistema se denomina bit (contracción de binarydigit). Se puede utilizar con nombre propio determinados conjuntos de dígitos en binario. Cuatro bits se denominan cuaterno(ejemplo: 1001), ocho bits octeto o byte (ejemplo: 10010110), al conjunto de 1024 bytes se le llama Kilobyte o simplemente K, 1024 Kilobytes forman un megabyte y 1024 megabytes se denominan Gigabytes.
El sistema numérico octal utiliza ocho símbolos o dígitos para representar cantidades y cifras numéricas. Los dígitos son: {0, 1, 2, 3, 4, 5, 6, 7}; la base de éste es ocho (8) y es un sistema que se puede convertir directamente en binario como se verá más adelante.
SISTEMA HEXADECIMAL.
El sistema numérico hexadecimal utiliza dieciséis dígitos y letras para representar cantidades y cifras numéricas. Los símbolos son: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F}; la base del sistema es dieciséis (16). También se puede convertir directamente en binario como se verá más adelante. En la tabla 1.1 se muestran los primeros veintiuno números decimales con su respectiva equivalencia binaria, octal y hexadecimal.
DECIMAL
|
BINARIO
|
OCTAL
|
HEXADECIMAL
|
0
|
0000
|
0
|
0
|
1
|
0001
|
1
|
1
|
2
|
0010
|
2
|
2
|
3
|
0011
|
3
|
3
|
4
|
0100
|
4
|
4
|
5
|
0101
|
5
|
5
|
6
|
0110
|
6
|
6
|
7
|
0111
|
7
|
7
|
8
|
1000
|
10
|
8
|
9
|
1001
|
11
|
9
|
10
|
1010
|
12
|
A
|
11
|
1011
|
13
|
B
|
12
|
1100
|
14
|
C
|
13
|
1101
|
15
|
D
|
14
|
1110
|
16
|
E
|
15
|
1111
|
17
|
F
|
16
|
10000
|
20
|
10
|
17
|
10001
|
21
|
11
|
18
|
10010
|
22
|
12
|
19
|
10011
|
23
|
13
|
20
|
10100
|
24
|
14
|
5.1.1 REPRESENTACIONES Y CONVERCIONES ENTRE BASE
SISTEMAS NUMÉRICOS: Conversiones y Operaciones
Es la manera de representar la información y estos se clasifican en:Sistema binario, se representa con: 0,1 y su base es: 2Sistema octal, se representa con: 0,1,2,3,4,5,6,7 y su base es: 8Sistema decimal, se representa con: 0,1,2,3,4,5,6,7,8,9 y su base es: 10Sistema hexadecimal, se representa con: 0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F y su base es:16.
SISTEMA BINARIO
Binario, significa dos, y es el principio fundamental en que se basan las computadorasdigitales. Todo lo que se ingresa a la computadora se convierte en números binariosconformados por los dos dígitos 0 y 1 (bits). Por ejemplo, cuando presiona la tecla "A"en su computadora personal, el teclado genera y transmite el número 01000001 a lamemoria de la computadora como una serie de pulsos. Los bits 1 se transmiten comovoltaje alto, mientras que los bits 0, como voltaje bajo.
SISTEMA OCTAL
Un sistema de numeración que emplea ocho dígitos. Es utilizado como una formaabreviada de representar números binarios que emplean caracteres de seis bits. Cada tres bits (medio carácter) es convertido en un único dígito octal. Okta es un término griegoque significa 8.
SISTEMA DECIMAL
Decimal, significa 10. Sistema de numeración universal que usa 10 dígitos. Lascomputadoras utilizan números binarios, ya que resulta más fácil diseñar sistemaselectrónicos que puedan mantener dos estados en vez de 10.
SISTEMA HEXADECIMAL
Hexa, significa dieciséis; un sistema numérico de base 16 usado como una formaabreviada de representar todos los valores posibles de un byte. A cada medio byte(cuatro bits) se le asigna un dígito hexa. El hexadecimal se utiliza para representar bytes por su uniformidad en la impresión y en la presentación por pantalla. Dos dígitoshexadecimales siempre constituyen un byte, mientras que el valor decimal de un byte puede ser un número desde uno hasta tres dígitos de longitud (0 a 255).
CONVERSIÓN DEL BINARIO AL DECIMAL
Para realizar la conversión de Binario a Decimal, realice lo siguiente:1) Inicie por el lado derecho del numero Binario, cada numeromultiplíquelo por (2) y elevarlo a la potencia consecutiva (iniciando por la potencia 0).2) Después de realizar cada una de las multiplicaciones, sume todas y élnumero resultante será el equivalente al Sistema Decimal
5.1.2 OPERACIONES BASICAS
Una operación es un conjunto de reglas que permiten obtener otras cantidades o expresiones.
Las siete operaciones básicas de la Aritmética son:
Suma
La operación suma consiste en obtener el número total de elementos a partir dos o más cantidades.
a + b = c
Los términos de la suma, a y b, se llaman sumandos y el resultado, c, suma.
Propiedades de la suma
1. Asociativa:
El modo de agrupar los sumandos no varía el resultado.
(a + b) + c = a + (b + c)
2. Conmutativa:
El orden de los sumandos no varía la suma.
a + b = b + a
3. Elemento neutro:
El 0 es el elemento neutro de la suma porque todo número sumado con él da el mismo número.
a + 0 = a
4.Elemento opuesto
Dos números son opuestos si al sumarlos obtenemos como resultado el cero.
a − a = 0
El opuesto del opuesto de un número es igual al mismo número.
La suma de números naturales no cumple esta propiedad.
Resta
La resta o sustracción es la operación inversa a la suma.
a - b = c
Los términos que intervienen en una resta se llaman: a, minuendo y b, sustraendo. Al resultado, c, lo llamamosdiferencia.
Propiedades de la resta
No es Conmutativa:
a − b ≠ b − a
Multiplicación
Multiplicar dos números consiste en sumar uno de los factores consigo mismo tantas veces como indica el otro factor.
a · b = c
Los términos a y b se llaman factores y el resultado, c, producto.
Propiedades de la multiplicación
1. Asociativa:
El modo de agrupar los factores no varía el resultado
(a · b) · c = a · (b · c)
2. Conmutativa:
El orden de los factores no varía el producto.
a · b = b · a
3. Elemento neutro:
El 1 es el elemento neutro de la multiplicación porque todo número multiplicado por él da el mismo número.
a · 1 = a
4. Elemento inverso:
Un número es inverso del otro si al multiplicarlos obtenemos como resultado el elemento unidad.
La suma de números naturales y de enteros no cumple esta propiedad.
5. Distributiva:
El producto de un número por una suma es igual a la suma de los productos de dicho número por cada uno de los sumandos.
a · (b + c) = a · b + a · c
6. Sacar factor común:
Es el proceso inverso a la propiedad distributiva.
Si varios sumandos tienen un factor común, podemos transformar la suma en producto extrayendo dicho factor.
a · b + a · c = a · (b + c)
División
La división o cociente es una operación aritmética que consiste en averiguar cuántas veces un número está contenido en otro número.
D : d = c
Los términos que intervienen en un cociente se llaman, D, dividendo y ddivisor. Al resultado, c, lo llamamoscociente.
Tipos de divisiones
1. División exacta:
Cuando el resto es cero.
D = d · c
2. División entera:
Cuando el resto es distinto de cero.
D = d · c + r
Propiedades de la división
1. No es Conmutativo:
a : b ≠ b : a
2. Cero dividido entre cualquier número da cero.
0 : a = 0
3. No se puede dividir por 0.
Potenciación
La potenciación es una multiplicación de varios factores iguales.
a · a · a · ... = an
Base
Es el número que multiplicamos por sí mismo.
Exponente
Indica el número de veces que multiplicamos la base.
Propiedades de la potencias
1. a0 = 1
2. a1 = a
3. Producto de potencias con la misma base:
Es otra potencia con la misma base y cuyo exponente es la suma de los exponentes.
am · a n = am+n
4. División de potencias con la misma base:
Es otra potencia con la misma base y cuyo exponente es la diferencia de los exponentes.
am: a n = am - n
25 : 22 = 25 - 2 = 23
5. Potencia de una potencia:
Es otra potencia con la misma base y cuyo exponente es el producto de los exponentes.
(am)n = am · n
6. Producto de potencias con el mismo exponente:
Es otra potencia con el mismo exponente y cuya base es el producto de las bases.
an· b n = (a · b) n
7. Cociente de potencias con el mismo exponente:
Es otra potencia con el mismo exponente y cuya base es el cociente de las bases.
an: bn= (a : b)n
Radicación
Es la operación inversa a la potenciación. Y consiste en que dados dos números, llamados radicando e índice, hallar un tercero, llamado raíz, tal que, elevado al índice, sea igual al radicando.
indice √ radicando =raiz
En la raíz cuadrada el índice es 2, aunque en este caso no se pondría. Consistiría en hallar un número conocido su cuadrado.
√ radicando = raiz
La raíz cuadrada de un número, a, es exacta cuando encontramos un número, b, que elevado al cuadrado es igual al radicando: b2 = a.
Cuadrados perfectos
Son los números que poseen raíces cuadradas exactas.
Raíz cuadrada exacta
Radicando = (Raíz exacta)2
Raíz cuadrada entera
Radicando = (Raíz entera)2 + Resto
El logaritmo de un número, en una base dada, es el exponente al cual se debe elevar la base para obtener el número.
loga x= y => av= x a< 0 y a ‡1
Propiedades de los logaritmos
No existe el logaritmo de un número con base negativa.
z log-ax
No existe el logaritmo de un número negativo.
z loga (-x)
No existe el logaritmo de cero.
z loga 0
El logaritmo de 1 es cero.
loga 1=0
El logaritmo en base a de a es uno.
loga a=0
El logaritmo en base a de una potencia en base a es igual al exponente.
loga an =n
Logaritmo de un producto
El logaritmo de un producto es igual a la suma de los logaritmos de los factores.
loga (x.y) =loga x + logay
Logaritmo de un cociente
El logaritmo de un cociente es igual al logaritmo del dividendo menos el logaritmo del divisor.
loga (x) =loga x - logay y
Logaritmo de una potencia
El logaritmo de una potencia es igual al producto del exponente por el logaritmo de la base.
loga (xn)= n loga x
Logaritmo de una raíz
El logaritmo de una raíz es igual al cociente entre el logaritmo del radicando y el índice de la raíz.
loga (n√x) 1/n loga x
5.1.3 ALGORITMOS DE BOOTH
El algoritmo de Booth es un método rápido y sencillo para obtener el producto de dos números binarios con signo en notación complemento a dos.
Para obtener el complemento a uno del numero en binario solo consta en cambiar sus ceros por unos, y sus unos por ceros (complementar): (010010 -> ca1:101101)
Complemento a2
El complemento a dos de un número binario es el resultado de sumar 1 al complemento a uno de dicho número binario (NOTA: En el Ca1 sólo se complementa si el número es negativo): mi numero en decimal es 86
Realizar una multiplicación con el algoritmo de Booth, resulta mucho más sencillo de implementar. Partimos del ejemplo de la multiplicación 6·2=12:
1º Obtengo mis números (multiplicando y multiplicador) en binario con longitud de 8 bits
2º asigno A= multiplicando, S= Complemento a2 de A, P= 8 bits en 0. Agrego 7 bits extras a la derecha de A y S, en P agrego el valor de multiplicador con longitud de 8 bits y un bit extra con valor 0. Como se indica a continuación:
Como se puede ver en la imagen superior, partiendo de los números binarios de la multiplicación 6·2 (multiplicando y multiplicador) creamos tres nuevos números binarios del doble de tamaño (16 en el ejemplo): A, S y P.
3o Partiendo del número P (producto) comenzamos a comparar los últimos 2 bits de la derecha, siguiendo los casos base del recuadro:
0 0 No hacer nada
0 1 P = P + A
1 0 P = P + S
1 1 No hacer nada
Se realizará esta comparación 8 veces en este ejemplo (número de bits de los operandos) y al final de cada comparación, realizamos un desplazamiento de un bit hacia la derecha, manteniendo el último bit de la izquierda, y descartando el último bit del lado contrario. Si hacemos una traza paso a paso nos quedarían los siguientes resultados:
Finalmente obtenemos el número en binario resultante (12 en este ejemplo), descartando el bit extra que hemos añadido al principio del procedimiento y que se encuentra en el extremo a la derecha.
El algoritmo de booth es un algoritmo que sirve para multiplicar (y dividir) números binarios con signo de manera rápida y sencilla en complemento a dos. Aqui explico de manera detallada el funcionamiento de ese algoritmo y muestro una implementacion del mismo para microcontroladores PIC.
La manera en que se representan los números binarios negativos es mediante su complemento a dos. El complemento a uno consiste en invertir el valor de cada bit, esto es que si se tiene el número 5 binario b’00000101′ su complemento a uno seríab’11111010′. Una vez teniendo el complemento a 1 para obtener el complemento a dos simplemente se le debe sumar un 1, asi que se tiene b’11111010 + 1′ de modo que el complemento a dos del número 5 binario es b’11111011′.
Ese es un dato muy importante ya que de ese modo se representan los números binarios negativos y el complemento a dos es parte del algoritmo de multiplicación de Booth. También es importante explicar que utilizando números de 8 bits el número mayor que se puede representar en complemento a dos es 127 y -127 que en binario son b’01111111′ y b’1000001′ respectivamente.
Dados enteros a, b con b0 existen enteros q y r tales que
a = b q + r y 0
r 
|b|
0 existen enteros q y r tales quea = b q + r y 0
r |b|
Al número a se le llama dividendo.
Al número b se le llama divisor.
Al número q se le llama cociente.
Al número r se le llama residuo.
Al número b se le llama divisor.
Al número q se le llama cociente.
Al número r se le llama residuo.
En el caso particular que a y b sean enteros positivos, se trata de hallar el número de veces que el dividendo contiene al divisor. Este número se llama cociente, y lo que queda se llama residuo.
5.2 ALGEBRA BOOLEANA
Álgebra Booleana
El álgebra booleana es un sistema matemático deductivo centrado en los valores cero y uno (falso y verdadero). Un operador binario " º " 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.
Para cualquier sistema algebraico existen una serie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el álgebra booleana a menudo emplea los siguientes postulados:
Para cualquier sistema algebraico existen una serie de postulados iniciales, de aquí se pueden deducir reglas adicionales, teoremas y otras propiedades del sistema, el álgebra booleana a menudo emplea los siguientes postulados:
- Cerrado. El sistema booleano se considera cerrado con respecto a un operador binario si para cada par de valores booleanos se produce un solo resultado booleano.
- Conmutativo. Se dice que un operador binario " º " es conmutativo si A º B = B º A para todos los posibles valores de A y B.
- Asociativo. Se dice que un operador binario " º " es asociativo si (A º B) º C = A º (B º C) para todos los valores booleanos A, B, y C.
- Distributivo. Dos operadores binarios " º " y " % " son distributivos si A º (B % C) = (A º B) % (A º C) para todos los valores booleanos A, B, y C.
- Identidad. Un valor booleano I se dice que es un elemento de identidad con respecto a un operador binario " º " si A º I = A.
- Inverso. Un valor booleano I es un elemento inverso con respecto a un operador booleano " º " si A º I = B, y B es diferente de A, es decir, B es el valor opuesto de A.
Para nuestros propósitos basaremos el álgebra booleana en el siguiente juego de operadores y valores:
- Los dos posibles valores en el sistema booleano son cero y uno, a menudo llamaremos a éstos valores respectivamente como falso y verdadero.
- El símbolo · representa la operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminará el símbolo ·, por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el producto entre A y B.
- El símbolo "+" representa la operación lógica OR, decimos que A+B es la operación lógica OR entre A y B, también llamada la suma de A y B.
- El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el símbolo " ' " para denotar la negación lógica, por ejemplo, A' denota la operación lógica NOT de A.
- Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia están adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es asociativo por la derecha.
Utilizaremos además los siguientes postulados:
- Los dos posibles valores en el sistema booleano son cero y uno, a menudo llamaremos a éstos valores respectivamente como falso y verdadero.
- El símbolo · representa la operación lógica AND. Cuando se utilicen nombres de variables de una sola letra se eliminará el símbolo ·, por lo tanto AB representa la operación lógica AND entre las variables A y B, a esto también le llamamos el producto entre A y B.
- El símbolo "+" representa la operación lógica OR, decimos que A+B es la operación lógica OR entre A y B, también llamada la suma de A y B.
- El complemento lógico, negación ó NOT es un operador unitario, en éste texto utilizaremos el símbolo " ' " para denotar la negación lógica, por ejemplo, A' denota la operación lógica NOT de A.
- Si varios operadores diferentes aparecen en una sola expresión booleana, el resultado de la expresión depende de la procedencia de los operadores, la cual es de mayor a menor, paréntesis, operador lógico NOT, operador lógico AND y operador lógico OR. Tanto el operador lógico AND como el OR son asociativos por la izquierda. Si dos operadores con la misma procedencia están adyacentes, entonces se evalúan de izquierda a derecha. El operador lógico NOT es asociativo por la derecha.
Utilizaremos además los siguientes postulados:
- P1 El álgebra booleana es cerrada bajo las operaciones AND, OR y NOT
- P2 El elemento de identidad con respecto a · es uno y con respecto a + es cero. No existe elemento de identidad para el operador NOT
- P3 Los operadores · y + son conmutativos.
- P4 · y + son distributivos uno con respecto al otro, esto es, A· (B+C) = (A·B)+(A·C) y A+ (B·C) = (A+B) ·(A+C).
- P5 Para cada valor A existe un valor A' tal que A·A' = 0 y A+A' = 1. Éste valor es el complemento lógico de A.
- P6 · y + son ambos asociativos, ésto es, (AB) C = A (BC) y (A+B)+C = A+ (B+C).
Es posible probar todos los teoremas del álgebra booleana utilizando éstos postulados, además es buena idea familiarizarse con algunos de los teoremas más importantes de los cuales podemos mencionar los siguientes:
- Teorema 1: A + A = A
- Teorema 2: A · A = A
- Teorema 3: A + 0 = A
- Teorema 4: A · 1 = A
- Teorema 5: A · 0 = 0
- Teorema 6: A + 1 = 1
- Teorema 7: (A + B)' = A' · B'
- Teorema 8: (A · B)' = A' + B'
- Teorema 9: A + A · B = A
- Teorema 10: A · (A + B) = A
- Teorema 11: A + A'B = A + B
- Teorema 12: A' · (A + B') = A'B'
- Teorema 13: AB + AB' = A
- Teorema 14: (A' + B') · (A' + B) = A'
- Teorema 15: A + A' = 1
- Teorema 16: A · A' = 0
Los teoremas siete y ocho son conocidos como Teoremas de DeMorgan en honor al matemático que los descubrió.
Características:
Un álgebra de Boole es un conjunto en el que destacan las siguientes características:
1- Se han definido dos funciones binarias (que necesitan dos parámetros) que llamaremos aditiva (que representaremos por x
+ y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo parámetro) que representaremos por x'.
2- Se han definido dos elementos (que designaremos por 0 y 1)
Y 3- Tiene las siguientes propiedades:
Un álgebra de Boole es un conjunto en el que destacan las siguientes características:
1- Se han definido dos funciones binarias (que necesitan dos parámetros) que llamaremos aditiva (que representaremos por x
+ y) y multiplicativa (que representaremos por xy) y una función monaria (de un solo parámetro) que representaremos por x'.
2- Se han definido dos elementos (que designaremos por 0 y 1)
Y 3- Tiene las siguientes propiedades:
- Conmutativa respecto a la primera función: x + y = y + x
Conmutativa respecto a la segunda función: xy = yx
Asociativa respecto a la primera función: (x + y) + z = x + (y +z)
Asociativa respecto a la segunda función: (xy)z = x(yz)
Distributiva respecto a la primera función: (x +y)z = xz + yz
Distributiva respecto a la segunda función: (xy) + z = (x + z)( y + z)
Identidad respecto a la primera función: x + 0 = x
Identidad respecto a la segunda función: x1 = x
Complemento respecto a la primera función: x + x' = 1
Complemento respecto a la segunda función: xx' = 0
Propiedades Del Álgebra De Boole
- Idempotente respecto a la primera función: x + x = x
Idempotente respecto a la segunda función: xx = x
Maximalidad del 1: x + 1 = 1
Minimalidad del 0: x0 = 0
Involución: x'' = x
Inmersión respecto a la primera función: x + (xy) = x
Inmersión respecto a la segunda función: x(x + y) = xLey de Morgan respecto a la primera función: (x + y)' = x'y'
Ley de Morgan respecto a la segunda función: (xy)' = x' + y'
Función Booleana
Una función booleana es una de A x A x A x....A en A, siendo A un conjunto cuyos elementos son 0 y 1 y tiene estructura de álgebra de Boole.
Supongamos que cuatro amigos deciden ir al cine si lo quiere la mayoría. Cada uno puede votar si o no. Representemos el voto de cada uno por xi. La función devolverá sí (1) cuando el numero de votos afirmativos sea 3 y en caso contrario devolverá 0.
Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0.
Producto mínimo (es el número posible de casos) es un producto en el que aparecen todas las variables o sus negaciones.
Una función booleana es una de A x A x A x....A en A, siendo A un conjunto cuyos elementos son 0 y 1 y tiene estructura de álgebra de Boole.
Supongamos que cuatro amigos deciden ir al cine si lo quiere la mayoría. Cada uno puede votar si o no. Representemos el voto de cada uno por xi. La función devolverá sí (1) cuando el numero de votos afirmativos sea 3 y en caso contrario devolverá 0.
Si x1 vota 1, x2 vota 0, x3 vota 0 y x4 vota 1 la función booleana devolverá 0.
Producto mínimo (es el número posible de casos) es un producto en el que aparecen todas las variables o sus negaciones.
El número posible de casos es 2n.
Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los posibles casos son:
Votos Resultado
ABCD
1111 1
1110 1
1101 1
1100 0
1011 1
1010 0
1001 0
1000 0
0111 1
0110 0
0101 0
0100 0
0011 0
0010 0
0001 0
0000 0
Siguiendo con el ejemplo anterior. Asignamos las letras A, B, C y D a los amigos. Los posibles casos son:
Votos Resultado
ABCD
1111 1
1110 1
1101 1
1100 0
1011 1
1010 0
1001 0
1000 0
0111 1
0110 0
0101 0
0100 0
0011 0
0010 0
0001 0
0000 0
Las funciones booleanas se pueden representar como la suma de productos mínimos (minterms) iguales a 1.
5.2.1 TEORAMA Y POSTULADOS
TEOREMAS Y POSTULADOS DEL ALGEBRA DE BOOLE
1. Propiedad de cierre.
Para un conjunto s se dice que es cerrado para un operador binario si para cada elemento de S el operador binario especifica una regla para obtener un elemento único de S.
Para el conjunto N = {1,2,3,4,…} es cerrado con respecto al operador binario (+) por las reglas de la adición aritmética, ya que para que cualquier elemento a,b pertenecientes a N por la operación a + b = c el conjunto de los números naturales no esta cerrado con respecto al operador binario (-) por la regla de la resta aritmética, debido a que 2-3 = -1 y 2,3 pertenecen a N pero -1 no pertenece a N.
2. Ley asociativa.
El operador binario (*) es un conjunto S es asociativo siempre que x*y*z = x*(y*z) para toda x, y pertenecientes a S.
3. Ley conmutativa.
Un operador binario (*) para un conjunto S es conmutativo siempre que: x*y = y*x para toda x,y pertenecientes a S.
4. Elemento identidad.
El conjunto S tendrá un elemento identidad multiplicativo “identidad (*)” en S si existe un e perteneciente a S con la propiedad e*x = x*e =e para cada x pertenecientes a S.
5. Inversa.
El conjunto S tiene un elemento identidad (e) con respecto al operador (*) siempre que para cada x perteneciente a S exista un elemento y perteneciente a S tal que x*y=e.
6. Ley distributiva.
Si el operador (*) y el operador (.), son operadores binarios de S, (*) se dice que es distributivo sobre (.).
Siempre que:
x*(y . z) = (x*y) . (x*z)
- El operador binario (+) define la adición. - Identidad aditiva es el cero. - La inversa aditiva define la sustracción. - El operador binario (.) define la multiplicación. - Identidad multiplicativa es 1. - Inversa multiplicativa de A es igual a 1/A define la división esto es A * 1/A = 1 - La única ley distributiva aplicable es la de operador (.) sobre el operador + (.) sobre (+) a(b+c)=(a.b) +(a.c)
Para definir formalmente el álgebra de Boole se emplean postulados de Huntington.
1. a) Cierre con respecto al operador (+) b) Cierre con respecto al operador (.)
2. a) Un elemento identidad con respecto al operador (+), designado por el cero x+0 =0+x=x b) Un elemento identidad con respecto al operador (.) designado por el uno x*1=1*x=x
3. a) Conmutativo con respecto al operador (+) : x+y = y+x b) Conmutativo con respecto al operador (.) : x*y =y*x
4. a) El operador (.) es distributivo sobre el operador (+) : x.(y+z) = (x.y) + (y.z) b) El operador (+) es distributivo sobre el operador (.) : x+(x.z) = (x+y) . (x+z)
5. Para cada elemento de x pertenencia a B existe un elemento x’ complemento perteneciente a B denominado complemento de x tal que:
a) x+x’ = 1 b) x’ = 0
6. Existen cuando menos dos elementos x,y pertenecientes a B tal que x diferente de y. Por lo tanto tenemos que el álgebra de Boole difiere de la aritmética y del álgebra ordinaria en la sig:
a) Los postulados Huntington: no incluyen al ley asociativa, no obstante esta ley es valida para el álgebra booleana (para ambos operadores)
b) La ley distributiva del operador (+) sobre el operador (.) esto es: x+(y.z) = (x+y).(x+z), la cual es valida para el álgebra de boole pero no para el álgebra ordinaria.
c) El álgebra booleana no tiene inversa aditiva a multiplicativa, por lo tanto no hay operaciones de sustracciones o división.
d) El postulado 5 define un operador llamado completo que no se encuentra en el álgebra ordinaria.
e) En el algebra de Boole se define un conjunto B de dos elementos (0 y 1) y el álgebra ordinaria trata con el conjunto de los números reales.
Postulado 2 a) x + 0 = x b) x . 1 = x Postulado 5 a) x + x’ = 1 b) x . x’ = 0 Teorema 1 a) x + x = x b) x . x = x Teorema 2 a) x + 1 = 1 b) x . 0 = 0 Teorema 3 involución (x’)’ = x Teorema 3 conmutativo a) x + y = y + x b) xy = yx Teorema 4 asociativo a) x + (y + z) = (x + y) +z b) x (yz) = (xy) z Postulado 4 distributivo a) x (y + z) = xy +xz b) x + yz = (x + y)(x+z) Teorema 5 morgan a) ( x + y)’ = x’ y’ b) (xy) = x’ + y’ Teorema 6 absorción a) x + xy = x b) x (x + y) = x
Ejemplos:x + x = x x + xy = x x + x = (x + x) . 1 x . 1 + xy = x x + x = (x + x) (x + x’) x (1 + y) = x x + x = x + xx’ x (y + 1) = x x + x = x + 0 x (1) = x x + x = x x = xLas variables booleanas pueden tomar varios valores de 1 ó 0. Una función booleana es una expresión formada por variables binarias.
Ejemplo:
F1 = xyz’
Para F1 considerar que es igual a 1 si:
x = 1; y = 1 ; z’ = 1; de otra manera F1 = 0.
Por lo tanto tendremos que una función booleana también puede representarse en una tabla de verdad. Para representar una función booleana en una tabla de verdad se necesita una lsit de 2ncombinaciones de 1 y 0 de las n variables binarias, y una columna que muestra combinaciones para las cuales f es igual a 1 ó 0.
x y z F1 F2 F3 F4 0 0 0 0 0 1 0 0 0 1 0 1 0 0 0 1 0 1 0 0 0 0 1 1 1 1 1 1 1 0 0 1 0 0 1 1 0 1 0 0 1 1 1 1 0 1 1 1 1 1 1 1 0 1 0 1
F1 = x’yz’ + x’yz + xy’z + xyz’ = x’y (z+z’) + xz’ (y+y’) = x’y + xz’
F2 = x’y’z + x’yz + xyz’ + xyz = x’z (y+y’) + xy (z+z’) = x’z + xy F3 = x’y’z’ + x’yz + xy’z + xyz’
F4 = x’y’z + xy’z’ + xy’z + xyz’ + xyz = xy’ (z+z’) + xy (z+z’) + x’yz = xy’ + xy + x’yz = x (y+y’) + x’yz = x + x’yz
FUNCIONES LOGICAS
Manipulación algebraica
Cuando una función se incrementa con compuertas lógicas, cada literal en la función denota una entrada a una compuerta.
1. Cada literal denota la entrada a una compuerta. 2. Cada termino se implanta con una compuerta.
Por el momento nos limitaremos a la minimización por literales. Por lo cual debe quedar muy claro que en la manipulación algebraica no hay reglas especificas a seguir a que garanticen la respuesta final.
Ejemplo: Reducir las siguientes funciones booleanas.
1. x (x’+y) = xx’ + xy = xy 2. x’y’z + x’yz + xy = x’z (y+y’) + xy = x’z + xy 3. x + x’y = (x+x’)(x+y) = x+y
Complemento de una función.
El complemento de una función F es F’ obteniendose por el intercambio de 1’s y 0’s y de 0’s y 1’s. Ejemplo:
(A+B+C)’ = (A+X)’ para X = B+C A’ . X’ ? A’ . (B+C)’ ? A’ . B’ .C’ (A+B+C+D+E+F+……..I) (A’.B’.C’.D’.E’.F’…….I’)
La forma generalizada de D’Morgan enuncia que el complemento de una función se obtiene del intercambio de los operadores AND y OR y complementando cada literal.
F1 = (x’yz’ + x’y’z)’ = (x+y’+z . x+y+z’) F2 = ? x (y’z’+yz)? = x’ + ? x (y+z).(y’+z’)?
Otra forma más simple para derivar el complemento de una función es tomar el dual de la función y complementar cada literal.
Hay que recordar que el cual de una función se obtiene por el intercambio de los operadores AND y OR y los 1’s y los 0’s. Ejemplo:
F1 = x’yz’ + x’y’z el dual: F1 = (x+y’+z) . (x+y+z’)
Las variables pueden ser normales (x) ó complemento (x’). Cuando tenemos un conjunto de n variables nosotros podemos formar 2n miniterminos de acuerdo a la siguiente tabla:
Para n=3 2n-1 combinaciones iniciando a partir de cero.
Cada minitérmino lo obtenemos de un término AND de las n variables y complementado cada variable si el número binario que representa es un 0 y no complementando si es un 1.
En estas se hace la consideración de que cada variable no complementada corresponde al bit 0 y complementada al bit 1.
F1= x’y’z + xy’z’ + xyz = m1+m4+m7 F2= x’yz + xy’z + xyz’ + xyz = m3+m5+m6+m7 F1’= x’y’z’ + x’yz’ + x’yz + xy’z + xyz’ (F1’)’ = (x+y+z) . (x+y’+z) . (x+y’+z’) . (x’+y+z’) . (x’+y’+z) = M0 . M2 . M3 . M5 . M6
El complemento de una función booleana lo podemos obtener al formar miniterminos para cada combinación que produce un cero en la función y aplicando el operador OR a esos términos.
Las funciones booleanas expresadas como una suma de miniterminos o productos de maxiterminos se dice que esta en forma canónica.
SIMPLIFICACION DE FUNCIONES
Como sabemos cualquier función booleana puede expresarse como una suma de miniterminos. La suma de estos elementos que son los que definen una función booleana son aquellos que dan los 1’s de la función en una tabla de verdad.
Algunas veces es conveniente expresar la función booleana en la forma de suma de miniterminos. Si no puede hacerse en esta forma entonces puede realizarse primero por la expansión de la expresión en una suma de los términos AND.
Después cada término se inspecciona para ver si contiene todas las variables, si se han perdido una o más variables, se aplica el operador AND con una expresión x+x’ en donde x es una de las variables perdidas.
Ejemplo: Expresar la función F = A+B’C en una suma de miniterminos.
F= A+B’C F(A,B,C) A= A(B+B’) = AB+AB’ = AB(C+C’) + AB’(C+C’) = ABC + ABC’ + AB’C +AB’C’
B’C = B’C (A+A’) = AB’C + A’B’C
F = ABC+ABC’+AB’C+AB’C’+AB’C+A’B’C F = A’B’C+AB’C’ +AB’C+ABC’+ABC F = m1+ m4+m5+ m6+ m7 F(A,B,C)=SUM(1,4,5,6,7)
La sumatoria representa al operador OR que opera en los términos y números siguientes son los minitérminos de la función.
Las letras entre paréntesis que siguen a F forman una lista de las variables en el orden tomado cuando el minitérmino se convierte en un término AND.
Producto de los maxitérminos.
Para expresar una función booleana como un producto de maxitérminos, primero debe llevarse a una forma de términos OR. Esto es posible al uso de la ley distributiva; esto es si x+yz = (x+y) (x+z); para cualquier variable perdida x en cada término se opera a OR con xx’.
Ejemplo:
F = (x’+y) (x+z) (y+z) (x’+y) = x’+y+zz’ = (x’+y+z) (x’+y+z) (x+z) = x+z+yy’ = (x+y+z) (x+y’+z) (y+z) = y+z+xx’ = (x+y+z) (x’+y+z) F = (x’+y+z) (x’+y+z’) (x+y+z) (x+y’+z) (x+y+z) (x’+y+z) F = (x’+y+z) (x’+y+z’) (x+y+z) (x+y’+z) F = (x+y+z) (x+y’+z) (x’+y+z) (x’+y+z’) M0 M2 M4 M5 F(x,y,z) = PI(0,2,4,5)
El operador PI denota la operación AND de maxitérminos; y los números son los maxitérminos de la función.
Conversión entre formas canónicas. El complemento de una función expresada como suma de minitérminos es igual a la suma de los minitérminos perdidos de la función original.
Ejemplo:
F(A,B,C) = SUM(1,4,5,6,7) F’(A,B,C) = SUM(0,2,3) = m0+m2+m3
Si obtenemos el complemento de F’ porque el teorema de D’Morgan se obtiene F en una forma diferente.
(F’)’ = (m0+m2+m3)’ = m0’.m2’.m3’ = M0 . M2 . M3 = PI(0,2,3) = (x+y+z) . (x+y’+z) . (x+y’+z’)
F = A’D+BD+B’D A’D = A’D(B+B’) = A’BD+A’B’D = A’BD(C+C’) = A’BCD+A’BC’D = A’B’D(C+C’) = A’B’CD+A’B’C’D BD = BD(A+A’) = ABD+A’BD = ABD(C+C’) = ABCD+ABC’D = A’BD(C+C’) = A’BCD+A’BC’D
B’D = B’D(A+A’) = AB’D+A’B’D = AB’D(C+C’) = AB’CD+AB’C’D = A’B’D(C+C’) = A’B’CD+A’B’C’D F = A’BCD+A’BC’D+A’B’CD+A’B’C’D+ABCD+ABC’D+AB’CD+AB’C’D
Minitérminos
Para una función booleana de n variables x1,...xn, un producto booleano en el que cada una de las n variables aparece una sola vez (negada o sin negar) es llamado minterms. Es decir, un minterms es una expresión lógica de nvariables consistente únicamente en el operador conjunción lógica (AND) y el operador complemento o negación (NOT).
Por ejemplo, abc, ab'c y abc' son ejemplos de minterms para una función booleana con las tres variables a, b y c.
En general, uno asigna a cada minterm (escribiendo las variables que lo componen en el mismo orden), un índice basado en el valor binario del minterm. un término negado, como a' es considerado como el numero binario 0 y el término no negado a es considerado como un 1. Por ejemplo, se asociaría el número 6 con a b c'(1102), y nombraríamos la expresión con el nombre m6. Entonces m0 de tres variables es a'b'c'(0002) y m7 debería ser a bc(1112).
Función equivalente
Se puede observar que cada minterm solo devuelve 'verdadero' con una sola entrada de las posibles. Por ejemplo, el minterm 5, a b' c, es verdadero solo cuando a y c son ciertos y b es falso - la entrada a = 1, b = 0, c = 1 da resultado 1.
Si tenemos una tabla de verdad de una función lógica, es posible escribir la función como "suma de productos". Por ejemplo, dada la tabla de verdad
a b f(a, b)
0 0 1
0 1 0
1 0 1
1 1 0
Observamos que las filas con resultado 1 son la primera y la tercera, entonces podremos escribir f como la suma de los minterms m0 y m2.
Si queremos verificar esto:
f(a,b) = m0 + m2 = (a'b')+(ab')
Tendremos que la tabla de verdad de la función, calculándola directamente, será la misma.
Maxitérminos
Un maxterm es una expresión lógica de n variables que consiste únicamente en la disyunción lógica y el operador complemento o negación. Los maxterms són una expresión dual de los minterms. En vez de usar operaciones AND utilizamos operaciones OR y procedemos de forma similar.
Por ejemplo, los siguientes son maxterms:
a+b'+c
a'+b+c
El complemento de un minterm es su respectivo maxterm. Esto puede ser fácilmente verificado usando la Ley de Morgan. Por ejemplo:
m1' = M1
(a'b)' = a+b'
Para indexar maxterms lo haremos justo de la forma contraria a la que seguimos con los minterms. Se asigna a cada maxterm un índice basado en el complemento del número binario que representa (otra vez asegurándonos que las variables se escriben en el mismo orden, usualmente alfabético). Por ejemplo, podemos asignar M6(Maxterm 6) al maxterm a'+b'+c. De forma similar M0 de tres variables debería ser a+b+c y M7 es a'+b'+c'.
Función equivalente
Se puede ver fácilmente que un maxterm sólo da como resultado un cero para una única entrada de la función lógica. Por ejemplo, el maxterm 5, a'+b+c', es falso solo cuando a y c son ciertos y b es falso - la entrada a = 1, b = 0, c = 1 da como resultado un cero.
Si tenemos una tabla de verdad de una función lógica, es posible escribir la función como "producto de sumas". Por ejemplo, dada la tabla de verdad
a b f(a, b)
0 0 1
0 1 0
1 0 1
1 1 0
Observamos que las filas que tiene como salida un 0 son la segunda y la cuarta, entonces podemos escribir f como un producto de maxterms M1 y M3.
Si queremos verificar esto:
f(a,b) = M1 M3 = (a+b')(a'+b')
Tendremos que la tabla de verdad de la función, calculándola directamente, será la misma
5.2.3 MAPAS DE KARNAUGH
El mapa de Karnaugh es un método gráfico que se utiliza para simplificar una ecuación lógica para convertir una tabla de verdad a su circuito lógico correspondiente en un proceso simple y ordenado. Aunque un mapa de Karnaugh (que de aquí en adelante se abreviará como mapa K) se puede utilizar para resolver problemas con cualquier numero de variables de entrada, su utilidad practica se limita a seis variables. El siguiente análisis se limitara a problemas de hasta cuatro entradas , ya que los problemas con cinco y seis entradas son demasiado complicados y se resuelven mejor con un programa de computadora.
Formato del mapa de Kamaugh El mapa K, al igual que una tabla de verdad, es un medio para demostrar la relaci6n entre las entradas l6gicas y la salida que se busca. La figura +-11 da tres ejemplos de mapas K para dos, tres y cuatro variables, junto con las tablas de verdad correspondientes. Estos ejemplos ilustran varios puntos importantes:
1. La tabla de verdad da el valor de la salida X para cada combinaci6n de valores de entrada. El mapa K proporciona la misma informaci6n en un formato diferente. Cada caso en la tabla de verdad corresponde a un cuadrado en el mapa. Por ejemplo, en la figura 4-11 (a),
Figura 4-11 Mapas de Karnaugh y tablas de verdad para (a) dos, (b) tres y (c) cuatro variables.
la condicion A = 0, B = 0 en la tabla de verdad corresponde al cuadrado A' B' en el mapa K. Ya que la tabla de verdad muestra X = 1 para este caso, se coloca un 1 en el cuadrado A'B' en el mapa K. En forma similar, la condicion A = 1, B = 1 en la tabla de verdad corresponde al cuadrado AB del mapa K, ya que X = 1 para este caso, se coloca un 1 en el cuadrado AS. Los demás cuadrados se llenan con ceros. Esta misma idea se utiliza en los mapas de tres y cuatro variables que se muestran en la figura.
2. Los cuadrados del mapa K se marcan de modo que los cuadrados horizontalmente adyacentes so1o difieran en una variable. Por ejemplo, el cuadrado superior de la izquierda del mapa de cuatro variables es A'B'C'D' en tanto que el cuadrado que se encuentra a la derecha es A'B'C'D (solo la variable D es diferente). De la misma manera, los cuadrados verticalmente adyacentes difieren so1o en una variable. Por ejemplo, el cuadrado superior izquierdo es A'B'C'D' en tanto que el que se encuentra a la derecha es A'BC'D' (solo la variable B es diferente).
Note que cada cuadrado del renglon superior se considera adyacente al correspondiente cuadrado del renglon inferior .Por ejemplo, el cuadrado A'B'CD del renglon superior es adyacente al cuadrado AB'CD del rengl6n inferior porque so1o difieren en la variable A. Haga de cuenta que la parte superior del mapa se dobla hasta tocar la parte inferior. Asimismo, los cuadrados del extremo izquierdo de la columna son adyacentes a los del extremo derecho de la columna.
3. A fin de que los cuadrados que son adyacentes tanto vertical como horizontalmente difieran en una sola variable, el marcado de arriba hacia abajo debe hacerse en el orden indicado, -A'B', A' B, AB, AB'. Lo anterior también es válido para el marcado de izquierda a derecha:
4. Una vez que el mapa K se ha llenado con ceros y unos, la expresi6n de suma de productos para la salida X se puede obtener operando con OR aquellos que contienen un 1. En el mapa con tres variables de la figura 4-11(b), los cuadrados A'B'C', A'BC', A BC' y ABC contienen un 1, de modo que X = A'B'C' + A'B'C + A'BC' + ABC'.
Agrupamiento La expresión de salida X se puede simplificar adecuadamente combinando los cuadros en el mapa K que contengan 1. El proceso para combinar estos unos se denomina agrupamiento.
Agrupamiento de grupos de dos (pares) La figura 4-12(a) es el mapa K de una tabla de verdad con tres variables. Este mapa contiene un par de unos que son verticalmente adyacentes entre si; el primero representa A'BC' y, el segundo ABC'. Note que en estos dos términos sólo la variable A aparece en forma normal y complementada (B y C' permanecen sin cambio). Estos dos términos se pueden agrupar (combinar) para dar un resultante que elimine la variable A, ya que ésta aparece en forma normal y complementada. Esto se demuestra fácilmente como sigue:
Este mismo principio es válido para cualquier par de unos vertical u horizontalmente adyacentes. La figura 4-12(b) muestra un ejemplo de dos unos horizontalmente adyacentes. Estos se pueden agrupar y luego eliminar la variable C, ya que aparecen en forma no complementada y complementada para dar una resultante de X = A' B.
Otro ejemplo se da en la figura 4-12{c). En un mapa K los cuadrados de los renglones superior e inferior se consideran adyacentes. Asi, los dos unos en este mapa se pueden repetir para dar una resultante de A'B'C' + AB'C' + B'C'.
La figura 4-12(d) muestra un mapa K que tiene dos pares de unos que se pueden agrupar. Los dos unos en el renglón superior son horizontalmente adyacentes. Los dos unos en el renglón inferior son, asimismo, adyacentes puesto que en un mapa K los cuadrados de las columnas de los extremos izquierdo y derecho se consideran adyacentes. Cuando se agrupa el par superior de unos, la variable D se elimina (ya que aparece como D y D') para dar el término A'B'C. El agrupamiento del par inferior elimina la variable C para dar el término AB'C'. Estos dos términos se operan con OR a fin de obtener el resultado final para X.
Para resumir lo anterior:
El agrupamiento de un par de unos adyacentes en un mapa K elimina la variable que aparece en forma complementada y no complementada.
Agrupamiento de grupos de cuatro (cuádruples) Un mapa K puede contener Un grupo de cuatro unos que sean adyacentes entre sí. Este grupo se denomina cuádruple. La figura 4-13 muestra varios ejemplos de cuádruples. En la parte (a) los cuatro unos son verticalmente adyacentes y en la parte (b) son horizontalmente adyacentes. El mapa K de la figura 4 - 13(c) contiene cuatro unos en un cuadrado y se consideran adyacentes entre sí. Los cuatro unos en la figura 4-13(d) también son adyacentes igual que los de la figura 4 - 13(e) ya que, como mencionamos anteriormente. los renglones superior e inferior y las columnas de los extremos izquierdo y derecho se consideran adyacentes entre sí.
Cuando se repite un cuádruple, el término resultante contiene sólo las variables que no cambian de forma para todos los cuadrados del cuádruple. Por ejemplo, en la figura 4 - 13(a) los cuatro cuadrados que contienen un uno son A'B'C, A'BC, ABC y AB'C. El análisis de estos términos revela que solamente la variable C permanece sin alterarse (A y B aparecen en forma complementada y no complementada). De este modo, la expresión resultante para X es simplemente X = C. Esto se puede demostrar de la siguiente manera:
Para poner otro ejemplo, consideramos las figura 4 - 13(d), donde los cuatro cuadrados que contienen unos son ABC'D', A'B'C'D', ABCD', y AB'CD'. El análisis de estos términos indica que sólo las variables A y D' permanecen sin cambios, así que la expresión simplificada para X es
X = AD
Esto se puede probar de la misma manera anteriormente utilizada.
El lector debe verificar cada uno de los otros casos de la figura 4 -13 para comprobar que sean las expresiones indicadas para X.Para resumir:
El agrupamiento cuádruple de unos elimina las dos variables que aparecen
en la forma complementada y no complementada.
Agrupamiento de grupos en ocho (octetos) Un grupo de ocho unos que son adyacentes entre sí se denomina octeto. En lafigura 4-14 se dan varios ejemplos de octetos. Cuando
porque solo una de ellas permanece inalterada. Por ejemplo, el análisis de los ocho cuadrados agrupados en la figura 14 -14(a) muestra que so1o la variable B está en la misma forma para los ocho cuadrados; las otras variables aparecen en forma complementada y no complementada. Así, para este mapa, X = B. El lector puede verificar los resultados de los otros ejemplos en la figura 4 - 14.
No hay comentarios:
Publicar un comentario