parte ii - ecotec€¦ · leyes del Álgebra de boole por tanto, habrá que aplicar un Álgebra de...

PARTE II

LÓGICA COMPUTACIONAL

Lógica de proposiciones

INTRODUCCION

Teniendo en mente que queremos presentar los sistemas deductivos de la lógica como una herramienta práctica para los informáticos, vamos a introducirnos en el estudio de la lógica comenzando por la más simple, la lógica de proposiciones, que corresponde a la lógica que simboliza y describe razonamientos basados en enunciados declarativos.


Proposiciones

Formalmente, se define una

proposición como un

enunciado declarativo que

puede ser verdadero o falso,

pero no ambos a la vez.


Las proposiciones se representan

mediante variables proposicionales

simbolizadas mediante letras.

Con la combinación de variables

proposicionales y conjunciones se

obtienen fórmulas sentenciales o

sentencias.


• Tautología: es la sentencia que es

verdadera.

• Contradicción: es la sentencia que

es falsa.

• Indeterminación: es la sentencia

que ni es verdadera ni falsa.


LENGUAJE PROPOSICIONAL

Sintaxis

El primer paso en el estudio de un lenguaje es definir los símbolos básicos que lo constituyen (alfabeto) y cómo se combinan para formar sentencias.

Está constituido por:

• Símbolos de veracidad: V para verdadero y F para falso.


• Símbolos de variables: p, q, r, s, ...

• Símbolos de conectivas: NO, Y, O, O ... O, SI ... ENTONCES, ... SI Y SOLO SI ...

• Símbolos de puntuación: ( , ), para evitar ambigüedades.


Reglas de formación

• Las clases de sentencias bien formadas se definen por reglas puramente sintácticas, llamadas reglas de formación, y que son:

• Una variable proposicional es una sentencia bien formada.

• Una sentencia bien formada precedida de la negación es una sentencia bien formada.


• Dos sentencias bien formadas unidas por una de las partículas conectivas binarias constituye una sentencia bien formada.

• Se pueden omitir los paréntesis que encierran una sentencia completa.

• El estilo tipográfico de los paréntesis se puede variar para hacerlos más evidentes usando corchetes y llaves.

• A las conjunciones y disyunciones se les puede permitir tener más de dos argumentos.


Conectivas

Las conectivas se dividen por su aplicación

en:

• Singulares: se aplican a una única

sentencia.

• Binarias: se aplican a dos sentencias.


Conectivas

Por su definición, también se pueden dividir

en:

• Primitivas: las variables proposicionales,

los paréntesis y las conectivas NO y O.

• Definidas: las conectivas Y, SI ...

ENTONCES, ... SI Y SOLO SI ... y O ... O.


Tablas de verdad

La tabla de verdad de una sentencia es una tabla en la que se presentan todas las posibles interpretaciones de las variables proposicionales que constituyen la sentencia y el valor de verdad de la sentencia para cada interpretación.


SEMANTICA

Negación (NO)

Consiste en cambiar el valor de verdad de una variable proposicional.

p NO p

========

V F

F V


Disyunción inclusiva (O)

La sentencia será verdadera cuando una o

ambas variables proposicionales sean verdaderas.

p q p O q

=============

V V V

V F V

F V V

F F F


Conjunción (Y)

Es una conectiva definida por:

p Y q = NO ( NO p O NO q )


La sentencia será verdadera sólo cuando ambas

variables proposicionales sean verdaderas.

p q p Y q

=============

V V V

V F F

F V F

F F F


Condicional (SI ... ENTONCES)


p COND q = NO p O q


La sentencia será verdadera cuando se

cumpla si es válido p entonces lo es q.

p q p COND q

================

V V V

V F F

F V V

F F V


Bicondicional (... SI Y SOLO SI ...)


p BICOND q = ( ( p COND q ) Y ( Q COND p ) )


La sentencia será verdadera cuando ambas

variables proposicionales sean iguales.

p q p BICOND q

==================

V V V

V F F

F V F

F F V


Disyunción exclusiva (O ... O)


p EXCL q = NO ( p BICOND q )


La sentencia será verdadera sólo cuando una de las dos variables proposicionales sea verdadera.

p q p EXCL q

================

V V F

V F V

F V V

F F F


Axiomas y reglas

Los axiomas para el cálculo proposicional

son:

• ( p O p ) COND p

• q COND ( p O q )

• ( p O q ) COND ( q O p )

• ( p COND q ) COND [ ( r O p ) COND ( r O q ) ]


A partir de estos axiomas y

aplicando las dos reglas de

transformación siguientes se

puede demostrar cualquier

teorema:


Regla de sustitución: el resultado de

reemplazar cualquier variable en un

teorema por una sentencia bien

formada es un teorema.

Regla de separación: si S y ( S

COND R ) son teoremas, entonces

R es un teorema.


Relativo a un criterio de validación, un sistema axiomático debe cumplir las siguientes propiedades:

• Debe ser lógico o razonable: en el sentido de que todo teorema es una tautología.

• Completo: toda sentencia bien formada v lida es un teorema y se debe poder demostrar a partir de los axiomas.


• Consistente: no se pueden demostrar como teoremas, sentencias bien formadas que no sean tautologías.

• Deben ser independientes: ningún axioma debe ser derivable a partir de los otros.

Leyes del Álgebra de

Boole

INTRODUCCION

Debido a que los computadores trabajan con información binaria, la herramienta matemática adecuada para el análisis y diseño de su funcionamiento es el Álgebra de Boole.

El Álgebra de Boole fue desarrollada inicialmente para el estudio de la lógica. Ha sido a partir de 1938, fecha en que C.E. Shanon publicó un libro llamado "Análisis simbólico de circuitos con relés"


Boole

Hoy en día, esta herramienta resulta fundamental para el desarrollo de los computadores ya que, con su ayuda, el análisis y síntesis de combinaciones complejas de circuitos lógicos puede realizarse con rapidez y eficacia.


Boole

Definiciones básicas

Se comenzará el estudio del Álgebra de Boole introduciendo 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.


Boole

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.


Boole

Diagramas de Venn

Los diagramas de Venn constituyen un sistema para representar gráficamente las clases.

Sus reglas básicas son las siguientes:

• La clase universal U se representa por un rectángulo.

• Una clase cualquiera A, perteneciente a la clase universal, se representa mediante la superficie definida por una curva cerrada, dibujada en el interior del rectángulo.


Boole

• Un elemento e de la clase A se representa por un punto dibujado en el interior de la curva cerrada.

• La clase complementaria A' de la clase A se representa por la superficie diferencia entre la de la clase universal U y la de la clase A.

• La clase vacía no tiene representación por medio de los diagramas de Venn.


Boole

• La representación de varias clases pertenecientes a la misma clase universal se realiza de la misma forma, es decir, dibujando en el interior del rectángulo tantos círculos como clases distintas se deseen representar.


Boole

• Las clases que tienen elementos comunes se representan mediante círculos que se cortan entre sí. El área común define el subconjunto formado por los elementos comunes a ambas clases. Si dos clases no tienen ningún elemento en común, no habrá ningún punto de corte entre sus dos diagramas.

• La representación de subclases de una clase dada se realiza dibujando círculos en el interior de la clase.


Boole

OPERACIONES

En esta sección se definirán las operaciones básicas del Álgebra de Boole, describiéndose a continuación su aplicación a los circuitos lógicos.


Boole

Unión o adición

La unión de dos clases A y B se define como la clase formada por todos los elementos de la clase A, todos los elementos de la clase B, y ningún otro elemento. La clase unión se representa mediante la simbología matemática:

A O B


Boole

Intersección o producto

La intersección de dos clases A y B se

define como la clase formada por todos

los elementos que pertenecen

simultáneamente a las clases A y B. La

clase intersección se puede representar

mediante los símbolos:

A Y B


Boole

Complementación

La clase complementaria de una dada ya ha

sido definida. Las notaciones simbólicas

empleadas para representar el

complementario de A son: A' o bien NO A.


Boole

Aquí se mencionarán dos

propiedades importantes de la

complementación, que se pueden

comprobar fácilmente:

A + A' =U (clase universal)

A + A' = 0 (clase vacía)


Boole

APLICACION A CIRCUITOS LOGICOS

Dado que los elementos de los circuitos

utilizados en los computadores sólo

admiten dos estados, las clases y

operaciones básicas del Álgebra de Boole

deberán particularizarse para este caso.


Boole

Por tanto, habrá que aplicar un Álgebra de Boole de tipo binario, donde sólo existirán dos clases: la universal que se representará por 1, y la vacía que se representará por 0.

El estado de un elemento del circuito lógico viene representado por una variable que sólo puede tomar valores 0 o 1, que se corresponden con las dos clases posibles en un Álgebra de Boole binaria.


Boole

En el caso de un álgebra binaria, las operaciones básicas del Álgebra de Boole pueden describirse mediante las denominadas tablas de verdad, que agrupan en forma tabulada todas las combinaciones posibles de operandos, con sus correspondientes resultados.


Boole

Adición

A B A + B

=============

0 0 0

0 1 1

1 0 1

1 1 1

Equivale a un circuito en paralelo con un interruptor en cada hilo, donde al conectar cualquiera de ellos hay conducción en el circuito.


Boole

Producto

A B A · B

=============

0 0 0

0 1 0

1 0 0

1 1 1

Equivale a un circuito en serie donde existe dos interruptores en el mismo hilo, de tal forma que sólo hay conducción cuando están cerrados ambos interruptores.


Boole

Complementación

A A'

======

0 1

1 0

Se representa bajo la forma de contactos

complementarios de un mismo interruptor, de

modo que si uno está cerrado el complementario

estará abierto, y viceversa.


Boole

LEYES FUNDAMENTALES

Teoremas

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.

• Ley de idempotencia: A + A = A | A · A = A

• Ley de involución: (A')' = A


Boole

• Ley conmutativa: A + B = B + A | A · B = B · A

• Ley asociativa: A + (B + C) = (A + B) + C | A · (B · C) = (A · B) · C

• Ley distributiva: A + B · C = (A + B) · (A + C) | A · (B + C) = A · B + A · C

• Ley de absorción: A + A · B = A | A · (A + B) = A

• Ley de De Morgan: (A + B)' = A' · B' | (A · B)' = A' + B'


Boole

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 con los de intersección, y de los 1 con los 0.


Boole

# ADICION PRODUCTO

===============================================

1 A + A' = 1 A · A' = 0

2 A + 0 = A A · 1 = A

3 A + 1 = 1 A · 0 = 0

4 A + A = A A · A = A

5 A + B = B + A A · B = B . A

6 A + (B + C) = (A + B) + C A · (B · C) = (A · B) · C

7 A + B · C = (A + B) · (A + C) A · (B + C) = A · B + A · C

8 A + A · B = A A · (A + B) = A

9 (A + B)' = A' · B' (A · B)' = A' + B'

Funciones lógicas

INTRODUCCION

Una vez definidas las operaciones básicas

en el Álgebra de Boole binaria, así como

sus relaciones fundamentales, se avanza

un paso más estableciendo el concepto

de función. Las funciones se utilizan para

describir el comportamiento de los

circuitos lógicos empleados en los

computadores.

Funciones lógicas

Concepto

Se define como función en el Algebra de Boole binaria o función lógica a todo conjunto de variables relacionadas entre sí por cualquiera de las tres operaciones básicas definidas anteriormente.

Funciones lógicas

De forma general, se representará como:

f = f( A, B, C, ... )

Según el teorema 1, el resultado de evaluar una función booleana es también una variable booleana.

A continuación se presentan dos teoremas de las funciones booleanas:

Funciones lógicas

Ley de De Morgan generalizada

El complemento de una función se obtiene

complementando todas las variables que

intervienen en ella e intercambiando las

operaciones adición y producto. Esto

puede expresarse simbólicamente de la

forma:

[ f( A, B, C, ... , +, · ) ] ' = f( A', B', C', ... , ·, + )

Funciones lógicas

Teorema de la descomposición de funciones

Toda función puede descomponerse, con respecto a cualquiera de las variables de las que depende, según la siguiente relación:

f( A, B, C, ... ) = A · f( 1, B, C, ... ) + A' · f( 0, B, C, ... )

Funciones lógicas

siendo f(1, B, C, ...) la función resultante de sustituir, en la función original, todas las A por 1, y las A' por 0.

El segundo término, f(0,B,C,...) es la función resultante de sustituir las A por 0 y las A' por 1.

Funciones lógicas

FUNCIONES LOGICAS ELEMENTALES

Función O (OR)

Operación: adición lógica.

Salida: A + B

A B A + B

=============

0 0 0

0 1 1

1 0 1

1 1 1

Funciones lógicas

Función Y (AND)

Operación: producto lógico.

Salida: A · B

A B A · B

=============

0 0 0

0 1 0

1 0 0

1 1 1

Funciones lógicas

Función NO (NOT)

Operación: complementación.

Salida: A'

A A'

======

0 1

1 0

Funciones lógicas

Función ON (NOR)

Operación: complementación de la adición lógica.

Salida: (A + B)' = A' · B'

A B A' · B'

===============

0 0 1

0 1 0

1 0 0

1 1 0

Funciones lógicas

Función YN (NAND)

Operación: complementación del producto lógico.

Salida: (A · B)' = A' + B'

A B A' + B'

===============

0 0 1

0 1 1

1 0 1

1 1 0

Funciones lógicas

Función OX (XOR)

Operación: O exclusiva.

Salida: A · B' + A' · B

A B A · B' + A' · B

=======================

0 0 0

0 1 1

1 0 1

1 1 0

Funciones lógicas

Función EQU (EQU)

Operación: equivalencia lógica.

Salida: A · B + A' · B'

A B A · B + A' · B'

=======================

0 0 1

0 1 0

1 0 0

1 1 1

Simplificación de

funciones

REPRESENTACION DE FUNCIONES

Expresión algebraica

Una función puede representarse mediante su formulación algebraica, que consiste en una combinación de variables relacionadas por las tres operaciones lógicas básicas.

Ejemplo:

f( A, B, C ) = A · B · C + A' · B · C + A' · B · C'

Simplificación de

funciones

Tabla de verdad

Otra forma de representar una función lógica consiste en utilizar una tabla en la que figuren todas las combinaciones posibles de las variables de entrada y el valor correspondiente de la función para cada una de dichas combinaciones.

Ejemplo:

f( A, B, C ) = A · B · C + A' · B · C + A' · B · C'

Simplificación de

funciones

A B C f

=============

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

Simplificación de

funciones

Transformación

A menudo resulta interesante obtener la

función algebraica equivalente de una

tabla de verdad. Para ello existe un

procedimiento que consiste en escribir la

ecuación de la función como suma de los

términos cuyas combinaciones en la tabla

de verdad tengan asignados el valor 1.

Simplificación de

funciones

Cada término consistirá en un

producto de todas las variables de

las que depende la función, escritas

en su forma natural o

complementada, según que en la

combinación correspondiente a

dicho término en la tabla aparezcan

con un 1 o con un 0

respectivamente.

Simplificación de

funciones

Ejemplo: obtener un expresión algebraica de la siguiente tabla de verdad.

A B C f

=========

0 0 0 1

0 0 1 0

0 1 0 0

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 1

1 1 1 0

f( A, B, C ) = A' · B' · C' + A' · B · C + A · B · C'

Simplificación de

funciones

FORMAS CANONICAS

Concepto

Una suma de productos de todas las variables.

Un producto de sumas de todas las variables.

Toda función booleana puede transformarse en

una forma canónica, y esta transformación es

única.

Simplificación de

funciones

Teorema de transformabilidad

Si n es el número de variables, existen 2^n

términos canónicos, y el número posible de

funciones canónicas es igual al de

variaciones con repetición de dos elementos,

0 y 1, tomados de 2^n en 2^n, es decir:

Nº funciones posibles = 2^2^n

Simplificación de

funciones

Expresión en minterms

Suele utilizarse la siguiente notación para referirse a los productos que aparecen en la primera forma canónica: cada producto se denomina mi, siendo i el valor decimal de la combinación binaria que se obtiene al sustituir por 1 las variables que, en el producto, aparecen en forma natural, y por 0 las que lo hacen en forma complementada.

Simplificación de

funciones

Estos términos reciben el nombre de minterms, que es contracción de minimum term, y que indica que los productos de conjuntos constituyen los conjuntos mínimos que se pueden formar operando con las variables.

Ejemplo: utilizando la función del ejemplo anterior m3 representa

A' · B · C = 011

Simplificación de

funciones

Expresión en maxterms

Análogamente se representan por Mi las sumas canónicas de la segunda forma, teniendo el índice i el mismo significado que en la definición de minterms.

Estos términos Mi reciben la denominación de maxterms.

Simplificación de

funciones

Nombre que ahora corresponde a la contracción de maximum term, y que indica que las sumas de conjuntos constituyen los conjuntos máximos que pueden formarse operando con las variables.

Ejemplo: utilizando la función del ejemplo anterior M5 representa

A + B' + C = 101

Simplificación de

funciones

Transformación entre minterms y maxterms

Si se representa ahora por f( i ) el valor que

adopta la función al sustituir las variables por 1 o 0, según el valor indicado por la combinación binaria correspondiente a i, las dos expresiones generales anteriores pueden escribirse así:

f( A, B, C,... ) = Suma [0, 2^n - 1] f( i ) · mi = Producto [0, 2^n - 1] ( f( 2^n - 1 - i ) + Mi )

Simplificación de

funciones

Por tanto, si en la primera forma canónica aparece en término mi, el término M^2n - 1 - i de la segunda forma canónica no aparecerá, y para pasar de la primera a la segunda forma canónica bastará con escribir los términos cuyo índice sea el complementario a 2^n - 1 de los productos canónicos que no aparecen en la primera forma.

Simplificación de

funciones

Ejemplo: pasar a la segunda forma

canónica la función

f( A, B, C ) = m1 + m2 + m7

m1 + m2 + m7 = A' · B' · C + A' · B · C' + A · B · C

Simplificación de

funciones

Los productos no utilizados en la primera

forma canónica son:

m0 + m3 + m4 + m5 + m6 = A' · B' · C' + A' ·

B · C + A · B' · C' + A · B' · C + A · B · C'

Simplificación de

funciones

mi = M2^n - 1 - i

=======================================

A' . B' . C' = A + B + C

A' . B . C = A + B' + C'

A . B' . C' = A' + B + C

A . B' . C = A' + B + C'

A . B . C' = A' + B' + C

f(A,B,C) = M1 · M2 · M3 · M4 · M7

= (A'+B'+C) · (A'+B+C') ·

(A'+B+C) · (A+B'+C') · (A+B+C)

Simplificación de

funciones

Obtención de las formas canónicas a partir de las tablas de verdad

La parte izquierda de la tabla representa todos los productos canónicos posibles, en los que las variables figuran en su forma natural o complementada según que en la combinación correspondiente de la tabla aparezca, para esa variable, un 1 o un 0, respectivamente.

En la parte derecha de la tabla aparecen los coeficientes f( i ), es decir, el valor que adopta la función al sustituir las variables por 1 o 0 según la regla anterior.

Simplificación de

funciones

La función, en su primera forma canónica, será la suma de los productos canónicos cuyos coeficientes sean 1, es decir, la suma de términos cuyo valor resultante en la tabla de verdad sea un 1.

La segunda forma canónica de una función puede obtenerse también de la tabla de verdad buscando las combinaciones para las que el valor de f es igual a 0, y escribiendo el término correspondiente como suma de variables que figurarán en su forma directa si en la tabla hay un 0, o en su forma complementada si en la tabla hay un 1.

Simplificación de

funciones

Ejemplo: dada la función booleana n determinada por la siguiente tabla de verdad.

A B C f

=============

0 0 0 1

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 0

1 0 1 0

1 1 0 0

1 1 1 1

1ª forma canónica: f(A,B,C) = A'·B'·C' + A'·B·C' + A'·B·C + A·B·C = m0 + m2 + m3 + m7

2ª forma canónica: f(A,B,C) = (A+B+C') · (A'+B+C) · (A'+B+C') · (A'+B'+C) = M1·M2·M3·M6

Simplificación de

funciones

SIMPLIFICACION DE FUNCIONES

Significado

La teoría de la conmutación tiene dos objetivos fundamentales:

Obtener los circuitos lógicos que representan a las diferentes funciones booleanas.

Obtener, de entre los muchos circuitos lógicos que pueden representar a una función dada, el circuito de coste mínimo.

Simplificación de

funciones

El problema de hallar la forma mínima de una expresión booleana, entendiendo por mínima las más económica posible, no está resuelto de una forma general y sistematizada.

Existen varios procedimientos sistemáticos, pero que no llegan a proporcionar de forma categórica la simplificación máxima para las diferentes funciones booleanas que se pueden presentar en la práctica. De entre ellos se describirá el procedimiento basado en los mapas de Karnaugh, que probablemente es el más simple y conocido.

Simplificación de

funciones

Orden de un circuito lógico

La solución simplificada de una función booleana no es única, pudiéndose obtener varias funciones distintas con igual grado de minimización, es decir, con el mismo coste. Cualquiera de esas funciones es válida y la elección de una u otra dependerá del usuario y de la consideración del orden de un circuito lógico.

Se define el orden como el número máximo de veces que una variable booleana debe atravesar circuitos lógicos en serie antes de alcanzar la salida.

Simplificación de

funciones

Normalmente, se elige siempre un orden inferior por las siguientes razones:

• Las señales se atenúan y deforman cada vez que se realiza con ellas una operación lógica.

• Los retardos en la señal que cada nivel produce.

Simplificación de

funciones

Método del mapa de Karnaugh

Un mapa de Karnaugh para funciones de n variables consiste en un conjunto de 2^n cuadrados, cada uno de los cuales se encuentra asociado a un minterm o a un maxterm, y dispuestos de tal forma que para pasar de un minterm a otro a lo largo de una de las dos direcciones posibles, horizontal o vertical, únicamente es preciso cambiar una variable.

Simplificación de

funciones

Mapa de Karnaugh para dos variables:

B' B

=============

A' m0 m1

A' · B' A' · B

=============

A m2 m3

A · B' A · B

=============

Simplificación de

funciones

Mapa de Karnaugh para tres variables:

B' B' B B

======================================

A' m0 m1 m3 m2

A' · B' · C' A' · B' · C A' · B · C A' · B · C'

======================================

A m4 m5 m7 m6

A · B' · C' A · B' · C A · B · C A · B · C'

======================================

C' C C C'

Simplificación de

funciones

Mapa de Karnaugh para cuatro variables:

C' C' C C

======================================

A' m0 m1 m3 m2 B'

A'·B'·C'·D' A'·B'·C'·D A'·B'·C·D A'·B'·C·D'

======================================

A' m4 m5 m7 m6 B

A'·B·C'·D' A'·B·C'·D A'·B·C·D A'·B·C·D'

======================================

A m12 m13 m15 m14 B

A·B·C'·D' A·B·C'·D A·B·C·D A·B·C·D'

======================================

A m8 m9 m11 m10 B'

A·B'·C'·D' A·B'·C'·D A·B'·C·D A·B'·C·D'

======================================

D' D D D'

Simplificación de

funciones

Para agrupar la función en términos

más simplificados, se agrupan las

casillas que contienen un 1

mediante potencias en base 2, es

decir, 2, 4, 8, ... y se

expresar mediante una suma de

productos, ya que, el caso más

usual es que venga expresada en

minterms.

Simplificación de

funciones

En el caso de que la función booleana

esté expresada en maxterms, el

método de Karnaugh se aplica de la

misma forma que en el caso de

minterms, la única diferencia estriba

en que los unos que deben ponerse

en las casillas son los

correspondientes a los maxterms

existentes en la función.

Simplificación de

funciones

Redundancias

A menudo, en el diseño de sistemas digitales sucede que ciertas combinaciones de las variables, es decir, ciertos minterms, son prohibidos por alguna razón.

Estas combinaciones prohibidas reciben el nombre de redundancias y pueden utilizarse para simplificar funciones booleanas.

Simplificación de

funciones

Para minimizar una función booleana que presente redundancias, pueden utilizarse los mapas de Karnaugh del mismo modo que en la subsección precedente, y puesto que los minterms correspondientes a las combinaciones prohibidas nunca se van a producir, los cuadros correspondientes en el mapa de Karnaugh pueden hacerse ceros o unos, en función de lo que interese al diseñador.

Cada minterm que sea redundante se indicará con una cruz en la casilla correspondiente del mapa de Karnaugh, y a continuación se pondrán unos o ceros en lugar de las cruces, según convenga en la simplificación.

Simplificación de

funciones

Criterios de valoración

• Simplificar la función con las reglas dadas de modo que se obtenga la expresión que contenga menos sumandos (si está expresada en forma de minterms) o menos productos (si está expresada en forma de maxterms).

• Si se obtienen varias funciones equivalentes desde el punto de vista considerado anteriormente, se tomará como más simple la expresión que contenga menos variables.

Simplificación de

funciones

• Se hallará la forma dual para ver si es más simple.

• Se estudiará, en caso de tener varias expresiones equivalentes (es decir, con el mismo número de términos y variables), cuál es la de menor orden.

• Si se tuviese que decidir finalmente entre varias funciones posibles con el mismo número de términos, de variables e igual orden, se elegirá la más económica, es decir, la que necesite menor número de diodos y transistores evaluando los circuitos AND, OR y NOT necesarios.

Representación de la

información

INTRODUCCION

Los computadores digitales actuales se basan en una tecnología electrónica que permite representar los datos mediante combinaciones de circuitos flip-flop o biestables. Estos elementos básicos sólo admiten dos estados, representados por el nivel de tensión a su salida.

La información que se representa mediante la combinación de elementos que sólo admiten dos estados se denomina información binaria. Cada uno de los elementos de la información binaria recibe el nombre de bit (binary digit) y se codifica mediante el empleo de uno de los dos únicos símbolos 0 o 1.


información

Dicho de otro modo, cualquier dato que se deba procesar en un computador digital deberá estar representado por un código formado por una secuencia de ceros y unos.

La codificación consiste en establecer unas reglas que definan una correspondencia entre cada elemento de información y la secuencia de bits que constituye su código.

Existen varios criterios genéricos para establecer esta correspondencia, que dan lugar a tipos diferentes de códigos. Dichos criterios se denominan sistemas de codificación.


información

Clasificación de la información

Existen dos flujos de información en un computador digital:

• Flujo de datos: han de ser manipulados para producir los resultados.

• Flujo de control: o flujo de instrucciones, expresa las manipulaciones a realizar en dichos datos.


información

Los datos pueden ser:

• Numéricos: números de tipo natural, entero o real.

• Alfabéticos: letras del alfabeto. El flujo de control se compone de las órdenes que debe ejecutar el computador, y que reciben el nombre de códigos de instrucción.


información

SISTEMAS DE CODIFICACION

Codificación directa

Es el sistema de codificación más simple de todos y consiste en establecer una correspondencia biunívoca entre un conjunto de símbolos y un conjunto de códigos binarios mediante una tabla.


información

Si se tiene un conjunto de n elementos tales que cada uno de ellos puede tomar m valores distintos, el número Nc de combinaciones distintas de valores que puede tomar dicho conjunto de elementos (número de códigos posibles) viene dado por la expresión:

Nc = m^n

Dado que m vale 2 para los elementos binarios, con n elementos se pueden obtener 2^n códigos distintos.


información

Codificación por campos

Cada campo se codifica por una tabla independiente. La suma de longitudes de estas tablas es inferior a la de una tabla directa única. La codificación por campos resulta habitualmente más sencilla que la codificación directa. Esta última presenta en contrapartida una total libertad en la asignación de códigos, lo que permite en muchos casos facilitar las operaciones de proceso de la información codificada.


información

Codificación por secuencias de códigos

A menudo los elementos de información no

se procesan o almacenan aisladamente

sino en conjunto. En estos casos los

códigos de los sucesivos datos suelen

tratarse o registrarse secuencialmente.


información

El tratamiento secuencial de los códigos abre una nueva posibilidad consistente en hacer que determinados códigos especiales modifiquen la interpretación de los que aparezcan a continuación.

Este sistema de codificación consigue reducir la longitud de las tablas de codificación a costa de aumentar la longitud del código asignado a ciertos símbolos.


información

CODIGOS NUMERICOS

Fundamentos

Se puede definir un sistema de numeración como el conjunto de símbolos y reglas que se utilizan para la representación de cantidades.


información

Existe un elemento fundamental que caracteriza a todos los sistemas de numeración, y que se denomina base del sistema de numeración. Dicha base es el número de símbolos que se utilizan para realizar la representación.

Se denomina rango de representación, en un sistema de numeración y con un número de cifras determinado n, al conjunto de cantidades representables en el mismo.


información

Sistemas posicionales

En los sistemas de numeración, la representación de una cantidad siempre se efectúa mediante cadenas de símbolos.

Si el significado de los símbolos varía en función de la posición que ocupen en la cadena, entonces dicho sistema de numeración recibe el nombre de posicional.


información

Los ejemplos más importantes de sistemas de numeración posicionales son el decimal o de base 10, utilizado por el hombre en la cultura occidental, y el binario o de base 2, que es el que utiliza el computador para representar la información y con el que es capaz de trabajar.

Cabe mencionar que existen otros sistemas de numeración, como los sistemas de residuos, que no son posicionales pero que no se tratarán por tener menos importancia.


información

Teorema fundamental de la numeración

Supóngase una cantidad X expresada en un sistema cuya base es b, y que está representada por una cadena de dígitos { xi } donde el subíndice indica la posición de la cifra respecto a la coma en el sentido mencionado anteriormente, y donde se considera que el dígito inmediatamente a la izquierda de la coma ocupa la posición de referencia 0.


información

Entonces dicha cantidad X (de la que se desea conocer normalmente su valor decimal) se obtiene a partir de su representación mediante la fórmula:

X = Suma de i [ -infinito, infinito ] xi · bi

Asimismo, dada una cantidad X y un sistema de representación posicional de base b, existirá una única representación posible de dicha cantidad en dicha base, realizada a partir de dígitos que cumplan la condición 0 <= xi < b, para todo i.


información

SISTEMAS DE NUMERACION

Sistema decimal

Es el de base 10 y es el que entiende de modo natural el ser humano. Es, por tanto, el sistema que se utilizará como referencia para conocer las cantidades representadas en los otros sistemas de numeración. Se suponen n cifras enteras y sin signo.

Rango de representación: 0 <= X < 10^n


información

Sistema binario

Este es el sistema de numeración que utiliza el computador internamente. Este sistema de numeración es de base 2. Para convertir un número decimal a binario, se divide sucesivamente por 2, y se toman sucesivamente el último cociente y desde el último resto hasta el primero.



información

Sistema octal

Este es el sistema de numeración en base 8 y utiliza 8 símbolos para representar las cantidades. Dichos símbolos son: 0, 1, 2, 3, 4, 5, 6 y 7 y tienen el mismo significado que sus equivalentes decimales. La conversión de octal a binario se realiza mediante la siguiente tabla:


información

OCTAL 0 1 2 3 4 5 6 7

==========================================

BINARIO 000 001 010 011 100 101 110 111



información

Sistema hexadecimal

Este es el sistema de numeración en base 16 y utiliza 16 símbolos para representar las cantidades. Dichos símbolos son: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E y F. Los diez primeros son los números decimales y tienen el mismo significado que en la numeración decimal.

Los seis últimos son letras que representan: A=10, B=11, C=12, D=13, E=14 y F=15.


información

La conversión de hexadecimal a binario se realiza mediante la siguiente tabla:

HEXADECIMAL 0 1 2 3 4 5 6 7

======================================================

BINARIO 0000 0001 0010 0011 0100 0101 0110 0111

======================================================

HEXADECIMAL 8 9 A B C D E F

======================================================

BINARIO 1000 1001 1010 1011 1100 1101 1110 1111



información

Sistema binario-decimal

Los denominados códigos binario-decimales corresponden a una codificación por campos, en la que cada campo contiene el código de una cifra decimal. Como existen 10 posibles cifras decimales, del 0 al 9, cada campo deberá tener al menos 4 bits, por ser 24 = 16 > 10.

DECIMAL BCD 8421 Aiken 2421 exceso de 3 Biquinario 5421

================================================

0 0000 0000 0011 0000

1 0001 0001 0100 0001

2 0010 0010 0101 0010

3 0011 0011 0110 0011

4 0100 0100 0111 0100

5 0101 1011 1000 1000

6 0110 1100 1001 1001

7 0111 1101 1010 1010

8 1000 1110 1011 1011

9 1001 1111 1100 1100


información

ARITMETICA BINARIA

Suma Resta

0 + 0 = 0 0 - 0 = 0

0 + 1 = 1 0 - 1 = 1 *

1 + 0 = 1 1 - 0 = 1

1 + 1 = 0 * 1 - 1 = 0

* = con 1 de acarreo * = con un préstamo de 1

Multiplicación División

0 x 0 = 0 0 / 0 = Error *

0 x 1 = 0 0 / 1 = 0

1 x 0 = 0 1 / 0 = Error *

1 x 1 = 1 1 / 1 = 1

* la división por 0 no tiene sentido


información

REPRESENTACION DE NUMEROS NEGATIVOS

Módulo y signo

El cambio de signo es inmediato: sólo cambiar el bit de la izquierda.

La multiplicación y la división se tratan sin dificultad oper ndose por un lado con las magnitudes y por otro con los signos.

La posibilidad de desbordamiento al operar con sumas, restas y multiplicaciones suponen una dificultad.


información

El rango de representación es simétrico [ -2^n-1 + 1, 2^n-1 - 1 ] pero la ambigüedad de representación del 0 complica la detección de números negativos.

La extensión de signo es relativamente complicada.

Las operaciones de suma y resta se complican al depender de los signos y magnitudes de los operandos.


información

Complemento a 1

El cambio de signo se reduce al complemento lógico (cambiar ceros por unos y viceversa).

La suma es sencilla pero teniendo en cuenta que cuando aparece un acarreo a la posición n se debe incrementar en una unidad el resultado.

Se complican la multiplicación y la división, puesto que hay que considerar la posibilidad de que haya operandos complementados.


información

Existe la posibilidad de desbordamiento, que deberá detectarse al operar.

El rango de representación es simétrico [ -2^n-1 + 1, 2^n-1 - 1 ] y el cero admite dos representaciones: 00...00 o 11...11.

La extensión de signo se limita a repetir el bit de la izquierda.


información

Complemento a 2

El cambio de signo es sencillo aunque ligeramente más complicado que en el complemento a 1: realizar el complemento lógico y añadir 1.

La suma y resta son más sencillas que con el complemento a 1: consiste en realizar la suma directa.

Existe la posibilidad de desbordamiento en estas operaciones, que no debe confundirse con el acarreo superior que se elimina.


información

Se complican la multiplicación y la división, puesto que hay que considerar la posibilidad de que haya operandos complementados.

El rango de representación es asimétrico [ -2^n-1, 2^n-1 - 1 ]. Esto presenta el problema de que no se puede hacer el complemento de -2^n-1 ya que daría el mismo código, lo que se supone que es un desbordamiento. Sin embargo el cero tiene una única representación.

La extensión de signo se limita a repetir el bit de la izquierda.


información

Exceso a M

En este sistema los números se

incrementan en M y el resultado se

representa luego en binario puro.

El número X viene representado por X

+ M expresado en binario.


información

En la mayoría de los casos se hace M

= 2^n-1, donde n es el número de

bits empleados para la

representación.

Este sistema de representación se

utiliza para expresar los exponentes

en el caso de coma flotante.


información

Representación en coma flotante

El exponente se representa en el

sistema de exceso a 2^n-1, siendo

n el número de bits que se dedican

al mismo.


información

La mantisa es un número real

normalizado: sin parte entera y tal

que la primera cifra fraccionaria es

significativa.

La base de exponenciación o raíz es

una potencia de 2 determinada por

el fabricante: 2, 8 o 16.


información

Coma flotante estándar IEEE 754

• Emplea mantisa fraccionaria normalizada.

• La mantisa se representa en el sistema de módulo y signo.


información

• Utiliza el formato de precisión ampliada, valiendo siempre 1 el bit implícito.

• La coma está a la derecha del bit implícito, constituyendo dicho bit la parte entera de la mantisa.

• El exponente se representa en exceso, pero a 2^n-1 - 1 en vez de a 2^n-1, como sucedía en los casos anteriores.


información

Juego de caracteres alfanuméricos

• Las letras del alfabeto: mayúsculas y

minúsculas.

• Las 10 cifras del sistema decimal: del 0 al

9.

• Los signos de puntuación: . , : ; ? + * % ...

• Los caracteres de control: órdenes entre

dispositivos.


información

• Longitud del código binario: número de

bits utilizados para codificar un carácter.

Suele estar entre 6 y 12 bits.

• El sistema de codificación suele ser

directo.

• Número máximo de caracteres distintos

que se pueden representar con la longitud

de código anteriormente definida:

2^longitud .

parte ii - ecotec€¦ · leyes del Álgebra de boole por tanto, habrá que aplicar un Álgebra de...

Documents