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:
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:
Esto lo podemos representar:
es lo mismo que
Referencias:
http://es.wikipedia.org/wiki/L%C3%B3gica_de_primer_orden#Cuantificadores
http://www.scribd.com/doc/21557553/CUANTIFICADORES
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:
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.
También nos menciona 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
Ehm. No deberías haber quitado ninguna arista. La expresión significa "hay por lo menos un nodo que tiene una flecha a todos los nodos", que en este caso implica que hubo que agregar una flecha del nodo central a si mismo, lo que sí hiciste. Por la mala interpretación verbal ("Rxy" es verdadera si existe cualquier "y" y por lo menos una "x") quito dos puntos, y quito otro por haber quitado la arista. 7 pts.
ResponderEliminar