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: