P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 1
SISTEMA BINARIO
Internamente, la máquina computadora representa los valores numéricos mediante
grupos de bits agrupados en bytes. Por ejemplo, el número 3 se representa mediante
un byte que tiene "activos" los bits primero y segundo contando desde la derecha
(00000011). Esta sería la forma de representación del número 3 en un sistema
numérico de base 2, también conocido como BINARIO. El sistema que utilizamos
normalmente es un sistema DECIMAL o de base 10. En un sistema DECIMAL, contamos
desde el 0 hasta el 9 antes de añadir un nuevo dígito. El número 22 en un sistema
decimal significa que tenemos dos conjuntos de 10s y 2 conjuntos de 1s.
En un sistema BINARIO sólo pueden haber dos valores para cada dígito: ya sea un
0=DESACTIVADO ó un 1=ACTIVADO. Para representar el número 22 en notación
BINARIA lo haríamos como 00010110, notación que se explica según la siguiente tabla:
Posición del BIT: 7 6 5 4 3 2 1 0
Valor Binario: 0 0 0 1 0 1 1 0
Valor Decimal: 128 64 32 16 8 4 2 1
Valores a Sumar: 0 0 0 16 0 4 2 0
Valor Resultante: 16 + 4 + 2=22
Conversión de Binario a Decimal:
Todos los valores que corresponden a posiciones a las que se asigna el valor binario de
0 (cero) no se cuentan, ya que 0 representa DESACTIVADO.
De la misma manera, los números que corresponden a las posiciones con valor binario
1 se sumarán, (16 + 4 + 2=22) ya que 1 representa ACTIVADO.
Conversión de decimal a binario:
Si queremos convertir cualquier número decimal en binario (base 2) debemos
proceder a dividir por 2 y tomar los restos (ceros o unos) i el último cociente, por
ejemplo, para convertir el número 45 a binario:
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 2
45 |_2
22 |_2
05 02 11 |_2
1 0 1 5 |_2
1 2 |_2
0 1
Por lo tanto el resultao es:
45 (decimal) = 101101 (bin)
Valores Decimales y sus equivalentes Binarios:
POSICIÓN BIT VALOR DECIMAL VALOR BINARIO
1 1 1
2 2 10
3 3 11
4 4 100
5 5 101
6 6 110
7 7 111
8 8 1000
9 9 1001
10 10 1010
11 16 10000
12 32 100000
13 64 1000000
14 100 1100100
15 256 100000000
16 512 1000000000
17 1000 1111110100
18 1024 10000000000
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 3
Bits, Bytes y Palabras...
Se suelen escribir los números binarios como una secuencia de grupos de cuatro bits,
también conocidos como NIBBLES. Según el número de estas agrupaciones los
números binarios se clasifican como:
Unidad: Núm. bits Ejemplo:
Bit 1 1
Nibble 4 0101
Byte (Octeto) 8 0000 0101
Palabra 16 0000 0000 0000 0101
Doble Palabra 32 0000 0000 0000 0000 0000 0000 0000 0101
Los computadores personales con el sistema operativo MS DOS utilizaban palabras de
16 BITS. Los sistemas operativos actuales sobre los que corre AutoCAD 2000 utilizan
Palabras de 32 BITS.
ALGEBRA DE BOOLE
Álgebra de Boole aplicada a la informática Se dice que una variable tiene valor booleano cuando, en general, la variable contiene un 0
lógico o un 1 lógico. Esto, en la mayoría de los lenguajes de programación, se traduce en false
(falso) o true (verdadero), respectivamente.
Una variable puede no ser de tipo booleano y guardar valores que no son booleanos, ya que
los compiladores trabajan con esos otros valores que son normalmente numéricos, aunque
también algunos permiten cambios, desde caracteres hasta valor booleano.
El 0 lógico
El valor booleano de negación suele ser representado como false, aunque también permite y
equivale al valor natural, entero y decimal (exacto) 0, así como la cadena "false", e incluso la
cadena "0".
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 4
El 1 lógico
En cambio, el resto de valores apuntan al valor booleano de afirmación, representado
normalmente como true, ya que, por definición, el valor 1 se tiene cuando no es 0.
Cualquier número distinto de cero se comporta como un 1 lógico, y lo mismo sucede
con casi cualquier cadena (menos la "false", en caso de ser ésta la correspondiente al 0
lógico).
Álgebra de Boole en informática y matemática, es una estructura algebraica en que
rigorizan 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, (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. 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.
Claude Shannon fue el primero en aplicarla en el diseño de circuitos de conmutación
eléctrica biestables, en 1938.
Operaciones Lógicas
Hemos definido el conjunto A = {0,1} como el conjunto universal sobre el que se aplica
el álgebra de Boole, sobre estos elementos se definen varias operaciones, veamos las
Operación suma (O lógica o OR)
La operación suma (+) asigna a cada par de valores a, b de A un valor c de A:
Su equivalencia en lógica de interruptores es un circuito de dos interruptores en
paralelo.
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 5
Si uno de los valores de a o b es 1, el resultado será 1, es necesario que los dos
sumandos sean 0, para que el resultado sea 0.
Su tabla de la verdad:
a b f=a+b
0 0 0
0 1 1
1 0 1
1 1 1
Operación producto (Y lógica o AND)
La operación producto ( ) asigna a cada par de valores a, b de A un valor c de A:
f=a·b
Esta operación en lógica de interruptores es un circuito en serie de dos interruptores
solo si los dos valores a y b son 1, el resultado será 1, si uno solo de ellos es 0 el
resultado será 0.
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 6
Con la siguiente tabla de la verdad:
A B f=a·b
0 0 0 0 1 0 1 0 0 1 1 1
Operación negación (NOT)
La operación negación presenta el opuesto del valor de a:
f=
Un interruptor inverso equivale a esta operación:
Tabla de la verdad:
a f=
0 1 1 0
Operaciones combinadas
Partiendo de estas tres operaciones elementales se pueden realizar otras más complejas,
que podemos representar como ecuaciones booleanas, por ejemplo:
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 7
f= +b
Que representado en lógica de interruptores es un circuito de dos interruptores en
paralelo, siendo el primero de ellos inverso.
La distinta secuencia de valores de a y b da los resultados vistos en la tabla de verdad.
La tabla de la verdad de la función seria:
A B f= +b
0 0 1 0 1 1 1 0 0 1 1 1
La operación OR exclusiva (XOR)
Hay un operación que en electrónica digital se utiliza mucho, llamada XOR (OR
exclusiva) y que se denota por el símbolo .
La equivalencia de esta función mediante contactos de interruptores será:
La secuencia de valores seria:
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 8
Esta operación la podemos definir mediante una tabla de verdad:
Fijándonos en esta tabla podemos ver lo que hace: esta operación devuelve ’0’ cuando los dos bits sobre los que operan son iguales, y ’1’ cuando con distintos.
Vamos a ver, tanto para esta operación como su negada:
F= cómo las podemos definir a partir de las operaciones + y - ,y ver algunas de sus propiedades. Partiremos de la tabla de verdad:
A B A B
0 0 0 1
0 1 1 0
1 0 1 0
1 1 0 1
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 9
Vamos a obtener las dos formas canónicas de ambas funciones:
A B= ·B+A· = (A+B) · ( + )
= · + A · B = (A+ )·( +B)
Y la siguiente propiedad es:
= B = A
Leyes fundamentales
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.
1. Ley de idempotencia:
2. Ley de involución:
3. Ley conmutativa:
4. Ley asociativa:
5. Ley distributiva:
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 10
6. Ley de cancelación:
7. Leyes de De Morgan:
Principio de dualidad
El concepto de dualidad permite formalizar este hecho: a toda relación o ley lógica le
corresponderá su dual, formada mediante el intercambio de los operadores unión (suma
lógica) con los de intersección (producto lógico), y de los 1 con los 0.
Además hay que cambiar cada variable por su negada. Esto causa confusión al aplicarlo
en los teoremas básicos, pero es totalmente necesario para la correcta aplicación del
principio de dualidad. Véase que esto no modifica la tabla adjunta.
Adición Producto
1
2
3
4
5
6
7
8
9
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 11
Otras formas de notación del álgebra de Boole
En matemática se emplea la notación empleada hasta ahora ({0,1}, + , ) siendo la
forma más usual y la más cómoda de representar.
Por ejemplo las leyes de De Morgan se representan así:
Cuando el álgebra de Boole se emplea en electrónica, suele emplearse la misma
denominación que para las puerta lógica AND (Y), OR (O) y NOT (NO), ampliándose
en ocasiones con X-OR (O exclusiva) y su negadas NAND (NO Y), NOR (NO O) y X-
NOR (equivalencia). las variables pueden representarse con letras mayúsculas o
minúsculas, y pueden tomar los valores {0, 1}
Empleando esta notación las leyes de De Morgan se representan:
( = · [NOT (a OR b) = NOT a AND NOT b]
( ) = ( + ) [NOT ( a AND b) = (NOT a OR NOT b)]
Simplificación de funciones booleanas
Cuando estamos diseñando circuitos digitales, utilizamos funciones booleanas para describirlos.
Y antes de implementarlos, es decir, antes de convertir las ecuaciones a componentes
electrónicos (puertas lógicas) tenemos que simplificar al máximo. No basta con realizar un circuito, sino que hay que hacerlo con el menor número posible de componentes electrónicos. Y esto es lo que conseguimos si trabajamos con funciones simplificadas.
Las funciones booleanas se tienen que simplificar al máximo, para diseñar los circuitos con el menor número de componentes electrónicos. Esta simplificación la podemos realizar de dos maneras diferentes:
1. Utilizando las propiedades y Teoremas del Algebra de Boole. Se denomina método analítico de simplificación de funciones. Hay que manejar muy bien estas propiedades para poder eliminar la mayor cantidad de términos y variables.
2. Utilizando el método de Karnaugh. Es un método gráfico que si lo aplicamos bien, nos garantiza que obtendremos la función más simplificada posible, a partir de una tabla de verdad.
Normalmente las formas canónicas no son las expresiones más simplificadas.
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 12
Método analítico de simplificación de funciones
No existe un método como tal. Hay que basarse en la experiencia y en el conocimiento de las propiedades y teoremas del Algebra de Boole.
Ejemplo:
Simplificar la siguiente función:
F = · ·C + ·B· + ·B·C + A·B·
Si aplicamos la propiedad distributiba:
F = · ·C + ·B· + ·B·C + A·B·
· ·C + ·B·C = ·C·( +B) = ·C
Haciendo lo mismo con los otros dos factores:
F = · ·C + ·B· + ·B·C + A·B·
·B· A·B·
·B· + A·B· = ( +A)·B· = B·
Con lo que nos queda:
F = ·C+ B·
Tanto la función inicial, como la que hemos obtenido son funciones equivalentes. Tienen la misma tabla de verdad, sin embargo, la segunda está mucho más simplificada: sólo tiene dos sumandos y cada sumando tiene sólo dos variables.
Método de Karnaugh
En este apartado veremos un método para obtener la función más simplificada a partir de una tabla de verdad.
Es un método gráfico, que funciona perfectamente para funciones con cualquier número de variables, si bien su máxima eficacia se da con las de hasta 4 variables. Para más de 4 también funciona, pero podría convertirse en un método excesivamente complejo.
Supongamos que tenemos una función F(A,B) de dos variables, cuya tabla de verdad es:
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 13
A B F Ecuación Lógica
igual a 1
0 0 0 -----
0 1 1 ·B
1 0 1 A·
1 1 1 A·B
La función desarrollada en forma canónica será:
F = ·B+A· +A·B
El método de Karnaugh se basa en construir una tabla con un sistema de casillas que nos permite, visualmente, una rápida simplificación, siempre que sigamos unas normas muy simples. Para el ejemplo que nos ocupa, situemos en la tabla de Karnaugh los valores de la función que resulten 1 en la tabla de la verdad, donde cada fila de la tabla de la verdad se corresponde con una casilla de la de Karnaugh. Las normas a seguir son:
1. Los ceros no se escriben 2. Si encabeza la fila o columna un 1 se pondrá el término o variable que indique
la fila o columna correspondiente 3. Si la variable de la casilla donde aparece un 1 esta encabezada por 0, se pondrá
el complemento de la variable, esto es el NEGADO Lógico de esta 4. Si dos celdas contiguas por cualquiera de sus lados contienen un 1 se agrupan
y se tendrán en cuenta solo las variable que en la fila o columna no cambien de valor
5. Si la celda contiene 1 la ecuación que la representa sera la del producto lógico (Y) de todas las variables de que la afecten, en el estado que indique la fila o columna
6. Todas las variables individuales que aparecen como resultado del apartado 5, se agrupan mediante una suma lógica (O), formando de este modo la ecuación resultante final
A
B
F = A+B
A
B 0
1
0 1
1 1 1
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 14
Con otro ejemplo veremos como actuamos con 3 variables.
Tenemos la tabla de la función F(A,B,C) de tres variables, cuya tabla de la verdad será:
A B C F
0 0 0 0
0 0 1 0
0 1 0 1
0 1 1 1
1 0 0 1
1 0 1 1
1 1 0 1
1 1 1 1
que de forma canonica:
F= ·B· + ·B·C+A· · +A· ·C+A·B· +A·B·C
Ahora la simplificaremos empleando el método estudiado, añadiendo las siguientes normas:
1. Primero creamos la tabla ordenandoa los ejes de modo que cada vez que cambiemos de fila o columna solo cambie una de las variables, esto es, mediante un ordenamiento NO BINARIO
A
BC 0 1
00
01
11
10
Para situar en la tabla los estados
de las variables, al pasar de una
fila a otra o de una columna a otra
solo podemos cambiar una
variable
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 15
2. Podemos combinar grupos de celdas adyacentes que contengan 1, de 2 en 2, de 4 en 4 o de 8 en 8, para simplificar a 2 o 1 variable
3. Las celdas que contengan 1 y no se puedan combinar representan las 3 variables o 4, según las filas y columnas que representen
4. Pueden intersectarse grupos entre si 5. También se consideran celdas adyacentes entre si las de los extremos
A
BC 0 1
00 1
01 1
11 1 1
10 1 1
Hemos agrupado por grupos de 2 celdas y nos queda la fórmula como sigue
F=A· +B·C+B·
No sera la mayor simplificación, pues podríamos, también, realizar agrupación de 4 componentes, lo cual nos daria una mejor simplificación:
A
BC 0 1
00 1
01 1
11 1 1
10 1 1
Con lo cual la función simplificada quedará:
F=A+B
Por último veremos un ejemplo con 4 variables.
Tenemos la siguiente tabla de la verdad:
A·
B·C
B·
A
B
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 16
A B C D F
0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 1 1 0
0 1 0 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 1 1
1 0 0 0 1 1 0 0 1 0 1 0 1 0 1 1 0 1 1 0
1 1 0 0 1 1 1 0 1 0 1 1 1 0 1 1 1 1 1 0
La función canónica será:
F= · · · + · ·C· + ·B· · + ·B· ·D+ ·B·C· + ·B·C·D+A· · ·+A· ·C· +A·B· · +A·B·C·
Evidentemente la simplificación es compleja. Apliquemos la tabla de Karnaugh para conseguir una simplificación más completa:
AB
CD
00
( )
01
( B)
11
(AB)
10
(A )
00 ( ) 1 1
01 ( D) 1 1 1 1
11 (CD) 1 1
10 (C ) 1 1
en donde agruparemos los 1 en grupos del mayor número de adyacentes posibles, respetando siempre que deben ser grupos de 1, 2, 4, 8, etc.:
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 17
(¡Podemos crear un grupo de 8 unos
adyacentes! Esto implica que como
resultado tendremos una sola variable)
( )
AB
CD
00
( )
01
( B)
11
(AB)
10
(A )
00 ( ) 1 1 1 1
01 ( D) 1
11 (CD) 1
10 (C ) 1 1 1 1
definitivamente la función queda:
F= + ·B
que definitivamente es la más reducida.
(Grupo de 4 variables)
·B
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 18
EJERCICIOS:
Ejercicio 1:
Realizar las siguientes operaciones:
1. 1 + 0 =
2. 1 + 1 =
3. 1� 0 =
4. 1� 1 =
5. A+0 =
6. A+1=
7. A�1=
8. A�0=
9. A+A=
10. A.A=
11. A+_ =
12. A� _ =
13. A+AB =
14. A(A+B) =
15. A+AB+B =
Ejercicio 2:
Aplicar las leyes de Morgan en los siguientes casos:
1. =
2. =
3. =
Ejercicio 3:
Obtener la tabla de la verdad de las siguientes funciones booleanas.
1. F= A+B 2. F= A+ 3. F= ·B+C 4. F=A·B+ ·B 5. F= ·B·C+A· ·C+ · ·C
P.Q.P.I. AUXILIAR MUNTTGE ORDINADORS – CARLOS CARDELO – IES MVM
28/02/2011 Pàgina 19
Ejercicio 4:
Simplificar la función F=A·B+ de las siguientes maneras:
1. Obteniendo la tabla de verdad y aplicando Karnaugh 2. Aplicando las propiedades del Algebra de Boole
Ejercicio 5:
Obtener las expresiones más simplificadas a partir de las tablas de verdad: