.png)
.png)
LINK AL CUADERNO CON TODA LA INFORMACIÓN DEL CAPITULO:
https://notebooklm.google.com/notebook/ea81783d-eeee-41e3-9269-0dd576b7e5fb
Formas canónicas.
Dada una función del AB, tenemos dos formas de describirla, de referirnos a ella, de definirla…
Por extensión y por comprensión.
Las funciones son un tipo especial de relaciones. Las relaciones son un subconjunto del producto cartesiano. Entonces las funciones son conjuntos.
Los conjuntos se pueden dar por extensión o por comprensión y por lo tanto las funciones también.
Por extensión es cuando damos su tabla de verdad.
Por ejemplo damos f, arbitrariamente, f(a,b) tal que
f(0,0)=1
f(0,1)=0
f(1,0)=0
f(1,1)=1
Por comprensión es cuando la indicamos a partir de la composición de los operadores básicos del álgebra.
Por ejemplo g(a,b,c)= a + /b + c
Notar que estamos introduciendo una notación funcional, con lo cual estamos trabajando con funciones dentro del AB. Funciones que toman tuplas de valores Booleanos y devuelven algún Booleano.
Lo hacemos con total naturalidad…
Si nos dan una función, por comprensión, podemos llevarla a su notación por extensión.
¿Cómo lo hacemos?
Por medio de la tabla de verdad.
Sea g una función que damos arbitrariamente:
g(a,b,c)= a + /b +c
Para darla por extensión, hacemos su tabla de verdad:
a b c g = a + /b + c
000 1
001 1
010 0
011 1
100 1
101 1
110 1
111 1
Aquí, con la tabla de verdad, g queda dada por extensión
Ahora vamos por el problema inverso.
Dada una función por extensión, cómo hacemos para escribirla por comprensión.
O sea, dada la tabla como armamos la fórmula…
Este método es el de las FORMAS CANONICAS. Veremos otro también, el MÉTODO DE KARNAUGH, que nos lleva a la expresión más simple de una función del AB.
Las formas canónicas son un método rápido y sencillo, pero que NO NECESARIAMENTE (y habitualmente NO lo hacen) llevan a la forma más simple.
“Más simple” es la expresión que no tiene nada por simplificar.
Por ejemplo si aparece ab+/ab sabemos que eso es b… sin embargo la primera es canónica y la segunda no…
Formas Canónicas
Observemos la siguiente tabla de verdad:
Notamos que estos términos que tienen todas las variables, comunes o negadas, tienen una particularidad, y es que son 0 en todas las líneas menos una.
Estos términos se llaman CANONICOS. Su característica es tener todas las variables, ya sea sin negar o negada. Y generan un solo UNO en la tabla, siendo CERO el resto.
Entonces, dada una tabla de verdad cualquiera, nosotros podemos razonar AL REVES, y expresarla como suma de términos canónicos…
Entonces dada f por su tabla de verdad, la descompongo como suma de términos canónicos, y por lo tanto f(a,b,c,)=abc+/a/b/c+a/bc+/abc
Y decimos que en este caso f está en su PRIMERA FORMA CANONICA.
Esta forma, tal como vemos, dista mucho de ser la más simple. Y habría que simplificarla, o bien por KARNAUGH o bien usando propiedades.
Cómo exactamente miramos la construcción de cada término canónico ?
Si la variable está en 1, va como está, y si está en 0, va negada.
Por ejemplo, 0 0 0 produce un 1, entonces es: /a./b./c
Ejercicio
Dada f(a,b,c) / f(0,0,1)=1 , f(1,1,0)=1 y f(1,1,1)=1 y en todo otro caso da 0… hallar la tabla de verdad de f, y su primera forma canónica.
Entonces f(a,b,c)= /a/bc+ab/c+abc es la primera forma canónica.
Segunda forma canónica:
f(a,b,c)=(a+b+c).(a+/b+c).(a+/b+/c).(/a+b+c).(/a+b+/c)
Principio de dualidad
Todo en el AB guarda simetría entre el 0 y el 1. Por qué? Porque las funciones base de la definición del álgebra la tienen.
Vale el siguiente principio de dualidad:
Sea E un enunciado del álgebra.
Construimos E’, el cual diremos es su dual, sustituyendo 0 por 1, 1 por 0, + por . y . por +
Entonces se cumple que: E’ es válido sii E es válido.
Por ejemplo, sabemos que: a.1=a
Entonces, por dualidad, a+0=a
Otro ejemplo, sabemos que /(a+b)=/a./b
Entonces, por dualidad, /(a.b)=/a + /b
Entonces, vamos a ver que la primera forma canónica tiene un dual, que es la SEGUNDA FORMA CANONICA o PRODUCTO DE SUMAS.
Segunda forma canónica: producto de sumas canónicas
Tomamos todos los CEROS y por cada uno de ellos armamos un término canónico, basado en sumas, donde cada variable que aparezca en 0, aparece sin negar, y cada variable que aparezca en 1, aparece negada. Luego multiplicamos esos términos.
Ejemplo
Entonces tenemos
f(a,b,c)=(a+b+c).(a+/b+c).(a+/b+/c).(/a+b+c).(/a+b+/c)
ATENCION CON ESTO
REVISEMOS ESTE RAZONAMIENTO
a+b.c+/a.c = por dualidad = a.(b+c).(/a+c)
¿ VÁLIDO O NO ?
a+b=por dualidad=a.b
NOOOOOO NO ES VALIDO Y EL PRINCIPIO DE DUALIDAD NO DICE ESO!
Ejemplo de aplicación correcta del principio:
Como a+b=b+a entonces a.b=b.a
Pero no dice a+b=a.b….
El principio de dualidad plantea una igualdad entre enunciados.
Otro ejemplo, de una forma SI correcta:
a+b+/c= doble negación
=/ ( / (a+b+/c)) = de Morgan
=/ (/a . /b . //c)=doble negación
=/(/a./b.c)
Notación sigma y pi
Esta es una forma abreviada de dar la tabla de verdad, es decir, de dar la función por extensión.
Para decir donde la función vale 1 (y por lo tanto, se deduce que donde no vale 1, vale 0) usamos la notación sigma.
En forma dual usamos la notación pi. Es decir, nos indica dónde la función vale 0.
Los lugares se numeran desde el cero.
Ejemplo:
Observación: Cantidad mínima de variables
Cuando no se especifica, tomamos la cantidad mínima de variables, que cumpla lo pedido.
Así, por ejemplo g=pi(0,4,6,7) tendrá 3 variables y será g(a,b,c)=pi(0,4,6,7).
Así, por ejemplo h=sigma(2,3,8) tendrá 4 variables y será g(a,b,c,d)=sigma(2,3,8).
Entonces, atención:
f=pi(0,4,6,7)=f(a,b,c)
PERO
f’(a,b,c,d)=pi(0,4,6,7) también es válida y es una función ABSOLUTAMENTE DIFERENTE
ASÍ COMO
f’’(a,b)=pi(0,4,6,7) NO TIENE SENTIDO
Cómo sabemos cuál es la cantidad mínima de variables…?
Si refieren hasta el 1, es una.
Si refieren hasta el 3, es dos.
Si refieren hasta el 7, es tres.
SI refieren hasta el 15, es cuatro variables.
Y así sucesivamente.
Ejemplo
f=pi(0,4,6,7)=f(a,b,c)=sigma(1,2,3,5)
Y
f’(a,b,c,d)=pi(0,4,6,7)=sigma(1,2,3,5,8,9,10,11,12,13,14,15)
Ejemplo
g=pi(0,4,6,7)=g(a,b,c)=sigma(1,2,3,5)
Cuando no me dicen la cantidad de variables, TOMAMOS LA MINIMA CANTIDAD QUE CUMPLA.
Para ordenarnos… tenemos:
Las funciones, dadas por extensión, se dan por su tabla de verdad. La misma se puede escribir en forma total, como tabla, o con notación sigma o pi.
Las funciones, dadas por comprensión, se dan con una fórmula. La misma puede ser simplificada por aplicación de propiedades, o por Karnaugh, lo cual veremos la clase próxima.
Si me dan la función por comprensión, hago la tabla y la obtengo por extensión.
Si me dan la función por extensión, aplico formas canónicas (o Karnaugh) y la obtengo por comprensión.
Ejercicio
Dada f=sigma(1,3,7) calcular su notación pi, su tabla de verdad, y sus formas canónicas.
f=f(a,b,c)=sigma(1,3,7)=pi(0,2,4,5,6)
f=/a./b.c+/a.b.c+a.b.c=(a+b+c).(a+/b+c).(/a+b+c).(/a+b+/c).(/a+/b+c)
Práctico
1)
a)
(a+/b+ab)(a+/b)(/ab)= asociativa= (a+/b+ab)((a+/b)(/ab))=distributiva=(a+/b+ab)(a/ab+/b/ab)=
=asoc producto, x/x=0, conmutat producto=(a+/b+ab)(0b+0a)=
Aplico 0.x=0 y 0+0=0
=(a+/b+ab)(0)=
Aplico x.0=0
=0
QED
b)
(a+/b+a/b)(ab+/ac+bc)= absorción y conmutativa=
=(a+/b)(ab+/ac+bc)=distributiva=
=aab+a/ac+abc+/bab+/b/ac+ /bbc= X.X=X X/X=0 X+0=X asoc conmu
=ab +abc +/a/bc= absorción = ab+/a/bc
QED
c)
(ab+c+d)(/c+d)(/c+d+e)= absorción dual X+XY=X….. X(X+Y)=X
=(ab+c+d)(/c+d)=distributiva=
=ab/c+c/c+d/c+abd+cd+dd= X./X=0 X+0=X X.X=X
=ab/c+d/c+abd+cd+d = absorción 3 veces=
=ab/c+d
QEDb
d)
/a(/b/c+/((b+/c)(/b+/c))) = de Morgan=
=/a(/b/c+ /(b+/c)+/(/b+/c)) )= de Morgan y //X=X =
=/a(/b/c+ /bc+bc )= factor común =
=/a(/b/c+c(b+/b))= X+/X=1
= /a(/b/c+c) = X+/XY=X+Y=
=/a(/b+c)
QED
Otra forma de hallar las formas canónicas.
Dada f(a,b,c)=a+bc
Puedo calcular la primera forma canónica, haciendo el razonamiento “enriqueciendo” los términos.
Usando que X=X1=X(Y+/Y)=XY+X/Y
f=a+bc= ab+a/b + bc=abc+ab/c+a/bc+a/b/c+abc+/abc= tacho repetidos=
= abc+ab/c+a/bc+a/b/c+/abc primera forma canónica.
Yo puedo sacar la tabla, mirando los productos canónicos:
Sabemos que la función es 1 en
111 110 101 100 011
Entonces la función es 0 en:
000 001 010
Con lo cual la segunda forma canónica es
f=(a+b+c)(a+b+/c)(0+/b+c)
Calcular las formas canónicas de g(ab)=a
g(a,b)=a=ab+a/b
Se hace 1 en 11 y 10
Entonces se hace 0 en 00 y 01
g(a,b)=(a+b).(a+/b)
Para ordenarnos… tenemos:
Las funciones, dadas por extensión, se dan por su tabla de verdad. La misma se puede escribir en forma total, como tabla, o con notación sigma o pi.
Las funciones, dadas por comprensión, se dan con una fórmula. La misma puede ser simplificada por aplicación de propiedades, o por Karnaugh, lo cual veremos ahora.
Si me dan la función por comprensión, hago la tabla y la obtengo por extensión.
Si me dan la función por extensión, aplico formas canónicas (o Karnaugh) y la obtengo por comprensión.
Ejercicio
Dada f=sigma(1,3,7) calcular su notación pi, su tabla de verdad, y sus formas canónicas.
f=f(a,b,c)=sigma(1,3,7)=pi(0,2,4,5,6)
f=/a./b.c+/a.b.c+a.b.c=(a+b+c).(a+/b+c).(/a+b+c).(/a+b+/c).(/a+/b+c)
EL METODO DE KARNAUGH
Lo vamos a ver para dimensión 2, 3 y 4, es decir para esos números de variables. PERO es extensible a más variables.
Lo primero que hacemos es identificar el mapa según la cantidad de variables. 2, 3 o 4
Lo segundo que necesitamos es numerar la tabla de verdad.
Permite simplificar funciones de forma “automática”, sin aplicar propiedades.
El método consiste en:
- Obtener la tabla de verdad
- Ponerla dentro de un esquema llamado mapa
- Construir los rectángulos
- Decodificar los rectángulos
Lo explicaremos a través de ejemplos.
Si bien, es posible razonarlo para más variables, lo trabajaremos en 2,3 y 4 variables.
Para 2 variables.
Ejemplo
Cubrimos los 1s o los 0s (a elección) de modo de lograr rectángulos de largos y anchos que sean potencias de 2.
Los rectángulos deben ser lo más grandes posible.
Desarmamos el rectángulo, se incluyen las variables del rectángulo que NO varían:
Como en este caso, la constante que se cumple en el rectángulo es b=0, entonces ponemos /b
f(a,b)=/b
Si levanto los 1s, obtengo suma de productos, si levanto los 0s, obtengo producto de sumas.
Ejemplo
g(a,b)=pi(0,3)
En el primer rectángulo a y b fijos, a=1 y b=0 entonces es a./b
g(a,b)=a./b + /a.b
En forma dual, levantemos los 0’s:
En 3 variables
Ahora los rectángulos podrán tener largo y ancho 1,2 o 4.
Ejemplo
f=sigma(1,2,5,7)
Ejemplo
g(a,b,c)=sigma(0,1,2,3,4,6)
En 4 variables
Ejemplo
f(a,b,c,d)=pi(0,2,4,6,8,10,12,14)
g(a,b,c,d)=sigma(1,3,5,6,7,8,9,14)
Simplificar por medio del método de Karnaugh la función f=a+ab+abc+abcd
Forma 1
Hacemos la tabla de verdad
abcd f
0000 0
0001 0
0010 0
0011 0
0100 0
0101 0
0110 0
0111 0
1000 1
1001 1
1010 1
1011 1
1100 1
1101 1
1110 1
1111 1
La ponemos en el mapa
f(a,b,c,d)=a
Además sabíamos que aplicando absorción, eso daba a.
Forma 2
Sin pasar por la tabla de verdad
Tenemos f(a,b,c,d)=a+ab+abc+abcd
Ejemplo
Simplificar
f(a,b,c)= ab+a/b+abc+a/bc+ac+a/c
Ejemplo de Karnaugh
g=sigma(0,2,8,10)
Este es un caso particular.
Práctico de Karnaugh
Ejercicio 1
a)
f=Σ(0,1,2,4)
b)
f=π(1,2,4,7)
c) f=
2)
F=bd+/b/d
b)
3)
4)
Al darme esta expresión, me están dando la forma canónica y de ella saco la tabla.
ii)
/x+/y significa que x=1 e y=1
/w+/x+y significa w=1 x=1 y=0
/w+x+z significa w=1 x=0 z=0
5)
Las X son don’t cares, y pueden valer cualquier cosa, según me convenga.
Los haremos valer 0 o 1 para maximizar el tamaño de los rectángulos.
Esta función cumple lo pedido.
Método de Karnaugh
Permite simplificar funciones de forma “automática”, sin aplicar propiedades.
El método consiste en:
- Obtener la tabla de verdad
- Ponerla dentro de un esquema llamado mapa
- Construir los rectángulos
- Decodificar los rectángulos
Lo explicaremos a través de ejemplos.
Si bien, es posible razonarlo para más variables, lo trabajaremos en 2,3 y 4 variables.
Para 2 variables.
Ejemplo
Cubrimos los 1s o los 0s (a elección) de modo de lograr rectángulos de largos y anchos que sean potencias de 2.
Desarmamos el rectángulo, se incluyen las variables del rectángulo que NO varían:
Como en este caso, la constante que se cumple en el rectángulo es b=0, entonces ponemos /b
f(a,b)=/b
Si levanto los 1s, obtengo suma de productos, si levanto los 0s, obtengo producto de sumas.
Ejemplo
g(a,b)=pi(0,3)
En el primer rectángulo a y b fijos, a=1 y b=0 entonces es a./b
g(a,b)=a./b + /a.b
En forma dual, levantemos los 0’s:
En 3 variables
Ahora los rectángulos podrán tener largo y ancho 1,2 o 4.
Ejemplo
f=sigma(1,2,5,7)
Ejemplo
g(a,b,c)=sigma(0,1,2,3,4,6)
En 4 variables
Ejemplo
f(a,b,c,d)=pi(0,2,4,6,8,10,12,14)
g(a,b,c,d)=sigma(1,3,5,6,7,8,9,14)
Simplificar por medio del método de Karnaugh la función f=a+ab+abc+abcd
Forma 1
Hacemos la tabla de verdad
abcd f
0000 0
0001 0
0010 0
0011 0
0100 0
0101 0
0110 0
0111 0
1000 1
1001 1
1010 1
1011 1
1100 1
1101 1
1110 1
1111 1
La ponemos en el mapa
f(a,b,c,d)=a
Además sabíamos que aplicando absorción, eso daba a.
Forma 2
Sin pasar por la tabla de verdad
Tenemos f(a,b,c,d)=a+ab+abc+abcd
Ejemplo
Simplificar
f(a,b,c)= ab+a/b+abc+a/bc+ac+a/c
Un ejemplo de implementación del Algebra de Boole en lenguaje funcional HASKELL
Un código Haskell para el método de Karnaugh
Aplicándolo a un ejemplo concreto
Supongamos que tenemos la siguiente función booleana:
F(A, B, C, D) = Σ(0, 1, 3, 5, 7, 8, 9, 10, 11, 15)
Queremos simplificar esta función utilizando el método de Karnaugh.
Primero, creamos un mapa de Karnaugh con las entradas apropiadas, donde las entradas son las combinaciones de valores de verdad para las variables A, B, C y D:
AB\CD 00 01 11 1000 | 1 | 1 | 0 | 001 | 1 | 0 | 0 | 111 | 0 | 0 | 1 | 110 | 1 | 0 | 0 | 0
Cada celda del mapa de Karnaugh representa el valor de verdad de la función booleana en una combinación particular de valores de entrada. Las celdas activas (donde la función booleana es verdadera) están marcadas con 1, y las celdas inactivas (donde la función booleana es falsa) están marcadas con 0.
Luego, pasamos este mapa de Karnaugh a nuestra función simplifyKMap. Aunque la función simplifyKMap actualmente simplemente devuelve el mapa de Karnaugh original, en una implementación completa, esta función simplificaría el mapa de Karnaugh para encontrar la expresión booleana más simple que es equivalente a la función original.
Ahora, veamos cómo se implementaría esto en Haskell:
module Main where-- Representación de un mapa de Karnaughtype KMap = [[Bool]]-- Función para simplificar una expresión booleana utilizando el método de KarnaughsimplifyKMap :: KMap -> StringsimplifyKMap kmap = "Expresión simplificada utilizando Karnaugh: " ++ show kmap -- Implementación pendiente-- Función para dibujar un mapa de KarnaughdrawKMap :: KMap -> StringdrawKMap kmap = unlines $ map (concatMap (\b -> if b then "1" else "0")) kmap-- Ejemplo de usomain :: IO ()main = doputStrLn "Ejemplo de Simplificación con Mapa de Karnaugh:"let exampleKMap = [[True, True, False, False],[True, False, False, True],[False, False, True, True],[True, False, False, False]]putStrLn "Mapa de Karnaugh:"putStrLn (drawKMap exampleKMap)putStrLn $ simplifyKMap exampleKMap
.png)
.png)
No hay comentarios:
Publicar un comentario