[skip-to-content]

Sección 1.1 Lógica Proposicional

Subsección 1.1.1 Proposiciones y Conectivos Lógicos

En un intento por sistematizar el razonamiento matemático, surge el concepto de Lógica Proposicional. Como su nombre lo explícita, trabajaremos con proposiciones lógicas; las cuales poseen un valor de verdad (verdadero o falso). Por convención, las denotaremos con letras minusculas. Por ejemplo; \(p,q,r,s\text{.}\)

Son ejemplo de proposiciones lógicas:
  1. \(p:\) El gato es café.
  2. \(q:\) 3 es un número primo.
  3. \(r:\) 18 es múltiplo de 3 y múltiplo de 6.
  4. \(s:\pi < e\text{.}\)

Estas proposiciones tienen un valor de verdad. En particular, \(p,q,r\) son verdaderas mientras que \(s\) es falsa.

No son ejemplos de proposiciones lógicas:
  1. \(p: \) ¿Qué hora es?
  2. \(q: \) Borra la pizarra.
  3. \(r: \) Tengo sueño.
  4. \(s: \pi + e\text{.}\)

Existen proposiciones simples y compuestas. En el Ejemplo 1.1.1, \(p,q,s\) son proposiciones simples, mientras que \(r\) es compuesta.

Las proposciones compuestas están formadas por más de una proposición simple, las cuales están unidas a través de conectivos lógicos.

La proposición \(p:\) Puerto Montt es una ciudad de Chile y Montevideo es una ciudad de Uruguay es una proposición compuesta.

Esta formada por dos proposiciones simples: \(q:\) Puerto Montt es una ciudad de Chile y \(r:\) Montevideo es una ciudad de Uruguay; las cuales están unidas por el conectivo lógico "y".

Definición 1.1.4.
(Negación): Sea \(p\) una proposición lógica. La negación de \(p\) se denota \(\overline{p}\) y toma el valor de verdad contrario a \(p\text{.}\)
Si \(p:\) Ushuaia es una ciudad de Argentina, su negación es \(\overline{p}:\) Ushuaia no es una ciudad de Argentina.
Si \(q:e < \pi\) entonces su negación es \(\overline{q}:\pi \le e\text{.}\)

El Ejemplo 1.1.3 nos permite introducir los conectivos lógicos.

Definición 1.1.7.
(Conectivos Lógicos) Se definen los conectivos lógicos:
  1. \(\land\text{:}\) Conjunción ("y")
  2. \(\lor\text{:}\) Disyunción ("o").
  3. \(\veebar: \) Disyunción Exclusiva ("o bien").
  4. \(\Rightarrow: \) Implicancia ("entonces").
  5. \(\Leftrightarrow: \) Equivalencia ("si y sólo si").
Definición 1.1.8.
(Tablas de Verdad) Una Tabla de Verdad representa los valores de verdad que puede tomar una proposición compuesta, en función de todos los posibles valores de verdad de las proposiciones simples que componen esta última.
La Tabla de Verdad de la Negación (Definición 1.1.4) corresponde a
\(p\) \(\overline{p}\)
V F
F V

A partir de las Tablas de Verdad, estudiaremos los Conectivos Lógicos dados en la Definición 1.1.7.

Definición 1.1.11.
(Conjunción, "y lógico") Dados \(p,q\text{;}\) dos proposiciones lógicas, se construye su conjunción como \((p \land q)\text{.}\) Se lee: \(p\) y \(q\text{.}\)

\((p \land q)\) es verdadera si \(p\) y \(q\) son simultaneamente verdaderas. En los demás casos, es falsa. La conjunción posee la tabla de verdad

\(p\) \(q\) \((p \land q)\)
V V V
V F F
F V F
F F F
Definición 1.1.13.
(Disyunción, "o lógico") Dados \(p,q\text{;}\) dos proposiciones lógicas, se construye su disyunción como \((p \lor q)\text{.}\) Se lee: \(p\) o \(q\text{.}\)

\((p \lor q)\) es falsa si \(p\) y \(q\) son simultaneamente falsas. En los demás casos, es verdadera. La disyunción posee la tabla de verdad

\(p\) \(q\) \((p \lor q)\)
V V V
V F V
F V V
F F F
Definición 1.1.15.
(Disyunción Exclusiva, "o bien") Dados \(p,q\text{;}\) dos proposiciones lógicas, se construye su disyunción exclusiva como \((p \veebar q)\text{.}\) Se lee: \(p\) o bien \(q\text{.}\)

\((p \veebar q)\) es falsa si \(p\) y \(q\) tienen el mismo valor de verdad. En caso contrario, es verdadera. La disyunción exclusiva posee la tabla de verdad

\(p\) \(q\) \((p \veebar q)\)
V V F
V F V
F V V
F F F
Definición 1.1.17.
(Implicancia, "entonces") Dados \(p,q\text{;}\) dos proposiciones lógicas, se construye su implicancia como \((p \Rightarrow q)\text{.}\) Se lee: \(p\) entonces \(q\text{.}\)

\((p \Rightarrow q)\) es falsa si \(q\) es falsa. En los demás casos, es verdadera. La implicancia posee la tabla de verdad

\(p\) \(q\) \((p \Rightarrow q)\)
V V V
V F F
F V V
F F V

La implicancia "verdadero implica falso" es falso será muy útil en muchas demostraciones de este curso; las cuales serán realizadas por contradicción (o reducción al absurdo).

Definición 1.1.19.
(Equivalencia, "si y sólo si") Dados \(p,q\text{;}\) dos proposiciones lógicas, se construye su equivalencia como \((p \Leftrightarrow q)\text{.}\) Se lee: \(p\) si y sólo si \(q\text{.}\)

\((p \Leftrightarrow q)\) es verdadera si \(p\) y \(q\) tienen el mismo valor de verdad. En caso contrario, es falsa. La equivalencia posee la tabla de verdad

\(p\) \(q\) \((p \Leftrightarrow q)\)
V V V
V F F
F V F
F F V

Subsección 1.1.2 Tautologías

En lo que sigue, buscaremos métodos que nos permitan demostrar que una determinada proposición compuesta es verdadera.

Cuando una proposición compuesta es verdadera, se denomina tautología. Si es falsa, se dice que es una contradicción.

Para verificar si una proposición compuesta es tautología, existen tres métodos que revisaremos a continuación:

  1. Tablas de Verdad.
  2. Álgebra de Proposiciones (mediante Tautologías Notables).
  3. Método Directo.
  4. Método Indirecto (Exploración, Contradicción, Contrarrecíproco).

Método 1 (Tablas de Verdad): Este método consiste en descomponer una proposición compuesta mediante proposiciones simples, explorando todos sus posibles valores de verdad.

Se probará mediante Tablas de Verdad que \(p \Rightarrow (p \lor q)\) es una tautología. En efecto, construyamos la tabla de verdad
\(p\) \(q\) \((p \lor q)\) \(\left[ p \Rightarrow (p \lor q)\right]\)
V V V V
V F V V
F V V V
F F F V

Como todos los casos posibles son verdaderos, entonces \(p \Rightarrow (p \lor q)\) es una tautología.

Este método no es complejo. Sin embargo, puede resultar tedioso si se trabajan con más de tres proposiciones (pues se tendrán ocho casos). Es por eso, que exploraremos un segundo método que resulta ser expedito y elegante: Álgebra de Proposiciones.

Usando Tablas de Verdad; pruebe que si \(p,q,\) son proposiciones lógicas, entonces \((p \land q) \land (\overline{p} \lor \overline{q})\) es una tautología.

Método 2 (Álgebra de Proposiciones): Considere las siguientes Tautologías Notables (las cuales se demuestran mediante tablas de verdad), para probar que una determinada proposicion compuesta es tautología. Sean \(p,q,r\text{;}\) proposiciones lógicas.

  1. Involución: \(\overline{\overline{p}}\Leftrightarrow p.\)
  2. Conmutatividad: \(p \lor q \Leftrightarrow q \lor p\) y \(p \land q \Leftrightarrow q \land p.\)
  3. Asociatividad: \((p \lor q)\lor r \Leftrightarrow p \lor (q \lor r)\) y \((p \land q)\land r \Leftrightarrow p \land (q \land r).\)
  4. Distribuitividad: \((p \lor q)\land r \Leftrightarrow (p \land r) \lor (q \land r)\) y \((p \land q)\lor r \Leftrightarrow (p \lor r) \land (q \lor r).\)
  5. Idempotencia: \((p \lor p) \Leftrightarrow p\) y \((p \land p) \Leftrightarrow p .\)
  6. Identidad: \((p \lor F) \Leftrightarrow p\text{,}\) \((p \lor V) \Leftrightarrow V\text{,}\) \((p \land F) \Leftrightarrow F\)y \((p \land V) \Leftrightarrow p.\)
  7. Complemento: \(\overline{V} \Leftrightarrow F\text{,}\) \(\overline{F} \Leftrightarrow V\text{,}\) \(p\lor \overline{p} \Leftrightarrow V\) y \(p\land \overline{p} \Leftrightarrow F\text{.}\)
  8. Leyes de De Morgan: \(\overline{(p \lor q)} \Leftrightarrow \overline{p} \land \overline{q}\) y \(\overline{(p \land q)} \Leftrightarrow \overline{p} \lor \overline{q}.\)
  9. Absorción: \((p \vee q) \wedge q \Leftrightarrow q\) y \((p \wedge q) \vee q \Leftrightarrow q.\)
  10. Simetría de la Equivalencia: \((p \Leftrightarrow q) \Leftrightarrow (q \Leftrightarrow p).\)
  11. Caracterización de la Implicancia: \((p\Rightarrow q) \Leftrightarrow \overline{p} \vee q.\)
  12. Caracterización de la Equivalencia: \((p \Leftrightarrow q) \Leftrightarrow [(p\Rightarrow q) \wedge (q\Rightarrow p)].\)
  13. Contrarrecíproco: \((p \Rightarrow q) \Leftrightarrow (\overline{q} \Rightarrow \overline{p}).\)
  14. Transitividad: \([(p\Rightarrow q) \wedge (q\Rightarrow r)] \Rightarrow (p\Rightarrow r)\) y \([(p\Leftrightarrow q) \wedge (q\Leftrightarrow r)] \Rightarrow (p\Leftrightarrow r).\)
Mediante Álgebra de Proposiciones, probaremos que \((p \land q) \Rightarrow p\) es una tautología. En efecto
\begin{align*} (p \land q) \Rightarrow p \amp \Leftrightarrow (\overline{p\land q}) \lor p\\ \amp \Leftrightarrow (\overline{p} \lor \overline{q}) \lor p\\ \amp \Leftrightarrow (\overline{q} \lor \overline{p}) \lor p\\ \amp \Leftrightarrow \overline{p} \lor (\overline{p} \lor p)\\ \amp \Leftrightarrow \overline{p} \lor V\\ \amp \Leftrightarrow V \end{align*}
Mediante Álgebra de Proposiciones, probaremos \((p \Rightarrow q) \Leftrightarrow (\overline{q} \Rightarrow \overline{p}).\) En efecto
\begin{align*} (p \Rightarrow q) \Rightarrow p \amp \Leftrightarrow \overline{p}\lor q\\ \amp \Leftrightarrow q\lor \overline{p}\\ \amp \Leftrightarrow \overline{\overline{q}} \lor \overline{p}\\ \amp \Leftrightarrow (\overline{q} \Rightarrow \overline{p}) \end{align*}
Sean \(p,q,r\text{;}\) proposiciones lógicas. Pruebe que \((p\Leftrightarrow q) \Leftrightarrow [\bar{p} \wedge \bar{q}] \vee (p \wedge q).\)

Método 3 (Directo): Sean \(p,q\text{;}\) dos proposiciones lógicas. El método directo se basa en verificar que \(p \Rightarrow q\) es verdadera. Por lo tanto, \(p\) se asume verdadero (hipótesis) y se debe demostrar que \(q\) también lo es (tesis).

Indique la hipótesis, tesis y demostración de la afirmación: Si \(a\) es un número entero entonces \(3\cdot a\) también es un número entero.

Estamos en presencia del método directo y la implicancia \(p \Rightarrow q\text{.}\) En efecto,

\begin{equation*} \text{Hipótesis} \ \ \ p: a \in \mathbb{Z} \end{equation*}
\begin{equation*} \text{Tesis} \ \ \ q: 3\cdot a \in \mathbb{Z} \end{equation*}

Por otro lado, \(\mathbb{Z}\) es cerrado bajo producto (la multiplicación de dos enteros es entero). Finalmente, ya que \(3 \in \mathbb{Z}\) y \(a \in \mathbb{Z}\) (por hipótesis, es verdadero) entonces \(3\cdot a \in \mathbb{Z}.\)

Finalmente, revisaremos el Método Indirecto. Este será clave a la hora de realizar demostraciones en Matemática.

Método 4 (Indirecto): Estudiaremos tres formas de demostrar que una proposición compuesta es una tautología. Exploración, Contradicción y Contrarrecíproco.

Exploración: Este método recurrirá al uso de Tablas de Verdad, descartando los casos "sencillos" en una proposición compuesta. Una aplicación de este mecánismo está dado por el Ejemplo 1.1.28

Probaremos que \((p \Rightarrow \overline{q}) \wedge (r \Rightarrow q) \Rightarrow (p \Rightarrow \overline{r})\) es una tautología mediante Exploración. Asumiremos que \(p \Rightarrow q \land r \Rightarrow q\) es verdadero (se descartará el caso en que esta proposición compuesta es falsa). Por consiguiente, probaremos que \(p \Rightarrow \overline{r}\) también es verdadera. Tendremos dos posibles casos
  1. \(p\) es falsa: Este caso es sencillo, ya que de la definición de implicancia se consigue inmediatamente que \(F\Rightarrow r\) es verdadera.
  2. \(p\) es verdadera: Como asumimos que \(p \Rightarrow q\) es verdadera, se sigue que \(q\) es falso. Como \(r \Rightarrow q\) también es verdadera, \(r\) es falso (ya que \(q\) también lo es). Por consiguiente, ya que \(r\) es falso, entonces \(p\Rightarrow r\) es verdadera.
Como los dos posibles casos permiten concluir que \(p \Rightarrow \overline{r}\) es verdadera, entonces \((p \Rightarrow \overline{q}) \wedge (r \Rightarrow q) \Rightarrow (p \Rightarrow \overline{r})\) es una tautología.

Contradicción (o Reducción al Absurdo): Este método está basado en la implicancia \(p \Rightarrow q\text{.}\) La estructura de esta técnica está dada por

\begin{equation*} \left[(p \Rightarrow q)\Leftrightarrow V)\right] \Leftrightarrow \left[(p\wedge \overline{q}) \Leftrightarrow F \right]\text{.} \end{equation*}

Es decir; para demostrar que \(p\Rightarrow q\text{,}\) basta considerar que \(\overline{q}\) es verdadero (junto con la hipótesis \(p\)). Esto implica obtener una inconsistencia. Por consiguiente, la única opción válida es que \(\overline{q}\) sea falsa. Así, \(q\) es verdadero. Esto permite concluir que \(p \Rightarrow q\) es una tautología.

Las demostraciones por contradicción juegan un rol importante dentro de la Matemática. Serán empleadas recurrentemente en los capítulos siguientes.

Probaremos que si \(t\in \mathbb{R}\text{,}\) entonces \(\left| \sin(t)\right| \le 1\) mediante contradicción.

La negación de \(\left| \sin(t)\right| \le 1\) es \(1 < \left| \sin(t)\right|\text{;}\) la cual se asume verdadero. Elevando al cuadrado (y empleando la propiedad \(\left| a\right|^{2}=a^{2}\text{,}\) para todo \(a\in \mathbb{R}\)), se consigue \(1 < \sin^{2}(t)\text{.}\)

Por otro lado, para todo \(t\in \mathbb{R}\) se obtiene que \(\cos^{2}(t) \ge 0\) y \(\sin^{2}(t)+\cos^{2}(t)=1\) (Identidad Trigonométrica Fundamental). Así, \(1 < \sin^{2}(t)+\cos^{2}(t)\text{.}\) Pero esto no es posible, ya que contradice la Identidad Trigonométrica Fundamental. Por lo tanto, si \(t\in \mathbb{R}\text{,}\) entonces \(\left| \sin(t)\right| \le 1\text{.}\)

Usando contradicción, pruebe que \((p\land q )\Rightarrow p\) es una tautología.

Contrarrecíproco: Este método esta basado en la tautología \((p \Rightarrow q) \Leftrightarrow (\overline{q} \Rightarrow \overline{p}).\)

Las demostraciones por contrarrecíproco juegan un rol importante dentro de la Matemática. Serán empleadas recurrentemente en los capítulos siguientes.

Probaremos que si \(m^{2}\) es un número entero par entonces \(m\) también es un número entero par mediante contrarrecíproco. Usaremos la tautología \((p \Rightarrow q) \Leftrightarrow (\overline{q} \Rightarrow \overline{p}).\) Definamos
\begin{equation*} p: m^{2} \\ \text{es un número entero par} \end{equation*}
\begin{equation*} q: m \\ \text{es un número entero par} \end{equation*}

Por lo tanto

\begin{equation*} \overline{q}: m \\ \text{es un número entero impar} \end{equation*}
\begin{equation*} \overline{p}: m^{2} \\ \text{es un número entero impar} \end{equation*}

Como \(\overline{q}\) es nuestra hipótesis (y se debe probar que \(m^{2}\) es un número entero impar), entonces existe \(k \in \mathbb{Z}\) tal que \(m=2k+1\text{.}\) Elevando al cuadrado y reordenando, se logra \(m^{2}=2t+1\) (con \(t=2k^{2}+2k \in \mathbb{Z}\)). Por lo tanto, \(m^{2}\) es un número entero impar. Finalmente, por contrarrecíproco; queda demostrado que si \(m^{2}\) es un número entero par entonces \(m\) también es un número entero par.