Diagramas de Bloques

Automatización y Control de Sistemas Dinámicos
Laboratorio: Entrada 3

Simplifique el diagrama de bloques que aparece en la imagen y obtenga la función de transferencia en lazo cerrado C(s)/R(s).

El siguiente diagrama de bloques es el original del problema, y mediante reglas del álgebra de bloques iré simplificando paso por paso el diagrama completo hasta dejar un solo bloque con la función de transferencia completa.

Teoría básica de Diagrama de Bloques

Un sistema de control suele estar compuesto de varios componentes, y cada uno de estos componentes lleva acabo una función. Para representar un sistema de control usamos un diagrama de bloques.

El diagrama de bloques es una representación gráfica donde podemos ver la relaciones que existen entre un componente y otro. Contiene información del comportamiento dinámico, pero no de la construcción física del sistema.

En el diagrama de bloques tenemos los llamados bloques funcionales donde se coloca algún símbolo para representar alguna función matemática dentro del sistema.

Tomando en cuenta el diagrama presentado al inicio podemos observar algunas funciones denominadas G y también algunas H, que suelen ser funciones de transferencia, para convertir la salida de datos, de alguna unidad a otra.

Las flechas indican hacia donde va el flujo, y se les conoce como señales.

Los círculos con signos positivos (+) y negativos (-), son puntos de suma y el lugar donde una línea se divide en más de una flecha se llama punto de ramificación.

Un diagrama de bloques con varios lazos de retroalimentación se puede simplificar mediante un reordenamiento de los bloques mediante reglas del álgebra de diagramas de bloque.

"Al simplificar un diagrama de bloques:
1. El producto de las funciones de transferencia en la dirección de la trayectoria directa debe ser el mismo.
2. El producto de las funciones de transferencia alrededor del lazo debe ser el mismo." [1]

En cuanto a las reglas del álgebra de diagramas de bloque, les dejo un PDF donde están todas las reglas necesarias para simplificar un diagrama como el que les mostré al inicio.

Tabla de Diagramas de Bloque

Simplificación de Diagrama de Bloques

Tenemos el diagrama de bloques como en la imagen al inicio de esta publicación. Es más fácil ir simplificando desde las partes más internas del diagrama.

La parte que tenemos encerrada en un cuadro rojo no tendrá un cambio algebraico, solo será un movimiento hacia la derecha, cambiando de orden con su vecino próximo. Esto no afecta en absoluto al sistema, ya que en los dos puntos de suma tenemos entrada de datos con signo negativo, y si se hace primero uno u otro no importa siempre y cuando sea antes del bloque G2.

La parte que si sufre un cambio es la encerrada en el círculo rojo. Ahí estamos cambiando la línea de entrada de H1, de antes de G2, a después de G2.

Para este cambio podemos demostrar mediante álgebra que no se ha desestabilizado el sistema.

Podemos ver que después del cambio, la salida de la flecha en ese punto será la misma que antes, solo que escrita de diferente forma.

En la siguiente imagen podemos ver ya los cambios plasmados en el diagrama de bloques. Pero aún nos falta seguir simplificando.

Ahora tenemos marcadas otras dos secciones de nuestro diagrama que vamos a simplificar, mediante las reglas proporcionadas en las tablas de las reglas para diagrama de bloques.

El recuadro rojo, se hace una unión entre nuestra G2 y H2, mientras que en el recuadro naranja tenemos una reducción de elementos.

Veamos como queda esta simplificación en la siguiente imagen. Y como podemos ver el diagrama poco a poco ha sido reducido.

Si notaron en este caso, el punto de suma que se había encerrado en el recuadro rojo, lo que se tiene es un signo negativo, y al aplicarlo en el bloque pasan los elementos con signo positivo. Esto se explica a detalle en el libro, y pasa porque en realidad el denominador es 1-(la sumatoria de los elementos), donde los elementos tienen signo negativo porque así lo marca el punto de suma, entonces al multiplicar este signo negativo por los elementos también con signo negativo, todos pasan a ser positivos en la función del bloque.

La siguiente parte más fácil de simplificar es la que tenemos en serie, y tenemos marcada en un rectángulo rojo en la siguiente imagen.

Cuando se tienen elementos en serie, tal y como en nuestro caso, las reglas nos dicen que hay que hacer una multiplicación de los elementos.

Este resultado lo colocamos en un bloque completo y el diagrama queda como se muestra a continuación.

Ahora vamos a simplificar esta sección marcada en rojo. Tenemos una retroalimentación del bloque grande y que pasa por la función de transferencia H3.

Para esto, según la reglas establecida, tenemos que dividir el bloque que tenemos de la simplificación anterior, entre 1 más la H3 que multiplica a ese mismo bloque. Veamos como se hace esta operación.

Y después de aplicar este cambio nos queda el siguiente diagrama.

La sección marcada con rojo, como en un caso anterior, se encuentra en serie, lo que implica una multiplicación de los dos bloques.

Como el bloque de G1 no tiene denominador, solo se multiplica este término en el numerador del siguiente bloque, y nos debe de quedar como sigue.

Y solo falta simplificar el último punto de suma, donde la misma salida retroalimenta de nuevo al sistema. Esta parte es simple, ya que las reglas de diagramas de bloque muestran que para esta última sección hacemos que el numerador del bloque, se sume al denominador.

Después de esto nuestro diagrama de bloques queda simplificado de la siguiente manera.

Y con esto podemos escribir nuestra función de transferencia en lazo cerrado que queda así:

Fuente consultada:
[1] - Ingeniería de Control Moderna, 3ra. edición, Katsuhiko Ogata, página 69.

Transformada de Laplace

Automatización y Control de Sistemas Dinámicos
Laboratorio: Entrada 2

En esta semana tuvimos un repaso de las transformadas de Laplace, así que para la segunda publicación de laboratorio, seleccionamos un problema del libro de Control de Sistemas Dinámicos, evidentemente relacionado con las transformadas de Laplace, y la tarea es contestarlo mediante definición de la transformada.

Como en mi problema tenía dos incisos, aproveche de hacer uno con la definición de la transformada de Laplace y el segundo un poco más directo mediante la ayuda de un formulario, y que aún así era necesario hacer algunos pasos extras por tratarse de un problema donde se tenía que utilizar la derivada de la función de F(s), para poder aplicarlo a la fórmula.

Al final se encuentra el documento que realicé para esta publicación, ya que ahí se puede ver un poco más claro la explicación y la secuencia de pasos.

Pero primero veamos como se define la transformada y después pasamos al problema resuelto.

Definición de Transformada de Laplace

"Sea f una función definida para t>= 0. Entonces la integral

se llama Transformada de Laplace de f, siempre y cuando la integral converja. Cuando la integral definitoria converge, el resultado es una función de s. Esta transformada integral tiene una serie de propiedades que la hacen útil en el análisis de sistemas lineales. Una de las ventajas más significativas radica en que la integración y derivación se convierten en multiplicación y división. Esto transforma las ecuaciones diferenciales e integrales en ecuaciones polinómicas, mucho más fáciles de resolver. Otra aplicación importante en los sistemas lineales es el cálculo de la señal de salida. Ésta se puede calcular mediante la convolución de la respuesta impulsiva del sistema con la señal de entrada. La realización de este cálculo en el espacio de Laplace convierte la convolución en una multiplicación, habitualmente más sencilla." [1]

Problema 1

Obtenga la transformada de la siguiente función.

Para empezar necesitamos pasar la función dada a una función más simple con la que podamos trabajar a lo largo del problema. Para esto tenemos una identidad trigonométrica que no ayudará a simplificar.

Vemos que lo que queda del lado derecho es la estructura de la función que enuncia el problema dado, veamos como queda al sustituir la u por nuestro wt.

Ahora podemos usar la parte izquierda de la función ya que es lo mismo que trabajar con la parte derecha, pero esta nos facilitará las cosas.

Y ahora veamos la definición de la Transformada de Laplace, que ya había mencionado unos párrafos más arriba.

Esta nos dice que la integral de cero a infinito del exponente e elevado a la -st y que multiplica a la función F(t), nos da como resultado la transformada de Laplace.

En los pasos anteriores podemos notar como la función que tenemos como F(t) se sustituye en la definición de la transformada. Luego se saca el 1/2 fuera de la integral por ser términos constantes, y luego procedemos a obtener la integral.

Para esto hacemos uso de la siguiente.

Y que en términos de nuestra función nos queda lo siguiente.

Ahora ya podemos sustituir los valores de b y 0.

La primer parte se elimina totalmente con solo saber que e elevado al infinito nos resulta cero, y toda esa parte se cancela. Solo nos queda por simplificar la otra parte.

Ya una vez simplificado todo lo posible podemos concluir con el siguiente resultado.

Nota: En el documento anexado al final, podrán ver como se resolvió también mediante la fórmula propuesta en un formulario.

Para corroborar el resultado obtenido, se probó con Wolfram Alpha. El resultado fue el mismo y además nos muestran una gráfica de la función resultante.

Problema 2

Ahora tenemos la siguiente función, y vamos a obtener su transformada de Laplace.

Esta vez resolveremos de una forma más sencilla que es utilizando la siguiente definición que se acopla a la función con la que estamos trabajando.

Así que para poder aplicarla primero tenemos que sacar la transformada de F(t) de la función principal, dejando fuera la t.

Ya que tenemos F(s), lo que sigue es obtener su primer derivada.

Comparar derivada con resultado de Wolfram.

Y con la primer derivada ya podemos hacer uso de la definición que nos ayudará a llegar al resultado mucho más rápido. Así que sustituimos la primer derivada de F(s) y luego simplificamos.

Y por último tenemos formalmente el resultado de la transformada de Laplace de la función dada al inicio del problema 2.

Esta también se verificó desde Wolfram Alpha para corroborar que el resultado es correcto y se obtuvo de la misma página la gráfica de la función.

Comparar transformada con Wolfram

La entrada originalmente era solamente un documento que creé, pero luego pensé en ser un poco más especifico en unos pasos, por lo que el siguiente documento es la resolución de los problemas ya planteados, pero con explicación más simple y además esta disponible para descargar en PDF.

Transformada De Laplace

Páginas consultadas:
[1] Definición de la Transformada de Laplace

Diffie-Hellman Key Exchange

Seguridad de la Información y Criptografía
Homework 3

For this week, the homework is:
Hack manually (pencil and paper) a very-short keyed Diffie-Hellman of your choice.

Definition of Diffie–Hellman Key Exchange

Diffie–Hellman key exchange is a specific method of exchanging cryptographic keys. It is one of the earliest practical examples of key exchange implemented within the field of cryptography. The Diffie–Hellman key exchange method allows two parties that have no prior knowledge of each other to jointly establish a shared secret key over an insecure communications channel. This key can then be used to encrypt subsequent communications using a symmetric key cipher. [1]

In the next image we can see how is the channel of communication between Alice and Bob, and like our next example, if we are another person named Eve, we can get the g, p, A, B, and try to hack they key.

[http://upload.wikimedia.org/wikipedia/commons/a/a3/Diffie-Hellman-Schl%C3%BCsselaustausch.png?uselang=es]

My Hacking

Like the example of the image, we have one of our classmates that represents "Alice" and other who is "Bob", I will be "Eve".

Here is the screenshot from Facebook where my classmates published the p, g, X, Y, and I need to get the x and y, and then a key k.

I did the hack manually in my notebook, here is a capture.

If you check in the image, I started doing divisions only changing the dividend per a potency of 10 with n, where n start with one and increment in each division, when I finish the fourth division I noticed that in the dividend is only necessary to add a zero, so I did a big division, in the right of the paper I wrote a table, and in the first column I put the number of n, that represents x and y, and the second column is the result of (10^n)mod(19).

When I tried the potency of 17 and 18, I found the same X and Y that my classmates wrote in the publication in Facebook, so I check if the two numbers, one for x, and the other for y, give me the same key k.

I get x=17, y=18 and k=1.

Then I posted the x, y and the k, in a comment in the same post, and my classmates, verify if I was correct, and yes, I was correct.

After that, I did a program that do the same thing that I did manually, isn't a method that found the key when someone use this protocol, is only a sequential program that increment x and y, and verify if are the correct values for get the correct key.

Here is the code:


An example of the execution in the terminal, with the same p, g, X, Y, of the example that I did manually.

I get the same x, y, and the k, that I found doing it manually, so it seems to work well.

References:
[1] - Diffie-Hellman Protocol

Diagrama de Decisión Binario

Verificación y Validación de Software
Entrada 4

¿Qué es un BDD y un ROBDD?

Un Diagrama de Decisión Binario (Binary Decision Diagram o BDD) es un grafo acíclico dirigido con: (a) Uno o dos nodos terminales etiquetados con 0 o 1. (b) Un conjunto de nodos variables con dos hijos. Cada nodo variable está etiquetado con un símbolo proposicional. [1]

Otro término relacionado con los diagramas de decisión son el Diagrama de Decisión Binario Reducido Ordenado (Reduced Ordered Binary Decision Diagram o ROBDD). Una ventaja de un ROBDD es que es único para una función particular y un orden de variables. Esta propiedad es útil por ejemplo en la verificación de funciones de equivalencia. [2]

Reducir un BDD a un ROBDD

Las instrucciones que se nos dieron de tarea para esta publicación, fueron las siguientes.

1. Inventen una expresión Booleana (usando por mínimo 3 variables y 4 conectivos básicos).
2. Construyan y dibujen su BDD.
3. Reduzcan el BDD resultante a un ROBDD.
4. Dibujen el ROBDD resultante.

Expresión Booleana

[(A∧D) ∧ (¬B∧¬D)] ∨ (B∨C)

Tabla de verdad

Con la tabla de verdad obtendremos los valores de salida para cada nodo al final del diagrama.

A	B	C	D	[(A∧D) ∧ (¬B∧¬D)] ∨ (B∨C)
0	0	0	0	0
0	0	0	1	0
0	0	1	0	1
0	0	1	1	1
0	1	0	0	1
0	1	0	1	1
0	1	1	0	1
0	1	1	1	1
1	0	0	0	0
1	0	0	1	0
1	0	1	0	1
1	0	1	1	1
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

Para no tardar en hacer paso por paso la tabla de verdad, utilice de nuevo el programa en python para obtener la salida final de la tabla de verdad y que ya he usado en las tareas anteriores.


Dibujo del BDD

Ahora dibujamos el diagrama de decisión con las salidas obtenidas en la tabla de verdad.

La reducción la hice por pasos iniciando desde abajo del diagrama. En este caso vemos que las salidas de 0 o 1 en los nodos marcados como D, fueron simplificados dejando solo una salida por cada uno de ellos, ya que eso era posible al tener pares de ceros y unos.

Ahora subiendo al nivel de C, podemos eliminar todas los nodos en D que están repetidos, y las líneas que surgen de C dirigen solo a un nodo D, ya que tiene la misma salida.

Ahora al subir a los nodos B, podemos notar a simple vista que todo los nodos bajo ellos son iguales, por lo que podemos eliminar una rama completa y unir la línea que queda libre en el nodo A hacia el B que dejamos.

Con esto ya tenemos nuestro diagrama de decisión binario reducido y ordenado.

Dibujo del ROBDD

Nota: Las líneas punteadas en el diagrama significan que que el valor que toma el nodo del que sale es un cero, mientras que las líneas continuas son unos. Y las cajas de color naranja es la salida que arroja un cierto camino por el diagrama y que siempre termina en 0 o 1.

Recursos consultados:
[1] - Lógica y Programación - Diagramas de Decisión Binarios - PDF
[2] - Diagrama de Decisión Binario

Analysis for Pseudorandomness in One-Time Keys

Seguridad de la Información y Criptografía
Homework 2

Last week we write a python program for create one-time pads for two users, and then we use one of the keys and send a encrypted message, and the other user receive that message and decrypt with the same key, and every key that we use was deleted.

In that program we use a python random function for create the one-time keys, and now we need to check if the keys are secure.

And the question is:

Are one-time pads unbreakable?
"Yes. But only if used properly. A one-time pad must be truly random data and must be kept secure in order to be unbreakable." [1]

In class we learn three characteristics of a randomness key:

• Unpredictable.
• Uncompressible.
• Unreproducible.

This three characteristics can be passed with a statistical test in the random keys, there are some tests that we can use, like Monobit Test, longest run of ones in a block, non overlapping template, and more.

In my case I use two tests that I had used in the past, monobit test and frequency block test, the next link is one of my publications in this blog, where I talk about statistical tests for pseudorandomness numbers.

Statistical tests for pseudorandomness numbers

I modify my last code for one-time pads, and in this case I add the functions for check every key with the two tests.

Note: I add a hashtag in the main function in the lines that encrypt and decrypt the message, because I only want to check the result of the test.

And here is my code:


And here is an example of an execution where I only request 4 keys, and every key was checked by the two tests.

If you check my code, in the part of the monobit test I need to change a character for a binary number (0 or 1), and in the frequency blocks I change the character for an int number.

Other important thing is that in the frecuency blocks, in my runnings ever gets a 1.0, but is because is use a little length of the key, if I change for 100000, the number change, but it takes more time for check every key.

One more thing that I used for check my one-time pads, is compressing the file with the keys and view the difference of size of the original file with the compressed file, and we can know how many is the percentage of compressing.

Pay attention in keys1 with keys1.tar.gz the compression is 16.95% less than the original, and keys22 with keys22.tar.gz the compression is the same, so if I create a file with more keys the percentage of compression don't change drastically.

ramon@pavilion:~/Documents/programas/criptologia/breakonetimepad$ ls -l
total 20672
-rwxr-xr-x 1 ramon ramon     3289 Aug 30 08:02 checkontimepad.py
-rw-rw-r-- 1 ramon ramon  1001000 Aug 30 08:05 keys1
-rw-rw-r-- 1 ramon ramon   831446 Aug 30 08:07 keys1.tar.gz
-rw-rw-r-- 1 ramon ramon  1001000 Aug 30 08:05 keys2
-rw-rw-r-- 1 ramon ramon 10010000 Aug 30 03:35 keys22
-rw-rw-r-- 1 ramon ramon  8313357 Aug 30 03:35 keys22.tar.gz

The percentage of compression isn't as bad as I think, so if the compression was more than 50%, someone can attack our keys easily, but isn't the case.

References and other pages:
[1] - One-time pad
Statistical Tests for Random Number Generators

Aplicaciones de la Lógica Proposicional

Verificación y Validación de Software
Entrada 3

En esta publicación hablaré de una de las aplicaciones de la lógica proposicional, primeramente veremos algunos términos y cosas básicas para entrar en el tema, y después hablaré del caso en específico.

Antes de empezar, cabe mencionar que la lógica proposicional es usada en muchos ámbitos, sobre todo computacionales, por lo que su uso suele ser básico en muchos sistemas. De entre varios usos aplicados que me ha tocado leer en internet son la representación del conocimiento o razonamiento con sentido común, dentro del campo de inteligencia artificial, verificación de propiedades en ingeniería de software, algoritmos de aproximación mediante teoría de la computación, verificación de protocolos criptográficos y diseño de circuitos digitales, entre muchos más.

Lógica proposicional

Definición:
"La lógica proposicional es la parte de la lógica que estudia la formación de proposiciones complejas a partir de proposiciones simples, y la inferencia de proposiciones a partir de proposiciones, pero sin tener en cuenta la estructura interna de las proposiciones más simples." [1]

Sintaxis usada en la lógica proposicional

Variables proposicionales (P): p, q, r, s, t...
(Se puede usar cualquier letra del abecedario, pero normalmente se usan letras a partir de la "p")

Conectivos lógicos: ¬, ∨, ∧, →, ↔
(Los conectivos anteriores suelen ser los que se usan, pero existen simbologías diferentes)

Símbolos de puntuación: (, )
(Se usan paréntesis para separar expresiones y evitar confusión, tal y como se hace en álgebra, y también puede ser usados corchetes y llaves)

Es importante saber que cada variable proposicional es una entidad completa y que no se puede dividir, y que solamente puede tomar uno de dos diferentes valores: verdadero (1) o falso (0).

Tablas de conectivas lógicas

Nombre	Lenguaje natural	Ejemplo	Símbolo
Negación	no	No hace frío	¬
Conjunción	y	Hace frío y está nublado	∧
Disyunción	o	Hace frío o hace calor	∨
Condicional	si-entonces	Si hace frío, entonces uso abrigo	→
Bicondicional	si y sólo si	Está nublado si y sólo si hay nubes visibles	↔

Para cada una de estas conectivas lógicas existen tablas de verdad, que me imagino ya hemos visto en algún momento dentro de nuestras clases, les dejo aquí una imagen con las tablas de verdad de los conectivos anteriores, obtenida de Wikipedia y que compare con algunos apuntes, para verificar que están correctas.

Uso de la lógica en computación

"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. 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." [2]

Todo lo anterior son nociones básicas que ya debemos de saber, y es solo una breve introducción, para poder entrar en el caso particular.

Diseño de circuitos

La realización del diseño de un circuito puede involucrar la creación de un sistema electrónico complejo, como el de una placa madre de una computadora, o circuitos menos complejos como el de un sistema integrado.

Cuando son diseños "pequeños" es fácil que una sola persona pueda hacerlos, pero cuando se habla de algo complejo, se requiere a un equipo de personas que hagan un diseño con enfoque sistemático y del cuál se puedan hacer pruebas mediante un simulador, antes de la fabricación del mismo.

La etapa del diseño del circuito, es donde se genera el esquema del circuito integrado, y se considera una etapa media entre el diseño lógico (donde se dice qué debería de hacer el circuito en base a que entradas) y el diseño físico (parte en la que se estructura el diseño del circuito a imprimir a una placa).

[Al hablar de un circuito impreso en una placa me refiero a algo como en la siguiente imagen]

[http://www.arqhys.com/contenidos/diseno-circuitos.html]

Un circuito lógico es aquél que interpreta la información y hace una operación en base a el voltaje de entrada, que puede ser "alto" (1) o "bajo" (0).

El circuito ejecutará una serie de funciones lógicas, a través de puertas lógicas como los conectivos NOT, AND y OR, así como de combinaciones de las mismas como XOR.

Puertas lógicas

En seguida imagen con las puertas lógicas mencionadas. Estas no son todas las existentes.

[http://blogpumaagl.blogspot.mx/2010/10/circuitos-logicos.html]

Como podemos observar cada puerta tiene dos valores de entrada, a excepción del NOT, y solamente pueden tener un valor de salida 0 o 1, y para cada una de ellas existe una tabla de verdad, las mismas que en los conectivos lógicos correspondientes mencionados en la primer parte de esta publicación.

Ejemplo de diseño de un circuito

Para realizar un circuito lo primero que necesitamos es saber las especificaciones del cliente, es decir, saber que es lo que se quiere que el circuito de como resultado.

Enseguida les comparto un ejemplo de mis apuntes de sistemas digitales, donde podemos aplicar el diseño de un circuito.

"Diseñar un circuito que indique al operador de la torre de control de un aeropuerto cuando un avión Jumbo 747 puede aterrizar. Se tienen 3 pistas en el aeropuerto (p, q y r), y cuando una de ellas esta disponible, se obtiene una entrada lógica de 1. Además este tipo de avión solo puede aterrizar cuando existen dos pistas contiguas disponibles."

Ahora sabemos que lo que se desea es un indicador para el operador de la torre, este puede ser un led que encienda cuando es posible aterrizar. Se enciende cuando la salida del circuito es 1, se mantiene apagado cuando la salida es 0. Como entrada tenemos 0 si la pista no esta disponible, y 1 cuando si lo esta.

Creamos una tabla de verdad con las salidas que necesitamos.

p	q	r	Salida
0	0	0	0
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	1

La tabla queda así, porque solo cuando tenemos dos unos contiguos en las entradas (dos pistas contiguas disponibles), significa que la salida sera 1 (puede aterrizar el Jumbo 747).

Ahora mediante mapas de Karnaugh, obtendremos la proposición de salida.

r \ pq	00	01	11	10
0	0	0	1	0
1	0	1	1	0

Con esto podemos obtener la función lógica del circuito.
S = qr + pq
S = (q^r) ∨ (p^q)

Y el diseño de este circuito usando puertas lógicas quedaría así:

Podemos simplificar:
S = q(r + p)
S = q^(r ∨ p)

[Imágenes creadas desde http://www.circuitlab.com/editor]

Con este circuito podemos dar solución al problema planteado, y básicamente los pasos que seguí son los que se utilizan para el diseño de circuitos.

Verificación y pruebas del diseño de un circuito

"Una vez que el circuito ha sido diseñado, debe ser a la vez verificado y probado. La verificación es el proceso de pasar a través de cada etapa de diseño y asegurando que va a hacer lo que la especificación exige que haga. Esto es frecuentemente un proceso altamente matemático y puede involucrar a gran escala simulaciones por ordenador del diseño. En cualquier diseño complejo que es muy probable que los problemas se encuentran en esta etapa y puede implicar una gran cantidad del trabajo de diseño de hacerse de nuevo con el fin de solucionarlos." [3]

Referencias y documentos consultados:
[1] y [2] Lógica proposicional
[3] Circuit design
Lógica proposicional - PDF
Diseño de circuitos lógicos - PDF

Forma Normal Disyuntiva - DNF

Verificación y Validación de Software
Agregado 1

Como tarea extra realice un ejemplo pequeño de una proposición y que lo pasaré a la forma normal disyuntiva, que se denota por DNF por sus siglas en inglés.

La idea de esto es inventar cualquier proposición, y mediante leyes de equivalencia, como las leyes de Morgan, hagamos que nuestra proposición quede expresada únicamente con los operadores de negación y disyunción, que se denota así {¬, ∨}.

Entonces la proposición simple que invente es.

(¬c → b)^(c → ¬a)

Y ahora vamos a cambiar los operadores usados para que quede, como ya dije, con operadores de negación y disyunción.

Por si tienen duda de las leyes de equivalencia, yo encontré en la siguiente página las más básicas y que me ayudaron en la realización de esta tarea.

Leyes de equivalencia

Entonces tenemos que:

(¬c → b) ^ (c → ¬a)
Primero pasamos a eliminar los operadores condicionales que están dentro de los paréntesis, con la ley de Implicación Material.

(¬¬c ∨ b) ^ (¬c ∨ ¬a)
Simplificamos la parte del doble operador negativo.

(c ∨ b) ^ (¬c ∨ ¬a)
Luego para eliminar la conjunción, usamos las leyes de Morgan.

¬[¬(c ∨ b) ∨ ¬(¬c ∨ ¬a)]

Y ahora ya tenemos la proposición expresada solo con operadores de negación y de disyunción. Ahora vamos a probar si la original, con esta última nos dan como resultado la misma tabla de verdad.

Para ahorrar tiempo use el mismo programa que había creado para verificar si una proposición era una tautología, y probé estas dos proposiciones.


Entonces para (¬c → b) ^ (c → ¬a) el siguiente resultado.

esteban@presario:~/Documents/programas/verificacion$ ./tabla_de_verdad.py 
conjuncion(condicional(negacion(C),B) , condicional(C,negacion(A)))
a b c  S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Y para ¬[¬(c ∨ b) ∨ ¬(¬c ∨ ¬a)] se obtuvo.

esteban@presario:~/Documents/programas/verificacion$ ./tabla_de_verdad.py 
negacion(disyuncion(negacion(disyuncion(C,B)),negacion(disyuncion(negacion(C),negacion(A)))))
a b c S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Y como podemos observar, en las dos tablas de verdad obtenemos los mismos valores en la salida S.

Ahora con mapas de Karnaugh

También es posible obtener la proposición en DNF, mediante códigos de Gray y mapas de Karnaugh.

Para esto partimos de la proposición original (¬c → b) ^ (c → ¬a) y obtenemos sus valores de salida junto con los códigos Gray, en una tabla de verdad.

a b c S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Y ahora usando mapas de Karnaugh obtendremos la forma normal disyuntiva (DNF).

c \ ab	00	01	11	10
0	0	1	1	0
1	1	1	0	0

Y los mapas nos dan la proposición a'c + bc', que podemos escribir también como (¬a^c) ∨ (b^¬c), y en base a la definición de wikipedia de "una fórmula está en forma normal disyuntiva (DNF) si corresponde a una disyunción de cláusulas conjuntivas" [1], sabemos que lo que esta entre paréntesis son las cláusulas conjuntivas, y hay una disyunción entre los dos.

Con el programa volvemos a probar con esta nueva fórmula, y vemos que la tabla de verdad sigue dando los mismos resultados de salida.

esteban@presario:~/Documents/programas/verificacion$ ./tabla_de_verdad.py 
disyuncion(conjuncion(negacion(A),C),conjuncion(B,negacion(C)))
a b c S
0 0 0  0
0 0 1  1
0 1 0  1
0 1 1  1
1 0 0  0
1 0 1  0
1 1 0  1
1 1 1  0

Recursos consultados:
[1] Forma normal disyuntiva - Wikipedia
Leyes de equivalencia