Download Logica
Document related concepts
Transcript
lógica proposicional LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional CONTENIDO Fórmulas y su semántica [H6.2]. Funciones de verdad [H6.2]. Formas normales [H6.2]. Razonamiento formal: reglas de inferencia, pruebas, sistemas axiomáticos [H6.3]. Completitud y sensatez [H6.2]. HEIN, JAMES. Discrete Structures, Logic and Computability. Jones and Bartlett Publishers. 1995 - 2001 conceptos básicos: la lógica LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional § La lógica es la disciplina que trata con métodos de razonamiento. § La lógica provee reglas y técnicas para determinar si un argumento dado es válido . Augustus De Morgan (1806-1871) George Boole (1815-1864) conceptos básicos: la lógica LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional § Pregunta: ¿Qué relación existe entre la lógica y la computación? mecanizar tareas complejas. n verificación de programas ( ¿coincide lo que se cree que hace el programa y lo que realmente hace?). n los ordenadores lo constituyen circuitos lógicos. n la lógica formal puede considerarse como una especie de lenguaje de programación. n ¿cómo razonamos? LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional ¿Cómo razonamos en nuestras vidas cotidianas? § Declaramos hechos y luego declaramos conclusiones en base a esos hechos. § Utilizamos palabras o frases de la siguiente lista para indicar que se realiza cierta conclusión: por lo tanto entonces de esto se concluye que de esto sigue que … ¿cómo razonamos? LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional La regla de inferencia más común se denomina modus ponens y funciona de la siguiente manera: § Supongamos A y B son sentencias y asumamos que A entonces B es verdadera y A es verdadera § Entonces podemos concluir B es verdadera ¿cómo razonamos? LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplo típico de inferencia por modus ponens: Si llueve entonces hay nubes en el cielo Llueve Por lo tanto hay nubes en el cielo ¿Cómo se aprende la regla de modus ponens? Probablemente durante la infancia ¿cómo razonamos? LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Otra regla que se aprende durante la infancia es llamada modus tollens y funciona de la siguiente manera: § Supongamos A y B son sentencias y asumamos que A entonces B es verdadera y B es falsa § Entonces podemos concluir A es falsa ¿cómo razonamos? LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Falacias lógicas Non sequitur: no se sigue Ío es la luna de Júpiter Titán es la luna de Saturno La Tierra es el tercer planeta más cercano al sol Si un objeto es de oro, brilla. Esta daga brilla. Esta daga es de oro. Si es Bahiense es Argentino No es Bahiense No es Argentino cálculo proposicional LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Una oración que es verdadera o falsa se denomina proposición: Ejemplos § El verano comienza en junio en el hemisferio Sur. § 2+2=4. § Si llueve, entonces hay nubes en el cielo. § Puedo ir o no ir al cine esta noche. § Todos los enteros son pares. § Existe un número primo mayor que 10 100 (googol). cálculo proposicional LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Conectivos lógicos § ┐ (o ’) negación § Λ conjunción § V disyunción § → implicación Otros conectivos se introducen para simplificar notación ej: ↔ equivalencia A B ┐A AΛB AVB A→B V V F V V V V F F V F F V F V V F F F F V V sintaxis vs. semántica LENGUAJES FORMALES Y AUTÓMATAS Sintaxis: § ¿Es esta sentencia gramaticalmente correcta? lógica proposicional Semántica § ¿Cuál es el significado de la siguiente expresión? sintaxis LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Conjunto de símbolos: § Símbolos de verdad: v, f § Conectivos : Λ,V,→,┐ § Variables Proposicionales: P, Q, R § Símbolos de puntuación: ( , ) sintaxis LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Definición informal de fórmula bien formada (fbf) Una fórmula bien formada es § un símbolo de verdad § una letra proposicional § la negación de una fbf § la conjunción de dos fbf § la disyunción de dos fbf § la implicación de una fbf a otra fbf § una fbf rodeada de paréntesis sintaxis LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplos de fbf: verdadero, falso, P, ┐Q, P ΛQ, P→Q, (PVQ) ΛR, PΛQ → R Ejercicios § Dar una gramática BNF para las fbf del cálculo proposicional. § Mostrar que PΛQVR es una fbf. § Mostrar que P→QV(RΛ┐Q) es una fbf. sintaxis LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional ¿Es posible asociar una tabla de verdad a cada fbf? Sí, pero antes debemos establecer una jerarquía de precedencia para los conectivos: ┐ (mayor precedencia, aplicar primero) Λ V → (menor precedencia, aplicar último) Además Λ, V y → son asociativos a izquierda Notar analogía con expresiones aritméticas sintaxis LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional PVQΛR significa P V (Q Λ R) P→Q→R significa (P → Q) → R ┐P V Q significa (┐P) V Q ┐P → P Λ Q V R significa (┐P) → ((P Λ Q) V R) ┐┐P ┐ (┐ P) significa Toda fbf tiene un árbol de sintaxis natural que muestra claramente la jerarquía de los conectivos. Λ Ejemplo: V P P Λ (Q V ┐ R) Q ┐ R árbol sintáctico mostrando jerarquía de conectivos semántica A continuación planteamos algunos ejercicios para repasar el concepto de tablas de verdad. LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejercicio n n Asumamos que P→Q es falso ¿Cuáles son los posibles valores de verdad para las siguientes fbf? § PVQ § ┐P → Q Λ R ¿Y si asumimos P→Q es verdadero? ¿Qué valores de verdad deben tener P, Q, R, S y T para que la siguiente fbf sea falsa? ( P ΛQ ) Λ R ® ( S V T ) semántica LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Tautologías, Contradicciones y Contingencias § Una fbf cuyos valores de verdad son siempre verdaderos (v) es llamada tautología. § Una fbf cuyos valores de verdad son siempre falsos (f) es llamada contradicción. § Una fbf cuyos valores de verdad son a veces v y otras f es llamada contingencia. semántica LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Dos fbf son equivalentes si tienen la misma tabla de verdad. Se nota A ↔ B o A≡B Ya vimos algunos ejemplos. Repasémoslos y veamos algunos nuevos. Algunas equivalencias básicas Negación Disyunción Conjunción ┐┐A ≡ A AVv≡v AΛv ≡A AVf ≡A AΛf ≡f AV A≡ A AΛA ≡ A A V ┐A ≡ v A Λ ┐A ≡ f Implicación A→ v≡v A → f ≡ ┐A v →A≡A f → ┐A ≡ v A→A≡v semántica LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Algunas conversiones A→B≡ ┐ A VB ┐(A→B) ≡AΛ┐B A→B ≡ AΛ┐B → f AVB≡BVA A Λ B≡ B Λ A (A V B) V C ≡ A V (B V C) (A Λ B) Λ C ≡ A Λ (B Λ C) A Λ (B V C) ≡ (A Λ B) V (A Λ C) A V (B Λ C) ≡ (A V B) Λ (A V C) semántica LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Leyes de absorción A Λ (AVB)≡ A A V (AΛB)≡ A A Λ (┐AVB)≡ AΛB A V (┐AΛB)≡ A VB Leyes de De Morgan ┐(AΛB)≡ ┐ A V┐B ┐(AVB)≡ ┐ A Λ ┐ B semántica LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Propiedades de la equivalencia: n ≡ es una relación de equivalencia. n Cualquier sub-fbf de una fbf puede ser reemplazada por una fbf equivalente sin cambiar el valor de verdad de la fbf original. funciones booleanas LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional ¿Que otros conectivos unarios existen además de ‘Ø’? P g1(P) P g2(P) P g3(P) P g4(P) v f v v v f v f v f f v f f f ¿Cuántos conectivos binarios diferentes podríamos definir? En general podemos n 2 definir 2 conectivos n-arios v P Q g(P,Q) v v v/f v f v/f f v v/f f f v/f forma normal disyuntiva LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Expresando otros conectivos en términos de Λ,V y Ø P Q g(P,Q) paso 1: v v f v f v Þ PÙØQ f v v Þ ØPÙQ f f f paso 2: Þ (PÙØQ) Ú (ØPÙQ) Toda fbf es equivalente a una forma normal disyuntiva (FND) forma normal conjuntiva LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional De manera análoga P Q g(P,Q) v v f v f v f v v f f f paso 1: paso 2: Þ ØP Ú ØQ Þ (ØP Ú ØQ ) Ù (P Ú Q) ÞPÚQ Toda fbf es equivalente a una forma normal conjuntiva (FNC) conjunto completo de conectivos LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Dado que se puede expresar cualquier función de verdad utilizando sólo ‘Ù’, ‘Ú’, e ‘Ø’, decimos que el conjunto de operadores {Ø, Ù, Ú} es completo. Recordemos las leyes de De Morgan: Ø(P Ù Q) ≡ ØP Ú ØQ Ø(P Ú Q) ≡ ØP Ù ØQ Por la propiedad de substitución, dado que {Ø, Ù, Ú} es un conjunto completo, de conectivos también lo son los conjuntos {Ø, Ù} y {Ø, Ú} un poco de terminología LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional n Un literal es una letra proposicional o su negación Ejemplos: P, Q, ØP, ØQ n Una conjunción fundamental es un literal o una conjunción de dos o más literales Ejemplos: P, PÙØQ n Una forma normal disyuntiva (FND) es § una conjunción fundamental, o § la disyunción de una o más conjunciones fundamentales Ejemplos: P Ú (ØPÙQ) (P ÙQ) Ú (ØQ ÙP) (P ÙQ ÙR) Ú (Ø P ÙQ ÙR) P ØP PÚØP Ø P ÙQ seguimos con funciones de verdad y formas normales … LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Previamente presentamos un método que permite obtener la FND y la FNC para cualquier función de verdad. Pregunta: ¿Qué ocurre cuando queremos obtener la FND (FNC) a partir de una tabla que no tiene ningún valor verdadero (falso)? P Ù Ø P ≡ falso P Ú Ø P ≡ verdadero dos maneras para obtener FND LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Podemos construir una FND para cualquier función de verdad utilizando el método visto en la clase previa Otra manera es mediante el uso de equivalencias que permiten transformar una fbf en una fbf en FND P Q g(P,Q) v v f f v f v f paso 1: paso 2: f v Þ PÙØQ Þ (PÙØQ) Ú (ØPÙQ) v Þ ØPÙQ f ¿Existe un método automático para tal fin? método para transformar una fbf a FND LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional 1. 2. Remover todas las apariciones del conectivo → A→B≡ Ø A VB Llevar las negaciones hacia adentro para crear literales utilizando leyes de De Morgan 1. 2. 3. Ø(A Ù B) ≡ ØA Ú ØB Ø(A Ú B) ≡ ØA Ù ØB Aplicar las leyes distributivas para obtener una FND A Ù (B Ú C) ≡ (A Ù B) Ú (A Ù C) A Ú (B Ù C) ≡ (A Ú B) Ù (A Ú C) método para transformar una fbf a FND LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplo Escribir la siguiente fbf en FND Ø((P Ú Q) Ù (Q → R)) Ø((P Ú Q) Ù (Q → R)) Ø (P Ú Q) Ú Ø (Q → R) (Ø P Ù Ø Q) Ú Ø (Q → R) (Ø P Ù Ø Q) Ú Ø (Ø Q Ú R) (Ø P Ù Ø Q) Ú (Q Ù Ø R) ≡ ≡ (De Morgan) ≡ (De Morgan) ≡ (implicación) (De Morgan) más terminología: el caso de FNC LENGUAJES FORMALES Y AUTÓMATAS n Una disyunción fundamental es un literal o una disyunción de dos o más literales. Ejemplos: P, P Ú ØQ lógica proposicional n Un forma normal conjuntiva (FNC) es una disyunción fundamental o la conjunción de dos o más disyunciones fundamentales. Ejemplos: P Ù (ØP Ú Q), (P Ú Q) Ù (ØQ Ú P) (P Ú Q Ú R) Ù (Ø P Ú Q Ú R) P ØP PÙØP ØPÚQ dos maneras para obtener FNC LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional De manera análoga a la FND, existen dos maneras para obtener una FNC para cualquier función de verdad n Utilizando el paso 2: P Q g(P,Q) paso 1: método de la Þ ØP Ú ØQ f v v tabla de verdad v f v Þ (ØP Ú ØQ ) Ù (P Ú Q) f v v visto en la f f f ÞPÚQ clase previa n Mediante el uso de equivalencias que permiten transformar una fbf en una fbf en FNC formas completa LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Supongamos que una fbf W tienen n letras proposicionales diferentes. Una FND para W se denomina forma norma disyuntiva completa si cada conjunción fundamental tiene exactamente n literales, uno para cada una de las n letras que aparecen en W. Ejemplo § (P Ù Q Ù R) Ú (Ø P Ù Q Ù R) es una FND completa. § P Ú (Ø P Ù Q) es una FND pero no es una FND completa. La definición para forma norma conjuntiva completa es análoga. método para transformar una fbf a FND completa LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplo Escribir la siguiente fbf en FND completa Ø((P Ú Q) Ù (Q → R)) Ø((P Ú Q) Ù (Q → R)) Ø (P Ú Q) Ú Ø(Q → R) (ØP Ù Ø Q) Ú Ø (Q → R) (ØP Ù Ø Q) Ú Ø (ØQ Ú R) (ØP Ù Ø Q) Ú (Q Ù ØR) ≡ ≡ (De Morgan) ≡ (De Morgan) ≡ (implicación) (De Morgan) La obtenida no es una forma completa. Realizamos los siguientes pasos adicionales aplicando equivalencias básicas y la ley distributiva: (ØPÙØQ) Ú (Q Ù ØR) ≡ (ØPÙØQ) Ù (RÚØR ) Ú (QÙØR) Ù (PÚØP) ≡ (ØPÙØQÙR) Ú (ØPÙØQÙØR) Ú (PÙQÙØR) Ú (ØPÙQÙØR) razonamiento formal LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Las tablas de verdad son suficientes para determinar si una fbf es verdadera. Sin embargo, construir una tabla de verdad para una fbf con muchas variables y conectivos puede volverse una tarea muy compleja. Alternativa: utilizar un sistema de razonamiento formal. reglas de inferencia LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Regla de inferencia: Patrón sintáctico que establece que a partir de un conjunto de premisas (hipótesis o antecedentes) podemos derivar una conclusión. P1 … Pk \C “\” significa “por lo tanto” reglas de inferencia LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Queremos que nuestras reglas de inferencia preserven la verdad. Pregunta: ¿Cuándo podemos asegurar que una regla de inferencia preserva la verdad? P1 … Pk \C Cuando P1 Ù ... Ù Pk → C es una tautología (recordar definición de argumento válido) reglas de inferencia LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Modus Ponens (MP) A A→B \B A B A→B A Ù (A→B) A Ù (A→B) → B v v f f v f v f v f v v v f f f v v v v Cualquier tautología condicional de la forma P 1 Ù ... Ù Pk → C puede ser usada como regla de inferencia. Por ejemplo, la tautología (A → B) Ù Ø B → Ø A da lugar a la regla de Modus tollens (MT) ØB A®B \ØA reglas de inferencia LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Listemos otras reglas de inferencia Regla de Conjunción (Conj.) A,B . \ AÙB Regla de Simplificación (Simp.) A Ù B. \A Regla de Adición (Ad.) A . \ A ÚB reglas de inferencia LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Silogismo Disyuntivo (SD) A Ú B, ØA . \B Silogismo Hipotético (SH) A →B, B →C \A→C axioma LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Un axioma es una fbf que queremos usar como base a partir de la cual podremos razonar. Un axioma es usualmente una fbf que conocemos como verdadera (por ejemplo, luego de verificar su valor de verdad usando una tabla de verdad). Cuando la lógica es aplicada a cierto tema, entonces un axioma podría ser algo que “queremos que sea verdadero” (ejemplo, “dos puntos determinan una única recta”). prueba LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Una prueba es una secuencia finita de fbf con la propiedad de que cada fbf en la secuencia es n un axioma, o n puede ser inferido de fbf previas en la secuencia La última fbf en la secuencia es llamada teorema. pruebas LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Escribiremos las pruebas en forma de tabla, donde cada línea está numerada y contiene una fbf junto con la razón por la cual fue incluida. Prueba 1. W 1 Razón para W1 2. W 2 Razón para W2 M n. W n Razón para Wn prueba condicional (PC) LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional 1. 2. 3. k. A B C P (premisa) P P M M D … 1,2,3,k,PC k+1. A ÙB ÙC → D prueba condicional LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplo Probar la siguiente sentencia (A Ú B) Ù (A Ú C) Ù ØA → B ÙC 1. 2. 3. 4. 5. 6. 7. AÚB AÚC ØA B C BÙC (A Ú B) Ù (A Ú C) Ù ØA → B ÙC P P P 1,3,SD 2,3,SD 4,5,Conj 1,2,3,6,PC prueba condicional: simplificaciones LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplo Probar la siguiente sentencia ((A Ú B) → (B ÙC)) → (B → C) Ú D 1. ((A Ú B) → (B ÙC)) P 2. B P – sub-prueba (B → C) 3. AÚB 2,Ad. 4. B ÙC 1,3,MP 5. C 4,Simp. 6. B → C 2,5,PC – fin sub-prueba 7. (B → C) Ú D 6,Ad. 8. ((A Ú B) → (B ÙC)) → (B → C) Ú D 1,7,PC Advertencia: no usar líneas de la sub-prueba para inferir líneas que aparezcan luego de que la sub-prueba haya finalizado prueba condicional: simplificaciones LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplo Probar la siguiente sentencia Ø(A Ù B) Ù (B Ú C) Ù (C → D) → (A → D) 1. Ø(A Ù B) P Nota: podemos utilizar reglas de 2. B Ú C P equivalencia 3. C → D P 4. ØA Ú ØB 1, Ø(A Ù B) ≡ ØA Ú ØB 5. A P 6. ØB 4,5,SD 7. C 2,6,SD 8. D 3,7,MP 9. A → D 5,8,PC 10. Ø(AÙB)Ù(BÚC)Ù(C→D)→(A→D) 1,2,3,9,PC prueba indirecta (PI) LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional 1. 2. 3. A B C P P P 4. ØD P para PI M M falso … 1,2,3,4,k,PI k. k+1. A ÙB ÙC → D prueba indirecta LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejemplo Probar la siguiente sentencia (A Ú B) Ù ØA Ù (ØC → ØB) → C 1. A Ú B P 2. ØA P 3. ØC → ØB P 4. ØC P para PI 5. ØB 3,4,MP 6. A 1,5,SD 7. ØA Ù A 2,6,Conj 11. falso 7,ØAÙA ≡ falso 12.(A Ú B) Ù ØA Ù (ØC → ØB) → C 1,2,3,4,11,PI pruebas LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejercicio Supongamos que tenemos las siguientes premisas: “No está soleado y no hace frío” “Si no está soleado entonces no vamos a nadar” “Si no vamos a nadar entonces vamos al cine” “Si vamos al cine entonces regresamos a casa tarde.” Probar que las premisas anteriores implican “Regresamos a casa tarde” pruebas LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejercicio: Mostrar que los siguientes argumentos son válidos: § “Pedro sacó dos A’s, pero si Pedro no promocionó entonces Pedro no sacó dos A’s, entonces Pedro promocionó”. § “Si el programa es eficiente, entonces ejecuta rápidamente. O bien el programa es eficiente o bien tiene un error. Sin embargo, el programa no ejecuta rápidamente. Por lo tanto el programa tiene un error”. sensatez y completitud LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Sensatez: (correctitud/sanidad): Queremos que todas las pruebas de teoremas devuelvan tautologías. tautologías teoremas tautologías Completitud: Queremos que todas las tautologías puedan ser probadas como teoremas. teoremas sistema de Hilbert (similar al original) LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Axiomas 1. A Ú A → A 2. A → A Ú B 3. A Ú B → B Ú A 4. (A → B) → (C Ú A → C Ú B) 5. A → B ≡ Ø A Ú B ≡ Ø (A Ù Ø B) David Hilbert (1862-1943) Reglas n Regla de inferencia Modus Ponens (MP) n Regla de Prueba Condicional (PC) pruebas usando el sistema de Hilbert LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Teorema 1: (A → B) Ù (B → C) → (A → C) 1. (A → B) P 2. (B → C) P 3. A P 4. B 1,3,MP 5. C 2,4,MP 6. A → C 3,5,PC 7. (A → B) Ù (B → C) → (A → C) 1,2,6,PC Podemos usar teoremas previamente probados para probar nuevos teoremas Teorema 2: A → A 1. A → A Ú A axioma 2 2. A Ú A → A axioma 1 3. A → A 1,2, Teorema 1,MP pruebas usando el sistema de Hilbert LENGUAJES FORMALES Y AUTÓMATAS lógica proposicional Ejercicios Dar una prueba para los siguientes teoremas usando el sistema de Hilbert Teorema 3: Teorema 4: Teorema 5: Teorema 6: Teorema 7: ØAÚA AÚØA ØAÚØØA A →Ø Ø A Ø Ø A→ A