Álgebra y Geometría

Sección 1.1 Lógica Proposicional

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{.}\)

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.

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

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

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

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.

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.

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).\)

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

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

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

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.

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.