lunes, 17 de septiembre de 2012

Semana 6


Para esta semana tenemos que escoger un problema (de aqui) y resolverlo.

Mi problema es el siguiente:

When a formula is false in a graph, we may want to change that graph in a minimal manner to make the formula true after all. Think of an engineer changing a blueprint to meet a given specification. Consider the following graph:
The formula ∃x∀yRxy is false in the graph if R is interpreted as the → relation. Make the formula true by adding a single → link to the graph.

Explicación: 

La parte teórica de este pdf no dice que  "Rxy" es una expresión con 2 objetos(nodos) que están unidos con una arista(en realidad una flecha) del primer objeto al segundo objeto.


y cualquiera de las siguiente formulas es verdadera para representarlo:

 


También nos menciona que esto:

es lo mismo que esto:


y su formula para representarlo es:

∀x∀y(Rxy → Ryx)

y no solo para este ejemplo, si no que también para cualquier grafo no dirigido.

Ahora que ya tenemos las herramientas suficientes, nuestro problema dice (en palabras generales), que a nuestro grafo no le pertenece la formula y que tenemos que rediseñar el grafo para que sea verdadera.

Recordemos la formula:

∃x∀yRxy 

Esto lo podemos representar:

"Rxy" es verdadera si existe cualquier "y" y por lo menos una "x"

es lo mismo que

"Rxy" es verdadera si existe cualquier "y" y por lo menos una "x"


Referencias:

http://es.wikipedia.org/wiki/L%C3%B3gica_de_primer_orden#Cuantificadores

http://www.scribd.com/doc/21557553/CUANTIFICADORES