SlideShare a Scribd company logo
1 of 34
Download to read offline
PD Tema 1: Sintaxis y semántica de la lógica proposicional




                             Lógica informática (2010–11)
              Tema 1: Sintaxis y semántica de la lógica proposicional


                                       José A. Alonso Jiménez
                                        Andrés Cordón Franco
                                       María J. Hidalgo Doblado

                                   Grupo de Lógica Computacional
                           Departamento de Ciencias de la Computación e I.A.
                                        Universidad de Sevilla




                                                                               1 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional




Tema 1: Sintaxis y semántica de la lógica proposicional

  1. Introducción

  2. Sintaxis de la lógica proposicional

  3. Semántica proposicional




                                                             2 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Introducción




Tema 1: Sintaxis y semántica de la lógica proposicional

  1. Introducción
         Panorama de la lógica
         Ejemplos de argumentos y formalizaciones

  2. Sintaxis de la lógica proposicional

  3. Semántica proposicional




                                                             3 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Introducción
     Panorama de la lógica



Lógica
          Objetivos de la lógica:
                  La formalización del lenguaje natural.
                  Los métodos de razonamiento.
          Sistemas lógicos:
                  Lógica proposicional.
                  Lógica de primer orden.
                  Lógicas de orden superior.
                  Lógicas modales.
                  Lógicas descriptivas.
          Aplicaciones de la lógica en computación:
                  Programación lógica.
                  Verificación y síntesis automática de programas.
                  Representación del conocimiento y razonamiento.
                  Modelización y razonamiento sobre sistemas.
          Lógica informática = Representación del conocimiento +
                               Razonamiento
                                                                    4 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Introducción
     Ejemplos de argumentos y formalizaciones



Argumentos y formalización
          Ejemplos de argumentos:
                  Ejemplo 1: Si el tren llega a las 7 y no hay taxis en la estación,
                  entonces Juan llegará tarde a la reunión. Juan no ha llegado tarde
                  a la reunión. El tren llegó a las 7. Por tanto, habían taxis en la
                  estación.
                  Ejemplo 2: Si hay corriente y la lámpara no está fundida, entonces
                  está encendida. La lámpara no está encendida. Hay corriente. Por
                  tanto, la lámpara está fundida.
          Formalización:
                  Simbolización:
                   Simb. Ejemplo 1                           Ejemplo 2
                      p     el tren llega a las 7            hay corriente
                                                                                     .
                      q     hay taxis en la estación         la lámpara está fundida
                      r     Juan llega tarde a la reunión la lámpara está encendida
                  Si p y no q, entonces r . No r . p. Por tanto, q.
                  p ∧ ¬q → r , ¬r , p |= q.
                                                                                       5 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional




Tema 1: Sintaxis y semántica de la lógica proposicional

  1. Introducción

  2. Sintaxis de la lógica proposicional
        El lenguaje de la lógica proposicional
        Recursión e inducción sobre fórmulas
        Árboles de análisis (o de formación)
        Eliminación de paréntesis
        Subfórmulas

  3. Semántica proposicional




                                                             6 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional
     El lenguaje de la lógica proposicional



El lenguaje de la lógica proposicional
          Alfabeto proposicional:
                   variables proposicionales: p0 , p1 , . . . ; p, q, r .
                   conectivas lógicas:
                           monaria: ¬ (negación),
                           binarias: ∧ (conjunción),         ∨ (disyunción),
                                     → (condicional),        ↔ (bicondicional).
                   símbolos auxiliares: “(“ y “)”.
          Fórmulas proposicionales:
                   Definición:
                           Las variables proposicionales son fórmulas (fórmulas atómicas).
                           Si F y G son fórmulas, entonces también lo son
                           ¬F , (F ∧ G), (F ∨ G), (F → G) y (F ↔ G)
                   Ejemplos:
                           Fórmulas: p, (p ∨ ¬q), ¬(p ∨ p), ((p → q) ∨ (q → p))
                           No fórmulas: (p), p ∨ ¬q, (p ∨ ∧q)

                                                                                             7 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional
     El lenguaje de la lógica proposicional



Fórmulas proposicionales (BNF)
          Notaciones:
                   p, q, r , . . . representarán variables proposicionales.
                   F , G, H, . . . representarán fórmulas.
                   VP representa el conjunto de los variables proposicionales.
                   Prop representa el conjunto de las fórmulas.
                   ∗ representa una conectiva binaria.
          Forma de Backus Naur (BNF) de las fórmula proposicionales:
                   F ::= p | ¬G | (F ∧ G) | (F ∨ G) | (F → G) | (F ↔ G).




                                                                                 8 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional
     Recursión e inducción sobre fórmulas



Definiciones por recursión sobre fórmulas
          Número de paréntesis de una fórmula:
                   Def: El número de paréntesis de           una fórmula F se define
                   recursivamente por:
                            
                            0,
                                                            si F es atómica;
                   np(F ) = np(G),                           si F es ¬G;
                            
                              2 + np(G) + np(H),             si F es (G ∗ H)
                            
                   Ejemplos:
                           np(p) = 0
                           np(q) = 0
                           np(¬q) = 0
                           np((¬q ∨ p)) = 2
                           np((p → (¬q ∨ p))) = 4




                                                                                      9 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional
     Recursión e inducción sobre fórmulas



Demostración por inducción sobre fórmulas
          Principio de inducción sobre fórmulas: Sea P una propiedad sobre
          las fórmulas que verifica las siguientes condiciones:
                   Todas las fórmulas atómicas tienen la propiedad P.
                   Si F y G tienen la propiedad P, entonces ¬F , (F ∧ G), (F ∨ G),
                   (F → G) y (F ↔ G), tienen la propiedad P.
          Entonces todas las fórmulas proposicionales tienen la propiedad
          P.
          Propiedad: Todas las fórmulas proposicionales tienen un número
          par de paréntesis.
                   Demostración por inducción sobre las fórmulas.
                           Base: F atómica =⇒ np(F ) = 0 es par.
                           Paso: Supongamos que np(F ) y np(G) es par (hipótesis de
                           inducción). Entonces,
                              np(¬F ) = np(F ) es par y
                              np((F ∗ G)) = 2 + np(F ) + np(G) es par,
                           para cualquier conectiva binaria .
                                                                                      10 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional
     Árboles de análisis (o de formación)



Árboles de análisis (o de formación)
        (p → (¬q ∨ p))                                           →


            p         (¬q ∨ p)                               p       ∨


                   ¬q                p                           ¬       p


                     q                                           q




                                                                             11 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional
     Eliminación de paréntesis



Criterios de reducción de paréntesis
          Pueden eliminarse los paréntesis externos.
             F ∧ G es una abreviatura de (F ∧ G).
          Precedencia de asociación de conectivas: ¬, ∧, ∨, →, ↔.
              F ∧ G → ¬F ∨ G es una abreviatura de
          ((F ∧ G) → (¬F ∨ G)).
          Cuando una conectiva se usa repetidamente, se asocia por la
          derecha.

                F ∨G ∨H                                 abrevia   (F ∨ (G ∨ H))
                F ∧ G ∧ H → ¬F ∨ G                      abrevia   ((F ∧ (G ∧ H)) → (¬F ∨ G))



                                                                                               12 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Sintaxis de la lógica proposicional
     Subfórmulas



Subfórmulas
          Def: El conjunto Subf(F ) de las subfórmulas de una fórmula F se
          define recursivamente por:
                     
                     {F },
                                                   si F es atómica;
                     
          Subf(F ) = {F } ∪ Subf(G),                si F es ¬G;
                     
                     {F } ∪ Subf(G) ∪ Subf(H), si F es G ∗ H
                     

          Ejemplos:
                   Subf(p) = {p}
                   Subf(q) = {q}
                   Subf(¬q) = {¬q, q}
                   Subf(¬q ∨ p) = {¬q ∨ p, ¬q, q, p}
                   Subf(p → ¬q ∨ p) = {p → ¬q ∨ p, p, ¬q ∨ p, ¬q, q}




                                                                             13 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional




Tema 1: Sintaxis y semántica de la lógica proposicional

  1. Introducción

  2. Sintaxis de la lógica proposicional

  3. Semántica proposicional
       Valores y funciones de verdad
       Interpretaciones
       Modelos, satisfacibilidad y validez
       Algoritmos para satisfacibilidad y validez
       Selección de tautologías
       Equivalencia lógica
       Modelos de conjuntos de fórmulas
       Consistencia y consecuencia lógica
       Argumentaciones y problemas lógicos                   14 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Valores y funciones de verdad



Valores y funciones de verdad
          Valores de verdad (B): 1: verdadero y 0: falso.
          Funciones de verdad:
                                                             1,        si i = 0;
                  H¬ : {0, 1} → {0, 1} t.q. H¬ (i) =
                                                             0,        si i = 1.
                                                                  1,      si i = j = 1;
                  H∧ : {0, 1}2 → {0, 1} t.q. H∧ (i, j) =
                                                                  0,      en otro caso.
                                                                  0,      si i = j = 0;
                  H∨ : {0, 1}2 → {0, 1} t.q. H∨ (i, j) =
                                                                  1,      en otro caso.
                                                                   0,      si i = 1, j = 0;
                  H→ : {0, 1}2 → {0, 1} t.q. H→ (i, j) =
                                                                   1,      en otro caso.
                                                                   1,      si i = j;
                  H↔ : {0, 1}2 → {0, 1} t.q. H↔ (i, j) =
                                                                   0,      en otro caso.

                                                                                              15 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Interpretaciones



Interpretaciones de fórmulas
          Funciones de verdad mediante tablas de verdad:
             i ¬i            i j i ∧j i ∨j i →j i ↔j
             1 0             1 1     1      1       1    1
             0 1             1 0     0      1       0    0
                             0 1     0      1       1    0
                             0 0     0      0       1    1
          Interpretación:
                  Def.: Una interpretación es una aplicación I : VP → B.
                  Prop: Para cada interpretación I existe una única aplicación
                  I : Prop → B tal que:
                                  
                                  I(F ),
                                                        si F es atómica;
                          I (F ) = H¬ (I (G)),           si F = ¬G;
                                  
                                     H∗ (I (G), I (H)), si F = G ∗ H
                                  
                  Se dice que I (F ) es el valor de verdad de F respecto de I.
                                                                                 16 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Interpretaciones



Interpretaciones de fórmulas
          Ejemplo: Sea F = (p ∨ q) ∧ (¬q ∨ r )
                  valor de F en una interpretación I1 tal que
                  I1 (p) = I1 (r ) = 1, I1 (q) = 0
                          (p ∨ q) ∧ (¬q ∨ r )
                          (1 ∨ 0) ∧ (¬0 ∨ 1)
                               1         ∧ (1      ∨ 1)
                               1         ∧         1
                                         1
                  valor de F en una interpretación I2 tal que
                  I2 (r ) = 1, I2 (p) = I2 (q) = 0
                          (p ∨ q) ∧ (¬q ∨ r )
                           0 0 0 0             10 1 1
          Prop.: Sea F una fórmula y I1 , I2 dos interpretaciones. Si
          I1 (p) = I2 (p) para todos las variables proposicionales de F ,
          entonces I1 (F ) = I2 (F ).
          Notación: Se escribe I(F ) en lugar de I (F ).
                                                                            17 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Modelos, satisfacibilidad y validez



Modelos y satisfacibilidad
          Modelo de una fórmula
                  Def.: I es modelo de F si I(F ) = 1.
                  Notación: I |= F .
                  Ejemplo (continuación del anterior):
                  – si I1 (p) = I1 (r ) = 1, I1 (q) = 0, entonces I1 |= (p ∨ q) ∧ (¬q ∨ r )
                  – si I2 (r ) = 1, I2 (p) = I2 (q) = 0, entonces I2 |= (p ∨ q) ∧ (¬q ∨ r ).
          Fórmulas satisfacibles e insatisfacibles
                  Def.: F es satisfacible si F tiene algún modelo.
                  Ejemplo: (p → q) ∧ (q → r ) es satisfacible
                          I(p) = I(q) = I(r ) = 0.
                  Def.: F es insatisfacible si F no tiene ningún modelo.
                  Ejemplo: p ∧ ¬p es insatisfacible
                                p     ¬p     p ∧ ¬p
                                1      0        0
                                0      1        0
                                                                                               18 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Modelos, satisfacibilidad y validez



Tautologías y contradicciones
         Def.: F es una tautología (o válida) si toda interpretación es modelo de
         F . Se representa por |= F .
         Def.: F es una contradicción si ninguna interpretación es modelo de F .
         Def.: F es contingente si no es tautología ni contradicción.
         Ejemplos:
            1. (p → q) ∨ (q → p) es una tautología.
            2. (p → q) ∧ ¬(p → q) es una contradicción.
            3. p → q es contingente.
          p q p → q q → p (p → q) ∨ (q → p) ¬(p → q) (p → q) ∧ ¬(p → q)
          1 1   1     1           1             0             0
          1 0   0     1           1             1             0
          0 1   1     0           1             0             0
          0 0   1     1           1             0             0




                                                                                    19 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Modelos, satisfacibilidad y validez



Clasificaciones de fórmulas


                                               Todas las fórmulas

    Tautologías                             Contigentes             Contradicciones

    Verdadera en todas las                  Verdadera en algunas    Falsa en todas las
    interpretaciones                        interpretaciones y      interpretaciones
                                            falsa en otras

    (ej. p ∨ ¬p)                            (ej. p → q)             (ej. p ∧ ¬p)

                                  Safisfacibles                      Insatisfacibles

                                               Todas las fórmulas

                                                                                         20 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Modelos, satisfacibilidad y validez



Satisfacibilidad y validez
          Los problemas SAT y TAUT:
                  Problema SAT: Dada F determinar si es satisfacible.
                  Problema TAUT: Dada F determinar si es una tautología.
          Relaciones entre satisfacibilidad y tautologicidad:
                  F es tautología     ⇐⇒ ¬F es insatisfacible.
                  F es tautología     =⇒ F es satisfacible.
                  F es satisfacible =⇒ ¬F es insatisfacible.
                                     /
                          p → q es satisfacible.
                                    I(p) = I(q) = 1
                               ¬(p → q) es satisfacible.
                                           I(p) = 1, I(q) = 0.




                                                                           21 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Algoritmos para satisfacibilidad y validez



Algoritmos para SAT y TAUT
          Tabla de verdad para |= (p → q) ∨ (q → p):
           p q (p → q) (q → p) (p → q) ∨ (q → p)
           1 1       1          1              1
           1 0       0          1              1
           0 1       1          0              1
           0 0       1          1              1
          Tabla de verdad simplificada para |= (p → q) ∨ (q → p):
           p q (p → q) ∨ (q                                  → p)
           1 1 1 1 1 1 1                                     1 1
           1 0 1 0 0 1 0                                     1 1
           0 1 0 1 1 1 1                                     0 0
           0 0 0 1 0 1 0                                     1 0

                                                                    22 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Algoritmos para satisfacibilidad y validez



Algoritmos para SAT y TAUT
          Método de Quine para |= (p → q) ∨ (q → p)
           (p → q) ∨ (q → p)
                      0
               0               0
                           1        0
            0      1
               1
          Método de Quine para |= (p → q) ∨ (q → p)
           (p → q) ∨ (q → p)
            0 0 1 0 1 0 0
              1∗




                                                             23 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Algoritmos para satisfacibilidad y validez



Algoritmos para SAT y TAUT
          Tablas de verdad para |= (p ↔ q) ∨ (q ↔ p)
           p q (p ↔ q) (q ↔ p) (p ↔ q) ∨ (q ↔ p)
           1 1      1         1              1
           1 0      0         0              0
           0 1      0         0              0
           0 0      1         1              1
          Método de Quine para |= (p ↔ q) ∨ (q ↔ p)
           (p ↔ q) ∨ (q ↔ p)
            0 0 1 0 1 0 0

            1       0        0     0       0      0     1



                                                             24 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Selección de tautologías



Selección de tautologías
    1.     F →F                                      (ley de identidad).
    2.     F ∨ ¬F                                    (ley del tercio excluido).
    3.     ¬(F ∧ ¬F )                                (principio de no contradicción).
    4.     (¬F → F ) → F                             (ley de Clavius).
    5.     ¬F → (F → G)                              (ley de Duns Scoto).
    6.     ((F → G) → F ) → F                        (ley de Peirce).
    7.     (F → G) ∧ F → G                           (modus ponens).
    8.     (F → G) ∧ ¬G → ¬F                         (modus tollens).




                                                                                        25 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Equivalencia lógica



Fórmulas equivalentes
          Def.: F y G son equivalentes si I(F ) = I(G) para toda
          interpretación I. Representación: F ≡ G.
          Ejemplos de equivalencias notables:
             1. Idempotencia: F ∨ F ≡ F ; F ∧ F ≡ F .
             2. Conmutatividad: F ∨ G ≡ G ∨ F ; F ∧ G ≡ G ∧ F .
             3. Asociatividad: F ∨ (G ∨ H) ≡ (F ∨ G) ∨ H ;
                                F ∧ (G ∧ H) ≡ (F ∧ G) ∧ H
             4. Absorción: F ∧ (F ∨ G) ≡ F ; F ∨ (F ∧ G) ≡ F .
             5. Distributividad: F ∧ (G ∨ H) ≡ (F ∧ G) ∨ (F ∧ H) ;
                                 F ∨ (G ∧ H) ≡ (F ∨ G) ∧ (F ∨ H).
             6. Doble negación: ¬¬F ≡ F .
             7. Leyes de De Morgan: ¬(F ∧ G) ≡ ¬F ∨ ¬G ;
                                       ¬(F ∨ G) ≡ ¬F ∧ ¬G
             8. Leyes de tautologías: Si F es una tautología,
                F ∧ G ≡ G ; F ∨ G ≡ F.
             9. Leyes de contradicciones: Si F es una contradicción
                F ∧ G ≡ F ; F ∨ G ≡ G.                                26 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Equivalencia lógica



Propiedades de la equivalencia lógica
          Relación entre equivalencia y bicondicional:
                  F ≡ G syss |= F ↔ G.
          Propiedades básicas de la equivalencia lógica:
                  Reflexiva: F ≡ F .
                  Simétrica: Si F ≡ G, entonces G ≡ F .
                  Transitiva: Si F ≡ G y G ≡ H, entonces F ≡ H.
          Principio de sustitución de fórmulas equivalentes:
                  Prop.: Si en la fórmula F se sustituye una de sus subfórmulas G
                  por una fórmula G lógicamente equivalente a G, entonces la
                  fórmula obtenida, F , es lógicamente equivalente a F .
                  Ejemplo: F = ¬(p ∧ q) → ¬(p ∧ ¬¬r )
                             G = ¬(p ∧ q)
                             G = ¬p ∨ ¬q
                             F = (¬p ∨ ¬q) → ¬(p ∧ ¬¬r )

                                                                                    27 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Modelos de conjuntos de fórmulas



Modelo de conjuntos de fórmulas
          Notación:
                  S, S1 , S2 , . . . representarán conjuntos de fórmulas.
          Modelo de un conjunto de fórmulas:
                  Def.: I es modelo de S si para toda F ∈ S se tiene que I |= F .
                  Representación: I |= S.
                  Ejemplo: Sea S = {(p ∨ q) ∧ (¬q ∨ r ), q → r }
                  La interpretación I1 tal que I1 (p) = 1, I1 (q) = 0, I1 (r ) = 1 es
                  modelo de S (I1 |= S).
                        {(p ∨ q) ∧ (¬ q ∨ r ),                    q → r}
                         1    1 0 1 1 0 1 1                       0 1 1
                  La interpretación I2 tal que I2 (p) = 0, I2 (q) = 1, I2 (r ) = 0 no es
                  modelo de S (I2 |= S).
                        {(p ∨ q) ∧ (¬ q ∨ r ),                    q → r}
                         0    1 0 0 0 1 0 0                       1 0 0


                                                                                           28 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Consistencia y consecuencia lógica



Conjunto consistente de fórmulas
          Def.: S es consistente si S tiene algún modelo.
          Def.: S es inconsistente si S no tiene ningún modelo.
          Ejemplos:
                  {(p ∨ q) ∧ (¬q ∨ r ), p → r } es consistente (con modelos I4 , I6 , I8 )

                  {(p ∨ q) ∧ (¬q ∨ r ), p → r , ¬r } es inconsistente
                          p     q    r     (p ∨ q)           (¬q ∨ r )   (p ∨ q) ∧ (¬q ∨ r )   p→r   ¬r
                   I1     0     0    0        0                 1                 0             1    1
                   I2     0     0    1        0                 1                 0             1    0
                   I3     0     1    0        1                 0                 0             1    1
                   I4     0     1    1        1                 1                 1             1    0
                   I5     1     0    0        1                 1                 1             0    1
                   I6     1     0    1        1                 1                 1             1    0
                   I7     1     1    0        1                 0                 0             0    1
                   I8     1     1    1        1                 1                 1             1    0
                                                                                                      29 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Consistencia y consecuencia lógica



Consecuencia lógica
          Def.: F es consecuencia de S si todos los modelos de S son
          modelos de F .
          Representación: S |= F .
          Ejemplos: {p → q, q → r } |= p → r y {p} |= p ∧ q
                    p     q     r p→q q→r                    p→r   p q p∧q
             I1     0     0     0  1   1                      1    1 1  1
             I2     0     0     1  1   1                      1    1 0  0
             I3     0     1     0  1   0                      1    0 1  0
             I4     0     1     1  1   1                      1    0 0  0
             I5     1     0     0  0   1                      0
             I6     1     0     1  0   1                      1
             I7     1     1     0  1   0                      0
             I8     1     1     1  1   1                      1
                                                                             30 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Consistencia y consecuencia lógica



Propiedades de la consecuencia
          Propiedades básicas de la relación de consecuencia:
                  Reflexividad: S |= S.
                  Monotonía: Si S1 |= F y S1 ⊆ S2 , entonces S2 |= F .
                  Transitividad: Si S |= F y {F } |= G, entonces S |= G.
          Relación entre consecuencia, validez, satisfacibilidad y
          consistencia:
                  Las siguientes condiciones son equivalentes:
                     1.   {F1 , . . . , Fn } |= G
                     2.   |= F1 ∧ · · · ∧ Fn → G
                     3.   ¬(F1 ∧ · · · ∧ Fn → G) es insatisfacible
                     4.   {F1 , . . . , Fn , ¬G} es inconsistente




                                                                           31 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Argumentaciones y problemas lógicos



Ejemplo de argumentación
          Problema de los animales: Se sabe que
             1.   Los   animales con pelo o que dan leche son mamíferos.
             2.   Los   mamíferos que tienen pezuñas o que rumian son ungulados.
             3.   Los   ungulados de cuello largo son jirafas.
             4.   Los   ungulados con rayas negras son cebras.
          Se observa un animal que tiene pelos, pezuñas y rayas negras.
          Por consiguiente, se concluye que el animal es una cebra.
          Formalización:
           { tiene_pelos ∨ da_leche → es_mamífero,
               es_mamífero ∧ (tiene_pezuñas ∨ rumia) → es_ungulado,
               es_ungulado ∧ tiene_cuello_largo → es_jirafa,
               es_ungulado ∧ tiene_rayas_negras → es_cebra,
               tiene_pelos ∧ tiene_pezuñas ∧ tiene_rayas_negras}
          |= es_cebra

                                                                                   32 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Semántica proposicional
     Argumentaciones y problemas lógicos



Problemas lógicos: veraces y mentirosos
         Enunciado: En una isla hay dos tribus, la de los veraces (que siempre
         dicen la verdad) y la de los mentirosos (que siempre mienten). Un
         viajero se encuentra con tres isleños A, B y C y cada uno le dice una
         frase
            1. A dice “B y C son veraces syss C es veraz”
            2. B dice “Si A y C son veraces, entonces B y C son veraces y A es
               mentiroso”
            3. C dice “B es mentiroso syss A o B es veraz”
         Determinar a qué tribu pertenecen A, B y C.
         Simbolización: a: “A es veraz”, b: “B es veraz”, c: “C es veraz”.
         Formalización:
         F1 = a ↔ (b ∧ c ↔ c), F2 = b ↔ (a ∧ c → b ∧ c ∧ ¬a) y
         F3 = c ↔ (¬b ↔ a ∨ b).
         Modelos de {F1 , F2 , F3 }:
         Si I es modelo de {F1 , F2 , F3 }, entonces I(a) = 1, I(b) = 1, I(c) = 0.
         Conclusión: A y B son veraces y C es mentiroso.
                                                                                     33 / 34
PD Tema 1: Sintaxis y semántica de la lógica proposicional
   Bibliografía




Bibliografía
     1. C. Badesa, I. Jané y R. Jansana Elementos de lógica formal.
        (Ariel, 2000)
                  Cap. 0 (Introducción), 6 (Sintaxis de la lógica proposicional), 7
                  (Semántica de la lógica proposicional), 9 (Consecuencia lógica) y
                  11 (Lógica proposicional y lenguaje natural).
     2. M. Ben–Ari, Mathematical logic for computer science (2nd ed.).
        (Springer, 2001)
                  Cap. 1 (Introduction) y 2 (Propositional calculus: formulas,
                  models, tableaux).
     3. J.A. Díez Iniciación a la Lógica, (Ariel, 2002)
                  Cap. 2 (El lenguaje de la lógica proposicional) y 3 (Semántica
                  formal. Consecuencia lógica).
     4. M. Huth y M. Ryan Logic in computer science: modelling and
        reasoning about systems. (Cambridge University Press, 2000)
                  Cap. 1 (Propositional logic).
                                                                                      34 / 34

More Related Content

What's hot

Señales de tiempo continuo y discreto MATLAB
Señales de tiempo continuo y discreto MATLABSeñales de tiempo continuo y discreto MATLAB
Señales de tiempo continuo y discreto MATLABJose Agustin Estrada
 
11 Transformada De Laplace
11 Transformada De Laplace11 Transformada De Laplace
11 Transformada De Laplacekahtya
 
Series de fourier 22 Ejercicios Resueltos
Series de fourier 22 Ejercicios ResueltosSeries de fourier 22 Ejercicios Resueltos
Series de fourier 22 Ejercicios ResueltosJoe Arroyo Suárez
 
ECUACIONES NO LINEALES
ECUACIONES NO LINEALESECUACIONES NO LINEALES
ECUACIONES NO LINEALESsdiupg1
 
Aplicaciones de los sistemas ecuaciones a la electricidad
Aplicaciones de los sistemas ecuaciones a la electricidadAplicaciones de los sistemas ecuaciones a la electricidad
Aplicaciones de los sistemas ecuaciones a la electricidadAlejandro Domínguez Torres
 
Serie de Fourier
Serie de FourierSerie de Fourier
Serie de FourierNhynoska
 
Introducción a los Métodos Numéricos
Introducción a los Métodos NuméricosIntroducción a los Métodos Numéricos
Introducción a los Métodos NuméricosJoanny Ibarbia Pardo
 
Ejercicios resueltos por cramer
Ejercicios resueltos por cramerEjercicios resueltos por cramer
Ejercicios resueltos por crameralgebra
 
Soluciones de sistema de ecuaciones en Matlab
Soluciones de sistema de ecuaciones en MatlabSoluciones de sistema de ecuaciones en Matlab
Soluciones de sistema de ecuaciones en MatlabHugo Piure
 
Ejemplo del Método de Bisección
Ejemplo del Método de BisecciónEjemplo del Método de Bisección
Ejemplo del Método de BisecciónDaniela Medina
 
Algoritmos de kruskal y prim
Algoritmos de kruskal y primAlgoritmos de kruskal y prim
Algoritmos de kruskal y primfher969
 

What's hot (20)

Señales de tiempo continuo y discreto MATLAB
Señales de tiempo continuo y discreto MATLABSeñales de tiempo continuo y discreto MATLAB
Señales de tiempo continuo y discreto MATLAB
 
11 Transformada De Laplace
11 Transformada De Laplace11 Transformada De Laplace
11 Transformada De Laplace
 
Metodo de busqueda
Metodo de busquedaMetodo de busqueda
Metodo de busqueda
 
Presentación Métodos Numéricos
Presentación Métodos Numéricos Presentación Métodos Numéricos
Presentación Métodos Numéricos
 
Series de fourier 22 Ejercicios Resueltos
Series de fourier 22 Ejercicios ResueltosSeries de fourier 22 Ejercicios Resueltos
Series de fourier 22 Ejercicios Resueltos
 
Practica 3 regla falsa
Practica 3 regla falsaPractica 3 regla falsa
Practica 3 regla falsa
 
ECUACIONES NO LINEALES
ECUACIONES NO LINEALESECUACIONES NO LINEALES
ECUACIONES NO LINEALES
 
Aplicaciones de los sistemas ecuaciones a la electricidad
Aplicaciones de los sistemas ecuaciones a la electricidadAplicaciones de los sistemas ecuaciones a la electricidad
Aplicaciones de los sistemas ecuaciones a la electricidad
 
Recursividad directa e indirecta
Recursividad directa e indirectaRecursividad directa e indirecta
Recursividad directa e indirecta
 
Metodo de biseccion en matlab
Metodo de biseccion  en matlabMetodo de biseccion  en matlab
Metodo de biseccion en matlab
 
Serie de Fourier
Serie de FourierSerie de Fourier
Serie de Fourier
 
Numeros complejos
Numeros complejosNumeros complejos
Numeros complejos
 
Series de fourier
Series de fourierSeries de fourier
Series de fourier
 
Introducción a los Métodos Numéricos
Introducción a los Métodos NuméricosIntroducción a los Métodos Numéricos
Introducción a los Métodos Numéricos
 
Ejercicios resueltos por cramer
Ejercicios resueltos por cramerEjercicios resueltos por cramer
Ejercicios resueltos por cramer
 
Ca tema 1 nvo
Ca tema 1 nvoCa tema 1 nvo
Ca tema 1 nvo
 
Soluciones de sistema de ecuaciones en Matlab
Soluciones de sistema de ecuaciones en MatlabSoluciones de sistema de ecuaciones en Matlab
Soluciones de sistema de ecuaciones en Matlab
 
Ejemplo del Método de Bisección
Ejemplo del Método de BisecciónEjemplo del Método de Bisección
Ejemplo del Método de Bisección
 
Algoritmos de kruskal y prim
Algoritmos de kruskal y primAlgoritmos de kruskal y prim
Algoritmos de kruskal y prim
 
Algebra Booleana
Algebra BooleanaAlgebra Booleana
Algebra Booleana
 

Similar to LI2011-T1: Sintaxis y semántica de la lógica proposicional

LMF-T5: Resolución proposicional
LMF-T5: Resolución proposicionalLMF-T5: Resolución proposicional
LMF-T5: Resolución proposicionalJosé A. Alonso
 
LI -T5: Resolución proposicional
LI -T5: Resolución proposicionalLI -T5: Resolución proposicional
LI -T5: Resolución proposicionalJosé A. Alonso
 
El conocimiento colectivo desde un punto de vista lógico
El conocimiento colectivo desde un punto de vista lógicoEl conocimiento colectivo desde un punto de vista lógico
El conocimiento colectivo desde un punto de vista lógicoostale
 
Taller sobre la logica
Taller sobre la logicaTaller sobre la logica
Taller sobre la logicahugo murcia
 
Mate_Discretas logica y_demostraciones
Mate_Discretas logica y_demostracionesMate_Discretas logica y_demostraciones
Mate_Discretas logica y_demostracionesVelmuz Buzz
 
Enrique bonilla.estructurasdiscretasi
Enrique bonilla.estructurasdiscretasiEnrique bonilla.estructurasdiscretasi
Enrique bonilla.estructurasdiscretasiEnrique Bonilla
 
Lógica Proposicional Por Segundo Silva Maguiña
Lógica Proposicional Por Segundo Silva MaguiñaLógica Proposicional Por Segundo Silva Maguiña
Lógica Proposicional Por Segundo Silva MaguiñaSegundo Silva Maguiña
 
Carlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretasCarlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretasCARLOSJAVIERMEDINA
 
Carlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretasCarlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretasCARLOSJAVIERMEDINA
 
Objetivo unidad 1.pdf estructura discreta 1 jhonder orozco
Objetivo unidad 1.pdf estructura discreta 1 jhonder orozcoObjetivo unidad 1.pdf estructura discreta 1 jhonder orozco
Objetivo unidad 1.pdf estructura discreta 1 jhonder orozcoJhonder Orozco
 
ejercicios pensamiento logico.docx
ejercicios pensamiento logico.docxejercicios pensamiento logico.docx
ejercicios pensamiento logico.docxNicolasTovar16
 

Similar to LI2011-T1: Sintaxis y semántica de la lógica proposicional (20)

LMF-T5: Resolución proposicional
LMF-T5: Resolución proposicionalLMF-T5: Resolución proposicional
LMF-T5: Resolución proposicional
 
LI -T5: Resolución proposicional
LI -T5: Resolución proposicionalLI -T5: Resolución proposicional
LI -T5: Resolución proposicional
 
Intro lógica de predicados
Intro lógica de predicadosIntro lógica de predicados
Intro lógica de predicados
 
El conocimiento colectivo desde un punto de vista lógico
El conocimiento colectivo desde un punto de vista lógicoEl conocimiento colectivo desde un punto de vista lógico
El conocimiento colectivo desde un punto de vista lógico
 
Taller sobre la logica
Taller sobre la logicaTaller sobre la logica
Taller sobre la logica
 
Mate_Discretas logica y_demostraciones
Mate_Discretas logica y_demostracionesMate_Discretas logica y_demostraciones
Mate_Discretas logica y_demostraciones
 
Logica
LogicaLogica
Logica
 
Logica
LogicaLogica
Logica
 
LOGICA
LOGICALOGICA
LOGICA
 
Sesión1.1_Logica.pdf
Sesión1.1_Logica.pdfSesión1.1_Logica.pdf
Sesión1.1_Logica.pdf
 
0428 amor
0428 amor0428 amor
0428 amor
 
Razonamiento monotono
Razonamiento monotonoRazonamiento monotono
Razonamiento monotono
 
Logica proposcional-1
Logica proposcional-1Logica proposcional-1
Logica proposcional-1
 
Enrique bonilla.estructurasdiscretasi
Enrique bonilla.estructurasdiscretasiEnrique bonilla.estructurasdiscretasi
Enrique bonilla.estructurasdiscretasi
 
Lógica Proposicional Por Segundo Silva Maguiña
Lógica Proposicional Por Segundo Silva MaguiñaLógica Proposicional Por Segundo Silva Maguiña
Lógica Proposicional Por Segundo Silva Maguiña
 
Lógica matemática
Lógica matemáticaLógica matemática
Lógica matemática
 
Carlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretasCarlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretas
 
Carlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretasCarlos j medina 15385618 estructuras discretas
Carlos j medina 15385618 estructuras discretas
 
Objetivo unidad 1.pdf estructura discreta 1 jhonder orozco
Objetivo unidad 1.pdf estructura discreta 1 jhonder orozcoObjetivo unidad 1.pdf estructura discreta 1 jhonder orozco
Objetivo unidad 1.pdf estructura discreta 1 jhonder orozco
 
ejercicios pensamiento logico.docx
ejercicios pensamiento logico.docxejercicios pensamiento logico.docx
ejercicios pensamiento logico.docx
 

More from José A. Alonso

Tema 12: Analizadores sintácticos funcionales.
Tema 12: Analizadores sintácticos funcionales.Tema 12: Analizadores sintácticos funcionales.
Tema 12: Analizadores sintácticos funcionales.José A. Alonso
 
Tema 23: Técnicas de diseño descendente de algoritmos
Tema 23: Técnicas de diseño descendente de algoritmosTema 23: Técnicas de diseño descendente de algoritmos
Tema 23: Técnicas de diseño descendente de algoritmosJosé A. Alonso
 
I1M-T19: El TAD de los árboles de búsqueda
I1M-T19: El TAD de los árboles de búsquedaI1M-T19: El TAD de los árboles de búsqueda
I1M-T19: El TAD de los árboles de búsquedaJosé A. Alonso
 
I1M-T17: El TAD de los conjuntos
I1M-T17: El TAD de los conjuntosI1M-T17: El TAD de los conjuntos
I1M-T17: El TAD de los conjuntosJosé A. Alonso
 
Panorama de la demostración asistida por ordenador
Panorama de la demostración asistida por ordenadorPanorama de la demostración asistida por ordenador
Panorama de la demostración asistida por ordenadorJosé A. Alonso
 
LMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer ordenLMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer ordenJosé A. Alonso
 
LMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer ordenLMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer ordenJosé A. Alonso
 
LMF-T5b: Aplicaciones de la lógica proposicional
LMF-T5b: Aplicaciones de la lógica proposicionalLMF-T5b: Aplicaciones de la lógica proposicional
LMF-T5b: Aplicaciones de la lógica proposicionalJosé A. Alonso
 
LMF-T3: Tableros semánticos
LMF-T3: Tableros semánticosLMF-T3: Tableros semánticos
LMF-T3: Tableros semánticosJosé A. Alonso
 
LMF-T2: Deducción natural proposicional
LMF-T2: Deducción natural proposicionalLMF-T2: Deducción natural proposicional
LMF-T2: Deducción natural proposicionalJosé A. Alonso
 
I1M-T21: El TAD de los polinomios en Haskell
I1M-T21: El TAD de los polinomios en HaskellI1M-T21: El TAD de los polinomios en Haskell
I1M-T21: El TAD de los polinomios en HaskellJosé A. Alonso
 
LI-T12: LI2011-12: Introducción a la programación lógica con Prolog
LI-T12: LI2011-12: Introducción a la programación lógica con PrologLI-T12: LI2011-12: Introducción a la programación lógica con Prolog
LI-T12: LI2011-12: Introducción a la programación lógica con PrologJosé A. Alonso
 
LI-T6: Sintaxis y semántica de la lógica de primer orden
LI-T6: Sintaxis y semántica de la lógica de primer ordenLI-T6: Sintaxis y semántica de la lógica de primer orden
LI-T6: Sintaxis y semántica de la lógica de primer ordenJosé A. Alonso
 
LI-T5b: Algoritmos para SAT. Aplicaciones
LI-T5b: Algoritmos para SAT. AplicacionesLI-T5b: Algoritmos para SAT. Aplicaciones
LI-T5b: Algoritmos para SAT. AplicacionesJosé A. Alonso
 
Panorama del razonamiento automático
Panorama del razonamiento automáticoPanorama del razonamiento automático
Panorama del razonamiento automáticoJosé A. Alonso
 
I1M2010-T24: Programación dinámica en Haskell
I1M2010-T24: Programación dinámica en HaskellI1M2010-T24: Programación dinámica en Haskell
I1M2010-T24: Programación dinámica en HaskellJosé A. Alonso
 
LI2011-T11: Resolución en lógica de primer orden
LI2011-T11: Resolución en lógica de primer ordenLI2011-T11: Resolución en lógica de primer orden
LI2011-T11: Resolución en lógica de primer ordenJosé A. Alonso
 
LI2011-T9: Formas normales de Skolem y cláusulas
LI2011-T9: Formas normales de Skolem y cláusulasLI2011-T9: Formas normales de Skolem y cláusulas
LI2011-T9: Formas normales de Skolem y cláusulasJosé A. Alonso
 
I1M2010-T23: Técnicas de diseño descendente de algoritmos.
I1M2010-T23: Técnicas de diseño descendente de algoritmos.I1M2010-T23: Técnicas de diseño descendente de algoritmos.
I1M2010-T23: Técnicas de diseño descendente de algoritmos.José A. Alonso
 

More from José A. Alonso (20)

Tema 12: Analizadores sintácticos funcionales.
Tema 12: Analizadores sintácticos funcionales.Tema 12: Analizadores sintácticos funcionales.
Tema 12: Analizadores sintácticos funcionales.
 
Tema 23: Técnicas de diseño descendente de algoritmos
Tema 23: Técnicas de diseño descendente de algoritmosTema 23: Técnicas de diseño descendente de algoritmos
Tema 23: Técnicas de diseño descendente de algoritmos
 
I1M-T19: El TAD de los árboles de búsqueda
I1M-T19: El TAD de los árboles de búsquedaI1M-T19: El TAD de los árboles de búsqueda
I1M-T19: El TAD de los árboles de búsqueda
 
I1M-T17: El TAD de los conjuntos
I1M-T17: El TAD de los conjuntosI1M-T17: El TAD de los conjuntos
I1M-T17: El TAD de los conjuntos
 
Panorama de la demostración asistida por ordenador
Panorama de la demostración asistida por ordenadorPanorama de la demostración asistida por ordenador
Panorama de la demostración asistida por ordenador
 
LMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer ordenLMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer orden
 
LMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer ordenLMF-T6: Sintaxis y semántica de la lógica de primer orden
LMF-T6: Sintaxis y semántica de la lógica de primer orden
 
LMF-T5b: Aplicaciones de la lógica proposicional
LMF-T5b: Aplicaciones de la lógica proposicionalLMF-T5b: Aplicaciones de la lógica proposicional
LMF-T5b: Aplicaciones de la lógica proposicional
 
LMF-T4: Formas normales
LMF-T4: Formas normalesLMF-T4: Formas normales
LMF-T4: Formas normales
 
LMF-T3: Tableros semánticos
LMF-T3: Tableros semánticosLMF-T3: Tableros semánticos
LMF-T3: Tableros semánticos
 
LMF-T2: Deducción natural proposicional
LMF-T2: Deducción natural proposicionalLMF-T2: Deducción natural proposicional
LMF-T2: Deducción natural proposicional
 
I1M-T21: El TAD de los polinomios en Haskell
I1M-T21: El TAD de los polinomios en HaskellI1M-T21: El TAD de los polinomios en Haskell
I1M-T21: El TAD de los polinomios en Haskell
 
LI-T12: LI2011-12: Introducción a la programación lógica con Prolog
LI-T12: LI2011-12: Introducción a la programación lógica con PrologLI-T12: LI2011-12: Introducción a la programación lógica con Prolog
LI-T12: LI2011-12: Introducción a la programación lógica con Prolog
 
LI-T6: Sintaxis y semántica de la lógica de primer orden
LI-T6: Sintaxis y semántica de la lógica de primer ordenLI-T6: Sintaxis y semántica de la lógica de primer orden
LI-T6: Sintaxis y semántica de la lógica de primer orden
 
LI-T5b: Algoritmos para SAT. Aplicaciones
LI-T5b: Algoritmos para SAT. AplicacionesLI-T5b: Algoritmos para SAT. Aplicaciones
LI-T5b: Algoritmos para SAT. Aplicaciones
 
Panorama del razonamiento automático
Panorama del razonamiento automáticoPanorama del razonamiento automático
Panorama del razonamiento automático
 
I1M2010-T24: Programación dinámica en Haskell
I1M2010-T24: Programación dinámica en HaskellI1M2010-T24: Programación dinámica en Haskell
I1M2010-T24: Programación dinámica en Haskell
 
LI2011-T11: Resolución en lógica de primer orden
LI2011-T11: Resolución en lógica de primer ordenLI2011-T11: Resolución en lógica de primer orden
LI2011-T11: Resolución en lógica de primer orden
 
LI2011-T9: Formas normales de Skolem y cláusulas
LI2011-T9: Formas normales de Skolem y cláusulasLI2011-T9: Formas normales de Skolem y cláusulas
LI2011-T9: Formas normales de Skolem y cláusulas
 
I1M2010-T23: Técnicas de diseño descendente de algoritmos.
I1M2010-T23: Técnicas de diseño descendente de algoritmos.I1M2010-T23: Técnicas de diseño descendente de algoritmos.
I1M2010-T23: Técnicas de diseño descendente de algoritmos.
 

Recently uploaded

Tema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificaciónTema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificaciónIES Vicent Andres Estelles
 
SECUENCIA DIDÁCTICA Matemática 1er grado
SECUENCIA  DIDÁCTICA Matemática 1er gradoSECUENCIA  DIDÁCTICA Matemática 1er grado
SECUENCIA DIDÁCTICA Matemática 1er gradoAnaMara883998
 
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptxTECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptxFranciscoCruz296518
 
CARPETA PEDAGÓGICA 2024.docx para educacion
CARPETA PEDAGÓGICA 2024.docx para educacionCARPETA PEDAGÓGICA 2024.docx para educacion
CARPETA PEDAGÓGICA 2024.docx para educacionCarolVigo1
 
Recursos Tecnológicos, página AIP-CRT 2 0 2 4.pdf
Recursos Tecnológicos, página  AIP-CRT 2 0 2 4.pdfRecursos Tecnológicos, página  AIP-CRT 2 0 2 4.pdf
Recursos Tecnológicos, página AIP-CRT 2 0 2 4.pdfNELLYKATTY
 
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didácticaLa poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didácticaIGNACIO BALLESTER PARDO
 
Kirpi-el-erizo libro descargar pdf 1 link
Kirpi-el-erizo libro descargar pdf 1 linkKirpi-el-erizo libro descargar pdf 1 link
Kirpi-el-erizo libro descargar pdf 1 linkMaximilianoMaldonado17
 
plan espacios inspiradores para nivel primaria
plan espacios inspiradores para nivel primariaplan espacios inspiradores para nivel primaria
plan espacios inspiradores para nivel primariaElizabeth252489
 
Los escritos administrativos, técnicos y comerciales
Los escritos administrativos, técnicos y comercialesLos escritos administrativos, técnicos y comerciales
Los escritos administrativos, técnicos y comercialeshanda210618
 
ficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primariaficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primariamichel carlos Capillo Dominguez
 
1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdf
1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdf1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdf
1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdfdiana593621
 
EL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLA
EL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLAEL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLA
EL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLAJAVIER SOLIS NOYOLA
 
Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023Ivie
 
sociales ciencias segundo trimestre tercero
sociales ciencias segundo trimestre tercerosociales ciencias segundo trimestre tercero
sociales ciencias segundo trimestre terceroCEIP TIERRA DE PINARES
 

Recently uploaded (20)

Tema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificaciónTema 4 Rocas sedimentarias, características y clasificación
Tema 4 Rocas sedimentarias, características y clasificación
 
SECUENCIA DIDÁCTICA Matemática 1er grado
SECUENCIA  DIDÁCTICA Matemática 1er gradoSECUENCIA  DIDÁCTICA Matemática 1er grado
SECUENCIA DIDÁCTICA Matemática 1er grado
 
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptxTECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
TECNOLOGÍA EDUCATIVA, USO DE LAS TIC.pptx
 
Sesión de clase ES: Adoración sin fin...
Sesión de clase ES: Adoración sin fin...Sesión de clase ES: Adoración sin fin...
Sesión de clase ES: Adoración sin fin...
 
CARPETA PEDAGÓGICA 2024.docx para educacion
CARPETA PEDAGÓGICA 2024.docx para educacionCARPETA PEDAGÓGICA 2024.docx para educacion
CARPETA PEDAGÓGICA 2024.docx para educacion
 
Recursos Tecnológicos, página AIP-CRT 2 0 2 4.pdf
Recursos Tecnológicos, página  AIP-CRT 2 0 2 4.pdfRecursos Tecnológicos, página  AIP-CRT 2 0 2 4.pdf
Recursos Tecnológicos, página AIP-CRT 2 0 2 4.pdf
 
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didácticaLa poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
La poesía del encarcelamiento de Raúl Zurita en el aula: una propuesta didáctica
 
Kirpi-el-erizo libro descargar pdf 1 link
Kirpi-el-erizo libro descargar pdf 1 linkKirpi-el-erizo libro descargar pdf 1 link
Kirpi-el-erizo libro descargar pdf 1 link
 
plan espacios inspiradores para nivel primaria
plan espacios inspiradores para nivel primariaplan espacios inspiradores para nivel primaria
plan espacios inspiradores para nivel primaria
 
Conducta ética en investigación científica.pdf
Conducta ética en investigación científica.pdfConducta ética en investigación científica.pdf
Conducta ética en investigación científica.pdf
 
Tema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdf
Tema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdfTema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdf
Tema 5.- BASES DE DATOS Y GESTIÓN DE LA INF. PARA EL MARKETING.pdf
 
Los escritos administrativos, técnicos y comerciales
Los escritos administrativos, técnicos y comercialesLos escritos administrativos, técnicos y comerciales
Los escritos administrativos, técnicos y comerciales
 
ficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primariaficha de aplicacion para estudiantes El agua para niños de primaria
ficha de aplicacion para estudiantes El agua para niños de primaria
 
1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdf
1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdf1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdf
1° GRADO UNIDAD DE APRENDIZAJE 0 - 2024.pdf
 
Tema 6.- La identidad visual corporativa y el naming.pdf
Tema 6.- La identidad visual corporativa y el naming.pdfTema 6.- La identidad visual corporativa y el naming.pdf
Tema 6.- La identidad visual corporativa y el naming.pdf
 
Power Point E. Sab: Adoración sin fin...
Power Point E. Sab: Adoración sin fin...Power Point E. Sab: Adoración sin fin...
Power Point E. Sab: Adoración sin fin...
 
EL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLA
EL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLAEL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLA
EL ECLIPSE DE LA PAZ (cuento literario). Autor y diseñador JAVIER SOLIS NOYOLA
 
VISITA DE ESTUDO À CRUZ VERMELHA _
VISITA DE ESTUDO À CRUZ VERMELHA                   _VISITA DE ESTUDO À CRUZ VERMELHA                   _
VISITA DE ESTUDO À CRUZ VERMELHA _
 
Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023Presentación contribuciones socioeconómicas del SUPV 2023
Presentación contribuciones socioeconómicas del SUPV 2023
 
sociales ciencias segundo trimestre tercero
sociales ciencias segundo trimestre tercerosociales ciencias segundo trimestre tercero
sociales ciencias segundo trimestre tercero
 

LI2011-T1: Sintaxis y semántica de la lógica proposicional

  • 1. PD Tema 1: Sintaxis y semántica de la lógica proposicional Lógica informática (2010–11) Tema 1: Sintaxis y semántica de la lógica proposicional José A. Alonso Jiménez Andrés Cordón Franco María J. Hidalgo Doblado Grupo de Lógica Computacional Departamento de Ciencias de la Computación e I.A. Universidad de Sevilla 1 / 34
  • 2. PD Tema 1: Sintaxis y semántica de la lógica proposicional Tema 1: Sintaxis y semántica de la lógica proposicional 1. Introducción 2. Sintaxis de la lógica proposicional 3. Semántica proposicional 2 / 34
  • 3. PD Tema 1: Sintaxis y semántica de la lógica proposicional Introducción Tema 1: Sintaxis y semántica de la lógica proposicional 1. Introducción Panorama de la lógica Ejemplos de argumentos y formalizaciones 2. Sintaxis de la lógica proposicional 3. Semántica proposicional 3 / 34
  • 4. PD Tema 1: Sintaxis y semántica de la lógica proposicional Introducción Panorama de la lógica Lógica Objetivos de la lógica: La formalización del lenguaje natural. Los métodos de razonamiento. Sistemas lógicos: Lógica proposicional. Lógica de primer orden. Lógicas de orden superior. Lógicas modales. Lógicas descriptivas. Aplicaciones de la lógica en computación: Programación lógica. Verificación y síntesis automática de programas. Representación del conocimiento y razonamiento. Modelización y razonamiento sobre sistemas. Lógica informática = Representación del conocimiento + Razonamiento 4 / 34
  • 5. PD Tema 1: Sintaxis y semántica de la lógica proposicional Introducción Ejemplos de argumentos y formalizaciones Argumentos y formalización Ejemplos de argumentos: Ejemplo 1: Si el tren llega a las 7 y no hay taxis en la estación, entonces Juan llegará tarde a la reunión. Juan no ha llegado tarde a la reunión. El tren llegó a las 7. Por tanto, habían taxis en la estación. Ejemplo 2: Si hay corriente y la lámpara no está fundida, entonces está encendida. La lámpara no está encendida. Hay corriente. Por tanto, la lámpara está fundida. Formalización: Simbolización: Simb. Ejemplo 1 Ejemplo 2 p el tren llega a las 7 hay corriente . q hay taxis en la estación la lámpara está fundida r Juan llega tarde a la reunión la lámpara está encendida Si p y no q, entonces r . No r . p. Por tanto, q. p ∧ ¬q → r , ¬r , p |= q. 5 / 34
  • 6. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional Tema 1: Sintaxis y semántica de la lógica proposicional 1. Introducción 2. Sintaxis de la lógica proposicional El lenguaje de la lógica proposicional Recursión e inducción sobre fórmulas Árboles de análisis (o de formación) Eliminación de paréntesis Subfórmulas 3. Semántica proposicional 6 / 34
  • 7. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional El lenguaje de la lógica proposicional El lenguaje de la lógica proposicional Alfabeto proposicional: variables proposicionales: p0 , p1 , . . . ; p, q, r . conectivas lógicas: monaria: ¬ (negación), binarias: ∧ (conjunción), ∨ (disyunción), → (condicional), ↔ (bicondicional). símbolos auxiliares: “(“ y “)”. Fórmulas proposicionales: Definición: Las variables proposicionales son fórmulas (fórmulas atómicas). Si F y G son fórmulas, entonces también lo son ¬F , (F ∧ G), (F ∨ G), (F → G) y (F ↔ G) Ejemplos: Fórmulas: p, (p ∨ ¬q), ¬(p ∨ p), ((p → q) ∨ (q → p)) No fórmulas: (p), p ∨ ¬q, (p ∨ ∧q) 7 / 34
  • 8. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional El lenguaje de la lógica proposicional Fórmulas proposicionales (BNF) Notaciones: p, q, r , . . . representarán variables proposicionales. F , G, H, . . . representarán fórmulas. VP representa el conjunto de los variables proposicionales. Prop representa el conjunto de las fórmulas. ∗ representa una conectiva binaria. Forma de Backus Naur (BNF) de las fórmula proposicionales: F ::= p | ¬G | (F ∧ G) | (F ∨ G) | (F → G) | (F ↔ G). 8 / 34
  • 9. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional Recursión e inducción sobre fórmulas Definiciones por recursión sobre fórmulas Número de paréntesis de una fórmula: Def: El número de paréntesis de una fórmula F se define recursivamente por:  0,  si F es atómica; np(F ) = np(G), si F es ¬G;  2 + np(G) + np(H), si F es (G ∗ H)  Ejemplos: np(p) = 0 np(q) = 0 np(¬q) = 0 np((¬q ∨ p)) = 2 np((p → (¬q ∨ p))) = 4 9 / 34
  • 10. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional Recursión e inducción sobre fórmulas Demostración por inducción sobre fórmulas Principio de inducción sobre fórmulas: Sea P una propiedad sobre las fórmulas que verifica las siguientes condiciones: Todas las fórmulas atómicas tienen la propiedad P. Si F y G tienen la propiedad P, entonces ¬F , (F ∧ G), (F ∨ G), (F → G) y (F ↔ G), tienen la propiedad P. Entonces todas las fórmulas proposicionales tienen la propiedad P. Propiedad: Todas las fórmulas proposicionales tienen un número par de paréntesis. Demostración por inducción sobre las fórmulas. Base: F atómica =⇒ np(F ) = 0 es par. Paso: Supongamos que np(F ) y np(G) es par (hipótesis de inducción). Entonces, np(¬F ) = np(F ) es par y np((F ∗ G)) = 2 + np(F ) + np(G) es par, para cualquier conectiva binaria . 10 / 34
  • 11. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional Árboles de análisis (o de formación) Árboles de análisis (o de formación) (p → (¬q ∨ p)) → p (¬q ∨ p) p ∨ ¬q p ¬ p q q 11 / 34
  • 12. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional Eliminación de paréntesis Criterios de reducción de paréntesis Pueden eliminarse los paréntesis externos. F ∧ G es una abreviatura de (F ∧ G). Precedencia de asociación de conectivas: ¬, ∧, ∨, →, ↔. F ∧ G → ¬F ∨ G es una abreviatura de ((F ∧ G) → (¬F ∨ G)). Cuando una conectiva se usa repetidamente, se asocia por la derecha. F ∨G ∨H abrevia (F ∨ (G ∨ H)) F ∧ G ∧ H → ¬F ∨ G abrevia ((F ∧ (G ∧ H)) → (¬F ∨ G)) 12 / 34
  • 13. PD Tema 1: Sintaxis y semántica de la lógica proposicional Sintaxis de la lógica proposicional Subfórmulas Subfórmulas Def: El conjunto Subf(F ) de las subfórmulas de una fórmula F se define recursivamente por:  {F },  si F es atómica;  Subf(F ) = {F } ∪ Subf(G), si F es ¬G;  {F } ∪ Subf(G) ∪ Subf(H), si F es G ∗ H  Ejemplos: Subf(p) = {p} Subf(q) = {q} Subf(¬q) = {¬q, q} Subf(¬q ∨ p) = {¬q ∨ p, ¬q, q, p} Subf(p → ¬q ∨ p) = {p → ¬q ∨ p, p, ¬q ∨ p, ¬q, q} 13 / 34
  • 14. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Tema 1: Sintaxis y semántica de la lógica proposicional 1. Introducción 2. Sintaxis de la lógica proposicional 3. Semántica proposicional Valores y funciones de verdad Interpretaciones Modelos, satisfacibilidad y validez Algoritmos para satisfacibilidad y validez Selección de tautologías Equivalencia lógica Modelos de conjuntos de fórmulas Consistencia y consecuencia lógica Argumentaciones y problemas lógicos 14 / 34
  • 15. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Valores y funciones de verdad Valores y funciones de verdad Valores de verdad (B): 1: verdadero y 0: falso. Funciones de verdad: 1, si i = 0; H¬ : {0, 1} → {0, 1} t.q. H¬ (i) = 0, si i = 1. 1, si i = j = 1; H∧ : {0, 1}2 → {0, 1} t.q. H∧ (i, j) = 0, en otro caso. 0, si i = j = 0; H∨ : {0, 1}2 → {0, 1} t.q. H∨ (i, j) = 1, en otro caso. 0, si i = 1, j = 0; H→ : {0, 1}2 → {0, 1} t.q. H→ (i, j) = 1, en otro caso. 1, si i = j; H↔ : {0, 1}2 → {0, 1} t.q. H↔ (i, j) = 0, en otro caso. 15 / 34
  • 16. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Interpretaciones Interpretaciones de fórmulas Funciones de verdad mediante tablas de verdad: i ¬i i j i ∧j i ∨j i →j i ↔j 1 0 1 1 1 1 1 1 0 1 1 0 0 1 0 0 0 1 0 1 1 0 0 0 0 0 1 1 Interpretación: Def.: Una interpretación es una aplicación I : VP → B. Prop: Para cada interpretación I existe una única aplicación I : Prop → B tal que:  I(F ),  si F es atómica; I (F ) = H¬ (I (G)), si F = ¬G;  H∗ (I (G), I (H)), si F = G ∗ H  Se dice que I (F ) es el valor de verdad de F respecto de I. 16 / 34
  • 17. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Interpretaciones Interpretaciones de fórmulas Ejemplo: Sea F = (p ∨ q) ∧ (¬q ∨ r ) valor de F en una interpretación I1 tal que I1 (p) = I1 (r ) = 1, I1 (q) = 0 (p ∨ q) ∧ (¬q ∨ r ) (1 ∨ 0) ∧ (¬0 ∨ 1) 1 ∧ (1 ∨ 1) 1 ∧ 1 1 valor de F en una interpretación I2 tal que I2 (r ) = 1, I2 (p) = I2 (q) = 0 (p ∨ q) ∧ (¬q ∨ r ) 0 0 0 0 10 1 1 Prop.: Sea F una fórmula y I1 , I2 dos interpretaciones. Si I1 (p) = I2 (p) para todos las variables proposicionales de F , entonces I1 (F ) = I2 (F ). Notación: Se escribe I(F ) en lugar de I (F ). 17 / 34
  • 18. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Modelos, satisfacibilidad y validez Modelos y satisfacibilidad Modelo de una fórmula Def.: I es modelo de F si I(F ) = 1. Notación: I |= F . Ejemplo (continuación del anterior): – si I1 (p) = I1 (r ) = 1, I1 (q) = 0, entonces I1 |= (p ∨ q) ∧ (¬q ∨ r ) – si I2 (r ) = 1, I2 (p) = I2 (q) = 0, entonces I2 |= (p ∨ q) ∧ (¬q ∨ r ). Fórmulas satisfacibles e insatisfacibles Def.: F es satisfacible si F tiene algún modelo. Ejemplo: (p → q) ∧ (q → r ) es satisfacible I(p) = I(q) = I(r ) = 0. Def.: F es insatisfacible si F no tiene ningún modelo. Ejemplo: p ∧ ¬p es insatisfacible p ¬p p ∧ ¬p 1 0 0 0 1 0 18 / 34
  • 19. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Modelos, satisfacibilidad y validez Tautologías y contradicciones Def.: F es una tautología (o válida) si toda interpretación es modelo de F . Se representa por |= F . Def.: F es una contradicción si ninguna interpretación es modelo de F . Def.: F es contingente si no es tautología ni contradicción. Ejemplos: 1. (p → q) ∨ (q → p) es una tautología. 2. (p → q) ∧ ¬(p → q) es una contradicción. 3. p → q es contingente. p q p → q q → p (p → q) ∨ (q → p) ¬(p → q) (p → q) ∧ ¬(p → q) 1 1 1 1 1 0 0 1 0 0 1 1 1 0 0 1 1 0 1 0 0 0 0 1 1 1 0 0 19 / 34
  • 20. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Modelos, satisfacibilidad y validez Clasificaciones de fórmulas Todas las fórmulas Tautologías Contigentes Contradicciones Verdadera en todas las Verdadera en algunas Falsa en todas las interpretaciones interpretaciones y interpretaciones falsa en otras (ej. p ∨ ¬p) (ej. p → q) (ej. p ∧ ¬p) Safisfacibles Insatisfacibles Todas las fórmulas 20 / 34
  • 21. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Modelos, satisfacibilidad y validez Satisfacibilidad y validez Los problemas SAT y TAUT: Problema SAT: Dada F determinar si es satisfacible. Problema TAUT: Dada F determinar si es una tautología. Relaciones entre satisfacibilidad y tautologicidad: F es tautología ⇐⇒ ¬F es insatisfacible. F es tautología =⇒ F es satisfacible. F es satisfacible =⇒ ¬F es insatisfacible. / p → q es satisfacible. I(p) = I(q) = 1 ¬(p → q) es satisfacible. I(p) = 1, I(q) = 0. 21 / 34
  • 22. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Algoritmos para satisfacibilidad y validez Algoritmos para SAT y TAUT Tabla de verdad para |= (p → q) ∨ (q → p): p q (p → q) (q → p) (p → q) ∨ (q → p) 1 1 1 1 1 1 0 0 1 1 0 1 1 0 1 0 0 1 1 1 Tabla de verdad simplificada para |= (p → q) ∨ (q → p): p q (p → q) ∨ (q → p) 1 1 1 1 1 1 1 1 1 1 0 1 0 0 1 0 1 1 0 1 0 1 1 1 1 0 0 0 0 0 1 0 1 0 1 0 22 / 34
  • 23. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Algoritmos para satisfacibilidad y validez Algoritmos para SAT y TAUT Método de Quine para |= (p → q) ∨ (q → p) (p → q) ∨ (q → p) 0 0 0 1 0 0 1 1 Método de Quine para |= (p → q) ∨ (q → p) (p → q) ∨ (q → p) 0 0 1 0 1 0 0 1∗ 23 / 34
  • 24. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Algoritmos para satisfacibilidad y validez Algoritmos para SAT y TAUT Tablas de verdad para |= (p ↔ q) ∨ (q ↔ p) p q (p ↔ q) (q ↔ p) (p ↔ q) ∨ (q ↔ p) 1 1 1 1 1 1 0 0 0 0 0 1 0 0 0 0 0 1 1 1 Método de Quine para |= (p ↔ q) ∨ (q ↔ p) (p ↔ q) ∨ (q ↔ p) 0 0 1 0 1 0 0 1 0 0 0 0 0 1 24 / 34
  • 25. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Selección de tautologías Selección de tautologías 1. F →F (ley de identidad). 2. F ∨ ¬F (ley del tercio excluido). 3. ¬(F ∧ ¬F ) (principio de no contradicción). 4. (¬F → F ) → F (ley de Clavius). 5. ¬F → (F → G) (ley de Duns Scoto). 6. ((F → G) → F ) → F (ley de Peirce). 7. (F → G) ∧ F → G (modus ponens). 8. (F → G) ∧ ¬G → ¬F (modus tollens). 25 / 34
  • 26. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Equivalencia lógica Fórmulas equivalentes Def.: F y G son equivalentes si I(F ) = I(G) para toda interpretación I. Representación: F ≡ G. Ejemplos de equivalencias notables: 1. Idempotencia: F ∨ F ≡ F ; F ∧ F ≡ F . 2. Conmutatividad: F ∨ G ≡ G ∨ F ; F ∧ G ≡ G ∧ F . 3. Asociatividad: F ∨ (G ∨ H) ≡ (F ∨ G) ∨ H ; F ∧ (G ∧ H) ≡ (F ∧ G) ∧ H 4. Absorción: F ∧ (F ∨ G) ≡ F ; F ∨ (F ∧ G) ≡ F . 5. Distributividad: F ∧ (G ∨ H) ≡ (F ∧ G) ∨ (F ∧ H) ; F ∨ (G ∧ H) ≡ (F ∨ G) ∧ (F ∨ H). 6. Doble negación: ¬¬F ≡ F . 7. Leyes de De Morgan: ¬(F ∧ G) ≡ ¬F ∨ ¬G ; ¬(F ∨ G) ≡ ¬F ∧ ¬G 8. Leyes de tautologías: Si F es una tautología, F ∧ G ≡ G ; F ∨ G ≡ F. 9. Leyes de contradicciones: Si F es una contradicción F ∧ G ≡ F ; F ∨ G ≡ G. 26 / 34
  • 27. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Equivalencia lógica Propiedades de la equivalencia lógica Relación entre equivalencia y bicondicional: F ≡ G syss |= F ↔ G. Propiedades básicas de la equivalencia lógica: Reflexiva: F ≡ F . Simétrica: Si F ≡ G, entonces G ≡ F . Transitiva: Si F ≡ G y G ≡ H, entonces F ≡ H. Principio de sustitución de fórmulas equivalentes: Prop.: Si en la fórmula F se sustituye una de sus subfórmulas G por una fórmula G lógicamente equivalente a G, entonces la fórmula obtenida, F , es lógicamente equivalente a F . Ejemplo: F = ¬(p ∧ q) → ¬(p ∧ ¬¬r ) G = ¬(p ∧ q) G = ¬p ∨ ¬q F = (¬p ∨ ¬q) → ¬(p ∧ ¬¬r ) 27 / 34
  • 28. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Modelos de conjuntos de fórmulas Modelo de conjuntos de fórmulas Notación: S, S1 , S2 , . . . representarán conjuntos de fórmulas. Modelo de un conjunto de fórmulas: Def.: I es modelo de S si para toda F ∈ S se tiene que I |= F . Representación: I |= S. Ejemplo: Sea S = {(p ∨ q) ∧ (¬q ∨ r ), q → r } La interpretación I1 tal que I1 (p) = 1, I1 (q) = 0, I1 (r ) = 1 es modelo de S (I1 |= S). {(p ∨ q) ∧ (¬ q ∨ r ), q → r} 1 1 0 1 1 0 1 1 0 1 1 La interpretación I2 tal que I2 (p) = 0, I2 (q) = 1, I2 (r ) = 0 no es modelo de S (I2 |= S). {(p ∨ q) ∧ (¬ q ∨ r ), q → r} 0 1 0 0 0 1 0 0 1 0 0 28 / 34
  • 29. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Consistencia y consecuencia lógica Conjunto consistente de fórmulas Def.: S es consistente si S tiene algún modelo. Def.: S es inconsistente si S no tiene ningún modelo. Ejemplos: {(p ∨ q) ∧ (¬q ∨ r ), p → r } es consistente (con modelos I4 , I6 , I8 ) {(p ∨ q) ∧ (¬q ∨ r ), p → r , ¬r } es inconsistente p q r (p ∨ q) (¬q ∨ r ) (p ∨ q) ∧ (¬q ∨ r ) p→r ¬r I1 0 0 0 0 1 0 1 1 I2 0 0 1 0 1 0 1 0 I3 0 1 0 1 0 0 1 1 I4 0 1 1 1 1 1 1 0 I5 1 0 0 1 1 1 0 1 I6 1 0 1 1 1 1 1 0 I7 1 1 0 1 0 0 0 1 I8 1 1 1 1 1 1 1 0 29 / 34
  • 30. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Consistencia y consecuencia lógica Consecuencia lógica Def.: F es consecuencia de S si todos los modelos de S son modelos de F . Representación: S |= F . Ejemplos: {p → q, q → r } |= p → r y {p} |= p ∧ q p q r p→q q→r p→r p q p∧q I1 0 0 0 1 1 1 1 1 1 I2 0 0 1 1 1 1 1 0 0 I3 0 1 0 1 0 1 0 1 0 I4 0 1 1 1 1 1 0 0 0 I5 1 0 0 0 1 0 I6 1 0 1 0 1 1 I7 1 1 0 1 0 0 I8 1 1 1 1 1 1 30 / 34
  • 31. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Consistencia y consecuencia lógica Propiedades de la consecuencia Propiedades básicas de la relación de consecuencia: Reflexividad: S |= S. Monotonía: Si S1 |= F y S1 ⊆ S2 , entonces S2 |= F . Transitividad: Si S |= F y {F } |= G, entonces S |= G. Relación entre consecuencia, validez, satisfacibilidad y consistencia: Las siguientes condiciones son equivalentes: 1. {F1 , . . . , Fn } |= G 2. |= F1 ∧ · · · ∧ Fn → G 3. ¬(F1 ∧ · · · ∧ Fn → G) es insatisfacible 4. {F1 , . . . , Fn , ¬G} es inconsistente 31 / 34
  • 32. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Argumentaciones y problemas lógicos Ejemplo de argumentación Problema de los animales: Se sabe que 1. Los animales con pelo o que dan leche son mamíferos. 2. Los mamíferos que tienen pezuñas o que rumian son ungulados. 3. Los ungulados de cuello largo son jirafas. 4. Los ungulados con rayas negras son cebras. Se observa un animal que tiene pelos, pezuñas y rayas negras. Por consiguiente, se concluye que el animal es una cebra. Formalización: { tiene_pelos ∨ da_leche → es_mamífero, es_mamífero ∧ (tiene_pezuñas ∨ rumia) → es_ungulado, es_ungulado ∧ tiene_cuello_largo → es_jirafa, es_ungulado ∧ tiene_rayas_negras → es_cebra, tiene_pelos ∧ tiene_pezuñas ∧ tiene_rayas_negras} |= es_cebra 32 / 34
  • 33. PD Tema 1: Sintaxis y semántica de la lógica proposicional Semántica proposicional Argumentaciones y problemas lógicos Problemas lógicos: veraces y mentirosos Enunciado: En una isla hay dos tribus, la de los veraces (que siempre dicen la verdad) y la de los mentirosos (que siempre mienten). Un viajero se encuentra con tres isleños A, B y C y cada uno le dice una frase 1. A dice “B y C son veraces syss C es veraz” 2. B dice “Si A y C son veraces, entonces B y C son veraces y A es mentiroso” 3. C dice “B es mentiroso syss A o B es veraz” Determinar a qué tribu pertenecen A, B y C. Simbolización: a: “A es veraz”, b: “B es veraz”, c: “C es veraz”. Formalización: F1 = a ↔ (b ∧ c ↔ c), F2 = b ↔ (a ∧ c → b ∧ c ∧ ¬a) y F3 = c ↔ (¬b ↔ a ∨ b). Modelos de {F1 , F2 , F3 }: Si I es modelo de {F1 , F2 , F3 }, entonces I(a) = 1, I(b) = 1, I(c) = 0. Conclusión: A y B son veraces y C es mentiroso. 33 / 34
  • 34. PD Tema 1: Sintaxis y semántica de la lógica proposicional Bibliografía Bibliografía 1. C. Badesa, I. Jané y R. Jansana Elementos de lógica formal. (Ariel, 2000) Cap. 0 (Introducción), 6 (Sintaxis de la lógica proposicional), 7 (Semántica de la lógica proposicional), 9 (Consecuencia lógica) y 11 (Lógica proposicional y lenguaje natural). 2. M. Ben–Ari, Mathematical logic for computer science (2nd ed.). (Springer, 2001) Cap. 1 (Introduction) y 2 (Propositional calculus: formulas, models, tableaux). 3. J.A. Díez Iniciación a la Lógica, (Ariel, 2002) Cap. 2 (El lenguaje de la lógica proposicional) y 3 (Semántica formal. Consecuencia lógica). 4. M. Huth y M. Ryan Logic in computer science: modelling and reasoning about systems. (Cambridge University Press, 2000) Cap. 1 (Propositional logic). 34 / 34