Apuntes de Lógica para Inteligencia Artificial

Lógica

Introducción a la Lógica

• La lógica es la teoría del pensar, la ciencia de las reglas y los límites del pensar justo y razonado.

• Se define como el estudio del razonamiento.

• En construcciones lingüísticas, establece conexiones entre enunciados.

• La lógica proposicional se manifiesta en la vida cotidiana.

• El estudio de la inferencia es crucial para razonar correctamente y evitar falacias argumentativas.

Lógica Proposicional

Definición

• Un enunciado lógico o proposición lógica es una afirmación con un valor de verdad: verdadero (1) o falso (0).

• Ejemplos:

  • "2 + 2 = 4" tiene valor de verdad 1.

  • "4 > 5" tiene valor de verdad 0.

  • La conjetura de Goldbach: "todo número par mayor que 2 se puede escribir como la suma de dos números primos" tiene un valor de verdad (aún no determinado).

  • "La mesa de Antonio" no es una proposición lógica.

Clasificación de Proposiciones

• Según su valor de verdad, las proposiciones se clasifican en:

  • Tautología: Siempre es cierta. Ejemplo: "5 es un número primo".

  • Contradicción: Siempre es falsa. Ejemplo: "La cantidad de números enteros es finita".

  • Contingencia: Puede ser verdadera o falsa, dependiendo del contexto. Ejemplo: "Ayer llovió".

Problema Recreativo

• Un explorador prisionero debe hacer una declaración para decidir si será asado o hervido.

• Si la proposición es verdadera, será hervido; si es falsa, será asado.

• El explorador dice: "Yo seré asado".

• Este escenario plantea una paradoja: si los caníbales creen que es verdad, deben hervirlo, pero si lo hierven, su declaración sería falsa. Si creen que es falso, deben asarlo, pero si lo asan, su declaración sería verdadera.

Ejemplos de Clasificación

• Ejemplos de proposiciones y su clasificación:

  • "Mañana salgo de casa ó tal vez no" - Contingencia.

  • "Todos los estudiantes de bachillerato en España hablan Ruso" - Contradicción.

  • $4 \geq 10$ - Contradicción.

  • "Hoy es Jueves" - Contingencia (depende del día).

  • $\pi$ es un número irracional" - Tautología.

  • "Lancé una moneda y salió cara" - Contingencia.

Conectores Lógicos

• Son términos que enlazan dos proposiciones para formar una nueva, cuyo valor de verdad depende de las proposiciones originales y del conector.

• Los conectores lógicos son:

  • Conjunción: $\land$, "y".

  • Disyunción: $\lor$, "o".

  • Disyunción Exclusiva: $\veebar$, "o…o".

  • Negación: $\sim$, $\neg$, "No".

  • Condicional: $\Rightarrow$. "Si… entonces".

  • Bicondicional: $\Leftrightarrow$. "Si y solo si".

Conjunción

• Dados dos enunciados lógicos p y q, la conjunción $p \land q$ (p y q) es verdadera solo si ambos p y q son verdaderos.

• Ejemplo:

  • p: Valencia pertenece a la Comunidad de Valencia (Verdadero).

  • q: Alicante pertenece a la Comunidad de Valencia (Verdadero).

  • r: Alicante pertenece a la provincia de Valencia (Falso).

  • $p \land q$ es Verdadero.

  • $p \land r$ es Falso.

• Tabla de verdad:

  p	q	p $\land$ q
  1	1	1
  1	0	0
  0	1	0
  0	0	0

• El conector $\land$ se puede identificar con la operación ".", producto.

Disyunción

• Dados dos enunciados lógicos p y q, la disyunción $p \lor q$ (p o q) es verdadera si al menos uno de los dos (o ambos) es verdadero.

• Ejemplo:

  • p: Valencia pertenece a la Comunidad de Valencia (Verdadero).

  • q: Alicante pertenece a la Comunidad de Valencia (Verdadero).

  • r: Alicante pertenece a la provincia de Valencia (Falso).

  • $p \lor q$ es Verdadero.

  • $p \lor r$ es Verdadero.

• Tabla de verdad:

  p	q	p $\lor$ q
  1	1	1
  1	0	1
  0	1	1
  0	0	0

• El conector $\lor$ se puede identificar con la operación "+", suma.

Disyunción Exclusiva

• Dados dos enunciados lógicos p y q, la disyunción exclusiva $p \veebar q$ (o p o q) es verdadera solo si exactamente uno de los dos es verdadero.

• Ejemplo:

  • p: Valencia pertenece a la Comunidad de Valencia (Verdadero).

  • q: Alicante pertenece a la Comunidad de Valencia (Verdadero).

  • r: Alicante pertenece a la provincia de Valencia (Falso).

  • $p \veebar q$ es Falso.

  • $p \veebar r$ es Verdadero.

• Tabla de verdad:

  p	q	p $\veebar$ q
  1	1	0
  1	0	1
  0	1	1
  0	0	0

Implicación Lógica (Condicional)

• Dados dos enunciados lógicos p y q, la implicación lógica $p \rightarrow q$ (p implica q) es verdadera a menos que p sea verdadera y q sea falsa.

• Establece una relación de causalidad: si p es verdad, entonces q debe ser verdad.

• Ejemplo: Un padre promete a su hijo: "Si apruebas el curso de Estructuras te llevo a Ibiza". El padre rompe la promesa solo si el hijo aprueba el curso y no lo lleva a Ibiza.

• Tabla de verdad:

  p	q	p $\rightarrow$ q
  1	1	1
  1	0	0
  0	1	1
  0	0	1

Implicaciones en Matemáticas

• En matemáticas, las proposiciones condicionales toman la forma:

  • Hipótesis $\rightarrow$ tesis.

  • Suficiente $\rightarrow$ Necesario.

• Ejemplos:

  • Si una función es derivable entonces es continua.

  • La figura es un cuadrado solo si es un rectángulo.

  • Una condición necesaria para que la figura sea un rectángulo es que sea un cuadrilátero.

  • Que la figura sea un cuadrado es una condición suficiente para que la figura sea un cuadrilatero.

Equivalencia, Bicondicional o Implicación Doble

• Dados dos enunciados lógicos p y q, la equivalencia $p \leftrightarrow q$ (p si y sólo si q) es verdadera si ambos p y q tienen el mismo valor de verdad.

• Si p es verdad, entonces q es verdad, y viceversa.

• Ejemplo:

  • P: 4 es un número impar (Falso).

  • Q: 1 + 1 = 3 (Falso).

  • $P \leftrightarrow Q$ es Verdadera.

• Ejemplo:

  • P: t es un número par.

  • Q: t + 2 es un número par.

  • $P \leftrightarrow Q$ es Verdadera.

• La proposición $P \leftrightarrow Q$ es equivalente a $(P \rightarrow Q) \land (Q \rightarrow P)$.

• Tabla de verdad:

  p	q	p $\leftrightarrow$ q
  1	1	1
  1	0	0
  0	1	0
  0	0	1

Negación Lógica

• Dado un enunciado lógico p, la negación $\neg p$ (no p) invierte el valor de verdad de p.

• Tabla de verdad:

  p	$\neg p$
  1	0
  0	1

• La negación de un enunciado p, además de $\neg p$, también puede denotarse por $\overline{p}$.

Fórmulas Lógicas

• Una fórmula lógica $F(p<em>1, p</em>2, …, p_k)$ consiste en una serie de enunciados lógicos conectados por conectores lógicos.

• Según su valor de verdad, puede ser:

  • Tautológica: Siempre verdadera.

  • Contradictoria: Siempre falsa.

  • Contingente: A veces verdadera, a veces falsa.

Ejemplos de Fórmulas Lógicas

• $p \lor \overline{p}$ es una tautología.

• $p \land \overline{p}$ es una contradicción.

• $p$ es contingente.

• $p \rightarrow p$ es una tautología.

• $\overline{p} \rightarrow p$ es contingente.

• $p \land q$ es contingente.

• $p \leftrightarrow \overline{p}$ es una contradicción.

• $(p \land q) \rightarrow (p \lor q)$ es una tautología.

• $(p \lor q) \rightarrow (p \land q)$ es contingente.

• $\overline{p} \leftrightarrow p$ es una contradicción.

Equivalencia de Fórmulas Lógicas

• Dos fórmulas lógicas son equivalentes si tienen el mismo valor de verdad para cualquier combinación de valores de las proposiciones que las integran.

• Ejemplo: $p \rightarrow q$ es equivalente a $\overline{p} \lor q$:

  p	q	p $\rightarrow$ q	$\overline{p}$	$\overline{p} \lor q$
  1	1	1	0	1
  1	0	0	0	0
  0	1	1	1	1
  0	0	1	1	1

Ejercicio

• Probar que $p \rightarrow q$ no es equivalente a su recíproco $(q \rightarrow p)$, pero sí que es equivalente a su contra-recíproco $(\overline{q} \rightarrow \overline{p} )$.

  p	q	p $\rightarrow$ q	$\overline{q}$	$\overline{q}$	$\overline{q} \rightarrow \overline{p}$
  1	1	1	0	0	1
  1	0	0	1	0	0
  0	1	1	0	1	1
  0	0	1	1	1	1

Propiedades de la Lógica Proposicional

• Asociatividad:

  • $p \land (q \land r) = (p \land q) \land r$, $p \lor (q \lor r) = (p \lor q) \lor r$

• Conmutatividad:

  • $p \land q = q \land p$, $p \lor q = q \lor p$

• Distributividad:

  • $p \land (q \lor r) = (p \land q) \lor (p \land r)$, $p \lor (q \land r) = (p \lor q) \land (p \lor r)$

• Complemento:

  • $p \land \overline{p} = 0$, $p \lor \overline{p} = 1$

• Identidad:

  • $p \land 0 = 0$, $p \lor 1 = 1$

  • $p \land 1 = p$, $p \lor 0 = p$

• Idempotencia:

  • $p \land p = p$, $p \lor p = p$

• Absorción:

  • $p \land (p \lor q) = p$, $p \lor (p \land q) = p$

• Involución:

  • $\overline{ \overline{p}} = p$

• Leyes de De Morgan:

  • $\overline{p \land q} = \overline{p} \lor \overline{q}$

  • $\overline{p \lor q} = \overline{p} \land \overline{q}$

Teoría de Conjuntos

Definición

• Un conjunto es una colección de objetos físicos o abstractos.

• Cada objeto es un elemento.

• Si A es un conjunto, $a \in A$ significa "a es un elemento de A" o "a pertenece a A".

• Los conjuntos se denotan entre llaves, separando elementos con comas.

Ejemplos

• Planetas del sistema solar: {Mercurio, Venus, Tierra, Marte, Júpiter, Saturno, Urano, Neptuno, Plutón}.

• Números naturales impares: {1, 3, 5, 7, 9, 11, …} = ${2n - 1 | n \in N }$.

• Pares de puntos sobre la parábola: $A = {(x, x^2) : x \in R }$

Cardinalidad

• El cardinal de un conjunto es el número de elementos que posee, denotado por $|A|$.

• Si un conjunto A tiene infinitos elementos, $|A| = \infty$.

• Ejemplos:

  • A = {planetas del sistema solar}, entonces $|A| = 9$.

  • B = {números naturales impares}, entonces $|B| = \infty$.

Propiedades de Conjuntos

• Cada elemento debe aparecer una única vez. Ejemplo: {a, b, c, c, d, a} es incorrecto; lo correcto es {a, b, c, d}.

• El conjunto vacío no tiene elementos y se denota por $\emptyset$.

• Ejemplo: A = {satélites de Venus}, entonces $A = \emptyset$.

Álgebra de Boole

Introducción

• El álgebra de Boole es fundamental en computación.

• Sus propiedades son base para el diseño de computadoras digitales, especialmente las binarias.

Definición

• Un Álgebra de Boole es una estructura algebraica formada por un conjunto B (con al menos dos elementos distintos: 0 y 1), dos operaciones binarias ($\lor$ y $\land$), y una operación unitaria ($\sim$, complemento).

• Propiedades para elementos p, q, r $\in$ B:

  1. Conmutatividad: $p \land q = q \land p$, $p \lor q = q \lor p$

  2. Asociatividad: $p \land (q \land r) = (p \land q) \land r$, $p \lor (q \lor r) = (p \lor q) \lor r$

  3. Distributividad: $p \land (q \lor r) = (p \land q) \lor (p \land r)$, $p \lor (q \land r) = (p \lor q) \land (p \lor r)$

  4. Identidad: $p \land 0 = 0$, $p \lor 1 = 1$

  5. Neutro: $p \land 1 = p$, $p \lor 0 = p$

  6. Complemento: $\forall p \in B, \exists \overline{p} \in B$:

     • $p \land \overline{p} = 0$

     • $p \lor \overline{p} = 1$

Ejemplo

• El Conjunto B = {0, 1}, dotado de las operaciones . (AND) y + (OR), donde:

  +	0	1
  0	0	1
  1	1	1

  , $\overline{0} = 1, \overline{1} = 0$

  .	0	1
  0	0	0
  1	0	1

• (B, +, .) es un álgebra de Boole.

Lógica de Predicados

• Algunas afirmaciones lógicas tienen una estructura más compleja.

• La lógica proposicional es limitada en estos casos.

• La lógica de primer orden analiza enunciados con predicados.

• Ejemplos:

  • x < 4.

  • Para todo entero x, si x es múltiplo de 4 entonces x es par.

  • Todos los planetas tienen una órbita elíptica.

  • Existe un entero z tal que z = z + 1.

  • Si x $\in$ Z, entonces x $\in$ N.