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