lunes, 3 de septiembre de 2012

Diagrama de decisión binario

Para esta tarea se nos pidió lo siguiente
  • Inventar una expresión Booleana (utilizando por mínimo 3 variables y 4 conectivos básicos).
  • Construir y dibujar su BDD.
  • Reducir el BDD resultante a un ROBDD.
  • Dibujar el ROBDD resultante.
La expresión que invente es la siguiente:

(p ^ q) v (q -> r) ^ (p v ¬r)

Tabla de verdad:



Árbol binario de decisión:



Reducir a ROBDD

Para reducir un árbol binario de decisión a un Diagrama Binario de Decisión se tienen que considerar dos reglas:
  1. Unir los isomorfismos (de igual forma) de subgrafos
  2. Eliminar los nodos que sus dos hijos sean isomorfos.



Un DDB se encuentra reducido a DDBR (Diagrama de decisión binario reducido ordenado) si tiene las siguientes características:
  • Unicidad: No existan dos nodos con el mismo símbolo proposicional ni con los mismos hijos izquierdo y derecho (nodos duplicados)
  • No redundancia: No existan nodos variables idénticos.



Con esto se redujo el primer árbol que observamos en la imagen. :)

lunes, 27 de agosto de 2012

Aplicación de la lógica proposicional

Lógica es el estudio del razonamiento, se refiere específicamente a si el razonamiento es correcto. 

Una proposición es un enunciado que puede afirmarse como verdadero o falso. 

"Lógica proposicional es la parte de la lógica que estudia la formación de proposiciones complejas a partir de proposiciones simples."


Proposiciones

Simples. Son las oraciones que se forman sin usar enlaces.
  • La casa es roja
  • Carlos es estudiante
Complejas. Son las oraciones que están formadas por dos o más proposiciones simples ligadas por un conector.
  • María es chef o es cantante
  • Si ayer llovió entonces hoy sale el sol
  • 2 es par y 9 es impar

Para validar preposiciones se necesita realizar las tablas de verdad, las cuales son diseños combinacionales dado por 2^n donde n es el número de proposiciones simples.

Los conectivos lógicos principales que son utilizados para formar proposiciones complejas son  ¬, ∨, ∧, →, ↔ ( no, o, y, si... entonces, si y sólo si ).

Las tablas de verdad de los conectivos principales son:


Conjunción.
La proposición p ^ q es verdadera solamente si p y q son verdaderas, en los demás casos es falsa.

Ejemplo:
Puedes salir cuando laves la ropa y arregles tu cuarto.



Disyunción.
La disyunción es verdadera si por lo menos una de las proposiciones es verdadera, y es falsa solamente cuando todas las preposiciones son falsas.

Por ejemplo.
Puedes ir a dormir o puedes hacer tu tarea



Implicación. 
La proposición p → q es falsa solamente si el antecedente es verdadero y el consecuente es falso. En los demás casos es verdadera.

Ejemplo.
p = Tengo dinero
q = Voy al cine
→ q = Si tengo dinero, entonces voy al cine

Doble implicación.
La proposición p ↔ q es verdadera cuando ambas preposiciones son verdaderas o ambas falsas.

Ejemplo.
r = El polígono es de cuatro lados
s = Es un cuadrilátero
↔ s = El polígono es de cuatro lados si y sólo si es un cuadrilátero.




Negación.
La negación es el conectivo lógico que permite cambiar el valor de verdad de una proposición.

Si p es verdadero, su negación ¬ es falsa y viseversa.

Por ejemplo. 
p = todos los triángulos son equiláteros
¬p = NO todos los triángulos son equiláteros



La lógica computacional puede ser aplicada al campo de la computación, su uso principal es en circuitos computacionales, programación lógica y análisis y optimización de algoritmos.

Sistema combinacional

Un sistema combinacional es un sistema digital en el que las salidas dependen de la combinación de sus entradas. Las funciones (OR, AND, NAND, XOR) son booleanas, o sea que cada función se puede representar en una tabla de verdad. 

Metodología de un sistema combinacional.

1. Especificar el sistema. En esta parte se detalla el propósito del diseño.

2. Determinar las entradas y salidas. Identificar las variables del problema, identificar entradas y salidas.

3. Construir la tabla de verdad. Trasladar el comportamiento del sistema a una tabla de verdad, indicando para cada combinación de entrada, la salida o salidas más convenientes para el diseño.

4. Minimizar. Para obtener las ecuaciones mínimas se pueden utilizar diferentes métodos como manipulación algebraica, mapas de karnaugh, entre otros.

5. Diagrama esquemático. Al obtener las ecuaciones mínimas, se representan en forma de símbolos para su análisis y comprensión.

6. Implementar. Hay dos formas de implementación, circuitos integrados de función fija (TTL) o dispositivos lógicos programables (PDLs).


Aplicación 

Para la tarea de esta semana nos pidieron lo siguiente:
"Investiguen aplicaciones de la lógica proposicional y documenten uno en su tercera tarea."

Para esta tarea explicaré una aplicación de circuitos combinatorios.

En una granja se tiene: 
  • Un granjero con una puerta muy grande y pesada en donde se requiere de varias personas para abrirla o cerrarla.
  • Un corral de ovejas.
  • Ocasionalmente llegan lobos.



El granjero necesita un sistema de alarma diseñado para lo siguiente:
  • Sea activado cuando las ovejas se encuentren fuera del corral y la puerta este abierta, para realizar una acción correctiva ya sea cerrar la puerta o poner las ovejas en el corral.
  • Sea activado cuando se encuentren los lobos cerca y las ovejas se encuentren fuera del corral, para realizar la acción correctiva de ahuyentar a los lobos.

1. Especificar el sistema
Las variables que intervienen son puerta, ovejas, lobos y alarma. Para las primeras tres variables se tienen sensores de deteccion.

Puerta
Abierta = 1 
Cerrada = 0

Ovejas
Fuera del corral = 1
Dentro del corral = 0

Lobos
Están cerca = 1 
Están lejos = 0

Para el dispositivo de alarma

Alarma
Activada = 1
Desactivada = 0


2. Determinar entradas y salidas
La puerta, las ovejas y los lobos (P, O y L) son las entradas del sistema, mientras que la Alarma (A) es la salida.

Diagrama de bloques.
3. Tabla de verdad

La alarma se activará cuando:
  • Las ovejas estén afuera y los lobos estén cerca.
  • La puerta esté abierta y las ovejas estén afuera del corral.
  • La puerta esté abierta, las ovejas estén afuera y los lobos estén cerca.


4. Minimizar

Para simplificar las ecuaciones utilizamos el método de Mapas de Karnaugh.


La ecuación quedaría de la siguiente manera:
F(A) = PO + OL 
F(A) = O (P + L)

Con esto se puede concluir que la alarma se activará cuando la puerta este abierta y las ovejas fuera del corral (PO) o cuando las ovejas estén fuera del corral y los lobos estén cerca (OL).


5. Diagrama esquemático



6. Implementación
La implementación se puede realizar con un dispositivo lógico programable (PLD) como el GAL16V8.

Referencias:
Proposiciones lógicas
Libro Matemáticas Discretas. Richard Johnsonbaugh. Sexta Edición.
Sistemas Digitales.

jueves, 23 de agosto de 2012

Grados de Libertad


En un sistema físico, el término grado de libertad se refiere a la cantidad mínima de números reales que se necesitan especificar para determinar completamente el estado físico. Este concepto lo podemos encontrar en mecánica clásica y termodinámica.

En mecánica, por cada una de las partículas libres del sistema y por cada dirección en la que se pueden moverse existen dos grados de libertad, uno se relaciona con la posición y el otro con la velocidad.

Cuando existan ligaduras entre las partículas, el número de grados de libertad será igual al número total de variables menos el número de ligaduras que las relacionan.



GRADOS DE LIBERTAD EN MECÁNICA CLÁSICA

En mecánica hamiltoniana, el número de grados de libertad de un sistema coincide con la dimensión topológica del espacio de fases del sistema.

Un conjunto de N partículas que interactúan entre sí y se mueven sin restricciones en un espacio tridimensional tiene 6N grados de libertad, o sea tres coordenadas de posición y tres velocidades.



EJEMPLO DE VARIOS GRADOS DE LIBERTAD

Considerando un sistema de 3 grados de libertad,



Hay 3 grados de libertad en este problema, para poder caracterizar el distema tenemos que tener las posiciones de las tres masas (x1, x2, y x3).

Se necesitan tres diagramas de cuerpo libre para formar las ecuaciones de movimiento. Sin embargo, es  posible formar las matrices de coeficientes directamente, ya que en cada parámetro en un sistema de masa-amortiguador-resorte tiene un papel muy importante.

Ecuaciones de movimiento para diagramas de cuerpo libre

Las ecuaciones de movimiento se pueden obtener de los diagramas de cuerpo libre, basados en la segunda ley de movimiento de Newton, F = m(a)



Las ecuaciones de movimiento se pueden expresar de la siguiente manera:



Entonces, la matriz de ecuaciones quedará así:




Ecuaciones de movimiento de la formación de la matriz directa
Si vemos las matrices de coeficientes anteriores, podemos encontrar que todos los términos de la diagonal principal son positivos y contienen términos que están directamente relacionados con los elementos correspondientes.
Los demás elementos son negativos y simétricos, son simétricos por que están unidos a dos elementos y los efectos son los mismos en esos dos elementos (condición conocida como teorema de reciprocidad de Maxwell) y son negativos debido a los desplazamientos o velocidades relativas de los dos elementos conectados.
En resumen para crear esas matrices se realizan los siguientes pasos:
1.     Determinar el número de grados de libertad del problema, estos determinan el tamaño de la masa, amortiguación y matrices de rigidez. Normalmente, un grado de libertad puede relacionarse con cada masa.
2.     Añade los valores de las masas (si están asociadas con grados de libertad) en las diagonales de la matriz de masas, el orden exacto no importa. Todos los demás valores de la matriz son ceros.







3.     Para cada masa (asociada con un grado de libertad), suma la amortiguación de todos los amortiguadores que tiene esa masa, agrega el valor en la matriz de amortiguación que corresponda a la masa en la matriz de masa.




4.     Identificar los amortiguadores que están conectados a dos masas, etiqueta las masas como m y n, Escribe el amortiguador negativo en los lugares (m,n) y (n,m) en la matriz de amortiguamiento. Repite el procedimiento para todos los amortiguadores, los términos restantes en la matriz de amortiguamiento son ceros.





5.     Para cada masa, suma la rigidez de todos los resortes unidos a la masa, añade ese valor en la matriz de rigidez en la diagonal que corresponde a la masa en la matriz de masa.




6.     Identificar los resortes que están conectados a dos masas, etiquetarlos como m y n. Escribir el resorte negativo en los lugares (m,n) y (n,m) en la matriz de rigidez. Repite el procedimiento para todos los resortes, los términos que restan en la matriz de rigidez son ceros.



7.     Suma las fuerzas externas aplicadas sobre cada masa (asociada con un grado de libertad), agrega ese valor en el vector de fuerza en el lugar de la fila correspondiente a la fila de esa masa en la matriz de masa.




8.     La matriz resultante de movimiento es:



One time pad - Python

For this introductory assignment, we have to do a one time pad program, I did it in python. 

"In cryptography, the one-time pad (OTP) is a type of encryption which has been proven to be impossible to crack if used correctly. Each bit or character from the plaintext is encrypted by a modular addition with a bit or character from a secret random key (or pad) of the same length as the plaintext, resulting in a ciphertext."

This method can be implemented as a software program, using data files as input (plaintext), output (ciphertext) and key material. The XOR operation is often used to combine the plaintext with the key. 

This is my code, it is very simple.







Screenshots:



References: