Lógica proposicional

Descargo de respnsabilidad

Este documento contiene mis notas personales tomadas durante las clases. Importante tener en cuenta que estas notas representan mi interpretación del material presentado y pueden contener errores o entendimientos parciales.

NO deben ser consideradas como una fuente definitiva o un reemplazo de los materiales de clase, las lecturas asignadas, o las explicaciones del profesor. Eres responsable de siempre verificar la información y consultar con el profesor si tienes alguna duda.

No me hago responsable de cualquier malentendido o error que pueda surgir de la lectura de estas notas.

Proposiciones

Una proposición es una oración declarativa o una expresión matemática que es verdadera o falsa pero no ambas. Ejemplo:

• “4 es un entero por”
• “15 $\le$ 15”
• “La solución de $2x-3=1$ es 2”
• “18 es múltiplo de 7” Ejemplo de expresiones que no son proposiciones:
• “73”
• "$2x-1=3$"
• ¿Cuál es la solución de $2x-3=1$?

Generalmente, para referirnos a proposiciones usamos las letras $P,Q,R,$ etc. Ejemplo:

• P: “26 es un entero par”
• Q: "$3+4=7$"

Las proposiciones pueden contener variables, por ejemplo, sea X un entero y consideremos:

• P: 2x +1 es un entero impar ⇒ P(x)

Conectivos lógicos

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

Podemos usar la palabra “y” para conectar las proposiciones y crear una nueva proposición. Por ejemplo, podemos conectar las proposiciones:

• P: El número 4 es un entero par.
• Q: El número 5 es un entero impar. Para formar:
• R: El número 4 es un entero par y el 5 es un entero impar.. En lógica usamos el símbolo "$\wedge$" (\land en LaTeX, del AND) en representación de la palabra “y”. La proposición nueva "$\wedge$" es verdadera si ambas proposiciones son verdaderas, en cualquier otro caso es falsa. Esto se resume en la siguiente “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 dos 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, por ejemplo: “El número 4 o el numero 3 es par”. Usamos el símbolo "$\vee$" (\lor en LaTeX, del OR) para la palabra “o”, lo que nos daría con el ejemplo anterior ”$4\vee 3$ es par”, su tabla de verdad asociada es la siguiente:

$P$	$Q$	$P\vee Q$
1	1	1
1	0	1
0	1	1
0	0	0
Otra manera de obtener nuevas proposiciones es usando la palabra “no”. Dada una proposición cualquiera $P$, podemos formar la nueva proposición “no es verdadero que P”, por ejemplo:
Si ”$P:$ El numero entero 3 es impar”, podemos formar “noP: No es verdadero que el numero 3 es impar”.

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

Se usa el símbolo "$\neg$" (\lnot en LaTeX, del NOT) para indicar la frase “no es verdadero que”; usando el ejemplo anterior sería: "$\neg P:3\equiv impar$" (ya veremos una mejor forma). Su tabla de verdad es la siguiente:

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

Proposiciones condicionales

Otra manera de conectar dos proposiciones es mediante el uso de condicionales. Dada dos proposiciones cualesquiera $P$ y $Q$, podemos formar la nueva proposición,

Equivalencia lógica

Dos proposiciones son logicamente equivalentes si sus valores de verdad coinciden linea por linea en la tabla de verdad y por tanto tienen el mismo significado. Por ejemplo, la proposición: $P⟺Q\equiv (P\wedge Q)\vee (\neg P\wedge \neg Q)$(la flecha doble sentido es \iff en LaTeX, significando $P\vee Q$ si y solo si $Q\vee P$, las dos tienen que ser verdaderas o falsas).

$P$	$Q$	$\neg P\neg Q$	$(P\wedge Q)$	$(\neg P\wedge \neg Q)$	$(P⟺Q)$	$(P\wedge Q)\vee (\neg P\wedge \neg Q)$
1	1	0
1	0	0
0	1	0
0	0	1

---

Bicondicional

Sean p y q dos proposiciones. Se define bicondicional de $p$ y $q$, a la proposición $⟺$ (que se lee si, y solo si $q$), cuya tabla de verdad es:

$P$	$Q$	$P⟺Q$	$(p$	$\to$	$q)$	$\wedge$	(q	$\to$	p)
1	1	1	1	1	1	1	1	1	1
1	0	0	1	0	0	0	0	1	1
0	1	1	0	1	1	0	1	0	0
0	0	1	0	1	0	1	0	1	0

Nótese que p ←> es equivalente a la proposición $(p\to q)$ ^ $(q\to p)$.

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$“². Otro ejemplo:

Definición 4: Dados dos enteros $a$ y $b$, si $b=a\ast c$ para algún entero $c$, decimos que $a$ divide a $b$, y escribimos $a|b$. En esta situación $a$ es un divisor de $b$ y $b$ es un múltiplo de $a$. ³

Definición 5: Decimos que un número natural $P$ es primo si sus únicos divisores positivos son $1$ y $P$. Ejemplo: $2,3,5,7,11,13,17,...$

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

Demostración directa

Una demostración directa, es la forma más natural de demostrar un teorema. Analizando la tabla de verdad para $P⟹Q$ vemos que si queremos demostrar el teorema $P⟹Q$ (equivalente a $P\wedge \neg (Q)$); es suficiente demostrar que $Q$ es verdadera siempre que $P$ lo sea.

$P$	$Q$	$P⟹Q$
1	1	1
1	0	0
0	1	1
0	0	1
Asi, en una demostración directa, asumimos que la hipótesis $P$ es verdadera y demostramos, usando argumentos lógicos, que $Q$ es verdadera.

Supongamos el esquema:

• Proposición: $P⟹Q$
  • Demostración: Supongamos $P$ ------⇒ en consecuencia $Q$.

Ejemplo:

• Proposición: Si $x$ es un número entero impar, entonces $x^2$ es un número entero impar.
• Demostración: Supongamos que $x$ es un entero impar (1). Por definición existe un entero $K+q$ (En orden)

$$\begin{array}{rlr}x& =2K+1;& \\ x^2& =(2K+1{)}^2=(2K{)}^2+4K+1.& \end{array}\text{\hspace{1em}(1)(2)}$$

Demostración por recíproca

Se usa para demostrar, al igual que la demostración directa, teoremas y proposiciones que tienen la forma $P⟹Q$. Esta forma de demostración se basa en el hecho de que $P⟹Q$ es lógicamente equivalente a $(\neg Q)⟹(\neg P)$, como se ve en la siguiente tabla.

P	Q	$\neg P$	$\neg Q$	$P⟹Q$	$(\neg Q)⟹(\neg P)$
1	1	0	0	1	1
1	0	0	1	0	0
0	1	1	0	1	1
0	0	1	1	1	1
Entonces, si queremos demostrar $P⟹Q$ por contra recíproca es suficiente demostrar $(\neg Q)⟹(\neg P)$ de manera directa.

Esquema:

• Proposición: $P⟹Q$
• Demostración: (por contrarecíproca) supongamos ($\neg Q$) $⟹$ en consecuencia ($\neg P$). ($(\neg Q)⟹(\neg P)$)

NOTA IMPORTANTE: Para poder entender esto bien es mejor seguirlo por instrucciones.

Ejemplo:

Proposición: Si $3x-1$ es par entonces $x$ es impar. Demostración (directa): Supongamos que $3x+1$ es par,

1. por definición, existe un entero $K$ tal que $3x+1=2K$,
2. así, restando $2x$ en ambos lados tenemos (por instrucciones):

$$\begin{array}{c}3x-1-2x=2K-2x\\ x-1=2(K-x)\\ x=2(K-x)+1\\ x=2K_2⟹K_2=K-x\end{array}$$

En consecuencia, $x$ es impar.

Demostración (por contrarecíproca): Supongamos que no es verdad que $x$ es impar. Entonces,

1. si $x$ es par, por definición, existe un entero $K$ tal que $x=2K$
2. ahora, $3x-1=3(2K)-1$, (se cambia $x$ por $2K$)

$$\begin{array}{c}2(3K)-1\\ 6K-1\\ 6K-2+2-1\\ 2(3K-1)+1\\ 2K_2+1donde{K}_2=3K-1\end{array}\text{\hspace{1em}([4])([5])}$$

^{4 5} (Por si no te has dado cuenta, lo que está en corchete es la nota del paso, en caso de no entenderla)

En consecuencia, $3x-1$ es un número impar en el que no es verdad que $3x-1$ es un número par.

Demostración por contradicción

Si queremos demostrar que una proposición $P$ es verdadera, una demostración por contradicción comienza suponiendo que $P$ es falsa, esto es, que $\neg P$ es verdadera, y finaliza deduciendo que, para una cierta proposición $C$, se tiene que $C\wedge (\neg C)$ es verdadera. Esto es una contradicción debido a que una proposición y su negación no pueden ser verdaderas. Esto es equivalente a mostrar que $P$ es verdadera, como se ve en la siguiente tabla:

$P$	$C$	$\neg P$	$\neg C$	$C\wedge \neg C$	$(\neg P)⟹(C\wedge \neg C)$
1	1	0	0	0	1
1	0	0	1	0	1
0	1	1	0	0	0
0	0	1	1	0	0
$P\equiv (\neg P)⟹(C\wedge \neg C)$
Así, para demostrar que $P$ es verdad, por contradicción, es suficiente con hacer una demostración directa para $P\equiv (\neg P)⟹(C\wedge \neg C)$.

Esquema:

• Proposición: $P$
• Demostración: (por contradicción) supongamos ($\neg P$) en consecuencia $C\wedge (\neg P)$

Ejemplo:

• 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.
• Proposición: El número $\sqrt{2}$ es irracional.
• Demostración: (por contradicción) Supongamos que no es verdad que $\sqrt{2}$ es irracional; entonces $\sqrt{2}$ es racional.
• Entonces (se indicará en paréntesis el paso):

$$\begin{array}{c}\sqrt{2}=\frac{a}{b},a,b\in \mathbb{Z},b\ne 0\\ ⟹mcd(a,b)=1\\ 2=\frac{a^2}{b^2}⟹a^2⟹2b^2\{I\}\end{array}\text{\hspace{1em}(1)(1.1)(2)}$$

$a^2$ es par $⟹$ a es par $⟹$ podemos hallar $K\in \mathbb{Z}$, tal que $a=2K\{II\}$. Sustituyendo:

$$\begin{array}{c}\{II\}=\{I\}⟹(2K{)}^2=2b^2\\ 4K^2=2b^2⟹2K^2=b^2\end{array}\text{\hspace{1em}(3)(4)}$$

así $b^2$ es par y por lo tanto $b$ es par. En conclusión $a$ y $b$ tienen a 2 como divisor común. y esto es una contradicción con el hecho de que $mcd(a,b)=1$.

Supongamos ahora que queremos demostrar $P⟹Q$ por el método de contradicción. Comenzamos suponiendo que $P⟹Q$ es falsa.

Conjeturas y contraejemplos

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”.

Ahora podemos tener proposiciones falsas, por ejemplo:

• Todos los números primos son impares

Casos Especiales de Proposición

Tautología:

$P$	$P\to P$
1	0
0	1

Contradicción:

$P$	$P\wedge \sim Q$
1	0
0	0
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.

Ejemplos:

1. $(p\to q)\equiv (\sim p\vee q)$ (Ley de la Condicional)

Ejercicio

2. Para cada condicional $p\to q$ (directa) tenemos las siguientes condicionales asociadas:

• Recíproca: $q\to p$
• Contraria: $\sim p\to \sim q$
• Contrareciproca: $\sim q\to \sim p$ Entonces, probar que $(p\to q)\equiv (\sim q\to \sim p)$.

Una formula que recibe el valor de verdad F (0) en CADA una de las filas de su tabla de verdad se dice que es una contradicción si, y sólo si ($⟺$), su negación es una tautologia. Ejemplos tenemos a $(P\wedge \neg P)$, $(\neg (Q\vee \neg Q))$.

Álgebra de Proposiciones o Cálculo Proposicional

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:
  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:
  • $\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:
  • $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$

Ilustraremos con un ejemplo como simplificar una fórmula del tipo $\neg \alpha$. Pero para hacerlo necesitamos la regla de sustitución…

Transitividad: Si $\alpha ⟺\beta$ y $\beta ⟺\delta$ entonces $\alpha ⟺\delta$.

Ejemplo: Consideremos la siguiente fórmula $\neg (P\to (Q\wedge R))$. Podemos transformarla usando las equivalencias y reglas de sustitución.

$$\begin{array}{c}P\to (Q\wedge R)\equiv \neg P\vee (P\vee Q)\\ \neg (P\to (Q\vee R))\equiv \\ \neg ((\neg P)\vee (Q\vee R))\equiv \neg (\neg P)\wedge \neg (Q\vee R)\\ \neg (\neg P)\equiv P\\ \neg (Q\vee R)⟺\neg Q\wedge \neg R\\ \neg (\neg P)\wedge \neg (Q\vee R)⟺P\wedge (\neg P\wedge \neg R)\\ (P\to (Q\wedge R))⟺\neg (\neg P)\wedge \neg (Q\vee R)\\ (P\to (Q\vee R))⟺P\wedge (\neg Q\wedge \neg R)\end{array}\text{\hspace{1em}(1)(2)(3)(4)(5)(6)(7)(8)}$$

Pero que instrucción es paso a paso?

1. Implicación
2. $S_1$ y línea 1
3. Se usan las leyes de DeMorgan
4. Doble negación
5. Se usan las leyes de DeMorgan
6. $S_2$ y líneas ($4$ y $5$)
7. Transitividad, usando linea ($2$, $3$ y $4$)
8. Transitividad, usando linea ($7$ y $6$)

Implicación Lógica

Definición: Diremos que $A$ implica $B$ ($A$ y $B$ dos proposiciones compuestas) si la condicional $A\to B$ es una tautología (”$A$ es verdadera siempre que $B$ lo sea”). En este caso se denota $A⟹B$.

Hay otras maneras de leer $A⟺B$:

1. $A$ es una consecuencia lógica de $B$.
2. $B$ es una condición suficiente de $A$.
3. $A$ es una condición necesaria para $B$.

Observación: $A⟹B$ significa que cualquier asignación de valores lógicos que hacen a $A$ verdadera, también hacen a $B$ verdadera.

Veamos ahora algunas implicaciones lógicas importantes:

Ejemplo

1. $P\Rightarrow (P\vee Q)$ (adición).
2. $(P\wedge Q)⟹P$ (simplificación)
3. $[P\wedge (P\to Q)]⟹Q$ Modus ponens
4. $[\neg Q\wedge (P\to Q)]⟹\neg P$ Modus tallens

Footnotes

1. En esta nota trataremos verdadero y falso en unos y ceros ($V=1$ y $F=0$) ↩

2. 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). ↩

3. Su ejemplo: 12 es múltiplo de 3 porque $12=3\ast 4$. También se puede decir que 3 es un divisor de 12 porque $3\ast 4=12$ ↩

4. ¿De dónde sale $-2+2$? Preguntate, cuánto es eso? 0. Estamos sumando 0 básicamente, lo hacemos más implícito. ↩

5. Se factoriza 6K - 2. ↩