Lógica Proposicional (LP) Proposición Ø Enunciado del que puede afirmarse si es verdadero o falso Ø Oración declarativa ¿Cuáles de las siguientes son proposiciones? 1) Pedro es alto. 2) Juan es estudiante. 3) Ayer llovió. 4) ¿Quién es? 5) Esta mesa es azul. 6) 3 es impar. Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009 Lógica Proposicional Proposición Simple • Mi perro es negro. • Juan es estudiante Compuesta •María es arquitecta o Juan es músico. • Si ayer llovió entonces hoy sale el sol. • 2 * 3 = 6 y 7 no es par. Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009 1
Lógica Proposicional
Definición del Lenguaje de la Lógica Proposicional
– Alfabeto ØSintaxis: cómo definir fórmulas bien formadas (fórmulas como cadenas de símbolos)
ØSemántica: cómo interpretar esas fórmulas, es decir cómo asignarles un valor de verdad – Lenguaje
– Valuaciones (fórmulas como enunciados que pueden ser verdaderos o falsos)
Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
Lógica Proposicional: Sintaxis
Alfabeto (APROP): APROP = Var ? { ¬, ?, ?, ? } ? { (, ) }
Símbolos auxiliares Variables o símbolos proposicionales (a, b, c, …, p, q, …) Conectivos proposicionales: ¬ negación ? y ? o ? si … entonces
Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
2
Lógica Proposicional: Sintaxis
Lenguaje de la LP – Conjunto de Fórmulas de la LP (Fm): Fm es el conjunto de cadenas de símbolos de APROP, Fm ? A*PROP, que se obtiene aplicando las siguientes reglas: ü Para toda variable p ? Var, entonces p ? Fm, es decir Var ? Fm ü Si A ? Fm, entonces ¬ A ? Fm Fórmulas atómicas Fórmulas no ü Si A, B ? Fm, entonces (A ? B), (A ? B), (A ? B) ? Fm atómicas á ((p ? q) ? r)
â p ? q ? r ((p ? q) ? ¬q)
((p ? ) ? ¬q) SON FORMULAS DE Fm
NO SON FORMULAS DE Fm Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
Lógica Proposicional: Sintaxis
Longitud de una Fórmula A (long A): ü Si A = p, p ? Var, entonces long(p) = 1 ü Si A = ¬B, B ? Fm, entonces long(A) = long(B) + 1 ü Si A = B * C, con B, C ? Fm, y * es uno de los conectivos ?, ?, ?, entonces long(A) = long(B) + long(C) + 1
Subfórmulas de una Fórmula A (Sf(A)): ü Sf(p) = { p } si p ? Var ü Sf(¬A) = Sf(A) ? {¬ A } si A ? Fm ü Sf((A * B)) = Sf(A) ? Sf(B) ? {(A * B)} si A, B ? Fm, y * es uno de los conectivos ?, ?, ?
Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
3
Lógica Proposicional: Sintaxis
Otra definición de Fm :
::= ? |
::= ? |
::= ? |
::= ( ) | ¬ |
::= a | b | c | … | z
Esta definición tiene en cuenta precedencia de conectivos: ¬, ?, ?, ? (de mayor a menor) Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
Lógica Proposicional: Semántica
• Interpretación de fórmulas como enunciados a los que se puede asignar sólo uno de dos valores: Verdadero (1, V, T) ó Falso (0, F, ?)
• La interpretación o valuación de una fórmula se obtiene como sigue: – se asigna un valor de verdad (1 ó 0) a las variables proposicionales
– se interpretan las fómulas no atómicas teniendo en cuenta el significado de los conectivos que contienen Interpretación de conectivos ¬ ? 0 1 ? 0 1 0 1 1 0 ? 0 1 0 0 0 1 0 1 0 1 0 1 1 1 ? 0 1 0 1 0 1 1 1 0 1 1 0 0 1 Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
4
Lógica Proposicional: Semántica Valuación: Es una función v: Fm ? {0, 1} que cumple con las siguientes propiedades para todo A, B ? Fm • v(¬A) = ¬v(A) • v(A ? B) = v(A) ? v(B) • v(A ? B) = v(A) ? v(B) • v(A ? B) = v(A) ? v(B) Ejemplo: Dada la fórmula A = p ? q ? ¬q y la valuación v(p) = 1 y v(q) = 1 v(A) = v(p ? q ? ¬q) = v(p ? q) ? v(¬q) = v(p) ? v(q) ? ¬v(q) = 1 ? 1 ? ¬1 =1 ? 0=0 Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
Lógica Proposicional: Semántica
Tablas de Verdad: Permiten calcular todos los posibles valores de verdad de una fórmula considerando todas las valuaciones posibles.
Fórmula ? secuencia finita de variables y conectivos: • conociendo valor de verdad de las k variables de la fórmula se puede construir la tabla de verdad • Tamaño de la tabla de verdad = 2k filas Ejemplo: Para la fórmula A=p ? q ? ¬q p 0 0 1 1 q 0 1 0 1 p ? q 0 0 0 1 ¬q 1 0 1 0 p ? q ? ¬q 1 1 1 0 Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
5
Lógica Proposicional: Semántica
Definiciones:
ü Una tautología es una fórmula A que es verdadera bajo toda valuación. Es decir, A es tautología sí y sólo sí para toda valuación v, v(A) = 1 En la tabla de verdad, todos los elementos de la columna correspondiente a la fórmula son 1. En símbolos = A ü Una contradicción es una fórmula A que es falsa bajo toda valuación. Es decir, A es contradicción sí y sólo sí para toda valuación v, v(A) = 0
ü Una contingencia es una fórmula A que es no es ni tautología ni contradicción.
ü Una fórmula A es una tautología sí y sólo sí su negación ¬A es una contradicción.
Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
Lógica Proposicional: Semántica Definiciones:
ü Una valuación v satisface una fórmula A si v(A) = 1
ü Una fórmula A se dice satisfacible si existe alguna valuación v que la satisfaga, es decir para alguna valuación v, v(A) = 1. En caso contrario, A es insatisfacible (contradicción).
ü Una valuación v satisface un conjunto de fórmulas G ? Fm si v satisface cada fórmula de G, es decir v(A) = 1 para toda fórmula A ? G
ü Un conjunto de fórmulas G son mutuamente satisfacibles, o consistentes entre sí, si existe al menos una valuación v que satisface cada fórmula de G, es decir v(A) = 1 para toda fórmula A ? G
Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
6
Lógica Proposicional: Semántica Equivalencia Lógica: Dos fórmulas A y B se dicen equivalentes, A = B, sí y sólo sí para toda valuación v, v(A) = v(B) = es una relación de equivalencia en el conjunto de las fórmulas Fm , es decir cumple las propiedades: • Reflexiva: A = A • Simétrica: Si A = B entonces B = A • Transitiva: Si A = B y B = C entonces A = C Ejemplos: • A ? B = ¬A ? B • A ? ¬A = A ? A • A = ¬¬A Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009 Lógica Proposicional: Semántica Equivalencia Lógica: Lema Sean A, B ? Fm. Entonces A = B sí y sólo sí v(A ? B) = 1 para toda valuación v. Demostración: ?) Si A = B entonces para cualquier valuación v, v(A) = v(B). Por lo tanto v(A ? B) = v(A) ?v(A) = 1 y v(B ? A) = v(B) ?v(B) = 1 Entonces v(A ? B) = v(A ? B) ? v(B ? A) = 1 ?) Sea v(A ? B) = 1. Es decir, v(A ? B) = 1 y v(B ? A) = 1 Supongamos que A = B, es decir existe v tal que v(A) ? v(B). Se pueden dar dos casos: v(A) = 1 y v(B) = 0 entonces v(A ? B) = 1 ? 0 = 0 v(A) = 0 y v(B) = 1 entonces v(B ? A) = 1 ? 0 = 0 En cualquier caso, se obtiene una contradicción. Por lo tanto v(A) = v(B) y entonces A = B Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009 7
Lógica Proposicional: Semántica Sustitución: Es una función e: Fm ? Fm que cumple con las siguientes propiedades para todo A, B ? Fm • e(¬A) = ¬e(A)
• e(A ? B) = e(A) ? e(B)
• e(A ? B) = e(A) ? e(B)
• e(A ? B) = e(A) ? e(B) Teorema: Dadas A, B ? Fm tal que A = B, y dada la sustitución e, entonces e(A) = e(B) Ejemplo: Sea p ? q = ¬p ? q y sea e(p) = a ? b y e(q) = a ? c Aplicando e a ? b ? a ? c = ¬(a ? b) ? a ? c (se reemplaza cada ocurrencia de la variable) Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
Lógica Proposicional: Semántica Definición: Sea A = B y X una fórmula donde A puede aparecer varias veces como subfórmula. Si se reemplaza en X la subfórmula A por B (en todas o alguna de sus ocurrencias) la fórmula Y obtenida es equivalente a X.
Ejemplo: Sea X = (p ? q) ? ((p ? q) ? p) y la equivalencia p ? q = ¬p ? q Reemplazando en X se obtiene la fórmula Y = (¬p ? q) ? ((p ? q) ? p) Se puede verificar que X = Y
Sustitución vs. Reemplazo La sustitución preserva la equivalencia entre las dos fórmulas porque se hace en toda ocurrencia de la fórmula sustituida (no requiere que la fórmula sustituida sea equivalente a la sustituyente)
El reemplazo preserva la equivalencia porque la fórmula sustituyente es equivalente a la sustituida (no requiere realizarse en toda ocurrencia de la fórmula sustituida) Ciencias de la Computación II – Filminas de Clase – Mg . Virginia Mauco – Facultad Cs. Exactas – UNCPBA – 2009
8