105 lines
4.8 KiB
TeX
105 lines
4.8 KiB
TeX
\documentclass[10pt,a4paper]{article}
|
||
\usepackage[utf8]{inputenc}
|
||
\usepackage[spanish]{babel}
|
||
\usepackage{amsmath}
|
||
\usepackage{amsfonts}
|
||
\usepackage{amssymb}
|
||
\usepackage{multicol}
|
||
\usepackage{hyperref}
|
||
\usepackage{graphicx}
|
||
\usepackage{listings}
|
||
\usepackage{xcolor}
|
||
\usepackage{caption}
|
||
\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 predicados (de primer órden)}
|
||
\begin{document}
|
||
\maketitle
|
||
|
||
Al tratar con objetos matemáticos, como seguramente ya lo han hecho en los semestres que llevan de la carrera, por lo regular se buscan relaciones generales de todos los objetos de un conjunto, o reconocer un elemento muy particular que sólo tiene ese sentido de particularidad cuando se piensa en todos los demás.
|
||
|
||
En la lógica de proposiciones sólo se hablaba de los átomos, las proposiciones, y las posibles operaciones sobre ellos, pero nada se hablaba de la relación entre átomos. Para poder agregar. Eso nos ahorra tener que dar enunciados lógicos para cada elemento de un conjunto y poder hablar de una generalidad, o de una singularidad que se diferencia de una generalidad.
|
||
|
||
De nueva cuenta definimos este lenguaje de manera recursiva, pero antes de ponerlo formalmente hay que listar lo que necesitamos (para ir a la tienda matemática y conseguir nuestra lista del súper):
|
||
|
||
\begin{enumerate}
|
||
\item Las \emph{variables}, que trataran de la generalidad, cuando queramos referir a la singularidad usaremos \emph{constantes}, en contraposición.
|
||
\item \emph{Símbolos predicados}, los que dará las características a las variables o constantes.
|
||
\item Los \emph{cuantificadores}, que justo nos dirán si una propiedad se cumple para todas las variables, o sólo para una o alguna.
|
||
\end{enumerate}
|
||
|
||
Realmente para definir algunos de estos elementos vienen en diversas presentaciones:
|
||
|
||
\newtheorem{defi}{Definición}
|
||
\begin{defi}
|
||
Un lenguaje de lógica de predicados consiste de los siguientes símbolos fundamentales:
|
||
\begin{itemize}
|
||
\item Símbolos lógicos
|
||
\begin{itemize}
|
||
\item \emph{Variables}: $x,y,z,...,x_0,y_0,z_0,...,x_i,y_i,z_i,...$
|
||
\item \emph{Conectores lógicos}: $\neg, \wedge, \vee, \rightarrow, \iff$
|
||
\item Coma y paréntesis: , ()
|
||
\item Cuantificadores: $\exists, \forall$
|
||
\end{itemize}
|
||
\item Símbolos específicos
|
||
\begin{itemize}
|
||
\item \emph{Símbolos predicados}: $P,Q,R,...,P_0,Q_0,R_0,...,P_i,...$
|
||
\item \emph{Símbolos de constantes}: $a,b,...,a_0,b_0,...,a_i,b_i,...$
|
||
\item \emph{Símbolos de funciones}: $f,g,f_0,g_0,...,f_i,...$
|
||
\end{itemize}
|
||
\end{itemize}
|
||
\end{defi}
|
||
|
||
Los símbolos predicados tendrán una \emph{aridad} dependiendo de cuantos símbolos sean parte de su argumento. Cada cuantificador es dual al otro, es decir que puede traducirse:
|
||
\begin{itemize}
|
||
\item $(\forall x)Q(x)\iff \neg(\exists x)\neg Q(x)$
|
||
\item $(\exists x)Q(x)\iff \neg(\forall x)\neg Q(x)$
|
||
\end{itemize}
|
||
|
||
\begin{defi}
|
||
Un \emph{término} se define inductivamente como:
|
||
\begin{itemize}
|
||
\item Una \textbf{constante} es un término.
|
||
\item una \textbf{variable} es un término.
|
||
\item Si $f$ es una \textbf{función} de aridad-n, y $t_1,...,t_n$ son términos, $f(t_1,...,t_n)$ es un término.
|
||
\end{itemize}
|
||
\end{defi}
|
||
|
||
\begin{defi}
|
||
Una \textbf{fórmula atómica} o \textbf{átomo} es toda secuencia de símbolos $P(t_1,...,t_n)$ donde $P$ es un símbolo predicado de aridad-n y $t_i$ son términos, para $i=1,2,...,n$.
|
||
\end{defi}
|
||
|
||
\begin{defi}
|
||
Una \textbf{fórmula} es definida inductivamente como:
|
||
\begin{itemize}
|
||
\item Todo \textbf{átomo} es una fórmula
|
||
\item Si $\sigma_1$ y $\sigma_2$ son fórmulas, $\neg \sigma_1$, $\sigma_1\wedge \sigma_2$, $\sigma_1\vee \sigma_2$, $\sigma_1\rightarrow \sigma_2$ y $\sigma_1\iff \sigma_2$ son fórmulas también.
|
||
\item Si $v$ es una variable y $\phi$ una fórmula entonces $((\exists v)\phi)$ y $((\forall v)\phi)$ también son fórmulas.
|
||
\item Solo las secuencias de símbolos formadas de acuerdo a los puntos anteriores son fórmulas.
|
||
\end{itemize}
|
||
\end{defi}
|
||
|
||
Bueno, ¿y eso para qué sirve o qué tiene que ver con programación? Pues lo prometido es deuda, veamos un poco de Haskell.
|
||
|
||
Definamos todos los posibles factores de un número natural cualquiera:
|
||
|
||
\lstinputlisting[firstline=1,lastline=3]{fact.hs}
|
||
|
||
Todos los número natural menores a un número natural dado:
|
||
|
||
\lstinputlisting[firstline=4,lastline=6]{fact.hs}
|
||
|
||
\end{document}
|