Categories
Bloque II Semántica Clases Teóricas

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


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.

Categories
Bloque II Semántica Clases Teóricas Pruebas Lógicas

Segunda Clase de Semántica!!!

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

Hoy hemos continuado con la clase número 2 sobre semática, en este caso hemos visto Técnicas y Métodos semánticos para interpretar fórmulas proposicionales.

De todos los métodos vistos hoy el más práctico me parece que es el del contraejemplo, aparte de que fácil de entender el proceso no es muy largo, mientras que las tablas de verdad son un método que se complica mucho cuando hay muchas variables.

En el primer ejemplo que hicimos demostramos la satisfascibilidad de un conjunto de fbf.

satisfacible1.jpg

Este conjunto es satisfascible o cosistente.



🙂 Hay Mecanismos que me dicen si la fbf es tautología, contradicción o contingencia.
En la clase de hoy, solo vimos 2 métodos:


  • TABLAS DE VERDAD
  • Proceso:
    1º.- Determinar el nº de interpretaciones de la fbf (nº de filas).
    2º.- Construir la tabla de verdad
    2º.- Interpretar las componentes de la fbf según jerarquía.
    3º.- Analizar la columna resultado (componente principal de fbf).
    4º.- Establecer valor semántico conforme el conjunto de I.

    La cantidad de columnas es el # de variables para el caso del mecanismo acumulativo, o el # de variables + 1 si es el mecanismo por pasos.
    La cantidad de filas: n vbles; Vble i: 2n^ / 2^i valores V y valores F.

    El siguiente ejemplo lo realizamos en clase utilizando tablas de verdad, por medio del mecanismo acumulativo.
    tv.jpg

    En este caso la fórmula es Contingencia, puesto que una interpretacion que la hace verdadera y 7 que las hace falsa.

    Veamos ahora el Método del Contraejemplo o Corto de Valoración
    Al aplicar este método suponemos que las premisas son verdaderas y la conclusión falsa. Si encontramos una interpretación que hace lo posible , dicha interpretación es un contraejemplo del argumento y por tanto este no es correcto.
    Si hallamos una contradicción, el contraejemplo no vale, el argumento es correcto y todas las interpretaciones modelo.

    Ejemplo 1
    ejemplo_2.jpg
    * He encontrado una interpretación que me hace falsa la fórmula y que por lo tanto no es tautología. Lo malo de este método es que no puedo saber si es contradicción o contingencia.

    Ejemplo 2
    ejemplo3.jpg
    Aquí en las flechas se señala que hay una contradicción y que por lo tanto la fórmula es tautología.

    Ejemplo 3 “EL ARGUMENTO DE LA CERVEZA”
    beer.jpg
    Al llegar a una contradicción, estamos demostrando que el argumento es correcto.

    Aquí enlazo la primera prueba lógica del bloque II PruebaLogica1BII

    Categories
    Bloque II Semántica Clases Teóricas

    Bloque II SEMANTICA

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

    En la clase del día de hoy hemos empezado el desarrollo del Bloque II, Interpretando fórmulas lógicas y validando argumentos.
    El hecho de haber trabajado desde el bloque I con tablas de verdad, a mi personalmente, me ha hecho sentirme un poco familiarizada con la temática, teniendo en cuenta que la interpretación lógica de una fbf no es más que una posible asignación de valores de verdad (Verdadero/Falso) a las fórmulas atómicas que conforman dicha fbf.

    Recordemos que Un Argumento es correcto: Si no se da el caso de que las premisas sean verdaderas y la conclusión falsa.



    Veamos ahora los términos nuevos que hemos utilizado en esta temática, con su respectiva definición.

    Interpretación Modelo: Interpretación que hace cierta fórmula. Ej: I = { p = v; q = v }
    Interpretación Contramodelo: Interpretación que hace falsa fórmula. Ej: I = { p = f; q = f }



    El Número de Interpretaciones de una fórmula depende, tanto si esta se encuentra en lenguaje proposicional o predicativo.

  • Para saber el número de interpretaciones de fórmulas del lenguaje proposicional se debe seguir la fórmula(2^n), donde n es el número de variables distintas contenidas en la fórmula, ejemplo:
  • p → ¬p tiene 2^1= 2 Interpretaciones posibles, las cuales son
    I ={p =v, p = f}.


  • Para saber el número de interpretaciones de fórmulas del lenguaje predicativo se debe seguir la fórmula (2)^(d^n), donde d es el dominio y n es la aridad variable del predicado, eso si, solo se puede hallar el número de interpretaciones en caso de que el dominio sea finito. Ejemplo:
  • ∀x ∃y P(x,y) ∧ ∀x Q(x) D={a,b,c}
    ∀x ∃y P(x,y) = 2^(3^2) = 2^9 = 512 Interpretaciones
    Q(x)=2^(3^1) = 2^3 = 8 Interpretaciones
    En total de interpretaciones de la fórmula es: 512 x 8 = 4096 Interpretaciones.



    ¿Como Interpretar Argumentos predicativos?

  • Definiendo un dominio no vacío D finito.
  • Asignando elementos de D a los términos.
  • Asignar valores de verdad a los predicados.
  • “Todos los planetas se limpian una vez al año”
    “La Tierra es un planeta”
    Luego, la tierra se limpia una vez al año.

    ∀x [Pl(x) → Li(x)]
    Pl(tierra) => Li(tierra)

    D={Universo} Tendríamos que estudiar infinitas interpretaciones.
    D={La Vía Lactea}

    ejemplo.jpg
    Si por ejemplo hay 8 planetas tendríamos 2^8 x 2^8, y solo deberíamos estudiar un caso.



    Veamos ahora términos de la validación de argumentos:

    Tautología: fbf del cálculo de proposiciones que es verdadera para toda interpretación, es decir, cuando toda atribución veritativa la satisface.
    Ejemplo:
    p v ¬ p
    ¬p → ¬p
    p → p
    p <-> p

    Contradicción: fbf del cálculo de proposiciones que no es verdadera bajo ninguna interpretación, es decir, cuando ninguna atribución veritativa la satisface.
    p ∧ ¬p
    p <-> ¬p
    p → ¬ p

    Contingencia: fbf del cálculo de proposiciones que no es ni tautología ni contradicción, es decir, cuando existe al menos una atribución veritativa que la satisface y otra que no lo hace.
    p v q
    p ∧ q
    p → q

    Una fbf es satisfacible si existe alguna interpretación que la haga V.

    Una fbf es insatisfacible si y sólo si es F para todas sus interpretaciones.

    Categories
    Bloque I: El Lenguaje de la Lógica de Primer Orden. Clases Teóricas

    Clase # 5


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

    Hola, la clase del día de hoy ha estado dividida en dos partes, al principio tuvimos un espacio para aclarar dudas sobre los examinadores 1 y 2 del primer bloque y luego realizamos el control sobre el bloque 1 referente a LPO.

    Ahora voy a hacer un recuento de lo que hasta ahora me ha parecido la asignatura.

    En general este primer bloque considero ha sido un comienzo familiarizado con la asignatura para saber un poco sobre lo que trata, porque la primera impresión de la misma es que tiene alto grado de dificultad :p.

    Lo que me ha parecido positivo de la asignatura es la organización de la misma, en cuanto a la metodología de enseñanza, y la cantidad de actividades para realizar, teniendo en cuenta la distribución del tiempo para su desarrollo, puesto que contamos con horas de clases para hacer bastantes ejercicios, incluyendo las pruebas lógicas, lo cual ayuda al aprendizaje y entendimiento de la misma.

    A continuación enlazo el Primer Control realizado con la solución de Carlos
    Control 1

    Categories
    Examinadores

    Examinador 2 Bloque I

    1. La expresión ∀xP(x)∃xQ(x) es:
    a) Una fbf del lenguaje proposicional
    b) Es una fbf del lenguaje predicativo
    c) No es una fbf porque la misma variable se utiliza en dos ámbitos
    d) Una fbf del lenguaje proposicional y predicativo

    2. Marco conceptual: Ana aprueba lógica: lo; Ana aprueba álgebra: al.
    “Ana aprueba lógica o álgebra, pero no ambas; no obstante si Ana no
    aprueba lógica, tampoco aprueba álgebra”
    se formaliza como:
    a) (lo ∨ al) ∧ (¬lo ∧ ¬al) ∧ (¬lo ∧ ¬al)
    b) (¬lo → al) ∧ (¬lo ∨ ¬al) ∧ (¬al ∨ lo)
    c) (lo ∧ al ∧ ¬lo ∧ ¬al) ∧ ¬(¬lo → al)
    d) Ninguna

    3. Marco conceptual: llevas zapatos: za; entras en el restaurante: re.
    “No es necesario, pero sí suficiente, que lleves zapatos para entrar en
    el restaurante,”
    se formaliza como:
    a) (¬za ∧ re) ∧ (re ∧ ¬za)
    b) ¬(za ∨ re) ∧ (re ∨ za)
    c) ( re → ¬za) ∧ (za → re)
    d) ¬(¬re ∨ za) ∧ ¬(za ∧ ¬re)

    4. Marco conceptual: entras en la piscina: pi; traes el bono: bo.
    “Es suficiente, aunque no necesario, que traigas el bono para entrar
    en la piscina”
    se formaliza como:
    a) (bo ∧ pi) ∧ ¬(pi ∧ bo)
    b) (¬bo ∨ pi) ∧ (pi ∧¬bo)
    c) (bo ∧ pi) ∧ ¬(pi ∧ bo)
    d) (pi → bo) ∧ (pi → ¬bo)

    5. Marco conceptual: Ana salta desde el trampolín: tr; Pedro empuja a Ana: em;
    Juan llena la piscina: pi.
    “Ana no salta desde el trampolín a menos que Pedro le empuje y Juan
    llene la piscina.”
    se formaliza como:
    a) ¬(pi ∧ ¬em ∧ ¬tr)
    b) ¬em ∨ ¬tr ∨ pi
    c) (¬tr ∨ em) ∧ (¬tr ∨ pi)
    d) (¬tr ∧ em) ∨ (¬tr ∧ pi)

    Se considera el Marco Conceptual: D= {personas}; Al(x): x es alumno; Pr(x): x
    es profesor; In(x): x es inteligente; M(x): x es marchoso;
    Ma(x,y): x está matriculado en y; Ad(x,y): x admira a y;

    6. “Todos los alumnos son inteligentes y marchosos” se formaliza como:
    a) ∀x[Al(x) → I(x) ∧ M(x)]
    b) ∀x[I(x) ∧ M(x) → Al(x)]
    c) ∀x[Al(x) ∧ I(x) ∧ M(x)]
    d) ∀x[I(x) ∧ M(x)]

    7. “Todos los alumnos matriculados en alguna asignatura admiran a
    algún profesor”
    se formaliza como:
    a) ∀x[∃yMa(x,y) → ∃zAd(x,z)]
    b) ∀x∃y∃z [Al(x) ∧ Ma(x,y) ∧ Pr(z) ∧ Ad(x,z)]
    c) ∀x[Al(x) ∧ Ma(x,x) → Pr(x) ∧ Ad(x,x)]
    d) ∀x[Al(x) ∧ ∃yMa(x,y) → ∃z(Pr(z) ∧ Ad(x,z))]

    8. “Ana es un alumno que no admira a nadie”, se formaliza como:
    a) ¬(¬Al(ana) ∨ ¬∀x¬Ad(ana,x))
    b) ¬∀x[Al(ana) ∧ Ad(ana,x)]
    c) ∀x¬Ad(x) ∧ Al(ana)
    d) ∃y¬Ad(ana,x) ∧ Al(ana)

    9. “Ana no está matriculada en ninguna asignatura”, se formaliza como:
    a) Al(ana) → ¬∃xMa(x,ana)
    b) ∀x¬Ma(ana,x)
    c) ¬∃xMa(x,ana)
    d) Al(ana) ∧ ¬∃xMa(x,ana)

    10. Para que la expresión S: ∀xA(x) B(x) sea una fbf :
    a) es necesario que la vble x esté libre en A(x)
    b) es suficiente que la vble x esté libre en A(x) al igual que en B(x)
    c) Es necesario que las vble del argumento de A y de B no sea la misma
    d) Es necesario definir un dominio de objetos constantes para la vble x

    Categories
    Examinadores

    Examinador 1 Bloque I

    1. Dada la sentencia: “No llueve en Alicante a menos que cantes en la ducha”
    ¿Cuál de las siguientes sentencias dice lo mismo?
    a) Para que llueva en Alicante es suficiente con que cantes en la ducha
    b) Si cantas en la ducha, llueve en Alicante
    c) Si llueve en Alicante entonces cantas en la ducha
    d) O no llueve en Alicante o no cantas en la ducha

    2. Con el marco conceptual: lo: estudiar lógica; di: las clases son divertidas;
    La fbf di → lo es la que resulta de formalizar la sentencia declarativa:
    a) Es necesario que las clases sean divertidas para estudiar lógica
    b) Es necesario y suficiente que las clases sean divertidas para estudiar l
    c) Es suficiente con que las clases sean divertidas para estudiar lógica
    d) Estudio lógica y las clases son divertidas

    3. Con el marco conceptual: po: me gusta el pollo; pe: me gusta el pescado;
    La sentencia: “No me gusta el pollo ni el pescado”
    Se formaliza en el lenguaje proposicional, como…
    a) ¬(po ∧ pe)
    b) ¬po ∧ pe
    c) ¬po ∧ ¬pe
    d) po ∧ pe

    4. ¿Cuál de las siguientes expresiones no es una fbf predicativa?
    a) p ∧ q ∧ r
    b) ∀x∃yR(x,y,z) D={a,b}
    c) P(a) ∧ R(¬b,c)
    d) P(a)

    5. En la fbf-1: ∀x∃yP(x,y,z), las variables “x” e “y” ¿están ligadas?
    a) Si, porque “x” está adosada a ∀ e “y” a ∃
    b) No, son libres porque “x” está adosada a ∀ e “y” a ∃
    c) No, porque la variable “z” no está adosada a ningún cuantificador
    d) No, porque necesitan estar definidas en varios predicados

    6. La expresión P(x,a,z)∀x∃yQ(x,y) ¿es una fbf? ¿por qué?
    a) Si, porque es la conjunción de dos fbf
    b) No, porque P(x,a,z) tiene variables libres
    c) Si, porque la fbf P(x,a,z) tiene una constante en sus argumentos
    d) No, porque todas las variables deben estar cuantificadas

    Con el marco conceptual Fa(x): x es famoso; Si(x): x es simpático; Re(x): x sale en
    las revistas; SH(x): x tiene sentido del humor. Formalizar las siguientes sentencias
    en el dominio D = {personas}.

    7. La sentencia: S1: “Los famosos son simpáticos”. Se formaliza como…
    a) ∀x[Fa(x) ∧ Si(x)]
    b) ∀x Fa(x) → Si(x)
    c) ∀x [Fa(x) → Si(x)]
    d) ∃x (Fa(x) ∧ Si(x))

    8. La sentencia: S2: “Nadie que no salga en las revistas es famoso”. Se
    formaliza como…
    a) ¬∃x [¬Re(x) ∧ Fa(x)]
    b) ¬∃x [¬Re(x) → Fa(x)]
    c) ∀x [¬Re(x) ∧ Fa(x)]
    d) ∀x [¬Re(x) → Fa(x)]

    9. La sentencia: S3: “Las personas que salen en las revistas tienen
    sentido del humor”
    . Se formaliza como…
    a) ∃x [Re(x) → SH(x)]
    b) ¬∃x [¬Re(x) → SH(x)]
    c) ∀x [Re(x) ∧ SH(x)]
    d) ∀x [Re(x) → SH(x)]

    10. La sentencia: S4: “No existe nadie que al mismo tiempo no sea famoso
    y no tenga sentido del humor”
    . Se formaliza como…
    a) ¬∃x ¬[Fa(x) ∧ SH(x)]
    b) ¬∀x [¬Fa(x) ∧ ¬SH(x)]
    c) ¬∃x [¬Fa(x) → ¬SH(x)]
    d) ∀x [¬Fa(x) → SH(x)]

    11. La sentencia: S5: “Algunas personas son simpáticas”. Se formaliza
    como…
    a) Si(personas)
    b) ∃x Si(personas)
    c) ∃x Si(x)
    d) ∀x Si(x)

    12. La sentencia: Q: “Algunas personas que salen en las revistas son
    simpáticas”
    . Se formaliza como…
    a) ∀x [R(x) → Si(x)]
    b) ∀x [R(x) ∧ Si(x)]
    c) ∃x [Re(x) ∧ Si(x)]
    d) ∃x [Re(x) → Si(x)]