Monografias.com > Filosofía
Descargar Imprimir Comentar Ver trabajos relacionados

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

    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.

    Categorias
    Newsletter