Scribd Logo
Cargar

¡Te damos la bienvenida a Scribd!

  • 32 vistas

    Tarea1 Logica 2020

    Cargado por

    Daniel Felipe Afanador Rodriguez
    Este documento presenta 11 ejercicios sobre lógica matemática divididos en 5 secciones: 1) Estructuras inductivas, 2) Proposiciones y tautologías, 3) Deducciones formales, 4) Compacidad en lógica proposicional, y 5) Términos y fórmulas en lógica de primer orden. Los ejercicios abarcan temas como conjuntos inductivos, forma normal disyuntiva/conjuntiva, validez de métodos de inferencia, compacidad, y lenguajes formales. El documento debe ser envi

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd

    Tarea1 Logica 2020

    Cargado por

    Daniel Felipe Afanador Rodriguez
    32 vistas3 páginas
    Este documento presenta 11 ejercicios sobre lógica matemática divididos en 5 secciones: 1) Estructuras inductivas, 2) Proposiciones y tautologías, 3) Deducciones formales, 4) Compacidad en lógica proposicional, y 5) Términos y fórmulas en lógica de primer orden. Los ejercicios abarcan temas como conjuntos inductivos, forma normal disyuntiva/conjuntiva, validez de métodos de inferencia, compacidad, y lenguajes formales. El documento debe ser envi

    Título original

    Tarea1-Logica-2020(3) (1)

    Derechos de autor

    © © All Rights Reserved

    Formatos disponibles

    PDF, TXT o lea en línea desde Scribd

    ¿Le pareció útil este documento?

    ¿Este contenido es inapropiado?

    Este documento presenta 11 ejercicios sobre lógica matemática divididos en 5 secciones: 1) Estructuras inductivas, 2) Proposiciones y tautologías, 3) Deducciones formales, 4) Compacidad en lógica proposicional, y 5) Términos y fórmulas en lógica de primer orden. Los ejercicios abarcan temas como conjuntos inductivos, forma normal disyuntiva/conjuntiva, validez de métodos de inferencia, compacidad, y lenguajes formales. El documento debe ser envi

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    32 vistas3 páginas

    Tarea1 Logica 2020

    Cargado por

    Daniel Felipe Afanador Rodriguez
    Este documento presenta 11 ejercicios sobre lógica matemática divididos en 5 secciones: 1) Estructuras inductivas, 2) Proposiciones y tautologías, 3) Deducciones formales, 4) Compacidad en lógica proposicional, y 5) Términos y fórmulas en lógica de primer orden. Los ejercicios abarcan temas como conjuntos inductivos, forma normal disyuntiva/conjuntiva, validez de métodos de inferencia, compacidad, y lenguajes formales. El documento debe ser envi

    Copyright:

    © All Rights Reserved
    Descargue como PDF, TXT o lea en línea desde Scribd
    Descargar como pdf o txt
    de 3

    TAREA 1

    LÓGICA MATEMÁTICA

    Fecha de entrega: Hasta el Lunes 7 de Septiembre de 2020 a las 6 a.m.


    Debe ser enviada al correo electrónico [email protected]

    Grupos: Cada tarea se entregará en grupos de entre 2 y 4 personas.

    Formato de la solución: Las tareas deben ser entregadas en formato PDF. Si


    realizan la tarea en formato LATEX, recibirán 5pts extra (La tarea se calificará sobre
    50 pts)

    Trabajo colaborativo: Pueden intercambiar ideas con otros grupos, y de hecho


    lo recomiendo fuertemente. Sin embargo, cada grupo debe escribir las soluciones
    de forma independiente y usando argumentos propios.

    Referencias externas: En caso de usar referencias externas (ayuda de monitores,


    libros, internet, trabajo con otros grupos, etc) para la solución de algunos de los
    problemas se deben citar dichas referencias.

    La solución de cada problema debe ser completamente autocontenida, citando úni-


    camente resultados vistos en el curso o durante la carrera.

    1. Estructuras inductivas
    Ejercicio 1. Sobre el espacio X = C∞ (R), de funciones infinitamente diferenciables de valor
    real, definimos una estructura inductiva tomando como bloques el conjunto B = {0, sin x}, y
    como operadores las funciones K = {F, G} donde
    Z
    F (f ) = f (x) dx (antiderivada, sin constante), G(f ) = f + 1.

    Describa el conjunto C(B, K). ¿Se tiene que (x3 /3) cos(x) ∈ C(B, K)?

    Ejercicio 2. Sea w una palabra admisible y sean i, j tales que 1 ≤ i < j ≤ long(w). Sean wi
    y wj las palabras admisibles que ocurren en w a partir de las posiciones i y j respectivamente.
    Demuestre que se tiene exactamente una de las siguientes condiciones:
    wi y wj no se sobreponen (es decir, i − 1 + long(wi ) < j), ó
    wj está totalmente contenida en wi .

    Ejercicio 3. Considere el conjunto de sı́mbolos F = {a, b, c, L1 , . . . , Ln } con función de aridad


    dada por ar(a) = ar(b) = ar(c) = 0, ar(Li ) = ki ≥ 2 para cada i = 1, . . . , n. Demuestre o
    refute la siguiente afirmación:

    El conjunto de posibles longitudes de palabras admisibles en F está dado por

    {long(w) : w es una palabra admisible} = k1 · N + · · · + kn · N + 1


    := {k1 · x1 + · · · + kn · xn + 1 : x1 , . . . , xn ∈ N}.
    1
    2

    2. Proposiciones y tautologı́as
    Ejercicio 4. Defina un lenguaje proposicional (es decir, un conjunto de letras proposicionales
    con una interpretación para cada una de ellas.) que describa el estado de un semáforo en dife-
    rentes instantes. Con este lenguaje, escriba un conjunto de fórmulas que exprese los siguientes
    hechos:
    (a) El semáforo está en verde, rojo ó amarillo, pero sólo uno de ellos en cada instante dado.
    (b) El semáforo cambia de verde a amarillo, de amarillo a rojo, y de rojo a verde.
    (c) El semáforo puede mantener el mismo color máximo por 3 instantes sucesivos.
    Ejercicio 5. Considere la relación ∼ en el conjunto Prop(A) dada por p ∼ q si y sólo si
    |= p ↔ q, o equivalentemente, si para toda asignación de verdad t se tiene que t(p) = t(q).
    (a) Demuestre que ∼ es una relación de equivalencia.
    (b) Determine la cardinalidad de P = Prop(A)/ ∼ si suponemos que |A| = n.
    Ejercicio 6 (Forma normal disyuntiva). Sea A = {a1 , . . . , an } con |A| = n. Muestre que cada
    proposición p ∈ Prop(A) que no es equivalente a ⊥ es equivalente a una disyunción p1 ∨ · · · ∨ pk
    donde cada proposición pi es de la forma aǫ11 ∧ · · · ∧ aǫnn .
    (En esta última expresión, cada ǫj es 1 ó −1, y definimos a1 := a, a−1 = ¬a.)
    Ejercicio 7 (Forma normal conjuntiva). Sea A = {a1 , . . . , an } con |A| = n. Muestre que cada
    proposición p ∈ Prop(A) que no es equivalente a ⊤ es equivalente a una conjunción q1 ∧ · · · ∧ qk
    donde cada proposición qi es de la forma aǫ11 ∨ · · · ∨ aǫnn .
    (En esta última expresión, cada ǫj es 1 ó −1, y definimos a1 := a, a−1 = ¬a.)
    Ejercicio 8. Considere los conectivos binarios nor (denotado como ↓), nand (denotado como
    |), y wow (denotado como ⋆) y el conectivo ternario Church1 (denotado por ♠) definidos por
    las siguientes tablas de verdad
    p q r ♠(p, q, r)
    0 0 0 0
    p q p↓q p q p|q p q p⋆q 0 0 1 1
    0 0 1 0 0 1 0 0 1 0 1 0 0
    0 1 0 0 1 1 0 1 0 0 1 1 0
    1 0 0 1 0 1 1 0 1 1 0 0 0
    1 1 0 1 1 0 1 1 0 1 0 1 1
    1 1 0 1
    1 1 1 1
    (a) Demuestre que los conjuntos {↓}, {|} son conjuntos completos de conectivos.
    (b) Muestre que el conectivo ¬ se puede escribir en términos de ⋆, y determine si {⋆} es un
    conjunto completo de conectivos
    (c) Muestre que el conectivo ∨ se puede escribir en términos de ♠, y determine si {♠} es un
    conjunto completo de conectivos.
    (d) Demuestre que nand y nor son los únicos conectivos binarios que son completos.

    3. Deducciones formales
    Ejercicio 9. Pruebe la validez de los siguientes métodos de inferencia:
    (a) (Silogismo disyuntivo) Si Σ ⊢ p ∨ q, Σ ⊢ p → r y Σ ⊢ q → r entonces Σ ⊢ r.
    (b) (Demostración por casos) Si Σ ⊢ p → q ∨ r, Σ ⊢ q → s y Σ ⊢ r → s entonces Σ ⊢ p → s.
    1Este operador se conoce como la disyunción condicionada, y fue creado por Alonzo Church. Se tiene que
    ♠(p, q, r) es equivalente a (q → p) ∧ (¬q → r)
    3

    Ejercicio 10. Considere las proposiciones


    (C1) p → (q → p)
    (C2) (p → (q → r)) → ((p → q) → (p → r))
    (C3) (¬q → ¬p) → (p → q)
    (a) Muestre que el Teorema de la Deducción vale en cualquier sistema que contenga los
    axiomas proposicionales C1, C2 y cuya única regla de deducción sea MP.
    (b) Muestre que Reducción al Absurdo vale en cualquier sistema que contenga los axiomas
    proposicionales C1,C2,C3 y cuya única regla de deducción sea MP.
    Ejercicio 11. Determine cuáles de las proposiciones siguientes son tautologı́as y cuáles no.
    En caso de que sean tautologı́as, realice una deducción formal justificando cada paso con (AP:
    Axioma Proposicional, P Σ Proposición en el conjunto de dedución, MP: Modus Ponens, TD:
    Teorema de la Deducción, RA: Reducción al absurdo, AD: Adición, Simp: Simplificación, EjX:
    Ejercicio X [hecho con anterioridad])2:
    (a) p ↔ ¬¬p (b) (p → q) ↔ (¬q → ¬p) (c) (p → (q → r)) ↔ ((p ∧ q) → r)
    (d) ¬(p ∧ q) ↔ (¬p ∨ ¬q) (e) (p → q) → (q → (p → q)) (f ) ((p → q) → q) → (p → q)
    (g) ((p → q) → p) → p (h) (p → q) ∨ (q → p) (i) ((p → q) ∧ ¬p) → ¬q

    4. Compacidad en lógica proposicional


    Ejercicio 12. Sea (P, ≤) un conjunto parcialmente ordenado. Muestre que existe un orden
    lineal  en P que extiende a P .
    Ayuda: Puede probar primero esto para órdenes parciales finitos usando el diagrama de Hasse. Después, use
    compacidad para probarlo en conjuntos arbitrarios.

    Ejercicio 13. Supongamos que Σ ⊆ Prop(A) satisface que para toda asignación de verdad
    t : A → {0, 1} existe p ∈ Σ tal que t(p) = 1. Muestre que existen proposiciones p1 , . . . , pn ∈ Σ
    tales que p1 ∨ · · · ∨ pn es una tautologı́a. (Por supuesto, el caso interesante es cuando A es
    infinito)
    5. Términos y fórmulas en lógica de primer orden
    Ejercicio 14. Considere los lenguajes LAb−gr = {0, −, +} y Lrings = {0, 1, −, +, ·} donde 0 es
    un sı́mbolo de constante, − es un sı́mbolo de función unaria y +, · son sı́mbolo de funciones
    binarias. Demuestre que para cada LAb−gr -término t(x1 , . . . , xn ) existen enteros k1 , . . . , kn tales
    que para cualquier grupo abeliano G = (G; 0, −, +) y cualquier tupla (a1 , . . . , an ) ∈ Gn ,
    tG (a1 , . . . , an ) = k1 a1 + · · · + kn an .
    Ejercicio 15.
    (a) Sea L = {<, U } un lenguaje que consiste en un sı́mbolo de relación binaria < y un
    sı́mbolo de relación unaria U . Muestre que existe una L-sentencias σ tal que para todo
    X ⊆ R se cumple que
    (R; <, X) |= σ si y sólo si X es finito.
    (b) Consideremos la estructura R = (R; 0, 1, −, +, <) (el grupo ordenado de los números
    reales, junto con el elemento 1). Demuestre que para cada par de reales distintos r, s
    existe una fórmula ϕr,s (x) en el lenguaje {0, 1, −, +, <} tal que (R; 0, 1, −, +, <) |= ϕr,s (r)
    pero (R; 0, 1, −, +, ·, <) 6|= ϕr,s (s).
    2Por el Teorema de Completitud, probar que ⊢ p es equivalente a probar que p es una tautologı́a, pero aquı́
    se están pidiendo las deducciones formales.

    También podría gustarte