383 lines
16 KiB
TeX
383 lines
16 KiB
TeX
\documentclass[10pt,a4paper]{article}
|
||
\usepackage[utf8]{inputenc}
|
||
\usepackage[spanish]{babel}
|
||
\usepackage{amsmath}
|
||
\usepackage{amsfonts}
|
||
\usepackage{amssymb}
|
||
\usepackage{multicol}
|
||
\usepackage{hyperref}
|
||
\renewcommand{\rmdefault}{ptm}
|
||
\usepackage{pgf}
|
||
\usepackage{tikz}
|
||
\usetikzlibrary{automata,positioning,arrows}
|
||
%\tikzset{->, % makes the edges directed
|
||
% >=stealth’, % makes the arrow heads bold
|
||
% node distance=3cm, % specifies the minimum distance between two nodes. Change if necessary.
|
||
% every state/.style={thick, fill=gray!10}, % sets the properties for each ’state’ node
|
||
% initial text=$ $ % sets the text that appears on the start arrow
|
||
% }
|
||
%\usetikzlibrary{arrows,automata}
|
||
%\usepackage[all,cmtip]{xy}
|
||
%\usepackage{graphicx}
|
||
\author{Lógica computacional}
|
||
\title{Lógica de enunciados (proposicional)}
|
||
\begin{document}
|
||
\maketitle
|
||
\section{Elementos}
|
||
|
||
La intención en este primer apartado es ver como se construye un lenguaje capaz de expresar ideas, pero estrictamente formal. Que a partir de una cantidad fija de reglas podamos construir enunciados. Si recuerdan sus clases de español en la primaria seguro recordarán que así se inicio su estudio de la lengua, pero al igual rememorarán que siempre salían las excepciones a la regla, los verbos con conjugaciones distintas, y aún más, que hay demasiadas formas de decir una misma cosa\footnote{Afortunadamente, eso hace a la lengua, sea el español, el inglés, el nahuatl, sumamente rica e interesante, gracias a ello es que hay literatura.}. Ahora queremos reducirlo al mínimo, lo que apenas nos alcance para dar sentido pero no llegando a que sea un lenguaje capaz de parecerse a cualquier lenguaje humano.
|
||
Un dato chusco es que existe el lenguaje de programación \emph{Shakespeare}, (SPL por sus siglas en inglés) donde el programa asemeja al guión de una obra de teatro de Shakespeare, los personajes son pilas que guardarán datos, los diálogos es como interactúan con esos datos y las preguntas que se hacen son enunciados condicionales, pueden ver un poco más de este lenguaje en: \url{https://en.wikipedia.org/wiki/Shakespeare_Programming_Language}.
|
||
|
||
Ya que queremos que las expresiones creadas en este lenguaje se les pueda aplicar una función, por ejemplo la concatenación, la negación o alguna transformación, y el resultado siga teniendo sentido, siga siendo una expresión del lenguaje, definimos de acuerdo a lo visto en el capítulo anterior, como un conjunto recursivo. Para ello necesitamos:
|
||
|
||
\begin{itemize}
|
||
\item Átomos, en este caso las proposiciones $A_1, A_2,...$
|
||
\item Los sómbolos: $\neg$, $\vee$, $\wedge$, $\rightarrow$ y $\iff$. Los conectivos de enunciados.
|
||
\item Los paréntesis ``(`` y ``)''.
|
||
\end{itemize}
|
||
|
||
Todos estos elementos forman un conjunto $S$, pero el que nos interesa es un $\bar{S}\subset S$, el subconjutno de las combinaciones de estos elementos que tienen sentido como expresión lógica.
|
||
|
||
Para poder definirlo inductivamente es necesario asegurar la cerradura. Por ello toda proposición en este lenguaje debe cumplir:
|
||
|
||
\begin{itemize}
|
||
\item Todo símbolo $A_i$ está en el lenguaje ($\bar{S}$) así como los símbolos $\{verdadero,falso\}$ también está en $\bar{S}$.
|
||
\item Si $A$ está en $\bar{S}$, $\neg A$ también está en $\bar{S}$.
|
||
\item Si $A$ y $B$ están en $\bar{S}$, $(A\vee B)$, $(A\wedge B)$, $(A\rightarrow B)$ y $(A\iff B)$ también están en $\bar{S}$.
|
||
\item Una cadena está en $\bar{S}$ si y sólo si es formada a través de los pasos anteriores.
|
||
\end{itemize}
|
||
|
||
Los paréntesis aseguran que $\bar{S}$ está libremente generado. Ejemplos de proposiciones bien armadas: $A_1$, $\neg A_2$, $(A_1\vee A_2) \rightarrow (\neg A_1 \wedge A_2)$.
|
||
Proposiciones sin sentido: $(())$, $(A_1\wedge A_2)\neg$.
|
||
|
||
Otra manera de ver estas construcciones es a partir de su árbol de generación, por ejemplo para la expresión $((P_1\wedge P_9)\rightarrow ((\neg P_6)\vee (P_8\iff P_6)))$, puede generarse por el árbol que se muestra en la imagen \ref{img:tree}.
|
||
|
||
\begin{figure} %para ue aparezca como figura, con sus caracteristicas
|
||
\begin{center}
|
||
\begin{tikzpicture} %aquí empieza el arbol
|
||
[
|
||
level 1/.style = {sibling distance = 3.cm, level distance = 1.cm}
|
||
] %sibling distance es el espacio horizontal, por si lo quieres hacer más amplio, level distance es el vertical, para hacerlo más alto
|
||
\node [draw] {$((P_1\wedge P_9)\rightarrow ((\neg P_6)\vee (P_8\iff P_6)))$} %draw dibija la cajita
|
||
child {node {$(P_1\wedge P_9)$}
|
||
child {node {$P_1$}}
|
||
child {node {$P_9$}}
|
||
child [missing]}
|
||
child {node {$((\neg P_6)\vee (P_8\iff P_6))$}
|
||
child {node {$(\neg P_6)$}
|
||
child [missing]
|
||
child {node {$P_6$}}}
|
||
child {node {$(P_6\iff P_8)$}
|
||
child {node {}}
|
||
child {node {$P_8$}}}};
|
||
|
||
\end{tikzpicture}
|
||
\caption{Construcción de una expresión lógica.} %el titulo de la figura
|
||
\label{fig:tree1} %puedes ponerle el label para referenciarlo
|
||
\end{center}
|
||
\end{figure}
|
||
|
||
El siguiente paso es evaluar cada una de las proposiciones $P_i$ a alguno de los valores de verdad\footnote{Se dice que se le da un valor de verdad, aunque esa es la acción, los valores en realidad pueden ser \emph{verdadero} o \emph{falso}.}. A partir del árbol podemos saber si la expresión tiene un valor de verdad de \emph{falso} o \emph{verdadero}.
|
||
|
||
\begin{equation*}
|
||
\bar{v}(A_1) = \{verdadero, falso\}
|
||
\end{equation*}
|
||
|
||
La evaluación es una función del tipo:
|
||
|
||
\begin{equation*}
|
||
\bar{v}: \bar{S}\rightarrow \{verdadero, falso\}.
|
||
\end{equation*}
|
||
|
||
Pero hacer este procedimiento por medio de un árbol para expresiones con demasiadas proposiciones se vuelve una tarea complicada, quizá convenga algún otro método, las tablas de verdad.
|
||
|
||
Para las operaciones que ya definimos antes, sus tablas de verdad serían:
|
||
|
||
\begin{center}
|
||
\begin{tabular}{c c c}
|
||
\begin{tabular}{c|c}
|
||
$A_1$ & $\neg A_1$ \\
|
||
\hline \\
|
||
F & V\\
|
||
V & F\\
|
||
\end{tabular}
|
||
& \begin{tabular}{c c|c}
|
||
$A_1$ & $A_2$ & $A_1\vee A_2$ \\
|
||
\hline \\
|
||
F & F & F\\
|
||
V & F & V\\
|
||
F & V & V\\
|
||
V & V & V
|
||
\end{tabular}
|
||
& \begin{tabular}{c c|c}
|
||
$A_1$ & $A_2$ & $A_1\wedge A_2$ \\
|
||
\hline \\
|
||
F & F & F\\
|
||
V & F & F\\
|
||
F & V & F\\
|
||
V & V & V
|
||
\end{tabular}\\
|
||
\hline
|
||
\begin{tabular}{c c|c}
|
||
$A_1$ & $A_2$ & $A_1\rightarrow A_2$ \\
|
||
\hline \\
|
||
F & F & V\\
|
||
V & F & F\\
|
||
F & V & V\\
|
||
V & V & V
|
||
\end{tabular}
|
||
& \begin{tabular}{c c|c}
|
||
$A_1$ & $A_2$ & $A_1\iff A_2$ \\
|
||
\hline \\
|
||
F & F & V\\
|
||
V & F & F\\
|
||
F & V & F\\
|
||
V & V & V
|
||
\end{tabular}
|
||
\end{tabular}
|
||
\end{center}
|
||
|
||
Hay más funciones booleanas que pueden definirse, sin argumentos como $V^0$ y $F^0$ que son las que regresan los valores $verdadero$ y $falso$ respectivamente sin necesidad de darles argumento alguno.
|
||
|
||
\section{Tautologías, contradicciones y contingencias}
|
||
|
||
Con estos elementos podemos construir distintas expresiones. En general para saber que valor de verdad tendrán al final deberemos evaluar, pero haciendo una división de nuestras posibilidades podemos tener algunos casos bastante particulares, algunos en los que sin hacer la evaluación podremos saber si es verdadero o falso, casos en los que podrá reducirse la expresión, y muchos otros en los que sin evaluare no podremos decir más.
|
||
|
||
|
||
|
||
\section{Formas distintas de decir lo mismo}
|
||
|
||
Un primer ejemplo que ya vimos son las leyes de DeMorgan:
|
||
|
||
\begin{align*}
|
||
\neg (A_1 \wedge A_2) &\iff (\neg A_1)\vee (\neg A_2)\\
|
||
\neg (A_1 \vee A_2)&\iff (\neg A_1)\wedge (\neg A_2)\
|
||
\end{align*}
|
||
|
||
Pero podemos sacar más jugo de esto en otros casos
|
||
|
||
|
||
Forma normal conjuntiva: La conjunción de una disyunción de fórmulas.
|
||
|
||
\begin{equation*}
|
||
\wedge_{i=1}^n (\vee_{j=1}^m \alpha_{i,j})
|
||
\end{equation*}
|
||
|
||
Forma normal disyuntiva: La disyunción de una conjunción de fórmulas.
|
||
|
||
\begin{equation*}
|
||
\vee_{i=1}^n (\wedge_{j=1}^m \alpha_{i,j})
|
||
\end{equation*}
|
||
|
||
\begin{center}
|
||
\begin{tabular}{cc|c|c}
|
||
$p$ & $q$ & $p\rightarrow q$ & $\neg p \vee q$\\
|
||
\hline \\
|
||
F & F & V & V\\
|
||
V & F & F & F\\
|
||
F & V & V & V\\
|
||
V & V & V & V\\
|
||
\end{tabular}
|
||
\end{center}
|
||
|
||
Expresar $A\iff B$ en forma normal conjuntiva.
|
||
|
||
\begin{center}
|
||
\begin{tabular}{cc|c|c}
|
||
$A$ & $B$ & $A\iff B$ & $(\neg A \vee B)\wedge (A \vee \neg B)$\\
|
||
\hline \\
|
||
F & F & V & V\\
|
||
V & F & F & F\\
|
||
F & V & F & F\\
|
||
V & V & V & V\\
|
||
\end{tabular}
|
||
\end{center}
|
||
|
||
Pasos para convertir a forma normal conjuntiva:
|
||
\begin{enumerate}
|
||
\item Cambiar $\rightarrow$ y $\iff$ por su correspondiente.
|
||
\item Usar las leyes de DeMorgan para introducir $\neg$ a los paréntesis
|
||
\end{enumerate}
|
||
|
||
\begin{equation*}
|
||
(p\wedge q)\rightarrow (t\wedge s)
|
||
\end{equation*}
|
||
|
||
Expresar $A\iff B$ en forma normal disyuntiva.
|
||
|
||
\textbf{Ejercicio}: Convierte a forma normal conjuntiva:
|
||
\begin{align*}
|
||
&A\iff (\neg B \wedge \neg C)\\
|
||
&\neg(A\wedge B \wedge \neg C)
|
||
\end{align*}
|
||
|
||
\section{Sistemas de demostraciones}
|
||
|
||
Para esta sección nos centraremos en el sistema de Łukasiewicz, para ello partamos de las siguientes tautologías:
|
||
|
||
\begin{enumerate}
|
||
\item $A_1: p\rightarrow (q\rightarrow p)$
|
||
\item $A_2: (p\rightarrow (q\rightarrow r))\rightarrow ((p\rightarrow q)\rightarrow(p\rightarrow r))$
|
||
\item $A_3: (\neg p\rightarrow \neg q)\rightarrow (q\rightarrow p)$
|
||
\end{enumerate}
|
||
|
||
Son tautologías, pueden comprobarlo con su tabla de verdad. La idea es partir de estos valores como axiomas, traducir toda expresión posible a estos tres axiomas y así, de manera directa resolver el sistema, sin necesidad de engorrosas tablas de verdad.
|
||
|
||
Lo único que hace falta es la regla de derivación, llamada \emph{modus ponens}\footnote{El nombre se deriva de los conceptos de Diogenes Laeritus, quizá uno de los primeros historiadores de la filosofía, biógrafo de los filósofos griegos.}:
|
||
|
||
\begin{equation*}
|
||
\frac{p\rightarrow q,\ p}{q}
|
||
\end{equation*}
|
||
|
||
\textbf{Ejercicio:} Prueba que $A\rightarrow A$ es una consecuencia lógica.
|
||
|
||
\begin{align*}
|
||
(A\rightarrow (B\rightarrow A))\rightarrow A\ &(A_1)\\
|
||
A\rightarrow ((B\rightarrow A)\rightarrow A)\ &(r.p.)\\
|
||
(A\rightarrow ((B\rightarrow A)\rightarrow A))\rightarrow ((A\rightarrow (B\rightarrow A))\rightarrow (A\rightarrow A))\ &(A_2)\\
|
||
((A\rightarrow (B\rightarrow A))\rightarrow (A\rightarrow A))\ &(M.P.)\\
|
||
(A\rightarrow A)\ &(A_1, M.P.)\square.
|
||
\end{align*}
|
||
|
||
\textbf{Ejercicio:} Asumiendo que $(A\wedge B)\iff \neg(A\rightarrow \neg B)$ y $\neg(A\vee B)\iff (\neg A\rightarrow B)$ son consecuencias lógicas, muestra que:
|
||
|
||
\begin{itemize}
|
||
\item $(\neg B \rightarrow \neg A)\iff (A\rightarrow B)$
|
||
\item $(A\wedge B)\rightarrow A$
|
||
\end{itemize}
|
||
|
||
\textbf{Ejercicio:} Muestra que las siguientes son expresiones lógicas válidas o no:
|
||
|
||
\begin{align*}
|
||
&\{B\rightarrow A, C\rightarrow C, D\rightarrow B, B\wedge c\wedge D\} \models A\wedge B\\
|
||
&\{A\wedge B\rightarrow C, A\rightarrow B\} \models A\rightarrow C
|
||
\end{align*}
|
||
|
||
\section{Deducción natural}
|
||
|
||
La \emph{deducción natural} es un tipo de sistema lógico, un sistema para poder obtener demostraciones siguiendo algunos pasos establecidos. Su principal característica es tener \emph{subpruebas}, partes de la prueba general que depende de premisas temporales.
|
||
|
||
Al mencionar que un enunciado puede asignársele un valor de verdad ($verdadero$ o $falso$) secciones atrás, se mencionó que era parecido a hacer un árbol con cada átomo como hoja y lo que los une es la operación lógica, binaria o unitaria. Eso ya es un sistema de deducción natural, muy parecido a lo que propuso Gentzen en su cálculo-$\mathcal{N}$.
|
||
|
||
Jaśkowski en 1934, en forma independiente propone un método pictórico de representar una demostración a partir de cajas que encierran porciones de la prueba.
|
||
|
||
\textbf{Ejemplo:} Probar que $((p\rightarrow q)\wedge (\neg r \rightarrow \neg q))\rightarrow (p\rightarrow r)$ es una consecuencia lógica:
|
||
|
||
\[
|
||
\boxed{
|
||
\begin{aligned}
|
||
&((p\rightarrow q)\wedge (\neg r\rightarrow \neg q))\ \text{(Suposición.)}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&p\ \text{(Suposición)}\\
|
||
&((p\rightarrow q)\wedge (\neg r\rightarrow \neg q))\ \text{(Reiteración)}\\
|
||
&(p\rightarrow q)\ \text{(Simplificación)}\\
|
||
&q\ \text{(Modus ponens)}\\
|
||
&(\neg r\rightarrow \neg q)\ \text{Simplificación}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&\neg r\ \text{(Suposición)}\\
|
||
&(\neg r \rightarrow \neg q)\ \text{(Reiteración)}\\
|
||
&\neg q\ \text{(Modus ponens)}\\
|
||
&q\ \text{Reiteración}\\
|
||
\end{aligned}
|
||
}\\
|
||
&r\ \text{(Reducción al absurdo)}\\
|
||
\end{aligned}
|
||
}\\
|
||
&(p\rightarrow r)\ \text{(Condicionalidad)}\\
|
||
\end{aligned}
|
||
}
|
||
\]
|
||
|
||
Pero viéndolo como está en clase:
|
||
|
||
\[
|
||
\boxed{
|
||
\begin{aligned}
|
||
&((p\rightarrow q)\wedge (\neg r\rightarrow \neg q))\ \text{(Hipótesis)}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&(p\rightarrow q)\ \text{(E $\wedge$)}\\
|
||
&(\neg r\rightarrow \neg q)\ \text{(E $\wedge$)}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&p\ \text{(Hipótesis)}\\
|
||
&q\ \text{(E $\rightarrow$)}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&\neg r\ \text{(Hipótesis)}\\
|
||
&\neg q\ \text{(E $\rightarrow$)}\\
|
||
&\bot\ \text{(I $\bot$)}
|
||
\end{aligned}
|
||
}\\
|
||
&\neg \neg r\ \text{(I $\neg$)}\\
|
||
\end{aligned}
|
||
}\\
|
||
&r\ \text{(E $\neg$)}\\
|
||
\end{aligned}
|
||
}\\
|
||
&(p\rightarrow r)\ \text{(I $\rightarrow$)}\\
|
||
\end{aligned}
|
||
}
|
||
\]
|
||
|
||
Ahora un ejemplo conocido. \textbf{Ejemplo}: Mostrar que $\neg(p\vee q)\iff (\neg p \wedge \neg q)$
|
||
|
||
\[
|
||
\boxed{
|
||
\begin{aligned}
|
||
&\neg (p\vee q)\ \text{(Hipótesis)}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&p\ \text{(Hipótesis)}\\
|
||
&(p\vee q)\ \text{(I $\vee$)}\\
|
||
&\bot\ \text{(I $\bot$)}
|
||
\end{aligned}
|
||
}\\
|
||
&\neg p\ \text{(I $\neg$)}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&q\ \text{(Hipótesis)}\\
|
||
&p\vee q\ \text{(E $\vee$)}\\
|
||
&\bot\ \text{(I $\bot$)}\\
|
||
\end{aligned}
|
||
}\\
|
||
&\neg q\ \text{(I $\neg$)}\\
|
||
&\neg p \wedge \neg q\ \text{(I $\wedge$)}\\
|
||
&\neg (p\vee q) \rightarrow (\neg p \wedge \neg q)\ \text{(I $\rightarrow$)}\\
|
||
&\neg p \wedge \neg q\ \text{(Hipótesis)}\\
|
||
&\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&\neg p\ \text{(Hipótesis)}\\
|
||
&\neg q\ \text{(E $\wedge$)}\\
|
||
\hspace{3 mm}\boxed{
|
||
\begin{aligned}
|
||
&p\vee q\ \text{(Hipótesis)}\\
|
||
&q\ \text{(E $\vee$)}\\
|
||
&\bot\ \text{(I $\bot$)}
|
||
\end{aligned}
|
||
}\\
|
||
&\neg(p\vee q)\ \text{(I $\neg$)}\\
|
||
\end{aligned}
|
||
}\\
|
||
&(\neg p \wedge \neg q)\rightarrow \neg(p\vee q)\ \text{(I $\rightarrow$)}\\
|
||
\end{aligned}
|
||
}
|
||
\]
|
||
|
||
\textbf{Ejercicio}: Prueba las siguientes proposiciones por deducción natural:
|
||
|
||
\begin{align*}
|
||
&(A\wedge (A\rightarrow B)) \rightarrow B\\
|
||
&((A\rightarrow B)\wedge (A\rightarrow C))\rightarrow (A\rightarrow (B\wedge C))
|
||
\end{align*}
|
||
|
||
\begin{thebibliography}{10}
|
||
\bibitem{Enderton2021} Enderton, Herbert B. ``Una Introducción matemática a la lógica'' Universidad Nacional Autónoma de México, Instituto de Investigaciones Filosóficas, 2a edición (2004), reimpresión (2021).
|
||
\bibitem{Gallier2003} Gallier, Jean. ``Logic for computer science. Foundations of automatic theorem proving'' University of Pensylvania (2003) \url{https://www.researchgate.net/publication/31634432_Logic_for_computer_science_foundations_of_automatic_theorem_proving_JH_Gallier}
|
||
\end{thebibliography}
|
||
|
||
|
||
\end{document}
|