Resumen Asignatura Lógica 2017/2018-1 PDF

Preview

Summary

Contenido Lógica de Enunciados..................................................................................................................................... Formalización de Enunciados................................................................................................................

Description

RESUMEN LÓGICA UOC

Contenido Lógica de Enunciados.....................................................................................................................................3 Formalización de Enunciados.....................................................................................................................3 Conectivas..............................................................................................................................................3 Otras conectivas:....................................................................................................................................3 Condiciones Suficientes y Necesarias.....................................................................................................3 Deducción Natural.....................................................................................................................................4 Reglas de Inferencia...............................................................................................................................4 Empezar por la conclusión.....................................................................................................................6 Mirar bien las premisas..........................................................................................................................6 Estrategias..............................................................................................................................................7 Reglas Derivadas....................................................................................................................................7 Equivalencias Deductivas.......................................................................................................................8 Teorema.................................................................................................................................................8 Álgebra de Boole........................................................................................................................................9 Forma Normal Conjuntiva (FNC) y Disyuntiva (FND)..............................................................................9 Obtener una FNC....................................................................................................................................9 Obtener una FND...................................................................................................................................9 Equivalencias..........................................................................................................................................9 Resolución..................................................................................................................................................9 Reducción al absurdo...........................................................................................................................10 Resolución lineal..................................................................................................................................10 Replanteamiento última decisión.........................................................................................................10 Conjunto de apoyo...............................................................................................................................11 Resultados Resolución..........................................................................................................................11 Simplificar conjunto de cláusulas.........................................................................................................11 Tablas de verdad......................................................................................................................................12 Tautología.............................................................................................................................................12 Antinomia.............................................................................................................................................12 Enunciado contingente.........................................................................................................................12 Contraejemplo.....................................................................................................................................12 Resultados............................................................................................................................................12 Lógica de Predicados....................................................................................................................................13 Formalización...........................................................................................................................................13 Predicados, variables y constantes.......................................................................................................13 Cuantificadores....................................................................................................................................13 Fórmulas..............................................................................................................................................14 RESUMEN LÓGICA UOC

PÁGINA 1

JUAN OVELAR

RESUMEN LÓGICA UOC Ámbito de los cuantificadores..............................................................................................................14 Cómo formalizar...................................................................................................................................14 Frases complejas de formalizar............................................................................................................14 Significados de los cuantificadores.......................................................................................................15 Deducción Natural...................................................................................................................................15 Reglas...................................................................................................................................................15 Reglas Derivadas y Equivalentes deductivos........................................................................................17 Forma Normal de Skolem.........................................................................................................................18 Eskolemización.....................................................................................................................................18 Resolución................................................................................................................................................ 18 El cálculo de sustituciones....................................................................................................................18 Algoritmo de unificación......................................................................................................................19 Tablas de verdad......................................................................................................................................19 Interpretaciones...................................................................................................................................19 De fórmulas a enunciados....................................................................................................................19 Contraejemplos....................................................................................................................................20

RESUMEN LÓGICA UOC

PÁGINA 2

JUAN OVELAR

RESUMEN LÓGICA UOC

Lógica de Enunciados Formalización de Enunciados Conectivas

Asociar la máxima prioridad a la conectiva ¬ y la mínima a la conectiva . Las conectivas ^ y v tendrán la misma prioridad y ésta estará entra la de ¬ y la de . En igualdad de prioridad consideraremos que la asociatividad es de izquierda a derecha. Eliminar los paréntesis más externos y los que la asignación de prioridades descrita en el punto anterior haga innecesarios. Aunque esta convención permite eliminar muchos de los paréntesis, se tiene absoluta libertad para dejar los que consideremos que mejoran la legibilidad.

Otras conectivas: Bicondicional: Se lee “si y sólo si”. Cuando sea necesario formalizar esta conectiva A  B, utilizaremos (AB) ^ (BA) Disyunción exclusiva: Se lee “o uno, o el otro, pero no los dos”. Cuando sea necesario formalizar A v B, utilizaremos (A v B) ^ ¬(A ^ B).

Condiciones Suficientes y Necesarias Condiciones suficientes. Expresan que algo es una condición suficiente para otra cosa. Ejemplos de condiciones suficientes • • • • • •

“Si como me reanimo”. Que coma es condición suficiente para que me reanime. “Cuando los zapatos son nuevos, me hacen daño”. Que los zapatos sean nuevos es suficiente para que me hagan daño. “Siempre que trabaja, su jefe lo felicita”. Que trabaje es suficiente para que su jefe lo felicite. “Corto el bacalao si el jefe no está y los otros me dejan”. Que el jefe no esté y los otros me dejen es condición suficiente para que corte el bacalao. “Tengo escalofríos y dolor de cabeza cuando como queso”. Que coma queso es suficiente para tener escalofríos y dolor de cabeza. “Basta con que piense que es peligroso para se quede en casa”. Que piense que es peligroso es suficiente para que se quede en casa.

Por regla general, las construcciones del estilo “si ... entonces ...”, “... si ...”, “cuando ... entonces ...”, “siempre que ...”, “... siempre que”, “basta con que... para que...”, etc., expresan una condición suficiente. Ahora bien, hay que tener en cuenta que el lenguaje natural es muy rico y que, por lo tanto, ofrece otras formas de expresar el mismo tipo de condición. RESUMEN LÓGICA UOC

PÁGINA 3

JUAN OVELAR

RESUMEN LÓGICA UOC Condiciones necesarias. Aquellas que expresan que algo es una condición necesaria para otra cosa. Ejemplos de condiciones necesarias • • • • •

“Debes tener dinero para poder ir a esquiar”. Tener dinero es necesario para poder ir a esquiar. “Sólo siendo feliz podrás vivir muchos años”. Ser feliz es necesario para vivir muchos años. “Para ganar debes ser hábil y tener suerte”. Ser hábil y tener suerte es necesario para ganar. “Para reanimarme debo comer”. Comer es necesario para reanimarme. “Es necesario que llueva para tener buenas cosechas”.

Habitualmente, las condiciones necesarias se expresarán con construcciones como por ejemplo “se debe ... para ...”, “sólo ...”, “sólo cuando ...”, “es necesario que ... para ...”. A es suficiente para B:

AB

A es necesario para B:

¬A  ¬B -||- B  A

La parte izquierda de una implicación se denomina “Antecedente” y la parte derecha “Consecuente”.

Deducción Natural Reglas de Inferencia Regla 1. Introducción de la conjunción (I^) Si existe “A” y existe “B” entonces puedo decir “A y B”

Regla 2. Eliminación de la conjunción (E^) Si existe “A y B” entonces puedo decir “A” por un lado y “B” por el otro.

Regla 3. Introducción de la disyunción (Iv) Si existe “A”, puedo decir “A o B” o “B o A”. Se puede inventar otro átomo.

RESUMEN LÓGICA UOC

PÁGINA 4

JUAN OVELAR

RESUMEN LÓGICA UOC Regla 4. Eliminación de la implicación o modus ponens (E ) Si existe “AB” y sólo si por otra parte tengo el antecedente “A”, puedo decir “B” por separado”.

Regla 5. Introducción de la implicación (I ) Para obtener “AB” es necesario abrir una subdeducción con el antecedente “A” como hipótesis. En el momento que se obtiene “B” se puede salir de la subdeducción con el resultado “AB”.

Regla 6. Introducción de la negación o reducción al absurdo (I¬) Para obtener “¬A” es necesario abrir una subdeducción con el atomo en positivo “A” y dentro de la subdeducción se debe encontrar una contradicción (pareja de átomos contrarios) “B” y “¬B”.

Regla 7. Eliminación de la negación (E¬) Para poder eliminar una negación se necesita tener dos negaciones consecutivas.

Regla 8. Eliminación de la disyunción o prueba por casos (Ev) Para poder eliminar la disyunción “A v B” es necesario abrir dos hipótesis, una con “A” y otra con “B”, y ambas deben llegar al mismo resultado “C”. RESUMEN LÓGICA UOC

PÁGINA 5

JUAN OVELAR

RESUMEN LÓGICA UOC

Regla 9. Iteración (it) Si existe “A” puedo volver a utilizarlo siempre que esté en el ámbito de la deducción o de la subdeducción en la que se está trabajando.

Empezar por la conclusión 1. Si la conclusión es una implicación empezar abriendo una subdeduccion con el antecedente como hipótesis. 2. Si la conclusión es una negación empezar abriendo una subdeducción con el átomo en positivo. 3. Si la conclusión es una conjunción empezar obteniendo cada conjuntando por separado. 4. Si la conclusión es una disyunción empezar por obtener uno de los dos disyuntando.

Mirar bien las premisas Prestar atención a las premisas!!! 1. Si hay implicaciones, ver si al aplicar la regla E-> el consecuente nos puede ser de utilidad. Tener en cuenta que se necesita contar con el antecedente en otro enunciado. 2. Si hay conjunciones, ver si al aplicar la regla E^ se puede obtener algún enunciado útil. 3. Si hay disyunciones, ver si se puede obtener un enunciado útil mediante la prueba por casos Ev

Estrategias Directa Plantear la demostración aplicando una regla que sea la que introduzca la conectiva principal de la conclusión. Refutativa (Reducción al absurdo) Plantear la demostración buscando una contradicción, utilizando la I¬ o E¬. Se debe abrir una hipótesis con la negación de una enunciado y a partir de ahí buscar la contradicción.

Reglas Derivadas Una regla derivada es una regla que puede demostrarse a partir de las reglas básicas. Silogismo hipotético (SH) Si hay dos implicaciones A -> B y B -> C podemos decir A -> C RESUMEN LÓGICA UOC

PÁGINA 6

JUAN OVELAR

RESUMEN LÓGICA UOC

Quodlibet sequitur (QS) De una contradicción, se puede obtener cualquier enunciado.

Silogismo disyuntivo (SD) Si tengo un enunciado que es una disyunción y otro enunciado que es la negación de uno de los disyuntandos, puedo obtener el segundo disyuntando.

Modus tollens (MT) Si tengo una implicación y la negación del consecuente puedo obtener el antecedente.

Resolución (Res) Si en dos disyunciones tenemos un átomo en uno de ellos y la contradicción de este en el otro, los podemos “eliminar” y quedarnos con los disyuntandos restantes en una nueva disyunción.

RESUMEN LÓGICA UOC

PÁGINA 7

JUAN OVELAR

RESUMEN LÓGICA UOC

Equivalencias Deductivas Una equivalencia deductiva es la igualdad de dos enunciados. Se pueden utilizar equivalentes deductivos en una demostración y se utiliza la sigla ED para marcar su utilización.

Teorema Es una demostración sin premisas que podemos usar como “herramienta” para una DN y se simboliza cuando no especificamos de qué teorema se está hablando. Tiene algunas propiedades: 1) Un teorema puede ser introducido en cualquier línea de una deducción, porque no necesita premisas para ser demostrado. Cuando un teorema se introduce en una demostración se nota con TE. 2) Todos los teoremas son equivalentes deductivos entre sí. 3) De la negación de cualquier teorema, se desprende una contradicción. Principios Aristotélicos

Axiomas de Hilbert

De la negación de cualquier teorema se desprende una contradicción, y se simboliza  cuando no se especifica de qué contradicción se habla.

Álgebra de Boole Es un conjunto en el que hay dos operaciones binarias, para los enunciados se trata de conjunciones y disyunciones. Sus propiedades se definen en forma de leyes:

RESUMEN LÓGICA UOC

PÁGINA 8

JUAN OVELAR

RESUMEN LÓGICA UOC Se deja de lado la conectiva Implicación, por lo tanto:

Forma Normal Conjuntiva (FNC) y Disyuntiva (FND) Cuando un enunciado se expresa como una conjunción de disyunciones o negaciones de éstas. (…v…v…v...) ^ (…v…v…v...) ^ (…v…v…v...) ^ (…v…v…v...) Cuando un enunciado se expresa como una disyunción de conjunciones o negaciones de éstas. (…^…^…^...) v (…^…^…^...) v (…^…^…^...) v (…^…^…^...)

Obtener una FNC 1. 2. 3. 4. 5.

Eliminar implicaciones Aplicar Ley de Morgan Eliminación de negaciones Aplicar Distributiva Simplificar resultado (idempotencia, complementariedad, ley del supremo)

Obtener una FND 6. Aplicar Distributiva a la conjunción obtenida en el paso anterior.

Equivalencias Cuando hay dos enunciados que tienen la misma FNC o la misma FND son enunciados equivalentes. Que no tengan la misma FNC no quiere decir que no sean equivalentes.

Resolución El método de resolución se basa en la regla de resolución, aplicada mediante una estrategia de reducción al absurdo sobre las FNC de las premisas y de la negación de la conclusión. Si en dos disyunciones tenemos un átomo en una de ellas y la contradicción de éste en la otra, los podemos “eliminar” y quedarnos con los disyuntandos restantes en una nueva disyunción. Al utilizar el método de resolución se denomina cláusula a cada disyunción y literal a cada uno de los disyuntandos. Cuando se aplica el método de resolución a dos cláusulas se dice que éstas se resuelven entre ellas. A la cláusula que obtenemos como resultado se la llama resolvente. Cuando dos cláusulas con un solo átomo (ejemplo A y ¬A) se resuelven entre sí, la resolvente no contiene ningún lateral y se la llama cláusula vacía, se simboliza . Ejemplo de representación de una resolución:

Reducción al absurdo. Esta estrategia prueba que de las premisas y de la negación de la conclusión se desprende una contradicción. Previamente se debe obtener las FNC de estos enunciados. RESUMEN LÓGICA UOC

PÁGINA 9

JUAN OVELAR

RESUMEN LÓGICA UOC Razonamiento correcto: cuando se encuentra la contradicción. Razonamiento incorrecto: cuando NO se encuentra la contradicción.

Resolución lineal Esta estrategia permite ahorrar las aplicaciones de la regla de resolución. Se representa de la siguiente manera:

Las cláusulas de la izquierda se las denomina cláusulas troncales, mientras que las de la derecha se denominan cláusulas laterales. Se intenta eliminar siempre el literal que está más a la derecha de la cláusula troncal.

Replanteamiento última decisión Para comenzar con el método de resolución se debe decidir por qué clausula comenzar, siempre se debe comenzar de izquierda a derecha. La siguiente decisión consiste en elegir la cláusula que permite eliminar el literal de más a la derecha de la cláusula troncal. En el momento que no se puede continuar se debe volver “un paso atrás” y modificar la última decisión, escogiendo una nueva cláusula. Primera decisión

Replanteamiento última decisión

Se debe replantear la última decisión cuando: 1. No se puede continuar 2. Aparece un teorema 3. Se repite una cláusula ya existente en el árbol.

Conjunto de apoyo Esta estrategia consiste en comenzar la resolución con cláusulas de la negación de la conclusión. Permite llegar a la contradicción (si existe) lo más rápido posible. Se debe comenzar escogiendo la primer premisa del conjunto de apoyo, si no se puede avanzar se coge la siguiente y se repite hasta acabar con las premisas del conjunto de apoyo.

RESUMEN LÓGICA UOC

PÁGINA 10

JUAN OVELAR

RESUMEN LÓGICA UOC

Resultados Resolución Se pueden utilizar siempre las cláusulas resultantes que se generan en el árbol de resolución para encontrar la contradicción. S...