Métodos Mecánicos (Método del Cuadro y Davis-Putnam)

Escrito el 27 noviembre 2007 por madlc.
Categorías: Bloque II Semántica, Clases Teóricas.

clase Nº 8, 27 de Noviembre de 2007, Horario: 15:00 – 17:00, Carlos Villagrá.

La temática del día de hoy ha sido la continuación de la clase anterior, hemos visto los métodos mecánicos que sirven para demostrar si una fbf es tautología, contradicción o contingencia.

Estos métodos son el Método del Cuadro y Davis-Putnam, me parecen métodos completos porque hasta ahora las tablas de verdad tenían el problema que se complicaban a medida que el número de variables aumentaba, y el método del contraejemplo en el caso de no ser tautología no brindaba información de contradicción o contingencia.
A pesar de que esos dos métodos son completos, al principio no me han gustado mucho, la verdad no son muy dificiles, pero al ver la lista de pasos que hay que seguir uno tiene mala recepción a el, pero al igual como he dicho en temas anteriores, con ejercicios de práctica se mejora y memorizan los pasos a aplicar.





Método del Cuadro

Para poder aplicar el método del cuadro es necesario tener la fórmula en su forma normal disyuntiva.
Los pasos para aplicar este método son:

1 Si en todas las conjunciones elementales aparece un literal afirmado y negado: CONTRADICCIÓN.

2 Si hay conjunciones elementales de un solo literal se le asigna el valor F y se reduce la fbf.

3 Si no paso 2, se elige conjunción y obtenemos dos FND:
C v B= (lit ∧ D) v B = (lit v B) ∧ (D v B) y se hace nuevamente el paso 2.

4 Se repiten 2 y 3 hasta obtener una conjunción elemental:
Si disyunción de literal y complementario: fbf TAUTOLOGÍA
Sino: fbf CONTINGENTE



Veamos el siguiente ejemplo visto en clase:

(p → q) v ¬r
FND: ¬p v q v ¬r

1) No es contradicción
2) ¬p = F = F V q V ¬r = q V ¬r
q= F = f v ¬r
¬r = F ó V, entonces CONTINTENGIA



El siguiente ejemplo también lo vimos en clase y es del libro Lógica de Primer Orden:
FND: p v (¬p ∧ q ∧ r) v (¬p ∧ ¬q ∧ r) v (¬p ∧ ¬r) v (p ∧ r)

1) No es contradicción
2) p = F = F v (V ∧ q ∧ r) v (V ∧ ¬q ∧ r) v (V ∧ ¬r) v (F ∧ r)
F v (q ∧ r) v (¬q ∧ r) v ¬r v F
(q ∧ r) v (¬q ∧ r) v ¬r

¬r = F = (q ∧ V) v (¬q ∧ V) v F
(q ∧ V) v (¬q ∧ V) v F
q v ¬q v F
q v ¬q, entonces TAUTOLOGIA



FND: (p ∧ ¬q ∧ r) v (¬p ∧ q) v (¬q ∧ ¬r)
1) No es Contradicción
2) Descomponer;
C = (¬p ∧ q)
B = (¬q ∧ ¬r) v (p ∧ ¬q ∧ r)

C v B = (¬p ∧ q) v (p ∧ ¬q ∧ r) v ¬q ∧ ¬r
lit v B = ¬p v (p ∧ ¬q ∧ r) v (¬q ∧ ¬r)
D v B = q v (p ∧ ¬q ∧ r) v (¬q ∧ ¬r)
Para que fuera tautología deberían serlo los dos.





Método de Davis-Putnam

Para poder aplicar el método del cuadro es necesario tener la fórmula en su forma normal conjuntiva.
Los pasos para aplicar este método son:

1 Si en todas las disyunciones elementales aparece un literal afirmado y negado: TAUTOLOGÍA.

2 Si hay disyunciones elementales de un solo literal se le asigna el valor V y se reduce la fbf.

3 Si un literal aparece sólo en un estado se le asigna el valor V y se reduce la fbf.

4 Sino, elegir literal (l) que desaparece de la fbf. Hacer:
B: disyunciones que contienen l;
C: disyunciones que contienen ¬l;
D: resto
Obtener FNC sin l: [∧ (b v c) ] ∧ D. y vuelve a realizarse el paso 2.
Si conjunción de literal y complementario: fbf CONTRADICCIÓN
Sino: fbf CONTINGENTE

Ejemplo:

¬p ∧ (p v q v r) ∧ (¬q v r v ¬s) ∧ (¬q v ¬r)

1) No es tautología
2) ¬p = V
V ∧ (F v q v r) ∧ (¬q v r v ¬s) ∧ (¬q v ¬r)
(q v r) ∧ (¬q v r v ¬s) ∧ (¬q v ¬r)
3)¬s = V
(q v r) ∧ (¬q v r v V) ∧ (¬q v ¬r)
(q v r) ∧ V ∧ (¬q v ¬r)
(q v r) ∧ (¬q v ¬r)
4) Elijo “q” y descompongo:
B = (q v r)
C = (¬q v ¬r)
r v ¬r = V, entonces CONTINGENCIA.

Qeet iMporTah
Comentario on noviembre 10th, 2009.

Taa MamOn !!
SiigOh Sin enTenDeR….
:$