\documentclass[12pt]{article}
\usepackage[spanish,es-tabla]{babel}
\usepackage[latin1]{inputenc}
\usepackage{hyperref}
\usepackage{texdraw}
\usepackage{multicol}
\usepackage{fancyheadings}
\usepackage{theorem}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{color}
\usepackage{xcolor}
\usepackage{bm}
\usepackage{kbordermatrix}

\usepackage[cal=boondox,scr=boondoxo]{mathalfa}
\usepackage{oldgerm}
\usepackage{euscript}
%\usepackage{newalg}
\usepackage{rotating}
\usepackage{enumerate}
\usepackage{textpos}
\usepackage{fge}
\usepackage{tikz-cd}
\usepackage{tikz}
\usetikzlibrary{positioning}
\tikzcdset{scale cd/.style={every label/.append style={scale=#1}, cells={nodes={scale=#1}}}}


\definecolor{processblue}{cmyk}{0.96,0,0,0}

{\theorembodyfont{\rmfamily} \newtheorem{teo}{Teorema}}
{\theorembodyfont{\rmfamily} \newtheorem{obs}{Observaci\'on}}
{\theorembodyfont{\rmfamily} \newtheorem{coro}{Corolario}}
{\theorembodyfont{\rmfamily} \newtheorem{lema}{Lema}}
{\theorembodyfont{\rmfamily} \newtheorem{prop}{Proposici\'on}}
{\theorembodyfont{\rmfamily} \newtheorem{defi}{Definici\'on}}
{\theorembodyfont{\rmfamily} \newtheorem{prob}{Problema}}
{\theorembodyfont{\rmfamily} \newtheorem{ejer}{Ejercicio}}
{\theorembodyfont{\rmfamily} \newtheorem{ejem}{Ejemplo}}

\newcommand{\find}[0]{\hfill $\blacksquare$}
\newcommand{\fine}[0]{\hfill $\Box$}
\newcommand{\findef}[0]{\noindent\hrulefill}
\newcommand{\derms}[0]{\overset{*}{\Rightarrow}}


\def\proof{\noindent{\textbf{Demostraci\'on}}\\}
\def\endproof{\hfill{\ensuremath\square}}
\def\refname{Referencias}
\def\abstractname{Resumen}

\title{Documento de ejemplo para reportar tareas \\
Estructuras Discretas \\
CCOS 009}
\author{José de Jesús Lavalle Martínez}
\date{}

\begin{document}
\maketitle

\begin{abstract}
Escribir brevemente qué se está reportando y cuál es su propósito.
\end{abstract}

\section{Nombre de la primera sección}
Desarrollar el discurso correspondiente al nombre de la primera sección, por ejemplo: 

\section{Nombre de la segunda sección}
Desarrollar el discurso correspondiente al nombre de la segunda sección, por ejemplo:

\section{Conclusiones}
Escribir dos o tres conclusiones sobre el trabajo desarrollado con respecto al propósito establecido en el resumen.

\section{Ejemplos}
\begin{teo}\label{teo1}
Para todo conjunto $S$, $\emptyset \subseteq S$ y $S \subseteq S$.
\end{teo}
\textit{Demostración:} Primero demostramos que $\emptyset \subseteq S$.

Sea $S$ un conjunto. Para demostrar que $\emptyset \subseteq S$, debemos demostrar que $\forall x (x \in \emptyset \rightarrow x \in S)$ es verdadera. Dado que el conjunto vacío no contiene elementos, se deduce que $x \in \emptyset$ siempre es falso. 

De ello se deduce que el enunciado condicional $x \in \emptyset \rightarrow x \in S$ es siempre verdadero, porque su hipótesis siempre es falsa y un enunciado condicional con una hipótesis falsa es verdadero. 

Por lo tanto, $\forall x (x \in \emptyset \rightarrow x \in S)$ es verdadera. Esto completa la prueba. Tenga en cuenta que este es un ejemplo de una prueba por vacuidad.

Para demostrar que $S \subseteq S$ tenemos que ver si $\forall x (x \in S \rightarrow x \in S)$ es verdadera, lo cual se cumple ya que cualquier enunciado siempre se implica a sí mismo, en este caso $x \in S \rightarrow x \in S$ es verdadero y como escogimos un $x \in S$ arbitrario entonces $S \subseteq S$ es cierto.

También podemos demostrar el Teorema \ref{teo1} por contradicción, de la siguiente manera.

Para demostrar que $\emptyset \subseteq S$, empezamos suponiendo que la afirmación es falsa. Así, tenemos que $\forall x (x \in \emptyset \rightarrow x \in S)$, lo cual implica que $x \in \emptyset$ es verdadera y $x \in S$ es falsa; pero como $\emptyset$ por definición no tiene elementos, llegamos a una contradicción. Por lo tanto es falsa nuestra suposición de que $\emptyset \subseteq S$ es falsa, así 
$\emptyset \subseteq S$ es verdadera.

De la misma manera para demostrar por contradicción que $S \subseteq S$, empezamos suponiendo que la afirmación $\forall x (x \in S \rightarrow x \in S)$ es falsa. Por lo tanto debemos tener que $x \in S \rightarrow x \in S$ es falsa, lo cual implica que $x \in S$ es al mismo tiempo verdadera y falsa, lo cual es una contradicción, de esta manera $S \subseteq S$ es verdadera. \find

\begin{ejem}\label{eje14}
¿Cuál es el conjunto potencia del conjunto $\{0, 1, 2\}$?

\textit{Solución:} El conjunto potencia $\mathcal{P}(\{0, 1, 2\})$ es el conjunto de todos los subconjuntos de $\{0, 1, 2\}$. Por lo tanto,
\[
\mathcal{P}(\{0, 1, 2\}) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0, 1\}, \{0, 2\}, \{1, 2\}, \{0, 1, 2 \}\}.
\]

Tenga en cuenta que el conjunto vacío y el conjunto en sí son miembros de este conjunto de subconjuntos.\fine
\end{ejem}

\begin{ejem}\label{eje15}
¿Cuál es el conjunto potencia del conjunto vacío? ¿Cuál es el conjunto potencia del conjunto $\{\emptyset\}$?

\textit{Solución:} El conjunto vacío tiene exactamente un subconjunto, a saber, él mismo. Por consiguiente, $\mathcal{P}(\emptyset) = \{\emptyset\}$.

El conjunto $\{\emptyset\}$ tiene exactamente dos subconjuntos, a saber, $\emptyset$ y el propio conjunto $\{\emptyset\}$. Por lo tanto, $\mathcal{P} = \{\emptyset, \{\emptyset\}\}$. \fine
\end{ejem}


\section{Como se produjo la tarea}
\begin{enumerate}
\item Liste los miembros de estos conjuntos.
\begin{enumerate}
\item $\{x |x \text{ es un número real tal que } x^2 =1\}$,
\item $\{x | x \text{ es un entero positivo menor que } 12\}$,
\item $\{x | x \text{ es el cuadrado de un entero y } x < 100\}$,
\item $\{x | x \text{ es un entero tal que } x^2 = 2\}$.
\end{enumerate}
\item Utilice la notación de constructor de conjuntos para dar una descripción de cada uno de estos conjuntos.
\begin{enumerate}
\item $\{0,3,6,9,12\}$,
\item $\{-3,-2,-1,0,1,2,3\}$,
\item $\{m,n,o,p\}$.
\end{enumerate}
\pagebreak
\item Para cada uno de estos pares de conjuntos, determine si el primero es un subconjunto del segundo, el segundo es un subconjunto del primero, o ninguno es un subconjunto del otro.
\begin{enumerate}
\item el conjunto de personas que hablan Inglés, el conjunto de personas que hablan Inglés con acento australiano.
\item el conjunto de frutas, el conjunto de frutas cítricas.
\item el conjunto de estudiantes que estudian estructuras discretas, el
conjunto de estudiantes que estudian estructuras de datos.
\end{enumerate}
\item Suponga que $A = \{2,4,6\}, B = \{2,6\}, C = \{4,6\}$ y $D = \{4, 6, 8\}$. Determine cuáles de estos conjuntos son subconjuntos de alguno de los restantes conjuntos.
\item ¿Cuál es la cardinalidad de cada uno de estos conjuntos?
\begin{enumerate}
\item $\emptyset$,
\item $\{\emptyset\}$,
\item $\{\emptyset, \{\emptyset\}\}$,
\item $\{\emptyset, \{\emptyset\}, \{\emptyset, \{\emptyset\}\}\}$.
\end{enumerate}
\item Encuentre el conjunto potencia de cada uno de estos conjuntos, en los que $a$ y $b$ son elementos distintos.
\begin{enumerate}
\item $\{a\}$,
\item $\{a, b\}$,
\item $\{\emptyset, \{\emptyset\}\}$.
\end{enumerate}
\item ¿Cuántos elementos tiene cada uno de estos conjuntos, donde $a$ y $b$ son elementos distintos?
\begin{enumerate}
\item $\mathcal{P}(\{a,b,\{a,b\}\})$,
\item $\mathcal{P}(\{\emptyset,a,\{a\},\{\{a\}\}\})$,
\item $\mathcal{P}(\mathcal{P}(\emptyset))$.
\end{enumerate}
\item ¿Cuál es el producto cartesiano $A \times B \times C$, donde $A$ es el conjunto de todas las aerolíneas, $B$ y $C$ son ambos el conjunto de todas las ciudades de Estados Unidos? Dé un ejemplo de cómo se puede utilizar este producto cartesiano.
\item Sean $A = \{a,b,c\}, B = \{x,y\}$, y $C = \{0,1\}$. Encuentre
\begin{enumerate}
\item $A\times B\times C$, 
\item $C\times B\times A$,
\item $C\times A\times B$,
\item $B\times B\times B$.
\end{enumerate}
\item Encuentre $A^3$ si
\begin{enumerate}
\item $A = \{a\}$,
\item $A = \{0, a\}$.
\end{enumerate}
\end{enumerate}

\section{Producto de matrices booleanas}

Cuando trabajamos con matrices booleanas zero-uno, interpretamos 1 como el valor de verdad $true$ y 0 como el valor de verdad $false$, las operaciones $\vee$, $\wedge$, $\neg$, $\rightarrow$, etc., se interpretan como en lógica proposicional.

\begin{defi}
El \textbf{producto booleano} de dos matrices zero-uno $A$ y $B$ (denotado mediante $A \odot B$), se  construye entrada por entrada de la matriz resultante de la siguiente manera:
$$[c_{ij}]_{A \odot B} = \bigvee_{k=1}^n [a_{ik}]_A \wedge [b_{kj}]_B,$$
para todo $i, j = 1, \ldots, n$.
\end{defi}

\begin{ejem}
Sea
$$
A =
\begin{bmatrix}
0 & 1 & 0 & 0\\
1 & 0 & 1 & 0\\
0 & 0 & 0 & 1\\
1 & 0 & 0 & 0
\end{bmatrix}
$$
Calcule $A \odot A$.

\textit{Solución: } Recuerde que $\wedge$ tiene mayor precedencia que $\vee$.
\begin{align*}
[c_{11}]_{A \odot B} & = \bigvee_{k=1}^4 [a_{1k}]_A \wedge [a_{k1}]_A \\
& = [a_{11}]_A \wedge [a_{11}]_A \vee [a_{12}]_A \wedge [a_{21}]_A \vee [a_{13}]_A \wedge [a_{31}]_A \vee [a_{14}]_A \wedge [a_{41}]_A \\
& = 0 \wedge 0 \vee  1 \wedge 1 \vee  0 \wedge 0 \vee  0 \wedge 1 \\
& = 0 \vee 1 \vee 0 \vee 0 \\
& = 1.
\end{align*}
\begin{align*}
[c_{12}]_{A \odot B} & = \bigvee_{k=1}^4 [a_{1k}]_A \wedge [a_{k2}]_A \\
& = [a_{11}]_A \wedge [a_{12}]_A \vee [a_{12}]_A \wedge [a_{22}]_A \vee [a_{13}]_A \wedge [a_{32}]_A \vee [a_{14}]_A \wedge [a_{42}]_A \\
& = 0 \wedge 1 \vee  1 \wedge 0 \vee  0 \wedge 0 \vee  0 \wedge 0 \\
& = 0 \vee 0 \vee 0 \vee 0 \\
& = 0. \\
\vdots
\end{align*}
\begin{align*}
[c_{23}]_{A \odot B} & = \bigvee_{k=1}^4 [a_{2k}]_A \wedge [a_{k3}]_A \\
& = [a_{21}]_A \wedge [a_{13}]_A \vee [a_{22}]_A \wedge [a_{23}]_A \vee [a_{23}]_A \wedge [a_{33}]_A \vee [a_{24}]_A \wedge [a_{43}]_A \\
& = 1 \wedge 0 \vee  0 \wedge 1 \vee  1 \wedge 0 \vee  0 \wedge 0 \\
& = 0 \vee 0 \vee 0 \vee 0 \\
& = 0. \\
\vdots
\end{align*}
\begin{align*}
[c_{43}]_{A \odot B} & = \bigvee_{k=1}^4 [a_{4k}]_A \wedge [a_{k3}]_A \\
& = [a_{41}]_A \wedge [a_{13}]_A \vee [a_{42}]_A \wedge [a_{23}]_A \vee [a_{43}]_A \wedge [a_{33}]_A \vee [a_{44}]_A \wedge [a_{43}]_A \\
& = 1 \wedge 0 \vee  0 \wedge 1 \vee  0 \wedge 0 \vee  0 \wedge 0 \\
& = 0 \vee 0 \vee 0 \vee 0 \\
& = 0. \\
\vdots
\end{align*}
Continuando de esta manera obtenemos:
$$
A \odot A=
\begin{bmatrix}
{\color{red}1} & {\color{red}0} & 1 & 0\\
0 & 1 & {\color{red}0} & 1\\
1 & 0 & 0 & 0\\
0 & 1 & {\color{red}0} & 0
\end{bmatrix}.
$$
Las entradas en {\color{red}rojo} corresponden a los valores que se calcularon explícitamente en el ejemplo.
\end{ejem}

Un ejemplo de una matriz de incidencias:
\begin{equation*}
\kbordermatrix{&e_1&e_2&e_3&e_4 & e_5 & e_6 \\
v_1&1 &1 &0 & 0& 0 & 0 \\
v_2&0 &0 &1 &1 &0 & 1\\
v_3&0 &0 & 0& 0&1 & 1\\
v_4& 1& 0& 1& 0& 0 & 0\\
v_5&0 &1 & 0& 1&1 & 0\\
}.
\end{equation*}

Matriz de adyacencias con las filas y columnas etiquetadas:

\begin{equation*}
\bm{A}_H =
\kbordermatrix{&v_6&v_3&v_4&v_5 & v_1 & v_2\\
v_6&0 &1 &0 & 1& 0&0 \\
v_3&1 &0 &1 &0 &0 & 1\\
v_4&0 &1 & 0& 1&0 &0 \\
v_5& 1& 0& 1& 0& 1& 0\\
v_1&0 &0 & 0& 1&0 & 1 \\
v_2&0 &1 & 0& 0&1 & 0 \\
}.
\end{equation*}


\end{document}