Monografías Plus      Agregar a favoritos      Ayuda      Português      Ingles     

Logica proposicional






Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
. . . . . – 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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
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

Monografias.com
ESTA PRESENTACIÓN CONTIENE MAS DIAPOSITIVAS DISPONIBLES EN LA VERSIÓN DE DESCARGA

Comentarios


Trabajos relacionados

  • Pitagoras y el pitagorismo

    Biografía de pitagoras. Armonía de los contrarios. La comunidad pitagorica. Nació hacia el año 578 ac. En samos (rival ...

  • Filósofos de la naturaleza

    Sócrates. La Política. Enseñanzas. El juicio. Tales de Mileto. Platón: Obra; Teoría de las ideas; Teoría del conocimien...

  • Eutanasia

    Definición del término eutanasia. Eutanasia: ¿Existe un derecho a morir?. Formas de aplicación de la eutanasia. La batal...

Ver mas trabajos de Filosofia

 
 

Nota al lector: es posible que esta página no contenga todos los componentes del trabajo original (pies de página, avanzadas formulas matemáticas, esquemas o tablas complejas, etc.). Recuerde que para ver el trabajo en su versión original completa, puede descargarlo desde el menú superior.


Todos los documentos disponibles en este sitio expresan los puntos de vista de sus respectivos autores y no de Monografias.com. El objetivo de Monografias.com es poner el conocimiento a disposición de toda su comunidad. Queda bajo la responsabilidad de cada lector el eventual uso que se le de a esta información. Asimismo, es obligatoria la cita del autor del contenido y de Monografias.com como fuentes de información.

Iniciar sesión

Ingrese el e-mail y contraseña con el que está registrado en Monografias.com

   
 

Regístrese gratis

¿Olvidó su contraseña?

Ayuda