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