Categories
Examinadores

Examinador 1 Bloque III

1. Un supuesto provisional es:
a) Una subdeducción que infiere una nueva fbf
b) Un método para determinar si una fbf es tautología
c) Una deducción que demuestra que una fbf es contradicción o tautología
d) Un paso del método del Cuadro

2. Dadas las sentencias: “ Javi juega al mus o al Chinchón, pero no a ambos; Javi no juega
al mus a menos que María también juegue; Sin embargo, María juega al mus sólo si Javi
juega” ¿ ¿Qué sentencia podemos deducir?
a) María no juega al mus.
b) María si juega al mus.
c) Si Javi juega al Chinchón, María juega al mus
d) Si María juega al mus entonces Javi juega al Chinchón o al mus

3. En D={Universidad} definimos S1: “No existen alumnos traviesos”. Con los predicados
Tr(x): x es travieso; Al(x): x es alumno. ¿cuál de las siguientes fbf podemos deducir de
S1 si nos aseguran que “no hay alumnos”?
a) Sólo se deduce esta fbf: ∀x[¬Al(x) ∨ Tr(x)]
b) Sólo se deduce esta fbf: ∀x[Al(x) → ¬Tr(x)]
c) Se deducen a) y b)
d) No se deduce ni a) ni b)

4. Dada la fbf ∀x[A(x) → B(x)] ¿Qué fbf podemos deducir si D={a}?
a) A(a)
b) B(a)
c) ∃xA(x) → ∃xB(x)
d) ∀xB(x) → ∀xA(x)

5. En D={a}, definimos la fbf : ∀x[A(x) → B(x) ∨ C(x)] ¿Qué fbf podemos deducir?
a) A(a)
b) ∃xA(x) → ∃x[B(x) ∨ C(x)]
c) ∀x[B(x) ∨ C(x)]
d) Ninguna de las tres

6. Dadas las fbfs: P1: ∀x∀y[Q(x,y) → ¬R(x,y)], P2: ∀xQ(x,x) ¿Qué fbf podemos deducir si
x, y ∈ D = {a,b}?
a) ¬R(a,b)
b) ¬R(x,y)
c) Q(a,b)
d) ¬R(a,a)

7. Dadas las fbfs: P1: ∀x[P(x) → Q(x)], P2: ¬∃xQ(x) ¿Qué fbf podemos deducir?
a) P(a)
b) ¬P(a) ∧ ¬Q(a)
c) P(b)
d) P(a) ∧ Q(a)

8. Dadas las fbs: P1: ∀x[A(x) → Q(x,b) ∧ R(x)], P2: ∃xQ(x,b), P3: ∃xA(x) ¿Qué fbf podemos
deducir?
a) ∀xA(x)
b) Q(a,b) ∧ R(a)
c) ∃x(Q(x,b) ∧ R(x))
d) Q(a,b) ∨ A(a)

9. Dadas las sentencias:
P1: Todas las modelos que saben desfilar le gustan a Carlos.
P2: A Carlos no le gusta Sara si ésta es actriz pero si no lo es, Sara besará a Carlos
apasionadamente.
P3: Por desgracia, nadie besa a Carlos apasionadamente.
¿Qué sentencia podemos deducir?
a) Sara no sabe desfilar
b) Sara besa a Carlos apasionadamente si Pilar le deja hacerlo
c) Sara es modelo
d) O Sara no es modelo o no sabe desfilar

10. Dadas las fbfs: P1: ∀x(Pi(x) → ¬Ca(x)). P2:∃x(Ca(x) ∧ Pe(x))

¿Qué fbf podemos deducir?
a) Ca(a) ∧ Pe(a)
b) ∃x [Pi(x) ∧ Pe(x)]
c) ∀x[Ca(x) ∧ Pe(x)]
d) ∃x[¬Pi(x) ∧ Pe(x)]

Categories
Bloque IV DAT Clases Teóricas

Bloque IV “DEMOSTRACIÓN AUTOMÁTICA DE TEOREMAS” DAT

clase Nº 13, 15 de Enero de 2007, Horario: 15:00 – 17:00, Carlos Villagrá.


Hoy después de cuatro meses hemos tenido nuestra última clase de lógica en la cual tuvimos la explicación del bloque IV e hicimos el último examinador sobre Deducción Natural.

Lo que pudimos ver del tema me hace pensar que no es muy dificil deducir argumentos por medio de la Resolución, pero claro!, hay que tener en cuenta que para poder utilizar este método antes que todo debemos obtener la Forma Clausual de la fórmula, factor que hace un poco desagradable el método para el caso de fórmulas del lenguaje predicativo, que incluye aplicar la forma normal de Prenex y de skolem, que aunque Prenex no presente dificultad, lo muestra skolem en el caso de encontrarse cuantificadores existenciales en el ámbito del cuantificador universal; del resto parece ser un método bastante práctico.






El proceso “DAT” para estudiar la validez de un argumento consiste en:

  • Formalizar el problema a resolver P1,…,Pn ⇒ Q.
  • Obtener un conjunto de fbfs C formado por todas las “CLÁUSULAS” que se obtienen de las premisas.
  • Negación de la fbf conclusión (¬Q) .
  • Añadir a C las cláusulas que se obtienen de ¬Q
  • Demostrar que el conjunto C ={CP1, CP2,…,C¬Q} es INSATISFACIBLE usando la REGLA DE RESOLUCIÓN DE ROBINSON.


  • La Regla de Resolución dice:

    Dadas dos claúsulas que contienen una el literal L y otra ¬L, es decir de la forma, L v A1, y ¬L v A2, puede deducirse de ambas la fórmula A1 v A2. Esta fórmula se llama cláusula resolvente, y a las fórmulas a las que se les aplica, formulas padres.

    La clausula resolvente se calcula tomando la disyunción de las dos cláusulas y eliminando de ellas el par de complementarios L v ¬L.

    Cláusulas Padre

    [L v A1 v A2 v … v An ] y [ ¬L v B1 v B2 v … v Bm ]

    Cláusula resolvente

    [A1 v … v An v B1 v … v Bm]






    Ejemplos:
    Cláusula Padre:P y ¬P v Q
    Cláusula Resolvente: Q

    Cláusula Padre:P v Q y ¬P v Q
    Cláusula Resolvente: Q

    Cláusula Padre:P v Q y ¬P v ¬Q
    Cláusula Resolvente: Q v ¬Q, P v ¬ P

    Cláusula Padre: Q y ¬ Q
    Cláusula Resolvente: NADA (La Cláusula Vacía [] significa contradicción)

    Cláusula Padre:P v Q Y ¬P v R
    Cláusula Resolvente: Q v R



    El siguiente argumento del calculo de proposiciones fué el ejemplo utilizado en clase para demostrar por medio de la Refutación por Resolución.

    (p→q)→r,¬p v q ⇒ r

    La Forma Clausual de la fórmula correspondiente a la afirmación de las premisas y la negación de la conclusión es:
    [(p → q) → r] ∧ (¬p v q) ∧ ¬ r
    [¬(¬p v q) v r] ∧ (¬p v q) ∧ ¬ r
    [(¬¬p ∧ ¬q) v r] ∧ (¬p v q) ∧ ¬ r
    [(p ∧ ¬q) v r] ∧ (¬p v q) ∧ ¬ r
    (p v r) ∧ (¬q v r) ∧ (¬p v q) ∧ ¬ r

    C1: p v r
    C2: ¬q v r
    C3: ¬q v q
    C4: ¬r

    ej_biv.jpg

    En conclusion hemos llegado a la clásula vacía que no es mas que una prueba de insatisfacibilidad, que demuestra que es correcto el argumento.





    RESOLUCIÓN EN EL LENGUAJE PREDICATIVO

    UNIFICACIÓN:
    Proceso por el cual mediante sustitución de términos de variables podemos obtener expresiones idénticas y así se pueden unificar.

    Veamos ahora el ejemplo visto en clase.

    Cualquiera que puede cantar es cantante
    Los pájaros no son cantantes
    Algún pájaro tiene buena voz
    Luego, Alguiennn que tiene buena voz no puede cantar

    R(x): x puede cantar
    C(x): x es cantante
    P(x): x es pájaro
    V(x): x tiene buena voz

    Formalizamos
    ∀x[R(x) → C(x)]
    ∀x[P(x) → ¬C(x)]
    ∃x[P(x) ∧ V(x)] ⇒ ∃x[V(x) ∧ ¬R(x)]

    Convertimos a Forma Clausual:

    ∀x[R(x) → C(x)] ∧ ∀x[P(x) → ¬C(x)] ∧ ∃x[P(x) ∧ V(x)] ∧ ¬∃x[V(x) ∧ ¬R(x)]

    C1: ¬R(x) v C(x)
    C2: ¬P(y) v ¬C(y)
    C3: P(a)
    C4: V(a)
    C5: ¬V(z) v R(z)
    ej2_biv.jpg

    Por último enlazo el examinador de Deduccion Natural, con la solución de Carlos:Control Bloque III.

    Categories
    Examinadores

    Examinador 3 Bloque II

    1. El razonamiento p→ q, q → r ⇒ p → r es correcto porque:
    a) La fbf ¬(p→ q) ∧ ¬(q → r) ∧ (p → r) es tautología
    b) La fbf p→ q es una tautología
    c) La fbf (p→ q) ∧ (q → r) ∧ (p → r) es contradicción
    d) La fbf ¬(p→ q) ∨ ¬(q → r) ∨ (p → r) es tautología

    2. Para demostrar que el razonamiento P1, P2, P3 ⇒ Q es correcto:
    a) Es suficiente con que la fbf Q sea tautología
    b) Es necesario que la fbf Q sea tautología
    c) Es necesario que la fbfs premisas sean tautologías
    d) Un argumento es correcto sólo si la fbf Q es tautología

    3. Si el razonamiento P1, P2, P3 ⇒ Q es correcto, podemos afirmar que :
    a) El conjunto C={ P1, P2, P3, Q} es contingente
    b) El conjunto C={ P1, P2, P3, ¬Q} es consistente
    c) El conjunto C={ P1, P2, P3, Q} es insatisfacible
    d) El conjunto C={ P1, P2, P3, ¬Q} es insatisfacible

    4. El método de Davis-Putnam se utiliza para :
    a) Determinar el número de interpretaciones de una fbf
    b) Normalizar fbfs del lenguaje proposicional
    c) Determinar cual es el valor semántico de una fbf
    d) Obtener la FNC de una fbf proposicional.

    5. ¿Cuál de las siguientes fbf puede ser la conclusión de un conjunto de premisas vacío?
    a) P(a,b,c) ∨ Q(a,b,c)
    b) P(a,b) ∨ ¬P(b,c)
    c) Ninguna fbf puede deducirse de un conjunto de premisas vacío
    d) P(a,b,c) ∨ ¬P(a,b,c) ∨ Q(a,b)

    6. Para demostrar que una conjunción de cláusulas es tautología:
    a) Es necesario que cada cláusula sea una tautología
    b) Es suficiente con que al menos una cláusula sea tautología y las demás sean
    contingentes
    c) Una conjunción de cláusulas no puede ser tautología, sólo contradicción
    d) Es necesario que todas las cláusulas tengan un literal afirmado

    7. Para demostrar que la fbf A: C1 ∨ C2 ∨ … ∨ Cn, n>=1, con Ci conjunciones elementales,
    es contradicción:
    a) Es necesario que todas las Ci sean contingentes
    b) Es suficiente con que al menos una conjunción elemental sea contradicción
    c) Es necesario que cada Ci sea contradicción
    d) Una disyunción de conjunciones nunca puede ser contradicción

    8. Dadas las sentencias:
    “A menos que me regales un anillo o bombones, no me caso contigo. Como me has
    regalado bombones”.
    ¿Qué sentencia es consecuencia lógica de ellas?
    a) Me caso contigo y me como los bombones
    b) Si no me regalas el anillo ni los bombones no me caso contigo
    c) Me caso contigo sólo si me regalas el anillo o te pones cariñoso
    d) Ni me caso ni me como los bombones

    9. En la sentencia:
    S1: “Para que salgan el hombre lobo o drácula es necesario que haya luna llena”
    interpretamos “no hay luna llena” como verdadera ¿Qué sentencia debemos interpretar
    también como verdadera para que S1 sea verdadera?
    a) Ni sale el hombre lobo ni drácula
    b) Sale el hombre lobo o drácula
    c) No sale el hombre lobo pero si sale drácula
    d) Salen los dos

    10. La fbf Q es consecuencia lógica de un conjunto de fbf P ={P1,…,Pn} cuando:
    a) Alguna interpretación que es un modelo de P es también un modelo de Q
    b) Toda interpretación que es un modelo de P es también un modelo de Q
    c) Toda interpretación que es un modelo de P es un contramodelo de Q
    d) Algunas interpretaciones son contramodelos de P y de Q

    Categories
    Examinadores

    Examinador 2 BLoque II

    1. El método del Cuadro sólo evalúa semánticamente fbf
    a) Escritas en forma normal disyuntiva
    b) Formalizadas con el lenguaje de predicados
    c) Escritas en forma normal conjuntiva
    d) Escritas en forma normal disyuntiva y conjuntiva

    2. El método de Davis-Putnam sólo evalúa semánticamente fbf
    a) Escritas en forma normal disyuntiva
    b) Formalizadas con el lenguaje de predicados
    c) Escritas en forma normal conjuntiva
    d) Escritas en forma normal disyuntiva y conjuntiva

    3. La fbf A: (p ∧ ¬p ∧ ¬r) ∨ (¬p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ r) ∨ ¬p, se interpreta como:
    a) Tautología cuando el literal ¬p se interpreta a verdadero
    b) Satisfacible, cuando el literal ¬p se interpreta a verdadero
    c) Insatisfacible, cuando el literal ¬p se interpreta a falso
    d) Contramodelo, cuando el literal ¬p se interpreta a falso

    4. La fbf A: (p ∧ ¬p ∧ ¬r) ∨ (¬p ∧ ¬q ∧ ¬r) ∨ (¬p ∧ r) ∨ ¬p, según el método del Cuadro se
    evalúa semánticamente como:
    a) No podemos saberlo porque tenemos una conjunción con un literal
    b) Contingente, porque tiene interpretaciones modelos y contramodelo
    c) Contradicción porque hay una conjunción con dos literales complementarios
    d) Tautología para el conjunto de interpretaciones de sus componentes

    5. La fbf B: (p ∨ ¬p ∨ r) ∧ (q ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬p) ∧ ¬r, se interpreta como:
    a) Contradicción cuando el literal ¬r se interpreta a falso
    b) Satisfacible, para cualquier interpretación de ¬r
    c) Falsa, cuando el literal ¬r se interpreta a falso
    d) Contramodelo, cuando el literal ¬r se interpreta a falso

    6. La fbf B: (p ∨ ¬p ∨ r) ∧ (q ∨ ¬q ∨ ¬r) ∧ (p ∨ ¬p) ∧ ¬r, según el método de Davis-Putnam
    se evalúa semánticamente como:
    a) No podemos saberlo porque tenemos una disyunción con un literal
    b) Tautología para el conjunto de interpretaciones de sus componentes
    c) Contradicción porque hay disyunciones con literales complementarios
    d) Contingente, porque tiene interpretaciones modelos y contramodelo

    7. Dado el argumento P1, P2, P3, P4 ⇒ Q aplicando dos veces el Teorema de Deducción
    obtenemos:
    a) Una estructura de la forma P1, P4 ⇒ P2 → (P3 → Q)
    b) Una estructura de la forma P1, P2 → (P3 → Q) ⇒ P4
    c) Una estructura de la forma P1, P4 , ⇒ P2 , P3 , Q
    d) Ninguna de las anteriores

    8. Dado el argumento P1, P2, P3, P4 ⇒ Q su fbf asociada es la siguiente:
    a) P1 ∧ P2 ∧ P3 ∧ P4 ∧ Q
    b) P1 ∧ P4 ∧ P2 ∧ P3 → Q
    c) ¬P1 ∨ ¬P4 ∨ ¬P2 ∨ ¬P3 ∨ ¬Q
    d) Ninguna, porque un argumento sólo tiene fbf asociada si ésta es tautología

    9. Dada la fbf C: ∀x[A(x) → B(x)] , D={a} Podemos asegurar que:
    a) La fbf C’: ∃x[A(x) ∧ B(x)] es equivalente a C
    b) La fbf C’’: ¬A(x) ∨ B(x) es equivalente a C
    c) La fbf C’’’: ¬∃x[A(x) ∧ ¬B(x)] es equivalente a C
    d) La fbf C’V :A(x) → B(x) es equivalente a C

    10. Dada la fbf C: ∀xA(x) → ∃xB(x) , D={a,b} Podemos asegurar que:
    a) La fbf C’: A(a) ∧ A(b) → B(a) ∧ B(b) es equivalente a C
    b) La fbf C’’: [A(a) → B(a)] ∧ [A(b) → B(b)] es equivalente a C
    c) La fbf C’’’: ∀x∃x[A(x) → B(x)] es equivalente a C
    d) La fbf C’V: A(a) ∧ A(b) → B(a) ∨ B(b) es equivalente a C

    Categories
    Bloque III Deducción Natural Clases Teóricas

    Segunda Clase de Deduccion Natural!!!

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

    En nuestra penúltima clase de lógica hemos estudiado las reglas básicas de cuantificación universal, además de hacer ejercicios para poner en practica las restricciones existentes en la introduccion del universal y la eliminacion del existencial. Para el caso del universal y del existencial, una regla es fácil y la otra es dificil.

    Desde el principio de la asignatura, el hecho de trabajar con cuantificadores para lenguaje predicativo añade un poco de dificultad en la realización de ejercicios. Estas reglas de inferencia básicas de cuantificadores nos permiten eliminar dichos cuantificadores y trabajar con ellos como si se tratara del lenguaje proposicional y también nos permiten introducir los cuantificadores para obtener deducciones que requieran lenguaje predicativo.

    Es importante tener en cuenta que siempre que se quiera conseguir una conclusión cuantificada, primero debemos tratar de conseguir la fórmula en lenguaje proposicional para luego introducir el cuantificador.

    Las Reglas de Cuantificación del Universal

  • Eliminacion del Universal (EU)

  • Significado: Si todos los elementos del universo verifican un propiedad P, cualquiera de ellos, por ejemplo a, también la verifica.

    Ejemplo:

    – 1 ∀x[P(x) → Q(x)]
    – 2 P(a) ⇒ Q(a)
    3 P(a) → Q(a) EU 1
    4 Q(a) MP 2,3

  • Introducción del Universal (IU) con restricciones

  • Significado: Si un individuo (a) verifica una propiedad P, entonces podemos afirmar que todos los x del universo la verifican si (a) es un individuo cualquiera, es decir (a) debe estar libre de toda condición anterior.

    Restricción: Es lícito pasar de P(a) a ∀x P(x), siempre que (a) no figure en ningún supuesto provisiona previo sin cancelar, del que dependa P(a) o en una premisa.

    Ejemplo: Veamos el ejemplo que hicimos en clase, cuyo enunciado es:

    “O todos los alumnos son guapos o todos son feos, luego todos son guapos o feos”

    – 1 ∀x Gx v ∀x F(x) ⇒ ∀x [Gx v F(x)]
    l¯2 ∀x Gx
    l 3 G(a) EU 2
    l_4 G(a) v F(a) ID 3
    l¯5 ∀x F(x)
    l 6 F(a) EU 5
    l_7 G(a) v F(a) ID 6
    8 G(a) v F(a) Cas 1,2-4,5-7
    9 ∀x [Gx v F(x)]

    Otra manera de hacerlo es:
    – 1 ∀x Gx v ∀x F(x) ⇒ ∀x [Gx v F(x)]
    l¯2 ∀x Gx
    l 3 G(a) EU 2
    l 4 G(a) v F(a) ID 3
    L 5 ∀x [Gx v F(x)] IU 4
    l¯6 ∀x F(x)
    l 7 F(a) EU 6
    l 8 G(a) v F(a) ID 7
    L9 ∀x [Gx v F(x)] IU 8
    10 ∀x [Gx v F(x)] Cas 1,2-5,6-9

    En este caso si podemos introducir el universal, poque partimos de ∀x Gx/∀x Fx para los casos, y no de un elemento en particular

    Las Reglas de Cuantificación del Existencial

  • Introducción del Exitencial (IE)

  • Significado: Si un individo verfica una propiedad P, desde luego que existe uno por lo menos que verifica dicha propiedad.

    Ejemplo:

    – 1 ∀x [Px → Q(x)]
    – 2 P(a) ⇒ ∃x Q(x)
    3 P(a) → Q(a) EU 1
    4 Q(a) MP 2,3
    5 ∃x Q(x) IE 4

    En este último ejemplo no podríamos introducir el universal, porque en las premisas se encuentra P(a), por lo tanto, no es individuo cualquiera.

  • Eliminación del Existencial (EE) con restricciones

  • Significado: Si un sujeto verifica una determinada propiedad entonces aún sin saber cual es exactamente ese sujeto, se puede pasar a las consecuencias que se siguen del supuesto de su identificación, es decir del supuesto de que de que un sujeto , supuestamente imaginado, posea dicha propiedad.

    Restricción:
    1. El individuo elegido no puede ser cualquiera, sino uno tal que posea la propiedad en cuestión, y que ese sujeto no haya sido mencionado en otro supuesto sin cancelar o premisa, es decir, si (a) es ejemplo de P, no puede ser ejemplo de otro tipo de condición.
    2. Para que la conclusión pueda ser aceptada, el individuo no debe aparecer en ella.

    Ejemplo: Veamos el ejemplo que hicimos en clase, cuyo enunciado es:

    -1 ∃x P(x) ∧ ∃x Q(x) ⇒ ∃x [P(x) ∧ Q(x)]
    -2 ∃x P(x) EC 1
    -3 ∃x Q(x) EC 1
    l¯4 P(a)
    l l¯5 Q(b)

    Este caso, vemos que no se puede obtener P(a) ∧ Q(a), puesto que al abrir dos supuestos es necesario que sean individuos diferentes, como maximo podríamos obtener P(a) ∧ Q(b), e introducir el existencial.

    Por tanto este argumento es incorrecto y no se puede demostrar.

    -1 ∃x[P(x) → Q(x)]
    -2 ∀x P(x) ⇒ ∃x Q(x)
    3 P(a) EU 2
    l¯4 P(a) → Q(a)
    l 5 Q(a) MP 3,4
    L 6 ∃x Q(x) IE 5
    7 ∃x Q(x) EE 1,4-6

    Al finalizar la clase, Carlos dejó el planteamiento del siguiente argumento, para formalizar y demostrar en el lenguaje proposicional!!!!!!!

    P1: Uso el coche solo si tengo gasolina
    P2: No consumo Gasoil a menos que la gasolina sea cara o use el coche
    P3: La gasolina no es cara
    P4: Uso gasoil a menos que no tenga dinero
    Q: Luego, solo si tengo dinero no tengo gasolina

    Formalización
    * Uso el Coche: co
    * Tengo Gasolina: ga
    * Consumo Gasoil: go
    * La gasolina es cara: ca
    * Tengo dinero: di

    P1: co → ga
    P2: go → ca v co
    P3: ¬ca
    P4: ¬go → ¬di
    Q: ¬ga → ¬di

    – 1 co → ga
    – 2 go → ca v co
    – 3 ¬ca
    – 4: ¬go → ¬di ⇒ ¬ga → ¬di
    l¯5 ¬ga
    l 6 ¬co MT 1,5
    l 7 ¬ca ∧ ¬ co IC 3,6
    l 8 ¬go MT 2,7
    L9 ¬di MP 4,8
    10 ¬ga → ¬di TD 4-9

    Este último argumento ha sido deducido mediante Prueba Directa , la cual se sugiere aplicar en casos en que la conclusión tenga forma de implicación, partiendo del supuesto del antecedente de la fórmula, como al final del supuesto hemos llegado al consecuente de la implicación, mediante el Teorema de Deduccion el argumento queda resuelto como correcto.

    Para mi opinión el tema de Deducción Natural ha sido bastante interesante, la complejidad considero que depende del tipo de argumento que se desea deducir, y al mismo tiempo pienso este bloque tiene menor grado de complicación que el Bloque III de semántica, de hecho me ha parecido mas interesante.

    Bueno…….
    Esto ha sido todo por hoy!!!