Equivalencias e implicaciones lógicas
En la sección de lógica de proposiciones vimos la definición de equivalencia lógica. La definición se puede extender a fórmulas de primer orden, pero la formalización de esto es más complicada. Sin embargo, es posible mantener la idea intuitiva de que dos fórmulas son equivalentes si tienen el mismo valor de verdad y \(\beta\) es consecuencia lógica de \(\alpha\) si siempre que \(\alpha\) es verdadera, \(\beta\) también lo es.
Para verificar que las fórmulas proposicionales que afirmamos son equivalentes, o que una es una consecuencia lógica de otra, podemos usar tablas de verdad. En el caso de fórmulas de primer orden no dimos un método que nos permitiera verificar esto de manera sistemática. En cualquier caso se puede usar Lean para verificarlo. Ya hemos escrito la verificación de las equivalencias e implicaciones lógicas que daremos a continuación.
Equivalencias lógicas
Daremos la lista de equivalencias dando un nombre para que sea más fácil de recordar y referirse a ellas. La lista no es exhaustiva, pero sí contiene las más comunes.
Conjunciones y disyunciones
Tanto la conjunción (\(\land\)) como la disyunción (\(\lor\)) son conmutativas
\[\alpha\land\beta \equiv \beta\land\alpha \quad\text{y}\quad \alpha\lor\beta \equiv \beta\lor\alpha\]Estas equivalencias se pueden usar para mostrar que la intersección y la unión de conjuntos son conmutativas:
Ejercicio: Demuestra que \(A\cap B=B\cap A\).
Solución
\[\begin{align*} x \in A\cap B & \iff x\in A \land x\in B && \text{def de } \cap\\ & \iff x\in B \land x\in A && \land\text{ es conmutativo}\\ & \iff x\in B\cap A && \text{def de } \cap \end{align*}\]Ejercicio: Demuestra que \(A\cup B=B\cup A\).
Solución
\[\begin{align*} x \in A\cup B & \iff x\in A \lor x\in B && \text{def de } \cup\\ & \iff x\in B \lor x\in A && \lor\text{ es conmutativo}\\ & \iff x\in B\cup A && \text{def de } \cup \end{align*}\]La conjunción y la disyunción son asociativas
\[\alpha\land(\beta\land\gamma)\equiv(\alpha\land\beta)\land\gamma \quad\text{y}\quad \alpha\lor(\beta\lor\gamma)\equiv(\alpha\lor\beta)\lor\gamma\]Ahora podemos demostrar que la intersección y la unión son asociativas.
Ejercicio: \(A\cap(B\cap C)=(A\cap B)\cap C\)
Solución
\[\begin{align*} x\in A\cap(B\cap C) &\iff x\in A \land x\in B\cap C && \text{def de }\cap\\ & \iff x\in A \land (x\in B\land x\in C) && \text{def de }\cap\\ & \iff (x\in A\land x\in B)\land x\in C && \land\text{ es asociativo}\\ & \iff x\in A\cap B \land x\in C && \text{def de }\cap\\ & \iff x\in (A\cap B)\cap C && \text{def de }\cap \end{align*}\]Ejercicio: \(A\cup(B\cup C)=(A\cup B)\cup C\)
Solución
\[\begin{align*} x\in A\cup(B\cup C) &\iff x\in A \lor x\in B\cup C && \text{def de }\cup\\ & \iff x\in A \lor (x\in B\lor x\in C) && \text{def de }\cup\\ & \iff (x\in A\lor x\in B)\lor x\in C && \lor\text{ es asociativo}\\ & \iff x\in A\cup B \lor x\in C && \text{def de }\cup\\ & \iff x\in (A\cup B)\cup C && \text{def de }\cup \end{align*}\]La conjunción y la disyunción son distributivas
\[\alpha\land(\beta\lor\gamma)\equiv(\alpha\land\beta)\lor(\alpha\land\gamma) \quad\text{y}\quad \alpha\lor(\beta\land\gamma)\equiv(\alpha\lor\beta)\land(\alpha\lor\gamma)\]Estas equivalencias se pueden usar para demostrar que la intersección y la unión son distributivas.
Ejercicio: \(A\cap(B\cup C)=(A\cap B)\cup(A\cap C)\)
Solución
\[\begin{align*} x\in A\cap(B\cup C) &\iff x\in A \land x\in B\cup C && \text{def de }\cap\\ & \iff x\in A \land (x\in B\lor x\in C) && \text{def de }\cup\\ & \iff (x\in A\land x\in B)\lor(x\in A\land x\in C) && \land\text{ y }\lor\text{ son distributivas}\\ & \iff x\in A\cap B \lor x\in A\cap C && \text{def de }\cap\\ & \iff x\in (A\cap B)\cup(A\cap C) && \text{def de }\cup \end{align*}\]Ejercicio: \(A\cup(B\cap C)=(A\cup B)\cap(A\cup C)\)
Solución
\[\begin{align*} x\in A\cup(B\cap C) &\iff x\in A \lor x\in B\cap C && \text{def de }\cup\\ & \iff x\in A \lor (x\in B\land x\in C) && \text{def de }\cap\\ & \iff (x\in A\lor x\in B)\land(x\in A\lor x\in C) && \lor\text{ y }\land\text{ son distributivas}\\ & \iff x\in A\cup B \land x\in A\cup C && \text{def de }\cup\\ & \iff x\in (A\cup B)\cap(A\cup C) && \text{def de }\cap \end{align*}\]La conjunción y la disyunción son idempotentes
\[\alpha\land\alpha\equiv\alpha \quad\text{y}\quad \alpha\lor\alpha\equiv\alpha\]Ejercicio: \(A\cap A=A\)
Solución
\[\begin{align*} x\in A\cap A &\iff x\in A \land x\in A && \text{def de }\cap\\ & \iff x\in A && \land\text{ es idempotente} \end{align*}\]Ejercicio: \(A\cup A=A\)
Solución
\[\begin{align*} x\in A\cup A &\iff x\in A \lor x\in A && \text{def de }\cup\\ & \iff x\in A && \lor\text{ es idempotente} \end{align*}\]La conjunción y la disyunción son absorbentes
\[\alpha\land(\alpha\lor\beta)\equiv\alpha \quad\text{y}\quad \alpha\lor(\alpha\land\beta)\equiv\alpha\]Ejercicio: \(A\cap(A\cup B)=A\)
Solución
\[\begin{align*} x\in A\cap(A\cup B) &\iff x\in A \land x\in A\cup B && \text{def de }\cap\\ & \iff x\in A \land (x\in A\lor x\in B) && \text{def de }\cup\\ & \iff x\in A && \text{absorción} \end{align*}\]Ejercicio: \(A\cup(A\cap B)=A\)
Solución
\[\begin{align*} x\in A\cup(A\cap B) &\iff x\in A \lor x\in A\cap B && \text{def de }\cup\\ & \iff x\in A \lor (x\in A\land x\in B) && \text{def de }\cap\\ & \iff x\in A && \text{absorción} \end{align*}\]Negaciones
Para los ejemplos de conjuntos vamos a suponer que tenemos un universo \(V\) donde todos los conjuntos están contenidos. La operación que captura la negación es el complemento, es decir, \(x\in A^c\) si y solo si \(x\not\in A\).
Leyes de De Morgan
\[\neg(\alpha\land\beta)\equiv\neg\alpha\lor\neg\beta \quad\text{y}\quad \neg(\alpha\lor\beta)\equiv\neg\alpha\land\neg\beta\]Ejercicio: \((A\cap B)^c=A^c\cup B^c\)
Solución
\[\begin{align*} x\in (A\cap B)^c &\iff x\not\in A\cap B && \text{def de complemento}\\ & \iff \neg(x\in A\land x\in B) && \text{def de }\not\in\\ & \iff \neg(x\in A)\lor\neg(x\in B) && \text{De Morgan}\\ & \iff x\in A^c\lor x\in B^c && \text{def de complemento}\\ & \iff x\in A^c\cup B^c && \text{def de }\cup \end{align*}\]Ejercicio: \((A\cup B)^c=A^c\cap B^c\)
Solución
\[\begin{align*} x\in (A\cup B)^c &\iff x\not\in A\cup B && \text{def de complemento}\\ & \iff \neg(x\in A\lor x\in B) && \text{def de }\not\in\\ & \iff \neg(x\in A)\land\neg(x\in B) && \text{De Morgan}\\ & \iff x\in A^c\land x\in B^c && \text{def de complemento}\\ & \iff x\in A^c\cap B^c && \text{def de }\cap \end{align*}\]Doble negación
\[\neg\neg\alpha\equiv\alpha\]Ejercicio: \((A^c)^c=A\)
Solución
\[\begin{align*} x\in (A^c)^c &\iff x\not\in A^c && \text{def de complemento}\\ & \iff \neg(x\in A^c) && \text{def de }\not\in\\ & \iff \neg(x\not\in A) && \text{def de complemento}\\ & \iff \neg\neg(x\in A) && \text{def de }\not\in\\ & \iff x\in A && \text{doble negación} \end{align*}\]Tercero excluido
\[\alpha\lor\neg\alpha\equiv\text{True}\]Ejercicio: \(A\cup A^c=V\)
Solución
Como \(V\) es el conjunto universal, \(x\in V\) para todo \(x\). Además, por la misma razón, \(A\cup A^c\subseteq V\). Por lo tanto, sólo hay que demostrar la otra contención.
Sea \(x\in V\). Por el tercero excluido, la fórmula \(x\in A\lor x\not\in A\) es verdadera. Por definición de complemento, la fórmula \(x\in A\lor x\in A^c\) es verdadera. Finalmente, usando la definición de unión se tiene que \(x\in A\cup A^c\).
Métodos de demostración
Demostración por casos
\[(\alpha\lor\beta)\to\gamma\equiv(\alpha\to\gamma)\land(\beta\to\gamma)\]Ejercicio: Demostrar \((P\to Q)\land P\models Q\).
Solución
Sea \(\text{ev}\colon\mathsf{Prop}\to\{0,1\}\) una función de evaluación. Veamos que \(\text{ev}((P\to Q)\land P)\leq\text{ev}(Q)\).
Como la función \(\text{ev}\) sólo puede tomar dos valores, entonces demostraremos la desigualdad por casos sobre el valor de \(\text{ev}((P\to Q)\land P)\).
Hay que tomar \(\alpha\) la fórmula \(\text{ev}((P\to Q)\land P=0)\), la fórmula \(\beta\) debe ser \(\text{ev}((P\to Q)\land P)=1\) y la fórmula \(\gamma\) es \(\text{ev}((P\to Q)\land P)\leq\text{ev}(Q)\). Así, la demostración por casos nos dice que tenemos que hacer dos demostraciones:
- Si \(\text{ev}((P\to Q)\land P)=0\), entonces \(\text{ev}((P\to Q)\land P)\leq\text{ev}(Q)\) y
- Si \(\text{ev}((P\to Q)\land P)=1\), entonces \(\text{ev}((P\to Q)\land P)\leq\text{ev}(Q)\).
Si \(\text{ev}((P\to Q)\land P)=0\), entonces \(\text{ev}((P\to Q)\land P)\leq\text{ev}(Q)\) ya que \(0\leq\text{ev}(Q)\).
Si \(\text{ev}((P\to Q)\land P)=1\), entonces \(\text{ev}(P\to Q)=1\) y \(\text{ev}(P)=1\). Recordando la definición de la función \(\text{ev}\), se tiene
\[1=\text{ev}(P\to Q)=\max\{1-\text{ev}(P),\text{ev}(Q)\} =\max\{1-1,\text{ev}(Q)\}=\max\{0,\text{ev}(Q)\}=\text{ev}(Q).\]Por lo tanto \(\text{ev}((P\to Q)\land P)\leq\text{ev}(Q)\).
Demostración de una disyunción
\[\alpha\to(\beta\lor\gamma)\equiv(\alpha\land\neg\beta)\to\gamma\]Ejercicio: Sean \(x,y\in\mathbb{R}\). Si \(x\cdot y=0\), entonces \(x=0\) o \(y=0\).
Solución
Si usamos la equivalencia para demostrar disyunciones, entonces tenemos que demostrar que si \(x\cdot y=0\) y \(x\neq 0\), entonces \(y=0\).
Como \(x\neq 0\), entonces tiene inverso multiplicativo, \(1/x\). Multiplicando ambos lados de la igualdad \(x\cdot y=0\) por \(1/x\) se tiene que \(y=0\).
Contrapuesta
\[\alpha\to\beta\equiv\neg\beta\to\neg\alpha\]Ejercicio: Si \(x\in\mathbb{Z}\) y \(x^2\) es impar, entonces \(x\) es impar.
Solución
Si usamos la contrapuesta, entonces tenemos que demostrar que si \(x\) es par, entonces \(x^2\) es par.
Si \(x\) es par, entonces \(x=2k\) para algún \(k\in\mathbb{Z}\). Entonces \(x^2=(2k)^2=4k^2=2(2k^2)\), que es par.
Reducción al absurdo o demostración por contradicción
\[\alpha\to\beta\equiv \alpha\land\neg\beta\to\text{False}\]Ejercicio: Si \(A\subseteq B\) entonces \(A\setminus B=\emptyset\).
Solución
Haremos esta demostración por contradicción, es decir, supondremos que \(A\subseteq B\) y \(A\setminus B\neq\emptyset\) y llegaremos a una contradicción.
Si \(A\setminus B\neq\emptyset\), entonces tiene un elemento, digamos \(x\). Este elemento debe satisfacer \(x\in A\) y \(x\not\in B\). Pero como \(A\subseteq B\) y \(x\in A\), entonces \(x\in B\). Por lo tanto, llegamos a una contradicción, \(x\in B\) y \(x\not\in B\).
Con cuantificadores
Existencial con disyunción
\[\exists x(\varphi(x)\lor\psi(x))\equiv\exists x\varphi(x)\lor\exists x\psi(x)\]Ejercicio: Si \(f\colon A\to B\) es una función y \(S,T\subseteq A\), entonces \(f(S\cup T)=f(S)\cup f(T)\).
Solución
\[\begin{align*} y\in f(S\cup T) &\iff \exists x(x\in S\cup T\land f(x)=y) && \text{def de imagen}\\ & \iff \exists x((x\in S\lor x\in T)\land f(x)=y) && \text{def de }\cup\\ & \iff \exists x[(x\in S\land f(x)=y)\lor(x\in T\land f(x)=y)] && \text{distributividad}\\ & \iff \exists x(x\in S\land f(x)=y)\lor\exists x(x\in T\land f(x)=y) && \text{existencial con disyunción}\\ & \iff y\in f(S)\lor y\in f(T) && \text{def de imagen}\\ & \iff y\in f(S)\cup f(T) && \text{def de }\cup \end{align*}\]Universal con conjunción
\[\forall x(\varphi(x)\land\psi(x))\equiv\forall x\varphi(x)\land\forall x\psi(x)\]Cuanificadores con negación
\[\neg\forall x\varphi(x)\equiv\exists x\neg\varphi(x) \quad\text{y}\quad \neg\exists x\varphi(x)\equiv\forall x\neg\varphi(x)\]Implicaciones lógicas
Conjunción y disyunción
Eliminación de la conjunción
\[\alpha\land\beta\models\alpha\]Ejercicio: Si \(x\in A\cap B\), entonces \(x\in A\).
Solución
\[\begin{align*} x\in A\cap B &\iff x\in A\land x\in B && \text{def de }\cap\\ & \implies x\in A && \text{eliminación de la conjunción} \end{align*}\]Introducción de la disyunción
\[\alpha\models\alpha\lor\beta\]Ejercicio: Si \(x\in A\), entonces \(x\in A\cup B\).