Ejemplo de lógica predicatica

Para ésta entrada, se nos encargó realizar un ejercicio en la que lo escogeriamos en del libro "Lean symbolic logic" de Lewis Carroll, el cuál yo escogí el ejercicio 57 de la página 104:

"All medicine is nasty" => "Toda medicina es desagradable"

"Senna is a medicine" => "Senna es una medicina"

Y lo buscado en esta actividad es expresar con lógica predicativa los enunciados dados.

Así que lo primero que hice fue expresar cada frase.

"All medicine is nasty" => "∀m→N(m)"

"Senna is a medicine" => "m(s)"

Una vez tenido las expresiones o con solo conocerlas, podemos concluir que "senna es desagradable":

"Senna is nasty" => "∴ ∀s→N(s) and N(s, m)"

Referencias:

http://www.gutenberg.org/files/28696/28696-h/28696-h.htm

http://es.wikipedia.org/wiki/Notaci%C3%B3n_matem%C3%A1tica

Diagrama de decisión binario

Para ésta entrada, se nos encargo realizar una actividad, que nos pedían realizar una expresión lógica y de ahí sacaramos un árbol de decisión binario (BDD), ya una vez tenido éste, se buscaría reducirse (RBB).

Introducción:

Definiendo un poquito ésto, encontramos que el Diagrama de decisión binario, nos sirve para representar una expresión lógica y ésta la vemos representada en un árbol binario.

Expresión booleana:

-((a^-b)V(c^a)) ^ -(-b^c)

Tabla de Verdad:

Árbol binario de decisión:

En mi caso, mi árbol de decisioón binario quedo de la siguiente manera:

Las flechas punteadas son falso y las normales verdadero.

Tips:

Podemos notar, que al momento de realizar ésto, los valores resultantes de la tabla, son los mismos de los nodos terminales (0 y 1).


Una vez teniendo el árbol, podemos proseguir a reducirlo, donde buscamos aplicar las siguientes reglas: quitar los últimos nodos que se repitan, dejando un solo nodo en 0 y 1, quitar los nodos repetidos y quitar auellos nodos que coincidan sus hijos.

Con ésto mi árbol se puede reducir de la siguiente forma:

En la cuál quite varios nodos terminales que apuntaban a uno mismo (en éste caso cero), así que los uní a uno solo, pero podemos ver que nuestro árbol aún puede ser más reducido, ya que unos nodos apuntan al mismo.

Referencia:

http://es.wikipedia.org/wiki/Diagrama_de_decisi%C3%B3n_binario 
http://ia2.freeiz.com/tema10.html

Criptografía factorización

Esta entrada es de un ejercicio visto en clase, donde lo buscado era hacer la comunicación entre bob y alice, en el que bob mandaba una número generado por la multiplicación de una lista de números dados, así que alice tendría que encontrar cuales era la lista.

Así que bob, mandaría 1594323 (con la lista 131*3*11*5*101*17) y alice buscaría encontrar esa lista.

¿Como alice encontraría la lista?
La respuesta es sencilla lo que hay que hacer es factorizar el número y tendremos la lista hecha por bob

Código:
Para eso generé un código que te factorice el número, aún falta optimizarlo un poco, pero te da la lista.

def factorM(num):
    b = list()
    for i in range(1, 100000): #Determinamos un alcance
        a = num % i  #Sacamos el modulo de i al numero, para saber si es 0 que es lo que buscamos
        if a == 0:
            num = num / i #Actualizamos el numero dividiendolo por el valor de i, para ir sacando los demas numero de lo contrario la lista creceria
            b.append(i)
    return b

a = float(raw_input("Dame el numero: "))
b = factorM(a)
print b

Resultado:

Así que listo, ya tenemos la lista de bob.

Diffie-Hellman hack

Para ésta entrada nos toco realizar una actividad en la que consistía tratar de sacar el mensaje y la clave emitidos por Alice & Bob.

Variables o valores a usar:
p: Es un número primo emitido por Alice & Bob (público)
g: Es un número cualquiera que pertenece a p (público)
X: Es el valor que obtiene Bob apartir de un x que el define (público)
Y: Es el valor que obtiene Alice apartir de un y que el define (público)

x: Es el valor definido por Bob (privado)
y: Es el valor definido por Alice (privado)
k: Es la clave (privada)

Fórmulas:

Actividad:

p = 29
g = 19
X = 21
Y = 6

Para ésta actividad, realice un programa en python en la cuál me devuelve el valor de x, y & k. Así que la idea para sacarlas emplie fuerza bruta buscando el valor y comprobando ésta con X o Y y una vez tenidas éstas sustitui en la fórmula.

x = g ^ (i) mod p
y = g ^ (i) mod p


e i comprobábamos que fuera igual a X & Y y una vez tenidos éstas sustituiamos en la fórmula para obtener k

Programa:

def sacarX(p,g,x):
    for i in range(p):
        newX = (g**i)%p
        if newX == x:
            print "x: "+str(i)
            return i

def sacarY(p,g,y):
    for i in range(p):
        newX = (g**i)%p
        if newX == y:
            print "y: "+str(i)
            return i

def sacarK(g,p,x,y):
    k = (g**(x*y))%p
    print "K vale: "+str(k)


p = 29
g = 19
x = 21
y = 6

x = sacarX(p,g,x)
y = sacarY(p,g,y)
sacarK(g,p,x,y)

Resultados:

Referencias:

http://es.wikipedia.org/wiki/Diffie-Hellman

Prueba de aleatoriedad clave One Time Pad

¿Para que nos serviría hacer una prueba de aleatoriedad para la clave generada?
La respuesta, es que si nosotros (que claro que si) estamos buscando generar una clave que sea dificil de romper o descifrar, a nosotros nos interesaría hacer éste tipo de test.

¿Pero como sabríamos si es aleatoria?
No sabemos bien si un número es totalmente aleatorio entonces lo que se hace es medir las frecuencias que estamos recibiendo.
En ésto me ayudo mucho en ver de otra forma, una caricatura que encontré en random.org

Para esto hay diferentes tipos de pruebas como anderson, chi, monobit, de bloques, run, entre otras. Cada una la aplicamos dependiendo del tipo de test que estamos buscando y su número aleatorio.

Para esta entrada se genero los números aleatorios de one time pad, donde buscaremos verificar que tan aleatorio es nuestra clave.

Prueba
El tipo de prueba empleado es el monobit, el cúal su fórmula ésta dada por:

Donde E es nuestra secuencia de bits
Sn nuestra sumatoria de E (hay que indicar que nuestra, que al momento de identificar un 0 esto lo cambia a -1)
n es nuestro tamaño total de E
P-value será tomada con erfc(sobs/sqrt(2))
donde erfc es la función de error complementario.
Ya para definir si fue aleatorio, se compara con una muestra de 0.01 y si esta es mayor la prueba pasa, de lo contrario no es aleatorio.


Código nuevo:

from random import randint
from math import sqrt, erfc

def generarClaves(cantidad, nombre):
    a = 'abcdefghijklmnopqrstuvwxyz '
    largoClave = 80
    for i in range(cantidad):
        clave = list()
        for j in range(largoClave):
            letra = randint(0, len(a)-1)#Creamos nuestro numero aleatorio del tamano del arreglo
            clave.append(letra)
        pruebasRand(clave)#mandamos llamar al metodo de pruebas
        #print clave

#clave.append("\n")
        #guardarClaves(clave, nombre)
def pruebasRand(clave):
    print "Prueba Monobit"
    print "\t Resultado:"+str(pruebaMonobit(clave))

def pruebaMonobit(clave):
    s = list()
    for i in clave:
        i = convertirUnosCeros(i) #Leemos cada elemento del arreglo para sacar unos y ceros
        s.append(i)
    sobs = abs(sum(s))/sqrt(len(s)) #Aplicamos la formula propuesta
    pValue = erfc(sobs/sqrt(2)) #Aplicamos la formula propuesta
    if(pValue > 0.01): return "Prueba pasada "+str(pValue) #Comparamos
    else: return "Prueba no pasada "+str(pValue)

def convertirUnosCeros(elemento):
    elemento = elemento % 2 #Lo sacamos tomando los numero pares e impares
    if elemento == 0: return -1 #Si el elemento es 0 lo convertimos a -1 para que este afecte en la sumatoria
    else: return 1

def guardarClaves(clave, nombre):
    clave = "".join(clave)
    archivo = open(str(nombre), "a")
    archivo.write(clave)
    archivo.close()
    otro = open("copia"+str(nombre), "a")
    otro.write(clave)
    otro.close()

cantidad = int(raw_input("Dame la cantidad de claves a generar: "))
nombre = raw_input("Dame el nombre del archivo: ")
generarClaves(cantidad, nombre)

Explicamos:jninininia..

Resultados:
Así que ahora proseguimos a verificar nuestros resultados y para verificarlos que estuvieran bien, la prueba se hizo varias veces:

1 vez:

5 veces:

Así que por lo valores arrojados, podríamos decir que nuestro generador de claves es seguro y es aleatorio.

Nota:
¿Pero que pasa si al test lo aplicamos más de 5 veces? Pues sorpresa, descubrimos que nuestro generador de números aleatorios, no es del todo aleatorio. Aunque nuestros resultados digan que pasaron la prueba, podemos observar que sus resultados se van repitiendo, hasta tenemos una que otra, que no paso la prueba y sus resultados son los mismos.

Resultado: FAIL.
Ya con ésto sabemos que tristemente nuestra clave no es aleatoria, ya que se repite la frecuencia, así que el posible problema es al momento de emplear randint de python, así que para solucionar ésto, podríamos implementar un número random uniforme, obteniedo unos mejores resultados o hacer nuestro número con lo visto de simulación, así que más adelante pondré mi código mejorado.

Como podemos ver en la imágen los números generados (fueron 10000), se van repitiendo con una frecuencia, haciendo esto muy inseguro.

Referencia:
http://goo.gl/IP3Wx
http://goo.gl/ExMC6
http://www.random.org/analysis/
http://www.random.org/analysis/Analysis2005.pdf

Lógica proposicional

Introducción:

Diariamente nos topamos con preguntas simples en la cuál su respuesta es falsa o verdadera, pero no ambas, mensionando algunos ejemplos vemos como: el jueves no hay tarea, el agua es un compuesto químico, el perro es un mamifero, entre otras. A esto se le llama lógica proposicional y estudia proposiciones mas complejas.

Conectivas lógicas:

las conectivas lógicas son utilizadas para unir sentencias y así formar una proposicion:

http://es.wikipedia.org/wiki/L%C3%B3gica_proposicional

Cada conectiva lógica se distigue por el valor devuelto en sus diferentes estados de valores de entrada, para esto ayuda mucho las tablas de verdad en la cuál podemos ver sus diferentes estados.

http://es.wikipedia.org/wiki/L%C3%B3gica_proposicional

• Negación: Resibiendo una proposicion p, y esta negando -p, es verdadera cuando p es falsa y p es falsa cuando p es verdadera.

• Conjunción: Resibiendo dos proposiciones p y q, tomamos que es verdadera cuando ambas son verdaderas, falso en cualquier otro caso.

• Disyunción: Resibiendo dos proposiciones p y q, tomamos que es verdadera cuando cualquiera de sus entradas sea verdadera, falso cuando ambas son falsas.

• Condicional: Resibiendo dos proposiciones p y q, tomamos que es falso cuando viniendo de un verdadero se pase a falso.

• Bicondicional: Resibiendo dos proposiciones p y q, tomamos que es verdadera cuando ambas entradas sean del mismo tipo como falso & falso o verdadero & verdadero.

Aplicaciones:

Dando una breve introducción y teniendo una idea mas clara, pasemos ahora a ver donde los podemos ocupar o donde son aplicados algunos ejemplos son: principalmente en la eletrónica e informática, circuitos eletrónicos/digitales, en el habla (como se mensiono en los primeros ejemplos), inteligencia artificial, criptografía, sistemas de computos, lineas de producción, etc.

Inteligencia Artificial:

Navegando por internet me encontré con una nota que me llamo la atención y me ayudo a ver y comprender mas del caso.

nota: ¿Inteligencia artificial para iluminar los semáforos del futuro? enlace es.engadget

Ya que un semáforo lo podemos ver como un sistema de automatización o línea de producción donde tenemos una secuencia, pero ¿que pasaría si a éste se le aplica inteligencia artificial?
Aquí es donde entra la lógica proposicional, que es cuando entra en la fase de reconocimiento, ya que para llegar a esto estamos evaluando posibles datos de entrada y salida, que nos llevará a una sola (semántica y sintaxis/teoría).
  

Referencia:

http://www.monografias.com/trabajos51/inteligencia-artificial/inteligencia-artificial.shtml
http://es.engadget.com/2012/08/26/estudio-semaforos-inteligencia-artificial/
http://www.educared.org/wikiEducared/L%C3%B3gica_proposicional.html
http://sp.rian.ru/images/14787/86/147878665.jpg

Interpolación de Lagrange

Este método nos sirve para construir un polinomio interpolante de grado n. Un polinomio interpolante se utiliza para encontrar un polinomio que pase por todos los puntos de un conjunto de datos (muestra). La respuesta aplicada en un problema, solo tiene una solución, ya que al tenerse otra, se debería sacar la difenrecia de éstas dos, dando un polinómio de grado k + 1.

Fórmula:

La siguiente fórmula es la que nos proporciona Wikipedia.

 

 Pero si se nos hace un poco confusa como a mí podemos sustituirla en la siguiente donde, Xn, será nuestro valor en x (nuestro puntos) y Fn nuestra interpolación.

Ejemplo propuesto:

Las densidades de sodio para tres temperaturas son dadas a continuación

i   Temperatura     Densidad
0   94°C               929kg/m3
1   205                 902
2   371                 860
       x                     y

1) Escribir la formula de la interpolación de Lagrange a los tres puntos dados.
2) Encontrar la densidad para x = 251°C con interpolación de Lagrange

Emplearemos la formula proporcionada donde sustituiremos:
n = 2 + 1 = 3 //Nos sirve para saber hasta cuantos Xn se harán a sustituir en la fórmula
x1 = 94°C
x2 = 205°C
x3 = 317°C
f(x0) = 929 kg/m3
f(x1) = 902 kg/m3
f(x2) = 860 kg/m3

A continuación les dejo una captura de pantalla de como se resuelve el problema, lo único que se hace es sustituir, lo valores por los de la fórmula:

En el problema de la pregunta 1, como se mencionó se sustituye en la fórmula planteada, obteniendo el polinomio y  en la pregunta 2, una vez que se obtiene la ecuación sustituimos 251 en x, para así obtener la densidad.

Otras aplicaciones:
La interpolación polinómica de Lagrage, también puede ser empleada en proyectores ortogolanes

Uno de los posibles problemas al implementar ésto, al momento de agregarle más números o puntos a interpolar, crece el tiempo y la complejidad de su resultado.

Link:

http://es.wikipedia.org/wiki/Interpolaci%C3%B3n_polin%C3%B3mica
http://es.wikipedia.org/wiki/Interpolaci%C3%B3n_polin%C3%B3mica_de_Lagrange