o o a o o o ia i. – o Inicio de la L´gica
Originalmente, la L´gica trataba con argumentos en el
lenguaje natural. Ejemplo ¿Es el siguiente argumento
v´lido? Todos los hombres son mortales. S´crates es
hombre. Por lo tanto, S´crates es mortal. La l´gica
deber´ poder usarse para demostrar que s´ IIC2212
L´gica Proposicional 2 / 56
o e o o a – o Inicio de la L´gica Ejemplo
¿Qu´ pasa con el siguiente caso? Algunas personas
son mujeres. S´crates es una persona. Por lo tanto,
S´crates es mujer. En este caso deber´iamos decir que
el argumento no es v´lido. IIC2212 L´gica
Proposicional 3 / 56
o a o o a e e e ia – o Inicio de la L´gica Pero los
argumentos pueden ser m´s complejos … Creo que todos los
hombres son mortales. Creo que S´crates es hombre. Por lo
tanto, creo que S´crates es mortal. ¿Es este
argumento v´lido? ¿Por qu´? ¿Qu´
signi?ca creo? ¿Qu´ pasar´ si reemplazamos
creo que por no se si? IIC2212 L´gica Proposicional 4 /
56
ia o ia e ia – o Paradojas en el lenguaje natural Un
d´ de la pr´xima semana les voy a hacer una
interrogaci´n, y les aseguro que el d´ que se las
haga van a estar sorprendidos. ¿Qu´ d´ voy a
hacer la interrogaci´n? IIC2212 L´gica Proposicional
5 / 56
u u u u a e – o Matem´tica en el lenguaje natural:
Paradoja de Berry Podemos representar los n´meros naturales
usando oraciones del lenguaje natural: “Mil quinientos
veinte”, “el primer n´mero”, … El
n´mero de palabras en el Diccionario de la Real Academia es
?nito. El n´mero de oraciones con a los m´s 50
palabras tambi´n es ?nito. IIC2212 L´gica
Proposicional 6 / 56
u u a a o e o – o Matem´tica en el lenguaje natural:
Paradoja de Berry Sea B el siguiente n´mero natural: El
primer n´mero natural que no puede ser de?nido por una
oraci´n con a lo m´s cincuenta palabras tomadas del
Dicciona- rio de la Real Academia. B est´ bien de?nido,
pero con s´lo 25 palabras. ¡Tenemos una
contradicci´n! ¿Qu´ pas´? IIC2212
L´gica Proposicional 7 / 56
a e i. – o M´s paradojas: Russell (1902)
Tambi´n pueden aparecer paradojas usando lenguaje
matem´tico. Sea A = {1, 2, 3} ¿A ? A? No. Sea B =
{{1, 2, 3}, {4, 5}} ¿A ? B? S´ ¿B ? B? No.
IIC2212 L´gica Proposicional 8 / 56
a i. o o o – o M´s paradojas: Russell (1902) Sea C el
conjunto de todos los conjuntos que tienen a lo menos dos
elementos: C = {A, B, . . .} ¿C ? C ? S´ Entonces
podemos de?nir el siguiente conjunto: U = {X | X ? X }. Tenemos:
A ? U, B ? U, C ? U. ¿U ? U? Por de?nici´n, U ? U si
y s´lo si U ? U. ¡Tenemos una contradicci´n!
¿C´mo de?nimos la noci´n de conjunto? IIC2212
L´gica Proposicional 9 / 56
e o a o u u o ia ia u o e e – o ¿Por qu´
necesitamos la L´gica? Necesitamos un lenguaje con una
sintaxis precisa y una sem´ntica bien de?nida. Queremos
usar este lenguaje en matem´ticas. – De?nici´n de
objetos matem´ticos: conjunto, n´meros naturales,
n´meros reales. – De?nici´n de teor´ias
matem´ticas: teor´ de conjuntos, teor´ de los
n´mero naturales. – De?nici´n del concepto de
demostraci´n. Tambi´n queremos usar este lenguaje en
computaci´n. ¿Por qu´? IIC2212 L´gica
Proposicional 10 / 56
e o o u ia o o ia o a – o ¿Por qu´ necesitamos
la L´gica en computaci´n? Algunas aplicaciones: –
Bases de datos: Lenguajes de consulta, lenguajes para
restricciones de integridad. – Inteligencia arti?cial:
Representaci´n de conocimiento, razonamiento con sentido
com´n. – Ingenier´ de software: Especi?caci´n
de sistemas (lenguaje Z ), veri?caci´n de propiedades. –
Teor´ de la computaci´n: complejidad descriptiva,
algoritmos de aproximaci´n. – Criptograf´ia:
veri?caci´n de protocolos criptogr´?cos. –
Procesamiento de lenguaje natural. – … IIC2212 L´gica
Proposicional 11 / 56
o o o – o L´gica Proposicional: Sintaxis Tenemos los
siguientes elementos: – Variables proposicionales (P): p, q, r ,
. . . – Conectivos l´gicos: ¬, ?, ?, ?, ? –
S´imbolos de puntuaci´n: (, ) Cada variable
proposicional representa una proposici´n completa e
indivisible, que puede ser verdadera o falsa. Ejemplo P =
{socrates es hombre, socrates es mortal }. IIC2212 L´gica
Proposicional 12 / 56
o o e o u – o L´gica Proposicional: Sintaxis
Conectivos l´gicos son usados para construir expresiones
que tambi´n pueden ser verdaderas o falsas. Ejemplo
socrates es hombre ? socrates es mortal socrates es hombre ?
(¬ socrates es mortal ) S´imbolos de puntuaci´n
son usados para evitar ambig¨edades. IIC2212 L´gica
Proposicional 13 / 56
o o o o – o Sintaxis de la L´gica Proposicional:
De?nici´n Dado: Conjunto P de variables proposicionales.
De?nici´n L(P) es el menor conjunto que satisface las
siguientes reglas: 1. P ? L(P). 2. Si ? ? L(P), entonces (¬?)
? L(P). 3. Si ?, ? ? L(P), entonces (? ? ?) ? L(P), (? ? ?) ?
L(P), (? ? ?) ? L(P) y (? ? ?) ? L(P). Ejercicio Veri?que que
((¬p) ? (q ? r )) es una f´rmula. IIC2212 L´gica
Proposicional 14 / 56
o o o o a o o – o Sintaxis de la L´gica
Proposicional: De?nici´n La naturaleza de la
de?nici´n es inductiva. – Permite construir programas
recursivos para chequear si una f´rmula est´ bien
construida. – Permite de?nir inductivamente conceptos asociados a
las f´rmulas. – Permite demostrar inductivamente
propiedades de las f´rmulas. IIC2212 L´gica
Proposicional 15 / 56
o s´ o : : a u e o – o De?niciones inductivas
Queremos de?nir una funci´n la que indica cuantos imbolos
tiene una f´rmula: la((p ? q)) = 5. Caso base Caso
inductivo Para cada p ? P, la(p) = 1. la((¬?)) = 3 + la(?) y
la((? ?)) = 3 + la(?) + la(?), donde corresponde a ?, ?, ? o ?.
En el ejemplo: la((p ? q)) = 3 + la(p) + la(q) = 3 + 1 + 1 = 5.
Ejercicio De?na las funciones pi y pd que indican cu´les
son los n´meros de par´ntesis izquierdos y derechos
en una f´rmula, respectivamente. IIC2212 L´gica
Proposicional 16 / 56
o u e o o o – o Demostraciones inductivas Lo siguiente
parece ser cierto: Cada f´rmula contiene el mismo
n´mero de par´ntesis izquierdos y derechos. pi (?) =
pd(?), para cada f´rmula ?. ¿C´mo podemos
demostrar esto? Podemos usar inducci´n … IIC2212
L´gica Proposicional 17 / 56
o u o : : e o o – o Inducci´n en los n´meros
naturales Principio de inducci´n: para cada A ? N tal que
Caso base Caso inductivo 0 ? A, si n ? A, entonces n + 1 ? A, se
tiene que A = N. Este principio se usa para demostrar que los
naturales tienen alguna propiedad. ¿Por qu´
funciona? Ejercicio Dar un principio de inducci´n para las
f´rmulas de un lenguaje proposicional L(P). IIC2212
L´gica Proposicional 18 / 56
o o o : : e o u e – o Inducci´n en la l´gica
proposicional Principio de inducci´n: Para cada A ? L(P)
tal que Caso base Caso inductivo p ? A, para cada p ? P, si ?, ?
? A, entonces (¬?) ? A y (? ?) ? A, donde ? {?, ?, ?, ?}, se
tiene que A = L(P). ¿Por qu´ funciona? Ejercicio
Demuestre que cada f´rmula contiene el mismo n´mero
de par´ntesis izquierdos y derechos. IIC2212 L´gica
Proposicional 19 / 56
o o u o s´ s´e e o o o – o Inducci´n en
la l´gica proposicional: Ejercicios 1. De?na v (?) como el
n´mero de ocurrencias de variables proposicionales en ?. 2.
Demuestre que para cada f´rmula proposicional ? que no
contiene el imbolo ¬ se tiene que la(?) = 3 · v (?)2 .
¿Qu´ sucede si ? contiene el imbolo ¬?
¿Qu´ sucede si las f´rmulas de la forma
(¬(¬?)) no son permitidas? 3. Demuestre que un pre?jo
propio de una f´rmula no es una f´rmula. IIC2212
L´gica Proposicional 20 / 56
o ´ o o o o o o ´ o ´ ´ o ´ –
o L´gica proposicional: Lectura unica Una f´rmula ?
es at´mica si ? = p, donde p ? P. Una f´rmula ? es
compuesta si no es at´mica. – Si ? = (¬a), entonces
¬ es un conectivo primario de ? y a es una subf´rmula
inmediata de ?. – Si ? = (a ß), entonces es un conectivo
primario de ? y a, ß son subf´rmulas inmediatas de ?.
Teorema (Lectura unica) Cada f´rmula compuesta tiene un
unico conectivo primario y unicas subf´rmulas inmediatas.
Ejercicio Demuestre el teorema de Lectura unica. IIC2212
L´gica Proposicional 21 / 56
a o o o o o – o Sem´ntica de la l´gica
proposicional ¿C´mo podemos determinar si una
f´rmula es verdadera o falsa? Este valor de verdad depende
de los valores de verdad asignados a las variables
proposicionales y de los conectivos utilizados. Valuaci´n
(asignaci´n): s : P ? {0, 1}. Ejemplo s(socrates es hombre)
= 1 y s(socrates es mortal ) = 0. IIC2212 L´gica
Proposicional 22 / 56
a o ˆ o ˆ 1 0 ˆ ˆ ˆ ˆ ˆ ˆ
ˆ ˆ – o Sem´ntica: De?nici´n Dado s :
P ? {0, 1}, queremos extender s: s : L(P) ? {0, 1}.
De?nici´n Dado ? ? L(P), – Si ? = p, entonces s(?) := s(p).
– Si ? = (¬a), entonces s(?) = – Si ? = (a ? ß),
entonces s(?) = 1 si s(a) = 0 0 si s(a) = 1 si s(a) = 1 o
s(ß) = 1 si s(a) = 0 y s(ß) = 0 IIC2212 L´gica
Proposicional 23 / 56
a o 1 0 1 0 ˆ ˆ ˆ ˆ ˆ ˆ ˆ
ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ ˆ
– o Sem´ntica: De?nici´n (continuaci´n) –
Si ? = (a ? ß), entonces s(?) = – Si ? = (a ? ß),
entonces s(?) = – Si ? = (a ? ß), entonces s(?) = si s(a) =
1 y s(ß) = 1 si s(a) = 0 o s(ß) = 0 si s(a) = 0 o
s(ß) = 1 si s(a) = 1 y s(ß) = 0 1 si s(a) =
s(ß) 0 si s(a) = s(ß) Por simplicidad vamos a usar s
en lugar de s. IIC2212 L´gica Proposicional 24 / 56
a – o Sem´ntica: Ejemplos Supongamos que s(socrates
es hombre) = 1 y s(socrates es mortal ) = 0. Entonces:
s((socrates es hombre ? socrates es mortal )) = 0 s((((socrates
es hombre ? socrates es mortal ) ? socrates es hombre) ? socrates
es mortal )) = 1 IIC2212 L´gica Proposicional 25 / 56
o o o o ´ = = = – o Equivalencia de f´rmulas
De?nici´n Dos f´rmulas ?, ? son equivalentes si para
toda valuaci´n s se tiene que s(?) = s(?). Notaci´n:
? = ?. Algunas equivalencias utiles: (¬(? ? ?)) (¬(? ?
?)) (? ? (? ? ?)) = = ((¬?) ? (¬?)) ((¬?) ? (¬?))
((? ? ?) ? ?) (? ? ?) (? ? ?) (¬(¬?)) = = ((¬?) ? ?)
((? ? ?) ? (? ? ?)) ? (? ? (? ? ?)) ((? ? ?) ? ?) IIC2212
L´gica Proposicional 26 / 56
o e – o Equivalencia de f´rmulas Notaci´n:
Desde ahora en adelante – vamos a omitir los par´ntesis
externos, – vamos a escribir ? ? ? ? ? en lugar de (? ? ?) ? ?
(lo mismo para ?). Ejercicio ¿Es ? asociativo? Vale decir,
¿Es cierto que (a ? ß) ? ? = a ? (ß ? ?)?
IIC2212 L´gica Proposicional 27 / 56
o o o a o a o – o Tablas de verdad Cada f´rmula se
puede representar y analizar en una tabla de verdad. p 0 0 1 1 q
0 1 0 1 ¬p 1 1 0 0 p ? q 0 1 1 1 p ? q 0 0 0 1 p ? q 1 1 0 1
p ? q 1 0 0 1 Observaci´n: Dos f´rmulas son
equivalentes si tienen la misma tabla de verdad. Ejercicio
Suponga que P = {p, q}. ¿Cu´ntas f´rmulas
contiene L(P)? ¿Cu´ntas f´rmulas no
equivalentes contiene este conjunto? IIC2212 L´gica
Proposicional 28 / 56
o o – o Conectivos ternarios Queremos de?nir el conectivo
l´gico: si p entonces q si no r . p 0 0 0 0 1 1 1 1 q 0 0 1
1 0 0 1 1 r 0 1 0 1 0 1 0 1 si p entonces q si no r 0 1 0 1 0 0 1
1 ¿C´mo se puede representar este conectivo usando
¬, ? y ?? IIC2212 L´gica Proposicional 29 / 56
p q r e o – o Conectivos ternarios (continuaci´n)
Soluci´n: (p ? q) ? ((¬p) ? r ). si p entonces q si no
r (p ? q) ? ((¬p) ? r ) 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 ¿Por qu´
el conectivo es equivalente a la f´rmula? Porque tienen la
misma tabla de verdad. IIC2212 L´gica Proposicional 30 /
56
. . . . . – o Conectivos n-arios Usando tablas de verdad
podemos de?nir conectivos n-arios: C (p1 , . . . , pn ). p1 0 0 .
. 1 p2 0 0 . . 1 ···
··· ···
··· ··· pn-1 0 0 . . 1
pn 0 1 . . 1 C (p1 , p2 , . . . , pn-1, pn ) b1 b2 . . b2n
¿Es posible representar C (p1 , . . . , pn ) usando ¬,
?, ?, ? y ?? IIC2212 L´gica Proposicional 31 / 56
o – o Conectivos n-arios Veamos un ejemplo: C1 (p, q, r ,
s). p 0 0 0 0 0 0 0 0 q 0 0 0 0 1 1 1 1 r 0 0 1 1 0 0 1 1 s 0 1 0
1 0 1 0 1 C1 (p, q, r , s) 0 1 0 0 0 0 1 0 p 1 1 1 1 1 1 1 1 q 0
0 0 0 1 1 1 1 r 0 0 1 1 0 0 1 1 s 0 1 0 1 0 1 0 1 C1 (p, q, r ,
s) 1 0 0 0 0 0 1 0 ¿C´mo de?nimos C1 (p, q, r , s)
usando ¬, ?, ?, ? y ?? IIC2212 L´gica Proposicional 32
/ 56
o i o – o Conectivos n-arios Soluci´n: C1 (p, q, r ,
s) es equivalente a la siguiente f´rmula ((¬p) ?
(¬q) ? (¬r ) ? s) ? ((¬p) ? q ? r ? (¬s)) ? (p ?
(¬q) ? (¬r ) ? (¬s)) ? (p ? q ? r ? (¬s))
Notaci´n Desde ahora en adelante ¬ tiene mayor
precedencia que los conectivos binarios. As´ por ejemplo,
(¬p) ? q es lo mismo que ¬p ? q y la f´rmula
anterior es lo mismo que: (¬p ? ¬q ? ¬r ? s) ?
(¬p ? q ? r ? ¬s) ? (p ? ¬q ? ¬r ? ¬s) ? (p ?
q ? r ? ¬s) IIC2212 L´gica Proposicional 33 / 56
o o – o Conectivos n-arios Soluci´n a nuestro
problema original: Suponiendo que si es la valuaci´n
correspondiente a la ?la i de la tabla de verdad de C (p1 , . . .
, pn ), este conectivo es equivalente a: i : bi =1 j : si (pj )=1
pj ? k : si (pk )=0 ¬pk . Conclusi´n Basta con los
conectivos l´gicos ¬, ?, ? para representar cualquier
tabla de verdad. IIC2212 L´gica Proposicional 34 / 56
o o o – o Conectivos funcionalmente completos
De?nici´n Un conjunto de conectivos es funcionalmente
completo si es posible de?nir cada f´rmula usando
s´lo estos conectivos. Ya demostramos que {¬, ?, ?} es
funcionalmente completo. ¿Son {¬, ?} y {¬, ?}
funcionalmente completos? Ejercicio – Demuestre que {¬, ?} es
funcionalmente completo. – ¿Es {?, ?, ?, ?} funcionalmente
completo? *Ejercicio ¿Es {¬, ?} funcionalmente
completo? IIC2212 L´gica Proposicional 35 / 56
o a o o o – o Formas normales Decimos que una f´rmula
? est´ en forma normal disyuntiva (DNF) si ? es de la
forma: m i =1 ni j=1 li ,j , donde cada li ,j es un literal, es
decir, una letra proposicional o la negaci´n de una letra
proposicional. Ejemplo (p ? q) ? (¬p ? r ). Teorema Toda
f´rmula es equivalente a una f´rmula en DNF. Ya
demostramos este teorema, ¿Cierto? IIC2212 L´gica
Proposicional 36 / 56
o a o o o – o Formas normales Decimos que una f´rmula
? est´ en forma normal conjuntiva (CNF) si ? es de la
forma: m i =1 ni j=1 li ,j , donde cada li ,j es un literal.
Ejemplo (p ? ¬q) ? (¬p ? ¬r ? s) ? (¬r ? s).
Teorema Toda f´rmula es equivalente a una f´rmula en
CNF. ¿C´mo se demuestre el teorema? IIC2212
L´gica Proposicional 37 / 56
o o o a o o o o – o La noci´n de consecuencia
l´gica Una valuaci´n s satisface un conjunto de
f´rmulas S si para cada ? ? S, se tiene que s(?) = 1.
Notaci´n: s(S) = 1. ¿Cu´ndo decimos que una
f´rmula ? se deduce desde S? De?nici´n ? es
consecuencia l´gica de S si para cada valuaci´n s tal
que s(S) = 1, se tiene que s(?) = 1. Notaci´n: S |= ?.
IIC2212 L´gica Proposicional 38 / 56
o – o La noci´n de consecuencia l´gica:
Ejemplos Modus ponens: {p, p ? q} |= q Demostraci´n por
partes: {p ? q ? r , p ? s, q ? s, r ? s} |= s Ejercicio –
Demuestre que si S |= a ? ß, entonces S |= a y S |=
ß. – ¿Es cierto que si S |= a ? ß, entonces S
|= a o S |= ß? IIC2212 L´gica Proposicional 39 /
56
ia o ia o o u – o Teorema de monoton´ Teorema
(Monoton´ia) Si S |= ?, entonces para cada f´rmula ?
se tiene que S ? {?} |= ?. Sabemos que {p, p ? q} |= q. Usando el
teorema de monoton´ deducimos que {p, p ? q, ¬q} |= q.
¿C´mo es esto posible? Ejercicio Demuestre el
teorema de monoton´ia. ¿Puede usarse la l´gica
proposicional para modelar razonamiento con sentido com´n?
IIC2212 L´gica Proposicional 40 / 56
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN
LA VERSIÓN DE DESCARGA