lunes, 27 de agosto de 2012

Aplicación de la lógica proposicional

Primero que nada para hablar de este tema se tiene que tener un concepto de que es la lógica proposicional.


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.

Una lógica proposicional es un sistema formal cuyos elementos más simples representan proposiciones, y cuyas constantes lógicas, llamadas conectivas, representan operaciones sobre proposiciones, capaces de formar otras proposiciones de mayor complejidad.

La proposición es el significado de una idea, enunciado,conjunto de palabras o letras a las que se les puede asignar uno y sólo uno de los valores de verdad, que pueden ser:

VERDADERO (V) o FALSO(F)


Por lo general, a las proposiciones se las representa por las letras del alfabeto desde la letra p, es decir, p, q, r, s, t, ... etc. Así, por ejemplo, podemos citar las siguientes proposiciones y su valor de verdad:




p : 15 + 5 = 21 (F)
q: Santa Fe es una provincia Argentina. (V) 
r: El número 15 es divisible por 3. (V)
s: El perro es un ave. (F)


Existe una notacion para trabajar con ellas y es esta:

Notación y Conectivos Lógicos
A partir de proposiciones simples es posible generar otras, simples o compuestas. Es decir que se puede operar con proposiciones, y para ello se utilizan ciertos símbolos llamados conectivos lógicos. A continuación vemos una concreta definición de cada uno:
ConectivaExpresión en el
lenguaje natural
EjemploSímbolo en
este artículo
Símbolos
alternativos
NegaciónnoNo está lloviendo.\neg \,\sim \,
ConjunciónyEstá lloviendo y está nublado.\and\And \, .
DisyunciónoEstá lloviendo o está soleado.\or
Condicional materialsi... entoncesSi está soleado, entonces es de día.\to \,\supset
Bicondicionalsi y sólo siEstá nublado si y sólo si hay nubes visibles.\leftrightarrow\equiv \,
Negación conjuntani... niNi está soleado ni está nublado.\downarrow \,
Disyunción excluyenteo bien... o bienO bien está soleado, o bien está nublado.\nleftrightarrow\oplus, \not\equiv, W
APLICACIÓN DE LA LÓGICA PROPOSICIONAL


La lógica proposicional dio origen a la algebra booleana que esta a su vez fue la base para la informatica y para la forma en que funcinarion los primeros ordenadores. Ya que el algebra de boole es el area de las matematicas que se aplica en el diseño de circuitos logicos .


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 Claude Shannon publicó un libro llamado "Análisis simbólico de circuitos con relés", estableciendo los primeros conceptos de la actual teoría de la conmutación, cuando se ha producido un aumento considerable en el número de trabajos de aplicación del Álgebra de Boole a los computadores digitales. 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ógicospuede realizarse con rapidez.


Ya que se puede aplicar de este modo.



La verdad de una proposición puede asociarse al pasaje de corriente en un circuito eléctrico con un interruptor.

Así, para representar a p, si es F, se tiene


y para p, si es V, se tiene:


Es decir, el interruptor se cierra si p es V y se abre si p es F.

Podemos, así, representar las operaciones proposicionales mediante circuitos con tantos interruptores como proposiciones componentes, combinados en serie o paralelamente.


Veremos, a continuación, como representar en forma booleana las operaciones que surgen de operar con dos proposiciones mediante los conectivos lógicos que conocemos

Conjuncion



Este circuito admite el pasaje de corriente, es decir la verdad de p^q , solo si ambas son V .

Disyuncion
Está representada por un circuito en paralelo.



Como vemos, admite el pasaje de corriente cuando al menos una de las dos es V (comprobar en la correspondiente tabla de verdad).




Cuando se trabaja con circuitos digitales es muy común que al final de un diseño se tenga un circuito con un número de partes (circuitos integrados y otros) mayor al necesario.

Para lograr que el circuito tenga la cantidad de partes correcta (la menor posible) hay que optimizarlo (reducirlo).

Un diseño óptimo causará que:
- El circuito electrónico sea más simple
- El número de componentes sea el menor
- El precio de proyecto sea el más bajo
- La demanda de potencia del circuito sea menor
- El mantenimiento del circuito sea más fácil.
- Es espacio necesario (en el circuito impreso) para la implementación del circuito será menor.

En consecuencia que el diseño sea el más económico posible.

Una herramienta para reducir las expresiones lógicas de circuitos digitales es la matemáticas de expresiones lógicas, que fue presentada por George Boole en 1854,herramienta que desde entonces se conoce como álgebra de Boole.
Las reglas del álgebra Booleana son:

Notas: (punto): significa producto lógico. + (signo de suma): significa suma lógica
Operaciones básicas en el algebra booleana

Algebra booleana. Operación AND. Operación OR y Operación NOT - Electrónica Unicrom

Ley Distributiva, ley Asociativa, ley Conmutativa

Ley distributiva - Algebra booleana - Electrónica Unicrom
Ley asociativa - Algebra booleana - Electrónica Unicrom

Precedencia y Teorema de Morgan



Para asegurarse de que la reducción del circuito electrónico fue exitosa, se puede utilizar la tabla de verdad que debe dar el mismo resultado para el circuito simplificado y el original.



 


Y esa es una aplicación que tiene la lógica proposicional , que se utiliza en el diseño de circuitos.



Referencias:
http://www.unicrom.com/dig_algebra_booleana.asp 

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

http://soko.com.ar/matem/Logica_proposicional.ht
m

miércoles, 22 de agosto de 2012

ONE TIME -PAD One Time Pad



Hay quienes creen que no existe un método de cifrado perfecto, o un cifrado que te pueda garantizar seguridad absoluta y se equivocan.
El método de cifrado de One-Time Pad, que fue inventado en 1917 por el Mayor Joseph Mauborgne y Gilbert Vernam de AT&T. Claude Shannon, 25 años después, se encargó de demostrar con la teoría de la información que este cifrado cumple con ser un secreto perfecto, lo que quiere decir que el contenido del mensaje no puede aportar nada de información a un atacante.

Preliminares
Necesitamos una llave de la misma longitud que el mensaje, la cual deberá ser de verdad aleatoria y no pseudo aleatoria. Además esta llave se supone que las dos partes la deben conocer (problema de intercambio de llaves) y cuando una parte cifre el mensaje debe destruir esa llave de alguna forma que no pueda recuperarse y luego enviar el mensaje cifrado, luego la otra parte va a descifrarlo y al terminar de hacerlo debe destruir la llave de nuevo.
Es primordial que no se vuelva a usar la misma llave dos veces pues un criptoanalista podría romper el cifrado sabiendo dos mensajes diferentes que se encriptaron con la misma llave.

FUNCIONAMIENTO

• El primer paso era conseguir un bloque (pad) de hojas con cientos de éstas.
• Cada hoja contenía una llave única en forma de línea de secuencias aleatorias de letras.
• Dos copias del bloque: una para el emisor y otra para el receptor.
• Para encriptar el emisor aplica el criptosistema de Vigenére con la primera hoja del bloque como llave.
• El receptor puede descriptar usando el mismo criptosistema y con la misma llave.
• Una vez que el mensaje fue encripatado, enviado, recibió y descriptado con éxito la hoja que se usó como hoja y se destruye.
• Cuando el siguiente mensaje se va a enviar la siguiente llave del bloque es usada
– la cual es subsecuentemente destruida y así se continua
• Debido a que cada llave es usada una sola vez, el
sistema se conoce como onetime pad
.




Ejemplo:
Llave:
P L M O E Z Q K J Z L R T E A V C R C B Y
Texto claro:
a t t a c k t h e v a l l e y a t d a w n
Criptosistema:
P E F O G J J R N UL C E I Y V V U C X L


Otro ejemplo mas simple
Es algo muy simple de entender, teniendo el texto:
Teniendo la llave:
El texto cifrado sería:
Porque:

A + R mod 26 = S
M + F mod 26 = S
A + T mod 26 = U
Suponiendo que A vale 1 y R vale 17: 1+17 = 18 y 18 / 26 nos daría como residuo 18, entonces el 18 corresponde a la letra S.
Es importante ver que no puede romperse incluso si pudieramos calcular todas las posibilidades y buscar mensajes coherentes, pues al decifrarlo podría decir SIVOY como NOVOY entonces es imposible saber cual es el mensaje cifrado sin saber la llave. Según dicen, los Rusos cifraron algunos mensajes con este método y siguen hasta la fecha sin poderse descifrar, y así seguirán para siempre.
El problema con este método y en general con cualquier método de cifrado simétrico es el intercambio de llaves, pues ¿cómo podrías intercambiar la clave del One Time Pad de una manera segura?
Con este código en javascript podríamos obtenerlo:

var charCodeCero = ("A".charCodeAt(0))-1;
function oneTimePad(mensaje, llave) {
 mensaje = mensaje.toUpperCase();
 llave = llave.toUpperCase();
 var cifrado = "";
        for(var i = 0; i < mensaje.length; i++) {
  cifrado += String.fromCharCode((( mensaje.charCodeAt(i) - charCodeCero +
                                                 llave.charCodeAt(i) - charCodeCero 
                                                 ) % 26) + charCodeCero);
 }
 return cifrado;
}


One time-pad



Hay quienes creen que no existe un método de cifrado perfecto, o un cifrado que te pueda garantizar seguridad absoluta y se equivocan.
El método de cifrado de One-Time Pad, que fue inventado en 1917 por el Mayor Joseph Mauborgne y Gilbert Vernam de AT&T. Claude Shannon, 25 años después, se encargó de demostrar con la teoría de la información que este cifrado cumple con ser un secreto perfecto, lo que quiere decir que el contenido del mensaje no puede aportar nada de información a un atacante.

Preliminares
Necesitamos una llave de la misma longitud que el mensaje, la cual deberá ser de verdad aleatoria y no pseudo aleatoria. Además esta llave se supone que las dos partes la deben conocer (problema de intercambio de llaves) y cuando una parte cifre el mensaje debe destruir esa llave de alguna forma que no pueda recuperarse y luego enviar el mensaje cifrado, luego la otra parte va a descifrarlo y al terminar de hacerlo debe destruir la llave de nuevo.
Es primordial que no se vuelva a usar la misma llave dos veces pues un criptoanalista podría romper el cifrado sabiendo dos mensajes diferentes que se encriptaron con la misma llave.

FUNCIONAMIENTO

• El primer paso era conseguir un bloque (pad) de hojas con cientos de éstas.
• Cada hoja contenía una llave única en forma de línea de secuencias aleatorias de letras.
• Dos copias del bloque: una para el emisor y otra para el receptor.
• Para encriptar el emisor aplica el criptosistema de Vigenére con la primera hoja del bloque como llave.
• El receptor puede descriptar usando el mismo criptosistema y con la misma llave.
• Una vez que el mensaje fue encripatado, enviado, recibió y descriptado con éxito la hoja que se usó como hoja y se destruye.
• Cuando el siguiente mensaje se va a enviar la siguiente llave del bloque es usada
– la cual es subsecuentemente destruida y así se continua
• Debido a que cada llave es usada una sola vez, el
sistema se conoce como onetime pad
.



Ejemplo:
Llave:
P L M O E Z Q K J Z L R T E A V C R C B Y
Texto claro:
a t t a c k t h e v a l l e y a t d a w n
Criptosistema:
P E F O G J J R N UL C E I Y V V U C X L

Otro ejemplo mas simple
Es algo muy simple de entender, teniendo el texto:
Teniendo la llave:
El texto cifrado sería:
Porque:

A + R mod 26 = S
M + F mod 26 = S
A + T mod 26 = U
Suponiendo que A vale 1 y R vale 17: 1+17 = 18 y 18 / 26 nos daría como residuo 18, entonces el 18 corresponde a la letra S.
Es importante ver que no puede romperse incluso si pudieramos calcular todas las posibilidades y buscar mensajes coherentes, pues al decifrarlo podría decir SIVOY como NOVOY entonces es imposible saber cual es el mensaje cifrado sin saber la llave. Según dicen, los Rusos cifraron algunos mensajes con este método y siguen hasta la fecha sin poderse descifrar, y así seguirán para siempre.
El problema con este método y en general con cualquier método de cifrado simétrico es el intercambio de llaves, pues ¿cómo podrías intercambiar la clave del One Time Pad de una manera segura?
Con este código en javascript podríamos obtenerlo:

var charCodeCero = ("A".charCodeAt(0))-1;
function oneTimePad(mensaje, llave) {
 mensaje = mensaje.toUpperCase();
 llave = llave.toUpperCase();
 var cifrado = "";
        for(var i = 0; i < mensaje.length; i++) {
  cifrado += String.fromCharCode((( mensaje.charCodeAt(i) - charCodeCero +
                                                 llave.charCodeAt(i) - charCodeCero 
                                                 ) % 26) + charCodeCero);
 }
 return cifrado;
}



Exponenciales y Logaritmicas

Función exponencial


La función exponencial, es conocida formalmente como la función real ex, donde e es el número de Euler, aproximadamente 2.71828...; esta función tiene por dominio de definición el conjunto de los números reales, y tiene la particularidad de que su derivada es la misma función. Se denota equivalentemente como f(x)=ex o exp(x), donde e es la base de los logaritmos naturales y corresponde a la función inversa del logaritmo natural.
En términos mucho más generales, una función real E(x) se dice que es del tipo exponencial en base a si tiene la forma
E(x)=K \cdot a^x
siendo aK ∈ R números reales, con a > 0. Así pues, se obtiene un abanico de exponenciales, todas ellas similares, que dependen de la base aque utilicen.

Definicion Formal

La función exponencial, es conocida formalmente como la función real ex, donde e es el número de Euler, aproximadamente 2.71828...; esta función tiene por dominio de definición el conjunto de los números reales, y tiene la particularidad de que su derivada es la misma función. Se denota equivalentemente como f(x)=ex o exp(x), donde e es la base de los logaritmos naturales y corresponde a la función inversa del logaritmo natural.
En términos mucho más generales, una función real E(x) se dice que es del tipo exponencial en base a si tiene la forma
E(x)=K \cdot a^x
siendo aK ∈ R números reales, con a > 0. Así pues, se obtiene un abanico de exponenciales, todas ellas similares, que dependen de la base aque utilicen.


Propiedades 
La función exponencial (y exponenciales en base distinta a e) satisfacen las siguientes propiedades generales.
  • Son las únicas funciones que son igual a su derivada (multiplicada por una constante, en el caso de que tengan una base distinta a e)
  •  \exp(x+y) = \exp(x) \cdot \exp(y)
  •  \exp(x-y) = \exp(x) / \exp(y) \,
  • \exp(-x) = {1 \over \exp(x)}
  •  \exp(0) = 1 \,
  • su límite en - ∞ es 0, y en + ∞ es + ∞


Como derivarla
La importancia de las funciones exponenciales en matemática y ciencias radica principalmente de las propiedades de su derivada. En particular,
{d \over dx} e^x = e^x


Es decir, ex es su propia derivada . Es la única función con esa propiedad (sin tomar en cuenta la multiplicación de la función exponencial por una constante). Otras formas de expresar lo anterior:
  • La pendiente del gráfico en cualquier punto es la altura de la función en ese punto.
  • La razón de aumento de la función en x es igual al valor de la función en x.
  • La función es solución de la ecuación diferencial y'=y.
Si la base de la exponencial no es el número e, sino otro número real arbitrario a mayor que 0, entonces la derivada de ésta es:
{d \over dx} a^x = a^x \cdot \ln(a)
donde la función ln denota el logaritmo natural.

Aquí unos ejemplos de la Derivada de la función exponencial de base e



La derivada de la función exponencial de base e es igual a la misma función 
por la derivada del exponente.

Derivada de una función exponencial


Ejemplos

cálculo de derivadas  
 cálculo de derivadas
cálculo de derivadas 
cálculo de derivadas
cálculo de derivadas = cálculo de derivadas
cálculo de derivadas
cálculo de derivadas
cálculo de derivadas


cálculo de derivadas
cálculo de derivadas
cálculo de derivadas

La integral de una exponencial es de esta formula :
integral exponencial
Y qui algunos ejemplos:
integral exponencial
integral exponencial


integral exponencial
integral exponencial

Logarítmicas
En matemáticas, el logaritmo de un número —en una base determinada— es el exponente al cual hay que elevar la base para obtener dicho número. Por ejemplo, el logaritmo de 1000 en base 10 es 3, porque 1000 es igual a 10 a la potencia 3: 1000 = 103 = 10×10×10.
De la misma manera que la operación opuesta de la suma es la resta y la de la multiplicación la división, el cálculo de logaritmos es la operación inversa a la potenciación de la base del logaritmo.
Para representar la operación de logaritmo en una determinada base se escribe la abreviatura log y como subíndice la base y después el número resultante del que deseamos hallar el logaritmo. Por ejemplo, 35=243 luego log3243=5. Cuando se sobreentiende la base, se puede omitir.
Los logaritmos fueron introducidos por John Napier a principios del siglo XVII como un medio de simplificación de los cálculos. Estos fueron rápidamente adoptados por científicos, ingenieros, y otros para realizar operaciones más fácilmente, usando reglas de cálculo y tablas de logaritmos. Estos dispositivos se basan en el hecho más importante — por derecho propio — que el logaritmo de un producto es la suma de los logaritmos de los factores:
 \log_b(xy) = \log_b (x) + \log_b (y). \,

Propiedades


Los logaritmos, independientemente de la base elegida, cumplen una serie de propiedades comunes que los caracterizan. Así, logaritmo de su base es siempre 1; logb b = 1 ya que b1 = b. El logaritmo de 1 es cero (independientemente de la base); logb 1=0 ya que b0 = 1.
Si el número real a se encuentra dentro del intervalo 0 <  a < 1 entonces logb a da un valor negativo o se dice que es un logaritmo negativo. Es evidente, ya que si logaritmo de 1 es cero, entonces valores reales menores que uno serán negativos por ser la función logarítmica estrictamente creciente y cuyo recorrido es (-∞, +∞). También se puede demostrar usando la identidad logarítmica logb(x/y)=logb x - logb y; puesto que a pertenece al intervalo 0 <  a < 1, su inverso a-1 será mayor que uno, con lo que logb(a)=logb(1/a-1) = logb 1 - logb(a-1)= -logb(a-1).
Los números negativos no tienen logaritmo en el cuerpo de los reales R, ya que cualesquiera que sea el exponente n, se tendrá siempre que bn será mayor que cero, bn > 0; en consecuencia, no hay ningún valor real de n que pueda satisfacer bn = x cuando x sea menor que 0. Sin embargo, este obstáculo se puede salvar, ampliando el dominio de definición al cuerpo de los números complejos C, pudiendo calcular logaritmos de números negativos usando el logaritmo complejo o recurriendo a la fórmula de Euler.
Las potencias consecutivas de una base forman una progresión geométrica y la de los exponentes una progresión aritmética. Por ejemplo, las potencias de 2 son 1,2,4,8,16,32,64...etc y sus exponentes serán 0, 1, 2, 3, 4... etc ya que 20 = 1, 21 = 2, 22 = 4, 23 = 8, y 24 = 16 etc. luego log2 1 = 0, log2 2 = 1, log2 4 = 2, log2 8 = 3 y log2 16 = 4 etc.


Los logaritmos poseen ciertas identidades peculiares y aquí se las muestro.


Los logaritmos mantienen ciertas identidades aritméticas muy útiles a la hora de realizar cálculos:
  • El logaritmo de un producto es igual a la suma de los logaritmos de los factores.
 \!\, \log_b(x y) = \log_b(x) + \log_b(y) \,
  • El logaritmo de un cociente es igual al logaritmo del numerador menos el logaritmo del denominador.
 \!\, \log_b \left ( \frac{x}{y} \right ) = \log_b(x) - \log_b(y) \,
  • El logaritmo de una potencia es igual al producto entre el exponente y el logaritmo de la base de la potencia.
 \!\, \log_b(x ^ y) = y \log_b(x) \,
  • El logaritmo de una raíz es igual al producto entre la inversa del índice y el logaritmo del radicando.
 \!\, \log_b(\sqrt[y]{x}) = \frac{\log_b(x)}{y} \,
En realidad la tercera y cuarta identidad son equivalentes, sin más que hacer:
 \!\, \sqrt[y]{x} = x^\frac{1}{y} \,

Derivada de un logaritmo

Derivada de una función logarítmica
Como cambio de base, también se puede expresar así:
Derivada de una función logarítmica

Derivada de un logaritmo neperiano

Derivada de un logaritmo neperiano

Ejemplos de derivadas logarítmicas

cálculo de derivadas
cálculo de derivadas
cálculo de derivadas
Aplicando las propiedades de los logaritmos tenemos:
cálculo de derivadas
cálculo de derivadas