94 lines
5.1 KiB
TeX
94 lines
5.1 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{Inducción y recursión}
|
||
\begin{document}
|
||
\maketitle
|
||
\section*{Preliminares}
|
||
|
||
Antes de empezar con el tema, que seguro es nuevo o al menos tiene aspectos nuevos para todos ustedes, debemos de partir de un suelo en común, las bases. Algunas no las cubriremos pues confiamos en que sus profesores de semestres pasados las dejaron muy claras, pero si no pueden acercarse, mandar un correo y podemos apoyarles en la medida de lo posible.
|
||
|
||
Hay dos conceptos que seguro ya vieron, pero que nos interesa regresar a ellos pues queremos ver algunos detalles específicos y además serán utilizados durante el curso (además de que de ahí salen ejercicios y debemos dejarles algo para que hagan ustedes). Estos son los de las inducción y la recursión.
|
||
|
||
En primer lugar hay algunas funciones que se definen de esta forma y que en esta materia tendrán importancia, tanto de forma inductiva como recursiva. Pero además durante el resto de la carrera necesitarán de estos conceptos y seguramente durante su desempeño profesional les serán útiles, ya más adelante les comentaré al respecto.
|
||
|
||
\subsecrtion{Relaciones}
|
||
|
||
Empecemos con las ideas básicas:
|
||
|
||
\newtheorem{defi}{Definición}
|
||
\begin{defi}
|
||
Dados dos conjuntos $A$ y $B$ (posiblemente vacíos), su \emph{producto Cartesiano}, denotado por $A\times B$, es le conjunto de parejas ordenadas:
|
||
\begin{equation*}
|
||
\{ \langle a,b \rangle \mid a\in B,\ b\in B \}.
|
||
\end{equation*}
|
||
\end{defi}
|
||
|
||
Definición que se puede ampliar a más conjuntos, digamos $A_1,A_2,...,A_n$, donde el producto Cartesiano es el conjunto de eneadas ordenadas $\langle a_1, a_2,...,a_n\rangle $. De esta forma podemos definir
|
||
|
||
\begin{defi}
|
||
Una \emph{relación binaria} entre $A$ y $B$ es cualquier subconjunto $R$ (posiblemente vacío) de $A\times B$.
|
||
\end{defi}
|
||
|
||
Ya en esta definición hay un \emph{espoiler}, ya que le llamo $R$, esto deriva en lo que llamamos una relación.
|
||
|
||
\begin{defi}
|
||
Dada una relación $R$ entre los conjuntos $A$ y $B$, el conjunto
|
||
\begin{equation*}
|
||
\{ x\in A \mid \exist y\in B\ \langle x,y \rangle \in R \},
|
||
\end{equation*}
|
||
\noindent es llamado el \emph{dominio} de R, $dom(R)$. El conjunto
|
||
\begin{equation*}
|
||
\{y\in B \mid \exist x\in A\ \langle x,y \rangle \in R \},
|
||
\end{equation*}
|
||
\noindent es llamado el \emph{rango} de $R$, $rango(R)$
|
||
\end{defi}
|
||
|
||
Para ahorrar espacio podemos escribir $\langle x,y\rangle \in R$ como $xRy$.
|
||
|
||
\subsection{Funciones parciales, totales y composición}
|
||
|
||
Si se dan cuenta, estamos poniendo en un lenguaje formal algunas cuestiones matemáticas que ya han usado desde hace años, seguro desde su primer curso de matemáticas en primaria. Recuerden que estamos en lo de las bases comunes, así que sean pacientes con el exceso de definiciones. Ahora vamos con una definición de las funciones a partir de las relaciones.
|
||
|
||
\begin{defi}
|
||
Una relación $R$ entre dos conjuntos $A$ y $B$ es funcional si y sólo si, para toda $x\in A$, y $y,z \in B$, $(x,y)\in R$ y $(x,z)\in R$ implica que $y=z$.
|
||
\end{defi}
|
||
|
||
\begin{defi}
|
||
Una función parcial es la tripleta $f=\langle A,G,B \rangle$, donde $A$ y $B$son conjuntos arbitrarios (posiblemente vacíos) y $G$ una relación funcional (posiblemente vacía) entre $A$ y $B$, llamada la \emph{gráfica} de $f$.
|
||
\end{defi}
|
||
|
||
Que también suele escribirse la función parcial como $f: A\rightarrow B$, el elemento único en el rango de $f$ tal que $(x,y)\in graf(f)$ se denota por $f(x)$. Una función total es aquella función para la cual $dom(f)=A$.
|
||
|
||
Y para no dejarlo, vamos a hacer más abstracto algo que ya usan desde hace años, pero sigan la corriente, estamos formalizando todo, como si fuéramos a una fiesta elegante.
|
||
|
||
\begin{defi}
|
||
Dadas dos relaciones binarias, $R$ entre $A$ y $B$, y $S$ entre $B$ y $C$, su \emph{composición} escrita como $R\cdot S$ es una relación entre $A$ y $C$ definida por el siguiente conjunto de parejas ordenadas
|
||
\begin{equation*}
|
||
\{\}
|
||
\end{equation*}
|
||
\end{defi}
|
||
|
||
%Si caminan por los pasillos de la facultad de ciencias, en una de sus escaleras hayaran el mural de Emmy Noether (quizá no se parece mucho, y no le dieron el tiempo suficiente a la persona que hizo el trabajo creativo, pero es valioso que se reconozca el trabajo de Emmy Noether). A esta matemática se le deben algunos de los conceptos que trataremos en este capítulo, pero ya iremos hablando más de ella.
|
||
|
||
\end{document}
|