Tarea. 12

Para esta tarea seleccione el porblema 2.6 el cual dice lo siuiente:

Whenever p is true, it cannot be true again until both q and r have been true (q and r need not have been true simultaneously)

-cuando p es verdadero, no puede ser verdad otra vez hasta que ambos q y r haber sido cierto (q y r no necesita ser verdad al mismo tiempo)

El problema nos pide si el enunciado se puede traducir en un CTL

Yo opino que si se puede:

Tarea

Seleccione el siguiente ejercicio del Linear Temporal Logic LTL el cual menciona:


A holds at all states s3k and does not hold at all states s3k+1 , s3k+2 , where k = 0, 1, . . ..

Basandonos en lo siguiente relizaremos el problema:

=holds at all states s3k 

 not hold at all states s3k+1 , s3k+2+

En conclusion A solo tiene los estados 0s3,1s3,2s3,3s3... pero no tiene los estados s3+1,2s3+2

Tarea 7: Aplicación de la Lógica Predictiva

Hola compañeros y Dra. en esta entrada les hablare de una aplicación de la lógica predictiva  llamada Sistema axiomático.

Sistema axiomático

Este método consiste en aceptar sin prueba ciertas proposiciones como son los axiomas o algunos postulados y después de esos axiomas en derivar todas las proposiciones del sistema, en calidad ya de teoremas. Los axiomas son los cimientos del sistema y los teoremas las superestructuras.

Enfoque axiomático 

El enfoque axiomático puede interpretarse como una máquina que produce formas predicativas, de acuerdo con: reglas sintácticas, reglas de validez y axiomas.

Características de un enfoque axiomático:

• El concepto de verdad aparece como accesorio
• Su modelo se conforma por tres partes:
• Un cálculo
• Reglas de transformación
• Axiomas
  

Modelo del enfoque axiómatico

Cálculo: Nos dice  cómo es que se construirán formas proposicionales correctas, o fórmulas bien formadas (fbf), del lenguaje.

Alfabeto (signos primitivos):

• coma: {,}
• paréntesis: {( , )}
• Conectivos primitivos: {∨,
• ¬}
• Cuantificador universal: {∀}
• Constantes individuales: Ac = {a, b, c,..., a1, b1, c1,...}
• Variables individuales: Av = {x, y, z,..., x1, y1, z1,...}
• Símbolos de predicado: Ap = {P, Q, R,...,P1, Q1, R1 ...}
• Símbolos de función: Af = {f, g, h,..., f1, g1, h1,...}

Reglas de formación de fórmulas:

• Cualquier fórmula atómica es una fbf.
• Si R y S son fbfs, entonces R ∨ S es una fbf.
• Si R es una fbf, entonces (R) es una fbf.
• Si R es una fbf, entonces ¬R es una fbf.
• Si R es una fbf, entonces ∀x R es una fbf.

Definición de otros signos complementarios

• Pueden emplearse otros conectivos lógicos como: ∧, →, y ↔ para crear fbfs. Su
• definición corresponde a las vistas en el cálculo proposicional.
• También puede introducirse el signo de cuantificador existencial ∃, definido como
• sigue:  ∃x P ↔ ¬∀x ¬P, donde P es una fbf.

Axiomas

Son fbfs iniciales que se emplean para generar fbfs dentro del sistema axiomático.

• Axioma de Idempotencia
• Axioma de Adjunción
• Axioma de Conmutatividad
• Axioma de Adición
• Sean P y Q fbfs, entonces la fbf ∀x(P → Q) → (P → ∀xQ) es un axioma, siempre que P no posea  ocurrencias libres de x.

Reglas de inferencia

• Modus Ponems
• Sustitución
• Ejemplificación Universal (E.U.)
• Sea la fbf ∀xP, entonces se puede obtener la fbf Px|t.
• Donde P es una fbf y el término t es libre de la variable x en P.

Casos:

• De la fbf ∀xP se puede producir la fbf Px|x .
• De la fbf ∀xP se puede obtener la fbf P, donde x es una variable sin ocurrencias libres en P.
• De la fbf ∀xP se puede obtener la fbf Px|a, donde a es una constante individual.

• Ejemplificación Existencial (E.E.)

• Sea la fbf ∃x P, entonces se puede producir la fbf Px|t.
• Donde P es una fbf y el término t es libre de la variable x en P.

Restricciones:

La variable x no puede exhibir ocurrencias libres en alguna de las premisas o en alguna fbf obtenida en un paso previo de la deducción.
No aparecer el término t en la fbf de la conclusión, en alguna premisa o una fbf
obtenida en un paso previo de la deducción.

Casos:

De la fbf ∃xP se puede obtener la fbf Px|x

De la fbf ∃xP se puede producir la fbf P, donde x es una variable sin ocurrencias libres en P.

De la fbf ∃xP se puede producir la fbf Px|a, donde a es una constante individual.

Observación:

Si el término t es un símbolo de variable, éste se torna fijo al representar un individuo

que no se conoce pero se sabe que existe y, por tanto, no puede efectuarse ninguna

generalización universal sobre él posteriormente.

• Generalización Universal (G.U.)
• Si P es una fbf, entonces se puede obtener la fbf ∀xP

Restricciones:

x no posee ocurrencias libres en alguna premisa.
No se permiten generalizaciones universales a partir de P si en ésta el símbolo x se obtuvo de la aplicación previa de la E.E.

• Generalización Existencial (G.E.)
• Sea P una fbf, entonces se puede producir la fbf ∃xP.

Donde P es una fbf y la variable x debe originarse de un
término que en P aparezca como una constate individual o una
variable libre.

Leyes importantes:

∀xP ↔ P donde x no posee ocurrencias libres en la fbf P.

∃xP ↔ P donde x no posee ocurrencias libres en la fbf P.

∀xP ↔ ∀yPx|y donde y no posee ocurrencias libres en la fbf P.

∃xP ↔ ∃yPx|y donde y no posee ocurrencias libres en la fbf P.

Intercambio de cuantificadores

∀x P ↔ ¬ ∃x ¬ P

∃x P ↔ ¬ ∀x ¬ P

¬ ∀x P ↔ ∃x ¬ P

¬ ∃x P ↔ ∀x ¬ P

Negación de expresiones con varios cuantificadores

¬ ∀x ∀y P ↔ ∃x ∃y ¬ P

¬ ∃x ∃y P ↔ ∀x ∀y ¬ P

¬ ∀x ∃y P ↔ ∃x ∀y ¬ P

¬ ∃x ∀y P ↔ ∀x ∃y ¬ P

Propiedades conmutativas

∀x ∀y P ↔ ∀y ∀x P donde P es una fbf

∃x ∃y P ↔ ∃y ∃x P donde P es una fbf

∃x ∀y P → ∀y ∃x P donde P es una fbf

Leyes distributivas

∀x(P ∨ Q) ↔ ∀xP ∨ Q donde P y Q son fbfs, Q no posee ocurrencia  libres de x.

∃x(P ∧ Q) ↔ ∃xP ∧ Q ∀xP ∨ ∀xQ → ∀x(P ∨ Q) donde P y Q son fbfs, Q no posee ocurrencia libres de x.  donde P y Q son fbfs

∀x(P ∧ Q) ↔ ∀xP ∧ ∀xQ donde P y Q son fbfs

∃x(P ∧ Q) → ∃xP ∧ ∃xQ donde P y Q son fbfs

∃x(P ∨ Q) ↔ ∃xP ∨ ∃xQ donde P y Q son fbfs

∀x(P → Q) → (∀xP → ∀xQ) donde P y Q son fbfs

∀xP ∨ ∀yQ ↔ ∀x ∀y (P ∨ Q) donde P y Q son fbfs; además y no posee ocurrencias libres en P y x no posee ocurrencias libres en Q.

Otras

∀x(P →Q) ↔ (∃xP → Q) donde Q no posee ocurrencias libres de x.

∃x(P → Q) ↔ (∀xP → ∃xQ)

(∃xP → ∀xQ) → ∀x(P → Q)

(∃xP → ∀xQ) → (∀xP → ∀xQ)

∀x ∀y ∀z(P ∧ Q → R) ↔ ∀x ∀z (∃y (P ∧ Q) → R); donde la fbf P tiene ocurrencias libres de x y y, la fbf Q posee ocurrencias libres de y y z, y la fbf R posee ocurrencias libres de x y z.

Observaciones a tener en cuenta en procesos demostrativos:

Es diferente P | Q de | P → Q. En el primero, P es una premisa; en el segundo, P debe tratarse como una hipótesis auxiliar.

Cuando se encuentre en un proceso demostrativo, aplique primero la ejemplificación existencial que la universal.

Si P es una fbf, es posible sustituir cualquier subexpresión, o fbf, B de A, por una fbf C, siempre y cuando B y C hallan sido demostradas como equivalentes. (Esta es una forma de expresar la R.V. sustitución).

Cuando en un proceso de prueba sólo se emplee la R.V. sustitución, el resultado obtenido es lógicamente equivalente a la expresión de la cual surgió. Esto implica que en algunos procesos demostrativos de bicondicionales, requieran sólo demostrarse un solo sentido.

Demostrar una fbf A, es equivalente a demostrar que la fbf ¬A lo lleva a una contradicción.

No poder demostrar una fbf A, es equivalente a no poder probar que la fórmula ¬A lo lleva a una contradicción.

Bibliografía:

Link1

Problema 4.24 Lógica de predicados se pueden utilizar para contar dos gráficas separadas: encontrar una fórmula que es cierto en el uno, pero no en la otra. Considere las siguientes dos imágenes:

Dar una fórmula, y R para la relación, cierto en el lado izquierdo y falso a la derecha

Como vemos la imagen anterior se compone de flechas dirigidas lo que lo hace un grafo dirigido, estas flechas dirigidas son llamadas bordes.

En el libro viene una explicación la cual es la siguiente:

Nos dice que la imagen es un grafo dirigido y que las siguientes formulas son correctas para que lo representemos:

$\mathbf{ \exists x\exists yRxy}$

$\mathbf{\exists xRxx}$

$\mathbf{\rightharpoondown \forall x\exists yRxy}$

Como en este caso que el primer grafo la relación es reflexiba y seria $\mathbf{xRy}$ por eso es verdadera si existe por lo menos una x y una y.

Propiedad Transitiva

La cual se representa de la siguiente manera:

$\mathbf{xRy \wedge  yRz\rightarrow xRz}$

Referencia

Figura 1

Nos piden la relacion y en este caso la relaciòn es transitiva, ya que siempre hay flechas de x a y y de y a z.

Figura 2

Como vemos aquí no hay ninguna relación transitiva, por lo cual vamos a formular la relación con la transitiva para que el grafo 1 sea verdadero y el 2 sea falso.

¿Por que no usamos la simétrica ni la reflexiva?, no la usamos ya que los dos grafos tienen relación simétrica y reflexiva y no podríamos tener una formula que sea falsa para la segunda.

Formula:

$\mathbf{\exists x\exists y\exists z\left ( Rxy \wedge  Ryz \right )}$

$\mathbf{\exists x\exists y\exists z\left ( Rxy \wedge  Ryz \right )}$ es verdadera si existe por lo menos una x,y y z que 

Entonces llegamos a la conclusión que es verdadera para la izquierda y falsa para la derecha ya que la derecha no tiene relación transitiva 

Tarea 5: Lógica Predictiva 

En la tarea 5 seleccionamos un ejercicio del libro  Lean Symbolic Logic de Lewis Carroll, en este caso me toco el ejercicio numero 38:

No emperors are dentists 

All dentists are dreaded by children 

No emperors are dreaded by children. 

Traducción español:

No hay emperadores que sean dentistas

Todos los dentistas son temidos por los niños

No hay emperadores que sean temidos por los niños

No hay=Ningunos

E(x): emperors(emperadores)
D(x): dentists(dentistas)
N(x): dreaded by children(temidos por los niños)

Simbolos fundamentales que usaremos:

$\forall$: cuantificador universal (todos)
$\exists$ : cuantificador existencial (existe)

Sustituimos las palabras por símbolos:

• No emperors are dentists : $\mathbf{\rightharpoondown\exists (x) E(x)\to D(x)}$

• All dentists are dreaded by children: $\forall (x)D(x)\to N\left ( x \right ) $

• No emperors are dreaded by children: $\mathbf{\rightharpoondown\exists (x) E(x)\to N(x)}$

Conclusión:

Some people, dreaded by children, are not emperors

Someone dreaded by children, are not emperors: $\mathbf{\exists (x) N(x)\to \rightharpoondown E(x)}$




Referencias:

Link1
Link2
Link3
Link4

Tarea 4:


 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.

1-. Inventen una expresión Booleana.  

(((p^r)^(p|q))|^((¬r)|(p^q)))^¬q

Como vemos nuestra expresión Booleana tiene tres variables y cuenta con los 4 conectivos que son:
¬ : Negación
| = conjunción
^ = disyunción
→ = Implicación


Después realizamos la tabla de verdad de la expresión:

Después realice el árbol binario de desición:

En el arbol la linea gris es 1 y la linea gris punteada es 0.

2-. Construyan y dibujen su BDD(Binary Decisión Diagram).

Para poder construir un Diagrama Binario de Desición se toma en cuenta:

1. Quitar los nodos terminales repetidos: Dejamos un solo nodo 0 y 1
2. Quitar los nodos no terminales repetidos (coinciden la variable y los hijos)

3. Quitar tests redundantes (coinciden los dos hijos)

3 y 4 -. Reduzcan el BDD resultante a un ROBDD y dibujarlo:

Cambie la posición de las variables como se muestra a r,q,p.

Como vemos se redujo a 4 nodos de los 5 que teniamos.

Referencias: DBB

Tarea2:

 La tarea 2 es checar si las claves que genera nuestro otp (one time pad) realmente es aleatoria.

 La clave evaluada fue la siguiente:


Esta clave es generada del programa anterior con el siguiente código:

Funciona leyendo las claves del archivo llamado key.txt pasandoselo a cada uno de los test.



Primero yo realice un test sencillo que se llama Monobit:

Monobit

Detecta los ceros y los unos que se encuentran en la cadena binaria, sustituyendo los ceros que encuentre por -1, asi realizando una suma. La aparición de ceros y unos en la secuencia global deberan de ser igualmente probables

Datos a tener:

n = tamaño de la clave binaria
ε =La secuencia de bits que se esta probando

Procedimiento:

1. Como mencione se buscan los ceros y se sustituyen por -1y se realiza una suma, ejemplo:
   lista=[1,1,0,0,1,0,1]
   quedaría:
   lista=[11,-1-1,1-11]
 y se realiza la suma de la lista

2-Se calcula la prueba estadística:

3. Se calcula p_value ( erfc es la función error complementaria.)

4.Si P - value > 0.01, la secuencia  es aleatoria.

Código:

Captura de pantalla de la prueba:

También utilice otras dos pruebas que es la de Poker y la de frecuencia de Bloques

Frecuencia de Bloques

En la prueba de bloques los ceros y unos deberan de ser igualmente probables.
 Datos:

n - largo de la secuencia
m - el largo de cada bloque
ε - secuencia de bits generada

Recomendaciones:

Procedimiento:

1. Se parte la prueba e bloques de un cierto tamaño se calcula de la siguiente manera:
  

2. Se determina la proporción de unos:

3. Se calcula la chi2=X2

4.  Se calcula la p_value:

Código

Captura de pantalla

Prueba de Póker

Lo que hace la prueba de póker es dividir la clave en numeros de 4 bist, por ejemplo si yo tengo esta:

0101000001100011

se divide de la siguiente manera :
0101 0000 0110 0011

entonces como se divide en 4 hay 16 posibles resulados que pueden salir y esos 16 resultados son contados las veces que estan o el número de frecuencias de cada uno.

La formula que se realiza es la siuiente:

en donde:
m = es el tamaño de la división de la secuencia en este caso 4
n = lóngitud o tamaño de la secuencia binaria
k = es la división de m entre n

Pasos:

1. Se divide la serie de número binarios en secciones de 4 numeros (0000).
2. Se buscan las frecuencias de los 16 diferentes numeros que se pueden encontrar
3. La frecuencia se eleva al cuadrado
4. Se realiza lo que es la ecuación anterior:

         x2=(16/k)(frecuencias al cuadrado)-k

La prueba se pasa cuando 1.03 < x < 57.4

Captura de pantalla

Con otra cantidad de claves:

Monobit

Frecuencia de Bloques

Poker test

La clave pasa las pruebas eso quiere decir que es segura.

Referencias:

Link1
Link2
LInk3