Programación Lógica (Metodo de Resolución)

Luis Abraham · #1 27-10-2004

Que tal foro !!!!

Necesito hacer un programa que compruebe Tautologias mediante el Método de Resolución, pero que previamente compruebe que las premisas introducidas son Formulas Bien Formadas.

Si alguien puede ayudarme o sabe donde puedo encontrar ayuda al respecto se lo agradecere infinitamente.

De antemano muchas gracias !!!!

roman · #2 27-10-2004

No sé a que tanta gente aquí le sea familiar el tema pero quizá si explicas un poco que significa todo esto (algunos ejemplos no caerían mal) haya alguien que te pueda dar ideas.

// Saludos

Luis Abraham · #3 27-10-2004

Tienes razon roman este no es un tema muy común pero tratare de explicarlo brevemente.

Quizas sea bueno comenzar con las tan famosas Tabas de Verdad, en las que se involucran distintas Premisas por medio de Operadores Lógicos. Las premisas son representadas con letras y mientras que los operadores lógicos son los ya conocidos And, Or, Implicación, Doble Implicación, entre otros, y sus simbolos son los siguientes:

And ^
Or v
Implicación ->
Doble Implicación <->

Y no olvidemos la famosa Negación representada como ~.

Cabe mencionar que la Implicación (P->Q) equivale a (~PvQ) y la Doble Implicacion (P<->Q) equivale a (P->Q)^(Q->P) o bien (~PvQ)^(~QvP).

Ahora bien como resultado de estas operaciones lógicas obtenemos 3 distintos tipos de respuestas. Tautologias, Contingencias y Contradicciones. Una Tautologia es cuando todos nuestros valores resultantes son verdaderos, una Contingencia es cuando nuestros valores obtenidos son tanto verdaderos como falsos y una Contradicción es cuando todos los valores de verdad obtenidos son falsos.

He aqui algunos ejemplos:

Tablas de Verdad sencillas:

P | Q | P^Q
-----------
V | V | V |
V | F | F |
F | V | F |
F | F | F |

P | Q | R | (P^Q)vR
-------------------
V | V | V | V | V | Nota: Observece que el resultado obtenido
V | V | F | V | V | de (P^Q) se evalua con vR.
V | F | V | F | V |
V | F | F | F | F |
F | V | V | F | V |
F | V | F | F | F |
F | F | V | F | V |
F | F | F | F | F |

Contingencia:

P | Q | R | (P->Q)->R
---------------------
V | V | V | V | V | Nota: Al igual que en el ejemplo anterior el
V | V | F | V | F | resultado de (P->Q) se evalua con ->R.
V | F | V | F | V | Como podemos ver al final obtenemos tanto
V | F | F | F | V | resultados Falsos como Verdaderos por lo que este
F | V | V | V | V | argumento es una Contingencia.
F | V | F | V | F |
F | F | V | V | V |
F | F | F | V | F |

Tautologia:

P | Q | (P->Q)v(Q->P)
----------------------
V | V | V | V | V |
V | F | F | V | V |
F | V | V | V | F |
F | F | V | V | V |

De igual forma que en los ejemplos anteriores la Contradicción es una operación en la que todos los valores de verdad resultantes son Falsos, por lo que creo que no es necesario poner un ejemplo mas.

Bueno, como se pueden dar cuenta nuestro número de resultados va a depender directamente del numero de Premisas que tengamos y es facil de calcular mediante la sencilla oprecion matemática 2^n, donde n es el numero de premisas. Por ejemplo si tenemos P, Q y R, tendremos 2^3 resultados, es decir 8, si tenemos P, Q, R, S y T, nuestros resultados seran 2^5=32, por lo que se hace demasiado laborioso construir la tabla de verdad conforme el número de premisas aumenta, ahora imagina que tienes algo como esto: {[(P->Q)^(~Q->R)^(R->S)^(S->~T)]<->~(UvV)}->(P->Q), la tabla de verdad seria algo verdaderamente espantoso

.

Es por eso que existen distintos metodos para comprobar si los argumentos son tautologias. Estos metodos hacen que sea mucho mas corto el procedimiento y mucho mas rapido y uno de ellos es el Metodo de Resolución, el cual necesito programar

.

Aqui podran encontrar un poco más sobre el metodo de resolucion:
http://www.uhu.es/nieves.pavon/pprog...exo/anexo.html
http://w3.mor.itesm.mx/~logica/log9808/Resolucion.html

Se darán cuenta que no es mas eliminación de terminos con signos contrarior y separacion de premisas unidas por un And ^, es decir si tengo (A^B), las puedo separar en dos A y B.

Bueno espero no haberlos enfadado con tanto rollo, Gracias.

roman · #4 27-10-2004

Interesante. No diré que me es totalmente desconocido pero lo que alguna vez aprendí lo tengo bastante oxidado.

Cita:

Empezado por Luis Abraham

Bueno espero no haberlos enfadado con tanto rollo

Para nada. En lo personal es agradable de vez en vez ver algo totalmente ajeno a sistemas y bases de datos.

Déjame ver si he entendido algo.

Entiendo que la tautología quizá más simple es P v ~P y la contradicción quizá más sencilla es P ^ ~P

Entiendo también que (P -> Q) sea equivalente a ~P v Q, aunque me es más sencillo entenderlo primero como equivalente a ~(P ^ ~Q).

Entonces me queda claro, por ejemplo, que (P -> Q) v (Q -> P) sea una tautología. Aunque llevado a la práctica me deje un poco perplejo:

Cita:

Una de las dos siguientes aseveraciones es cierta:

A. Si los pingüinos vuelan entonces los delfines caminan
B. Si los delfines caminan entonces los pingüinos vuelan

Según entiendo entonces, comprobar que una proposición es una tautología es comprobar que cualesquiera valores (F o V) que tomen sus premisas el resultado siempre será verdadero ¿cierto?

Pero vamos a ver. No me queda claro si la comprobación debe hacerse necesariamente probando cada posible valor y examinando su resultado (construir la tabla de verdad). Me explico:

Supongamos que quiero ver que (P -> Q) or (Q -> P) es una tautología. (Voy a cambiarte la notación: v=or, ^=and, ~=!)

Procedería por pasos, derivando proposiciones equivalentes:

(P -> Q) or (Q -> P)
(!P or Q) or (!Q or P) por equivalencia de implicaciones
!P or (Q or (!Q or P)) por asociatividad
!P or ((Q or !Q) or P) por asociatividad
!P or (true or P) por tautología
!P or true por tautología
true por tautología

Claro que no sé cómo se haría en un caso general pero quizá hay una forma canónica de reducir proposiciones a su mínima expresión.

Bueno, realmente no estoy ayudando en nada pero ¿qué quieres? Esto me gusta (aunque no lo entienda del todo) y tú empezaste

.

Ahora, falta que aclares (si no hay problema) qué significa que una proposición (¿fórmula?) esté bien formada y cuáles serían las técnicas lógicas para determinarlo. Supongo que éste es el primer punto a resolver pues pienso que primero que nada hay que ver de qué manera se va a representar una fórmula ya en términos computacionales (¿Posiblemente un árbol binario?)

Oye, y ¿no sería mejor usar algo como Prolog?

// Saludos

pd: Ahora discúlpame tú por este rollo que no ayuda

maruenda · #5 27-10-2004

hola. bueno lo que planteas es largo de hacer. Yo lo hice en el año 95 mas o menos. En la universidad de alicante nos lo pusieron como practica de logica. Habia que hacer 3 cosas.
introducias una formula y
1º - decir si la formula era correcta.
2º - pasarlo a forma normal conjuntiva y normal disyuntiva
3º - y decir si era cierto, falso o indeterminacion .

tarde 1 mes en hacerlo. use prolog, e implemente el algoritmo con listas. no utilizé arboles. la parte mas complicada fue la tercera. Para resolverlo planteate todas las posibles causas que hacen que una formula sea cierto, las que sean falso, y las que sean indeterminacio. haz las dos mas faciles, y la mas dificil o larga, dejala y la resuelves por eliminacion ( si algo no es cierto ni falso, entonces debe ser indeterminacion ,, por ej ).
yo use ese metodo . Voy a ver si tengo algo en un disquete y te amplio un poco mas la informacion. Ufff, hace de eso un chorro de años.