Repaso desde Lógica Proposicional hasta Teoría de Conjuntos

Esta nota todavía está en construcción.

Esta nota es un esbozo y por lo tanto incompleta. Ampliandola ayudarás a mejorar esta página.

Esta nota tiene como bonus aprender Lean. Más información abajo.

Sabemos que la Lógica es la disposición natural de los seres humanos para pensar de forma coherente. Es una estructura del pensamiento que permite verificar si un razonamiento es correcto o incorrecto.

La proposición

Una proposición es una oración declarativa o una expresión matemática que es de tipo booleano o lógico: verdadero o falso, pero no puede ser ambas a la vez.

Por ejemplo:

• “El hielo es caliente”. (Es una proposición, aunque sea Falsa).
• “3 es mayor que 1”. (Es una proposición, y es Verdadera).

Entonces, que NO es proposición:

• “¿Qué hora es?” (Las preguntas no son ni verdaderas ni falsas).
• “¡Siéntate!” (Las órdenes tampoco).
• “x + 2 = 5” (No sabemos cuánto vale “x”, así que no podemos decir si es verdad o mentira todavía).

Y entonces… Para qué Lean?

Nota

Estas secciones son opcionales, no es necesario usar Lean para aprender desde Lógica Proposicional hasta Teoría de Conjuntos pero es recomendable para poder verificar demostraciones (y poder hacerlas.)

Distinguiremos las secciones de Lean como: “En Lean”.

Lean básicamente es un lenguaje de programación de código abierto creado por Leonardo de Moura en Microsoft Research en 2013 (que rápido pasa el tiempo, no?). Lo que hace especial a este lenguaje es que es un asistente de demostraciones (o probador de teoremas dependiendo del idioma); en pocas palabras tu le dices que demostrar y como demostrar y te dice si es posible o no posible usando una sintaxis $\text{semi-}\text{LATEX}$ (te suena de algo?).

En este caso, podemos ver que 2 + 2 es verdadero, y del tipo de los "Nat"urales.

Para poder usar Lean se recomienda instalar Visual Studio Code, aunque también puedes usar la playground.

Si has instalado Lean en Visual Studio Code, y creado un proyecto en Lean con el nombre Repaso, te debería salir una estructura de directorio de la siguiente manera:

Repaso/
	Basic.lean
Main.lean
Repaso.lean

Por ahora, ignora Main.lean y crea un nuevo archivo llamado Logica.lean, con el siguente código:

-- 1. Definimos las variables P y Q como Proposiciones:
variable (P Q : Prop)
 
-- 2. Le pedimos a Lean que verifique *qué* son estas expresiones:
#print "Conectivos:" -- Imprime "Conectivos:"
#check P ∧ Q  -- Conjunción (Y)
#check P ∨ Q  -- Disyunción (O)
#check ¬P     -- Negación (No)

Verás que a la derecha se te abre una columna, llamada Lean Infoview (aparece también en el playground).

Retornaremos pronto a esto pero lo que necesitas saber es que en Lean todo tiene un “tipo” (como una etiqueta). Las Proposiciones tienen el tipo Prop (“Prop”osiciones). Por ejemplo, si escribimos 2 + 2 = 4 tal que en la imagen anterior, Lean reconoce que esto es algo que puede probarse (un Prop) y le asigna un resultado o tipo esperado (Nat, de los números naturales, $\mathbb{N}$)

Conectivos lógicos

Sabemos que al identificar una proposición, podemos darle un Valor de Verdad (o valor booleano si estás en computación), lo cual es simple:

• Si la proposición coincide con la realidad → Verdadero/V (o 1).
• Si no coincide → Falso/F (o 0).

La palabra “y”, AND ($\wedge$, conyunción)

Podemos usar la palabra “y” para conectar las proposiciones y crear una nueva proposición, sean esas proposiciones verdaderas o falsas. El resultado de esta conexión solo será verdad si ambas son verdad, de lo contrario será falsa:

• $P\wedge Q$ significa ”$P$ y $Q$“.
• En Lean: Se escribe ∧ (\and también funciona en el editor).

Para resumir todos los posibles casos, usamos lo que se llama una Tabla de Verdad:

$P$	$Q$	$P\wedge Q$
1	1	1
1	0	0
0	1	0
0	0	0

La palabra “o”, OR ($\vee$, disyunción)

También podemos conectar proposiciones usando la palabra “o”. Dada dos proposiciones cualquiera $P$ y $Q$, la afirmación ”$P$ o $Q$”, significa que una o ambas proposiciones son verdaderas; solo es falsa si ambas son falsas.

• $P\vee Q$ significa ”$P$ o $Q$“.
• En Lean: Se escribe ∨ (\or también funciona en el editor).

Resumiendo todos los casos posibles:

$P$	$Q$	$P\vee Q$
1	1	1
1	0	1
0	1	1
0	0	0

La palabra “no”, NOT ($\neg$, negación)

En cambio, la palabra “no” invierte el valor de verdad de la proposición.

• Si $P$ es “Está lloviendo” (V), entonces $\neg P$ es “No está lloviendo” (F).
• En Lean: Se escribe ¬ (\not también funciona en el editor).

Viendo los casos en una Tabla de Verdad:

$P$	$\neg P$
0	1
1	0

En Lean (Parte 1)

Aquí viene algo interesante de Lean.

• En papel, escribimos “2 + 2 = 5” y decimos “Tiene un Valor de Verdad, falso”.
• En Lean, escribimos 2 + 2 = 5 y Lean dice: “Vale, esto es una Proposición (Prop), es una frase válida gramaticalmente”.
• Sin embargo, si intentas demostrarla (crear un teorema), Lean te detendrá y dirá: “¡Alto! No puedo encontrar una prueba para esto”.

En Lean, distinguirás entre enunciar algo (escribir la frase) y demostrarlo (probar que es verdad).

Ahora, retornando al código anterior, para ver su “resultado” tendrás una columna llamada Lean InfoView. Normalmente en Visual Studio Code se abre sola a la derecha, tal como se ve en la imagen:

Si no te aparece, haz clic en el ícono de Lean (el $\forall$) y presiona Toggle Lean InfoView o presiona Ctrl+Shift+Enter.

Ahora coloca el cursor del texto (no el del mouse) en la línea que dice #check P ∧ Q, al final de esa línea. Si has hecho todo al pie de la letra, verás que en el InfoView te aparece lo siguiente:

Nos afirma que $P\wedge Q$ es una Proposición. Y ahora, si ponemos el cursor en Q, veremos que nos da un tipo esperado, otra proposición:

Así se entiende y se verifica un tipo en Lean.

La implicación ($⟹$)

Se escribe $P⟹Q$ y se lee “Si $P$, entonces $Q$” o "". Importante saber que:

• $P$ es el antecedente (La condición).
• $Q$ es el consecuente (La conclusión).

Esta proposición SOLO ES FALSA cuando la condición $P$ se cumple pero la conclusión $Q$ es falsa. En todos los otros casos, es verdadera.

Por ejemplo, supongamos que nuestra proposición es una promesa: “Si sacas 20 en el examen ($P$), te compro un auto ($Q$)“.

1. Sacas 20 (V) y te compro el auto (V) → V.
2. Sacas 20 (V) y NO te compro el auto (F) → F.
3. No sacas 20 (F).
   • Aquí viene lo curioso: Si no sacas 20, yo no estoy obligado a nada. Si te compro el auto o no, no he roto mi promesa. Por tanto, la implicación sigue siendo Verdadera.

Resumido en la siguiente tabla de verdad:

$P$	$Q$	$P⟹Q$
1	1	1
1	0	0
0	1	1
0	0	1

La Bicondicional ($⟺$)

El “si y solo si”, agarra dos proposiciones: $P⟺Q$, Lo cual se leería como ”$P$ si y solo si $Q$“. Esto indica que las dos son Verdaderas si y solo si, ambas proposiciones tienen el mismo valor de verdad.

Por ejemplo, si P y Q son verdaderas la proposición resultante es Verdadera, si P y Q son falsas la proposición resultante es Verdadera; es decir tienen el mismo valor de verdad de forma que la proposición resultante da el valor Verdadero.

En cambio, si ambos tienen diferente valor de verdad, entonces la proposición resultante da el valor de verdad Falso.

Visto en la siguiente tabla de verdad:

$P$	$Q$	$P⟺Q$
1	1	1
1	0	0
0	1	0
0	0	1

Una equivalencia lógica ($\equiv$) es entonces, es una relación entre dos proposiciones, no un operador/conectivo. Por ejemplo, se dice que $P\equiv Q$ cuando la columna de $P⟺Q$ está llena de valores de verdad V. (es decir, es una tautología, ya se verá más tarde).

Casos especiales: Tautología

Casos especiales: Contradicción

Las proposiciones que no sean ni tautologías ni contradicciones las llamamos Contingentes. También una equivalencia lógica $P\equiv Q$ puede entenderse como una tautología.

En Lean (Parte 2)

En el mismo archivo Logica.lean, agrega lo siguiente:

#check P -> Q -- Implicación (Si P entonces Q)
#check P <-> Q -- Bicondicional
#eval false <-> true -- Ejemplo de un bicondicional

PD: Lean entiende que el -> es una flecha →. No te preocupes por ello.

Revisa ahora la entrada.

Luego veremos cómo verificar si una proposición es verdadera o falsa.

Definiciones y demostraciones

Definición

Una definición es una explicación exacta y sin ambigüedad del significado de un término o frase matemática. Daremos algunos ejemplos, aunque asumiremos que todos están familiarizados con los números naturales: $\mathbb{N}=\{1,2,3,4,...\}$y los números enteros.. $\mathbb{Z}=\{...,-3,-2,-1,0,1,2,3,...\}$Ejemplos:

• Definición 1: Un entero $n$ es par si existe un entero $K$, tal que $n=2K$. Ejemplo…
• Definición 2: Un número entero $n$ es impar si existe un entero $K$ tal que $n=2K+1$. Ejemplo…
• Definición 3: Dos proposiciones compuestas $P$ y $Q$ son lógicamente equivalentes si y sólo si sus tablas de verdad coinciden en todos los casos posibles. Ejemplo…

Cómo se puede observar, las definiciones se suelen expresar como proposiciones condicionales, aunque lo más adecuado sería expresarlas como proposiciones bicondicionales. Es decir la definición 1, debería ser técnicamente: “un número entero $n$ es par si, y sólo si, existe un entero $K$, tal que $n=2K$” ¹.

Teorema

Un teorema es una proposición matemática que es verdadera y puede ser (y ha sido) verificada como verdadera; los teoremas usualmente son proposiciones condicionales del tipo $P⟹Q$, aunque el enunciado o proposición a veces oculta este hecho.

Ejemplo:

Proposición: Las soluciones de la ecuación $a{x}^2+bx+c=0$ son:

$$x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$$

Proposición: Si $x$ es una solución de la ecuación $a{x}^2+bx+c=0$, entonces la ecuación sería $x=\frac{-b\pm \sqrt{b^2-4ac}}{2a}$.

Las dos proposiciones dicen lo mismo pero la segunda muestra el hecho de que es una proposición condicional.

Cuando un teorema se expresa como una proposición condicional $P⟹Q$, la proposición $P$ se llama hipótesis y la proposición $Q$ se llama tesis. También hay teoremas que simplemente son proposiciones, ejemplo: “Existen infinitos números primos”.

Demostración

Una demostración de un teorema es una verificación escrito que muestra que el teorema es verdadero. Consiste de una sucesión de afirmaciones $(1),(2),...,(n)$, tales que cada afirmación tiene una o más razones que justifican su validez, que pueden ser hipótesis, definiciones, afirmaciones anteriores en la demostración o proposiciones matemáticas ya demostradas y la última afirmación $(n)$, es la tesis que queremos demostrar.

En las demostraciones se usan atajos llamados Reglas de Inferencia:

Reglas de Inferencia

Modus Ponens (MP)

Supongamos que tenemos una premisa (proposición) $P⟹Q$: “Si ocurre $P$, entonces ocurre $Q$“. Entonces se dice que $P⟹Q$ es verdadera y que la condición ($P$) se cumplió, por lo tanto la consecuencia ($Q$) TIENE que haberse cumplido.

Modus Tollens (MT)

Esta es una ley de negación del consecuente o ley de contraposición: En cambio si tenemos $P⟹Q$ y $Q$ no se cumple ($\neg Q$), entonces $P$ no se cumple. “Por lo tanto, no $P$“.

Silogismo hipotetico

También es una forma de argumento valido en el que consiste en un silogismo con una sentencia condicional para una o ambas de sus proposiciones. Tenemos las dos proposiciones:

• $P⟹Q$
• $Q⟹R$

Por lo tanto $P⟹R$. Por ejemplo:

• $P$: Estudio mucho.
• $Q$: Aprobé el parcial.
• $R$: Me dan el titulo.

Si sabemos que $P⟹Q$ (Si estudio mucho, aprobaré el parcial) y $Q⟹R$ (Si apruebo el examen, me darán el titulo), por lo tanto $P⟹R$ (Si estudio mucho, me darán el titulo).

Silogismo disyuntivo

También es otra forma de argumento valido en el que consiste también en un silogismo con una sentencia condicional pero que una de sus condiciones es falsa. Por ejemplo, tenemos 2 proposiciones:

• $P$: El postre es helado.
• $Q$: El postre es pastel. Sabemos que:
• El postre es helado o pastel ($P\vee Q$).
• El postre NO es helado. ($\neg P$).

Por lo tanto, el postre es Pastel ($Q$).

Tipos de demostraciones

Demostración directa

Esta es la forma natural de demostrar un teorema, se usa casi siempre para probar una implicación del tipo “Si $P$, entonces $Q$” ($P⟹Q$); es suficiente demostrar que $Q$ es verdadera siempre que $P$ lo sea usando nuestras reglas de inferencia.

Por ejemplo:

Supongamos el esquema:

• Proposiciones:
  • $P⟹Q$
  • $Q⟹R$
• Queremos demostrar $P⟹R$.
• Demostración:
  • Supongamos que tenemos $P$ y $P$ es verdadero. entonces, por consiguiente $Q$ es verdadera; usaremos la segunda proposición y si $R$ es verdadera, entonces, **por definición, $P$ implica $R$.

Demostración por contrarrecíproca

Esta ley dice que $P⟹Q$ es idéntica a $\neg Q⟹\neg P$. Entonces, si quieres probar $P⟹Q$, puedes probar que al negar el consecuente, se niega obligatoriamente el antecedente.

Por ejemplo:

Supongamos el esquema:

• Proposiciones:
  • $P$: Es un pez
  • $Q$: Sabe nadar
• Queremos demostrar $P⟹Q$.
• Demostración:
  • Supongamos que no es verdad ($\neg Q$) que sabe nadar. En consecuencia, es un pez. En el que no es verdad que es un pez ($\neg P$). (usando MT)
• En resumen:
  1. $P⟹Q$ Premisa (Dato que ya sabíamos)
  2. $\neg Q$ Hipótesis Auxiliar (la suposición)
  3. $\neg P$ Modus Tollens entre 1) y 2)

Demostración por recíproca

La estructura es, idéntica a la contrarrecíproca ($Q⟹P$), pero no es un método de demostración para la implicación original ($Q⟹P$) . Por ello, se usa más a la hora de demostrar bicondicionales: $P⟺Q\to P⟹Q\equiv Q⟹P$ Por ejemplo:

Supongamos el esquema:

• Proposiciones:
  • $P$: Un número entero $n$ es par.
  • $Q$: $n+1$ es impar
• Queremos demostrar $P⟺Q$.
• Demostración:
  • Sabemos que si $n$ es par, entonces $n+1$ es impar.
  • Por definición, existe un entero $K$ impar, tal que $n+1=2K+1$.
  • Restando $-1$ en ambos lados (usando teclas), tenemos: $n=2K$.
  • En consecuencia, $n$ es par.

Demostración por contradicción (o Reducción al absurdo)

Si queremos demostrar que $P$ es verdad, empezamos suponiendo que $\neg P$ es verdadera, y que esa suposición lleva a una contradicción (para una proposición $C$, se tiene que $C\wedge (\neg C)$ es verdadera, por lo tanto, se contradice).

Por ejemplo:

Supongamos el esquema:

• Proposiciones:
  • $P$: $\sqrt{2}$ es un número irracional.
• Queremos demostrar $P$.
• Definición: Un número racional es un número real de la forma $\frac{a}{b}$, donde $a$ y $b$ son enteros, y $b\ne 0$. Un número irracional es un número real que no es racional, es decir no puede ser expresado de la forma $\frac{a}{b}$.
• Demostración:
  • Suponemos que no es verdad que $\sqrt{2}$ es un número irracional (es decir, asumimos que es un número racional).
    • Entonces, por definición sabemos que $\sqrt{2}=\frac{a}{b}$ y sabemos que $a,b$ pertenecen a los enteros ($\mathbb{Z}$), y que $b\ne 0$.
    • Primero nos tendríamos que deshacer de la raíz cuadrada, por lo cual elevamos la otra parte (usando teclas) al cuadrado, tal que: $2=\frac{a^2}{b^2}$. Debemos entonces encontrar una contradicción. Hay que despejar $a^2$ y $b^2$, por lo tanto dividimos 2 en ambos lados (usando teclas).
    • Lo cual nos quedaría $\frac{a^2}{2b^2}$ y tenemos que ahora despejar $b$ (usando teclas), lo cual nos quedaría que $a^2=2b^2\{\text{I}\}$.
  • Aquí es donde volvemos entonces a la definición de par: $n=2K$. Tenemos lo mismo en esa ecuación $\{\text{I}\}$: $a^2$ es par, y por lo tanto, $a\ast a$ siempre será un numero par, es decir $a$ es par.
  • Aquí entonces, podemos hallar un entero $K\in \mathbb{Z}$ tal que $a=2K\{\text{II}\}$, ya tenemos nuestra segunda ecuación.
    • Remplazamos $\{\text{I}\}$ con $\{\text{II}\}$: $(2K{)}^2=2b^2$.
    • Simplificando la ecuación obtenida: $4K^2=2b^2$ y dividiendo ambos lados de la ecuación obtenemos $2K^2=b^2$.
  • Tenemos un descubrimiento clave: $b^2$ es par también. Ahora sabemos que $a,b$ son pares. Recordando la hipótesis, sabemos que $\sqrt{2}=\frac{a}{b}$ (no se puede simplificar la fracción, es racional), y una de las características es que estos pares tienen como 2 a divisor común, por lo que la fracción se puede simplificar más, y, por consecuente, la suposición de $\sqrt{2}$ ser un número racional es falsa.
  • Por lo tanto, $\sqrt{2}$ es un número irracional.

Demostración por contraejemplo

Antes de continuar, debemos de saber que las conjeturas son proposiciones cuya verdad o falsedad aún no ha sido verificada, pero hay indicios de que son verdaderas. Ejemplo: La conjetura de Goldbach: “Cualquier número entero par mayor que 2 es la suma de 2 primos”.

Por ello, un contraejemplo es el método más rápido para demostrar que una proposición universal (“Para todo…”, “Todos los…”, “Siempre…”) es falsa. Solo se necesita un caso donde la afirmación no se cumple.

Por ejemplo:

Supongamos el esquema:

• Proposición: “Para todo número real $x$, si $x>2$, entonces $x^2>4x$“.
• El punto: Buscar un número que cumpla el antecedente ($x>2$) pero no el consecuente ($x^2>4x$, es decir se debe cumplir que $x^2\le 4x$).
• Demostración:
  • Obtenemos un número par 4 la cual cumple el antecedente ($4>2$).
  • Si hacemos $4^2=16$ vemos que $16\ngtr 4\cdot 4$. (Cuidado con esa concha de mango, pudiera ser verdadero SI $17>16$.)

Algebra de Proposiciones

Una Ley Proposicional es una fórmula que siempre resulta en una Equivalencia Lógica (es decir, el bicondicional entre ambos lados es una tautología).

A través de las equivalencias lógicas es posible transformar las fórmulas y, en algunos casos, obtener extensiones más simples. Algunas equivalencias lógicas importantes:

• Doble negación:
  1. $\neg (\neg P)\equiv P$
• Leyes Independientes:
  1. $(p\vee p)\equiv p$
  2. $(p\wedge p)\equiv p$
• Leyes Asociativas:
  1. $(p\vee p)\vee r\equiv p\vee (q\vee r)$
  2. $(p\wedge p)\wedge r\equiv p\wedge (q\wedge r)$
• Leyes Conmutativas:
  1. $(p\wedge q)\equiv (q\wedge p)$
  2. $(p\vee q)\equiv (q\vee p)$
• Leyes Distributivas: Permiten “multiplicar” un conector sobre una suma/resta lógica.
  1. $p\vee (q\wedge r)\equiv (p\vee q)\wedge (p\vee r)$
  2. $p\wedge (q\vee r)\equiv (p\wedge q)\vee (p\wedge r)$
• Leyes de Identidad o Elemento Neutro: $p\vee 0\equiv p$, $p\wedge 1\equiv p$
• Leyes de Dominación: $p\vee 1\equiv 1$, $p\wedge 0\equiv 0$
• Leyes de Complementación:
  1. $p\vee \sim p\equiv 1$. (Tercer Excluido)
  2. $p\wedge \sim p\equiv 0$. (Contradicción)
  3. $\sim (\sim p)\equiv 0$. (Doble negación) $0\sim 1\equiv 0$, $\sim 0\equiv 1$
• Leyes de DeMorgan: Estas leyes te permiten “distribuir” la negación dentro de un paréntesis, pero al hacerlo, obligan al conector a cambiar.
  • $\sim (p\vee q)\equiv \sim p\wedge \sim q$
  • $\sim (p\wedge q)\equiv \sim p\vee \sim q$
• Contra positiva o contra recíproca
  • $P\to Q\equiv \neg P\to \neg Q$
• Implicación
  • $P\to Q⟺\neg P\vee \neg Q$
• Ley del Condicional
  • $P\to Q\equiv (\neg P\vee Q)$
• Ley de la Absorción: Estas leyes son los atajos más útiles para simplificar rápidamente. Ocurren cuando tienes una variable afuera y esa misma variable está adentro con el conector opuesto.
  • $P\wedge (P\vee Q)\equiv P$
  • $P\vee (P\wedge Q)\equiv P$
  • $\neg P\vee (P\wedge Q)\equiv \neg P\wedge Q$

Otras propiedades importantes de la equivalencias lógica son las reglas de sustitución. Sean $\alpha ,\beta ,\delta$ y $\gamma$ formulas.

Suponga que $\alpha ⟺\beta$ y $\delta ⟺\gamma$ entonces:

Reglas de sustitución… $S_1$) $\neg \alpha ⟺\neg \beta$ $S_2$) $\delta \wedge \alpha ⟺\gamma \wedge \beta$ $S_3$) $\delta \vee \alpha ⟺\gamma \vee \beta$

$\stackrel{\text{Hola! Puto de mierda}}{\to }$

Implicación Lógica

Teoría de conjuntos

Footnotes

1. En términos matemáticos, una Definición es una proposición bicondicional en la que se suele omitir el “solo si” del “si y solo si” (por eso técnicamente). ↩