Tema 1: Intro de la Lógica - Apuntes PDF

**Tema 1: Intro de la lógica** **--** **La Ley del tercio excluido**: una sentencia denota un hecho del mundo (real o ficticio) sobre el cual sólo podemos decir que es cierto o falso ,estos son los dos únicos estados en los que puede estar. **El Principio de no contradicción**: un hecho del mundo...

**Tema 1: Intro de la lógica** **--** **La Ley del tercio excluido**: una sentencia denota un hecho del mundo (real o ficticio) sobre el cual sólo podemos decir que es cierto o falso ,estos son los dos únicos estados en los que puede estar. **El Principio de no contradicción**: un hecho del mundo y su contrario no pueden suceder al mismo tiempo. ¿Qué es la lógica? Tipo test examen **Tema 2: Lógica proposicional** **Asignación**: es una función (v) que le da a cada fórmula atómica un valor de verdad (en relación con los hechos que denotan o referencian). **Evaluación**: es el valor de verdad de una fórmula compuesta, que se obtiene a partir de la evaluación de los componentes de su estructura sintáctica según la prioridad de las conectivas y las sucesivas anidaciones. Las fbfs pueden ser **Válidas/tautologías**: verdaderas (V) para todas sus interpretaciones. ** Contingentes**: verdaderas (V) para algunas interpretaciones y falsas (F) para otras ** Falseables:** que tiene al menos una interpretación evaluada como falsa (F). ** Satisfacible**: si resultan verdaderas (V) para al menos una interpretación. ** Contradicción/insatisfacible**: falsas (F) para todas sus interpretaciones. **[Decibilidad y Satisafacibilidad]**. Si a un conjunto insatisfacible de fbfs se le añade una fbf, aunque sea una tautología, sigue siendo insatisfacible. Si a un conjunto insatisfacible de fbfs se le suprime una fbf, este nuevo conjunto puede volverse satisfacible. Un conjunto defbfs que contenga una fbf contradicción es un conjunto insatisfacible Un conjunto insatisfacible puede estar formado por fbfs satisfacibles Si la oración α es una TAUTOLOGÍA entonces la oración α no puede ser FALSEABLE. Y viceversa. Si una oración es una TAUTOLOGÍA, entonces dicha oración es SATISFACIBLE. Pero no viceversa. Si una oración es INSATISFACIBLE, será una oración FALSEABLE. Pero no viceversa. Si α es INSATISFACIBLE, entones noα es una TAUTOLOGÍA Hemos dicho anteriormente que una fbf verdadera en todas sus interpretaciones (todos sus mundos posibles) es una fbf semánticamente válida. También hemos dicho que a ese tipo de fbf se la llama tautología. Las dos tautologías más importantes son la equivalencia lógica y la implicación lógica. La equivalencia lógica es útil para sustituir o intercambiar fbfs en el proceso de razonamiento (la interdefinibilidad de las conectivas de los estoicos) La implicación lógica es útil como esquema de razonamiento válido. Así, la estructura lógica del mundo tal como la interpretamos, es igual a la estructura lógica de nuestro lenguaje. **Tema 3 : Razonamientos** - **[Razonamiento Lógico:]** \- Un razonamiento es **válido** si la conclusión se sigue lógicamente de las premisas. \- Para comprobar la validez, se puede hacer: \- **Directamente**: Ver si la oración completa es siempre verdadera (tautología). \- **Por refutación**: Ver si negar la conclusión junto con las premisas lleva a una contradicción. - **[Sistema Deductivo:]** \- Está compuesto por: \- **Premisas**: Afirmaciones que se aceptan al principio. -**Reglas de inferencia**: Esquemas que permiten derivar nuevas afirmaciones a partir de las anteriores. \- **Una demostración** es una secuencia de pasos que utiliza las reglas de inferencia para llegar a una conclusión. - **[Solidez y Completitud:]** \- Un sistema deductivo es **sólido** cuando todo lo que se puede demostrar es también verdadero en términos lógicos. \- Es **completo** cuando todo lo que es verdadero en términos lógicos se puede demostrar en el sistema. - **[Consistencia y Decidibilidad:]** \- Una **teoría** es un conjunto de fórmulas que es cerrado bajo demostraciones, es decir, contiene todas las conclusiones que se pueden deducir de sus axiomas. \- Una teoría es **consistente** si no permite demostrar una afirmación y su negación al mismo tiempo. \- Un sistema es **decidible** si existen métodos para determinar si una teoría es consistente o inconsistente. Es **semidecidible** si se puede determinar la inconsistencia, pero no siempre la consistencia. Un sistema es **indecibible** si y solo si no es posible determinar la inconsistencia, ni la consistencia. **¿Cómo pasar a oración FNC?** - Eliminar todos los operadores binarios salvo v y ( v invertida). Para ello aplicamos estas reglas de LO - Aplicar D'Morgan para reducir alcance de las negaciones: - Eliminar las negaciones múltiples aplicando **idempotencia: nonoalpha=Alpha** - Aplicar **distributividad:** - Reducir paréntesis:  - Eliminar información redundante - Eliminar literales opuestos - Eliminar constantes  - Eliminar literales iguales - Quedarnos con expresiones subsumidas  **Tema 4: Problemas SAT en L0** **[¿Cómo hacer un Tableaux Semántico?]** **No necesito FNC** **Reglas Alpha y beta** **[¿Cómo hacer DPLL?]** El **algoritmo DPLL** (Davis-Putnam-Logemann-Loveland) es un método utilizado para resolver el **problema de la satisfacibilidad booleana (SAT)**, es decir, busca determinar si una fórmula lógica en forma normal conjuntiva (FNC) es satisfacible o insatisfacible. A continuación te explico cómo funciona DPLL paso a paso. **Resumen del Algoritmo DPLL** El algoritmo DPLL combina varias técnicas para decidir la satisfacibilidad de una fórmula lógica: 1. **Regla de la tautología**: Eliminar cláusulas que contienen literales complementarios. 2. **Regla de la propagación unitaria**: Si una cláusula tiene un solo literal, se asigna el valor que lo hace verdadero. 3. **Regla del literal puro**: Si un literal aparece en una fórmula pero nunca aparece su negación, se le asigna el valor que lo hace verdadero. 4. **Regla de ramificación**: Si no se puede hacer más, el algoritmo elige un literal arbitrario, lo propaga y sigue resolviendo. **Paso a paso del algoritmo DPLL** Supongamos que tenemos el siguiente conjunto de cláusulas: φ={{p,q},{¬p,r},{r,¬q},{¬r}}\\varphi = \\{\\{p, q\\}, \\{\\neg p, r\\}, \\{r, \\neg q\\}, \\{\\neg r\\}\\}φ={{p,q},{¬p,r},{r,¬q},{¬r}} La fórmula está en **Forma Normal Conjuntiva** (FNC), es decir, es una conjunción de disyunciones. **1. Eliminación de cláusulas tautológicas** Primero, se eliminan las cláusulas que contienen literales complementarios, como {p,¬p}\\{p, \\neg p\\}{p,¬p}, ya que estas siempre son verdaderas. En este ejemplo no hay cláusulas tautológicas, por lo que no eliminamos ninguna cláusula. **2. Propagación unitaria** Buscamos cláusulas unitarias, es decir, aquellas con un solo literal. Aquí tenemos {¬r}\\{\\neg r\\}{¬r}, que es una cláusula unitaria. Esto significa que podemos asignar **falso** a rrr (porque ¬r\\neg r¬r debe ser verdadero). - Asignamos r=Fr = Fr=F. - Eliminamos todas las cláusulas que contienen rrr (porque al ser r=Fr = Fr=F, esas cláusulas se satisfacen). Esto elimina la cláusula {¬p,r}\\{\\neg p, r\\}{¬p,r}. - En las cláusulas donde aparece ¬r\\neg r¬r, quitamos el literal ¬r\\neg r¬r (porque ¬r\\neg r¬r ya es verdadero). Esto elimina ¬r\\neg r¬r de la cláusula {r,¬q}\\{r, \\neg q\\}{r,¬q}, dejándonos con {¬q}\\{\\neg q\\}{¬q}. El conjunto de cláusulas ahora es: φ′={{p,q},{¬q}}\\varphi\' = \\{\\{p, q\\}, \\{\\neg q\\}\\}φ′={{p,q},{¬q}} **3. Regla del literal puro** Un literal puro es un literal que aparece siempre con el mismo signo en todas las cláusulas, sin su negación. En este caso, ppp es un literal puro porque aparece solo como ppp y nunca como ¬p\\neg p¬p. Por lo tanto, podemos asignar p=Vp = Vp=V (verdadero). - Asignamos p=Vp = Vp=V. - Eliminamos las cláusulas que contienen ppp porque ya están satisfechas. Esto elimina la cláusula {p,q}\\{p, q\\}{p,q}. El conjunto de cláusulas ahora es: φ′′={{¬q}}\\varphi\'\' = \\{\\{\\neg q\\}\\}φ′′={{¬q}} **4. Propagación unitaria de nuevo** Ahora, tenemos la cláusula unitaria {¬q}\\{\\neg q\\}{¬q}, lo que nos obliga a asignar q=Fq = Fq=F (falso). - Asignamos q=Fq = Fq=F. - No quedan más cláusulas por eliminar. Como hemos asignado valores a todas las variables y no nos quedan cláusulas insatisfacibles, podemos concluir que la fórmula **es satisfacible** con la asignación: p=V,r=F,q=Fp = V, r = F, q = Fp=V,r=F,q=F **Resumen de los pasos en DPLL:** 1. **Buscar cláusulas unitarias** y asignar los valores que las hagan verdaderas. 2. **Eliminar cláusulas satisfechas** y **reducir otras** eliminando literales satisfechos. 3. **Asignar valores a literales puros**. 4. Si no queda nada más por hacer, seleccionar un literal arbitrario y ramificar (probar con valores **verdadero** o **falso**). 5. Si llegamos a una contradicción (la cláusula vacía □\\square□), retroceder y probar la otra opción. 6. Si se pueden asignar valores a todos los literales sin contradicciones, la fórmula es satisfacible. **Ejemplo de ejecución:** 1. **Cláusula unitaria**: ¬r→r=F\\neg r \\rightarrow r = F¬r→r=F. 2. **Literal puro**: p→p=Vp \\rightarrow p = Vp→p=V. 3. **Cláusula unitaria**: ¬q→q=F\\neg q \\rightarrow q = F¬q→q=F. Con esta asignación, la fórmula es satisfacible. Si hubiéramos encontrado una contradicción en alguno de los pasos, habríamos intentado la **otra rama** en la ramificación (backtracking)