% UTF-8 encoding
% Compile with latex+dvipdfmx, pdflatex, xelatex or lualatex

\documentclass[UTF8]{ctexart}
\usepackage{graphicx}
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{subfigure}
\usepackage{geometry}
\usepackage{caption}

\newcommand{\true}{{\rm T}}
\newcommand{\false}{{\rm F}}
\newcommand{\snatural}{\mathbb{N}}
\newcommand{\sinteger}{\mathbb{Z}}
\newcommand{\srational}{\mathbb{Q}}
\newcommand{\sreal}{\mathbb{R}}
\newcommand{\card}{\rm{card}}
\newcommand{\modt}{\text{mod }}
\newcommand{\ran}{{\rm ran}}
\newcommand{\dom}{{\rm dom}}

\title{离散数学——第十一周作业}
\author{计83  刘轩奇  2018011025}
\date{2019.11.21}

\geometry{left=2.0cm, right=2.0cm, top=2.5cm, bottom=2.5cm}

\begin{document}

\maketitle

\paragraph{10.1}\label{10.1}
列出下列关系$R$的元素。

(1) $ A = \{ 0,1,2 \} , B= \{ 0,2,4 \} $ ，而
$$ R = \{ \langle x,y \rangle | x,y \in A \cap B \}  $$

(2) $ A = \{ 1,2,3,4,5 \}, B = \{1,2,3\}$ ，而
$$R = \{ \langle x,y \rangle | x \in A \land y \in B \land x = y^2 \} $$

\paragraph{解}
(1) $R = \{ \langle 0,0 \rangle , \langle 0,2 \rangle , \langle 2,0 \rangle , \langle 2,2 \rangle \} $

(3) $R = \{ \langle 1,1 \rangle , \langle 4,2 \rangle \} $

\paragraph{10.2}\label{10.2}
设$A = \{ \langle 1,2 \rangle , \langle 2,4 \rangle , \langle 3,3 \rangle \} , B = \{ \langle 1,3 \rangle , \langle 2,4 \rangle , \langle 4,2 \rangle \} $

求$A \cup B, A \cap B, \dom(A), \dom(B), \ran(A), \ran(B), \dom(A \cup B), \ran(A \cap B)$

\paragraph{解}
\begin{align*}
    A \cup B & = \{ \langle 1,2 \rangle , \langle 1,3 \rangle , \langle 2,4 \rangle , \langle 3,3 \rangle , \langle 4,2 \rangle \} \\
    A \cap B & = \{ \langle 2,4 \rangle \} \\
    \dom(A) & = \{ 1,2,3 \} \\
    \dom(B) & = \{ 1,2,4 \} \\
    \ran(A) & = \{ 2,3,4 \} \\
    \ran(B) & = \{ 2,3,4 \} \\
    \dom(A \cup B) & = \{ 2,3,4 \} \\
    \ran(A \cap B) & = \{ 4 \} 
\end{align*}

\paragraph{10.3}\label{10.3}
证明：
$$\dom(R \cup S) = \dom(R) \cup \dom(S), \dom(R \cap S)\subseteq \dom(R) \cap \dom(S)$$

\paragraph{证}
(1) 证$\dom(R \cup S) = \dom(R) \cup \dom(S)$
\begin{align*}
    x \in \dom(R \cup S) & \Longleftrightarrow ( \exists y) \langle x,y \rangle \in R \cup S \\
    & \Longleftrightarrow ( \exists y) (\langle x,y \rangle \in R \lor \langle x,y \rangle \in S) \\
    & \Longleftrightarrow x \in \dom(R) \lor x \in \dom(S) \\
    & \Longleftrightarrow x \in \dom(R) \cup \dom(S)
\end{align*}
$$\therefore \dom(R \cup S) = \dom(R) \cup \dom(S)$$

(2) 证$\dom(R \cap S)\subseteq \dom(R) \cap \dom(S)$
\begin{align*}
    x \in \dom(R \cap S) & \Longleftrightarrow ( \exists y) \langle x,y \rangle \in R \cap S \\
    & \Longleftrightarrow ( \exists y)( \langle x,y \rangle \in R \land \langle x,y \rangle \in S) \\
    & \Longrightarrow ( \exists y) \langle x,y \rangle \in R \land ( \exists y) \langle x,y \rangle \in S \\
    & \Longleftrightarrow x \in \dom(R) \land x \in \dom(S) \\
    & \Longleftrightarrow x \in \dom(R) \cap \dom(S)
\end{align*}
$$\therefore \dom(R \cap S)\subseteq \dom(R) \cap \dom(S)$$

\paragraph{10.4}\label{10.4}
设：$A=\{1,2,3\}$，在$A$上有多少不同的关系？设$|A|=n$，在$A$上有多少不同的关系？

\paragraph{答} $A=\{1,2,3\}$上有$2^9$种不同的关系。$|A|=n$时，$A$上有$2^{n^2}$种不同的关系。

\paragraph{10.5}\label{10.5}
列出所有从$A=\{a,b,c\}$到$B=\{d\}$的关系。

\paragraph{答}
$$\varnothing,  \{ \langle a,d \rangle \} , \{ \langle b,d \rangle \} , \{ \langle c,d \rangle \},$$
$$ \{ \langle a,d \rangle , \langle b,d \rangle \} , \{ \langle a,d \rangle , \langle c,d \rangle \} , \{ \langle b,d \rangle , \langle c,d \rangle \}, $$
$$ \{ \langle a,d \rangle , \langle b,d \rangle , \langle c,d \rangle \} $$
共8个关系。

\paragraph{10.6}\label{10.6}
对$n \in \snatural$且$n >2$，从二元关系定义$n$元关系。
\paragraph{答}
$$ \langle x_1, x_2, x_3 \rangle = \langle \langle x_1, x_2 \rangle , x_3 \rangle $$
$$ \langle x_1, x_2, x_3, x_4 \rangle = \langle \langle x_1, x_2, x_3 \rangle , x_4 \rangle $$
$$ \cdots $$
$$ \langle x_1, x_2, \cdots, x_n \rangle = \langle \langle x_1, x_2, \cdots, x_ { n-1 } \rangle , x_n \rangle $$

\paragraph{10.7}\label{10.7}
对$A=\{0,1,2,3,4\}$上的下列关系，给出关系图和关系矩阵。

(1) $R_1 =  \{ \langle x,y \rangle |2 \le x \land y \le 2 \} $

(3) $R_3 = \{ \langle x,y \rangle | x\text{和}y\text{是互质的} \}$

\paragraph{解} 关系图如图 10.7 所示。
\begin{figure}[!htb]
    \centering
    \begin{minipage}[t]{0.221\textwidth}
    \centering
    \includegraphics[width=1\textwidth]{p7-1.png}
    \caption*{(1)}
    \end{minipage}
    \begin{minipage}[t]{0.221\textwidth}
    \centering
    \includegraphics[width=1\textwidth]{p7-3.png}
    \caption*{(3)}
    \end{minipage}
    \caption*{图 10.7}
\end{figure}
关系矩阵
$$A_1 = \begin{bmatrix}
    0 & 0 & 0 & 0 & 0 \\
    0 & 0 & 0 & 0 & 0 \\
    1 & 1 & 1 & 0 & 0 \\
    1 & 1 & 1 & 0 & 0 \\
    1 & 1 & 1 & 0 & 0
\end{bmatrix},
A_3 = \begin{bmatrix}
    0 & 0 & 0 & 0 & 0 \\
    0 & 1 & 1 & 1 & 1 \\
    0 & 1 & 0 & 1 & 0 \\
    0 & 1 & 1 & 0 & 1 \\
    0 & 1 & 0 & 1 & 0
\end{bmatrix}$$

\paragraph{10.10}\label{10.10}
设$R,S,T$是$A$上的关系，证明
$$R\circ (S \cup T) = (R \circ S) \cup (R \circ T)$$
\paragraph{证}
\begin{align*}
    \langle x,y \rangle \in R \circ (S \cup \true ) & \Longleftrightarrow ( \exists z)( \langle z,y \rangle \in R \land \langle x,z \rangle \in S \cup \true ) \\
    & \Longleftrightarrow ( \exists z)( \langle z,y \rangle \rangle \in R \land ( \langle x,z \rangle \in S \lor \langle x,z \rangle \in \true )) \\
    & \Longleftrightarrow ( \exists z)(( \langle z,y \rangle \in R \land \langle x,z \rangle \in S) \lor ( \langle z,y \rangle \in R \land \langle x,z \rangle \in \true )) \\
    & \Longleftrightarrow ( \exists z)( \langle z,y \rangle \in R \land \langle x,z \rangle \in S) \lor ( \exists z)( \langle z,y \rangle \in R \lor \langle x,z \rangle \in \true ) \\
    & \Longleftrightarrow \langle x,y \rangle \in R \circ S \lor \langle x,y \rangle \in R \circ \true \\
    & \Longleftrightarrow \langle x,y \rangle \in (R \circ S) \cup (R \circ \true )
\end{align*}
$$\therefore R\circ (S \cup T) = (R \circ S) \cup (R \circ T)$$

\end{document}