Download (A`+B`+C) · (A`+B+C`) · (A`+B+C) · (A+B`+C`) · (A+B+C)

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.
Lógica de proposiciones
Proposiciones
Formalmente, se define una
proposición
como
un
enunciado declarativo que
puede ser verdadero o falso,
pero no ambos a la vez.
Lógica de proposiciones
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.
Lógica de proposiciones
• 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.
Lógica de proposiciones
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.
Lógica de proposiciones
• 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.
Lógica de proposiciones
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.
Lógica de proposiciones
• 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.
Lógica de proposiciones
Conectivas
Las conectivas se dividen por su aplicación
en:
• Singulares: se aplican a una única
sentencia.
• Binarias: se aplican a dos sentencias.
Lógica de proposiciones
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.
Lógica de proposiciones
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.
Lógica de proposiciones
SEMANTICA
Negación (NO)
Consiste en cambiar el valor de verdad de una
variable proposicional.
p NO p
========
V
F
F
V
Lógica de proposiciones
Disyunción inclusiva (O)
La sentencia será verdadera cuando una o
ambas variables proposicionales sean
verdaderas.
p q
pOq
=============
V V
V
V F
V
F V
V
F F
F
Lógica de proposiciones
Conjunción (Y)
Es una conectiva definida por:
p Y q = NO ( NO p O NO q )
Lógica de proposiciones
La sentencia será verdadera sólo cuando ambas
variables proposicionales sean verdaderas.
p q
pYq
=============
V V
V
V F
F
F V
F
F F
F
Lógica de proposiciones
Condicional (SI ... ENTONCES)
Es una conectiva definida por:
p COND q = NO p O q
Lógica de proposiciones
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
Lógica de proposiciones
Bicondicional (... SI Y SOLO SI ...)
Es una conectiva definida por:
p BICOND q = ( ( p COND q ) Y ( Q COND p ) )
Lógica de proposiciones
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
Lógica de proposiciones
Disyunción exclusiva (O ... O)
Es una conectiva definida por:
p EXCL q = NO ( p BICOND q )
Lógica de proposiciones
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
Lógica de proposiciones
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 ) ]
Lógica de proposiciones
A partir de estos axiomas y
aplicando las dos reglas de
transformación siguientes se
puede demostrar cualquier
teorema:
Lógica de proposiciones
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.
Lógica de proposiciones
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.
Lógica de proposiciones
• 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"
Leyes del Álgebra de
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.
Leyes del Álgebra de
Boole
Definiciones básicas
Se
comenzará el estudio del Álgebra
introduciendo el concepto de clase.
de
Boole
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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:
AOB
Leyes del Álgebra de
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:
AYB
Leyes del Álgebra de
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.
Leyes del Álgebra de
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)
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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.
Leyes del Álgebra de
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
Leyes del Álgebra de
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'
Leyes del Álgebra de
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.
Leyes del Álgebra de
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
funciones
la
descomposición
de
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
maxterms
entre
minterms
y
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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,
un sistema de numeración y con
número de cifras determinado n,
conjunto de cantidades representables
el mismo.
en
un
al
en
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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
Representación de la
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.
Rango de representación: 0 <= X < 2^n
Representación de la
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:
Representación de la
información
OCTAL
0
1
2
3
4
5
6
7
==========================================
BINARIO 000 001 010 011 100 101 110 111
Rango de representación: 0 <= X < 8^n
Representación de la
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.
Representación de la
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
Rango de representación: 0 <= X < 16^n
Representación de la
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
Representación de la
información
ARITMETICA BINARIA
Suma
0+0=0
0+1=1
1+0=1
1+1=0*
* = con 1 de acarreo
Resta
0-0=0
0-1=1*
1-0=1
1-1=0
* = con un préstamo de 1
Multiplicación
0x0=0
0x1=0
1x0=0
1x1=1
División
0 / 0 = Error *
0/1=0
1 / 0 = Error *
1/1=1
* la división por 0 no tiene sentido
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
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.
Representación de la
información
Coma flotante estándar IEEE 754
• Emplea mantisa fraccionaria normalizada.
• La mantisa se representa en el sistema
de módulo y signo.
Representación de la
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.
Representación de la
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.
Representación de la
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 .