chap3.tex

\documentclass{book}
\usepackage{ctex}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage[mathscr]{eucal}
\newcommand{\Eqv}{\Leftrightarrow}
\newcommand{\eqv}{\leftrightarrow}
\newcommand{\To}{\Rightarrow}
\newcommand{\A}{\forall}
\newcommand{\E}{\exists}
\newcommand{\no}{\varnothing}
\newcommand{\scr}[1]{\mathscr{#1}}
\newcommand{\nsubset}{\not\subset}
\begin{document}
\chapter{集合恒等式及其证明}
\section{集合恒等式}
\noindent
关于$\cap, \cup$
\begin{enumerate}
    \item 幂等律\quad $A\cup A=A, A\cap A=A$
    \item 交换律\quad $A\cup B=B\cup A, A\cap B=B\cap A$
    \item 结合律\quad $(A\cup B)\cup C)=A\cup (B\cup C)$
    \item 分配律\quad $A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$ 
    \item 吸收律\quad $A\cup (A\cap B)=A, A\cap (A\cup B)=A$
\end{enumerate}
关于$\sim$
\begin{enumerate}
    \item 双重否定律\quad $\sim\sim A=A$
    \item 德摩根律\quad $\sim (A\cup B)=\sim A\cap \sim B, \sim (A\cap B)=\sim A\cup \sim B$
\end{enumerate}
关于$E, \no$
\begin{enumerate}
    \item 零律\quad $A\cup E=E, A\cap\no=\no$
    \item 同一律\quad $A\cup\no=A, A\cap E=A$
    \item 排中律\quad $A\cup\sim A=E$
    \item 矛盾律\quad $A\cap\sim A=\no$
    \item 全补律\quad $\sim\no=E,\sim E=\no$
    \item 补交转换律\quad $A-B=A\cap\sim B$
\end{enumerate}
推广到集族
\begin{enumerate}
    \item 分配律\quad $B\cup (\bigcap\{A_\alpha\}_{\alpha\in A})=\bigcap_{\alpha\in S}(B\cup A_\alpha)$\\
        $B\cap (\bigcup\{A_\alpha\}_{\alpha\in S}=\bigcup_{\alpha\in S}(B\cap A_\alpha)$
     \item 德摩根律 $\sim (\bigcup\{A_\alpha\}_{\alpha\in S})=\bigcap_{\alpha\in S}(\sim A_\alpha)$\\
        $\sim (\bigcap\{A_\alpha\}_{\alpha\in S})=\bigcup_{\alpha\in S}(\sim S_\alpha)$\\
        $B-(\bigcup\{A_\alpha\}_{\alpha\in S})=\bigcap_{\alpha\in S}(B-A_\alpha)$\\
        $B-(\bigcap\{A_\alpha\}_{\alpha\in S})=\bigcup_{\alpha\in S}(B-A_\alpha)$
\end{enumerate}
\subsection{对偶原理}
\noindent
对偶式：一个集合关系式，如果只含有$\cap,\cup,\sim,\no,E,=,\subseteq$，那么同时把$\cup$与$\cap$互换，把$\no$与$E$互换，把$\subseteq$与$\supseteq$互换，得到的式子称为原式的对偶式。\\
对偶原理：对 偶式同真假，或者说，集合恒等式的对偶式还是恒等式。
\section{半形式化证明} 
\subsection{逻辑演算法} 
证明$A=B$:
\begin{align*}
    &\A x,\\
    &x\in A\\
    \Eqv&\dots \mbox{(定义，逻辑等值式)}\\
    \Eqv&\dots\quad (\dots)\\
    \Eqv&x\in B\\
    &\therefore A=B
\end{align*}  
例子:$A\cup (B\cap C)=(A\cup B)\cap (A\cup C)$
\begin{align*} 
&\A x\\
&x\in A\cup (B\cap C)\\
\Eqv&x\in A\lor (x\in B\land x\in C)\quad\mbox{$\cup$与$\cap$的定义}\\
\Eqv&(x\in A\lor x\in B)\land (x\in A\lor x\in C)\quad\mbox{命题逻辑分配律}\\
\Eqv&x\in A\cup B\land x\in A\cup C\quad\mbox{$\cup$定义}\\
\Eqv&x\in (A\cup B)\land x\in (A\cup C)\quad\mbox{$\cap$定义}\\
&\therefore A\cup (B\cap C)=(A\cup B)\cap (A\cup C)
\end{align*}
\subsection{集合演算法}
\noindent
吸收律的证明
\begin{align*}
&A\cup (A\cap B)\\
=&(A\cap E)\cup (A\cap B)\quad\mbox{同一律}\\
=&A\cap (E\cup B)\quad\mbox{分配律}\\
=&A\cap E\quad\mbox{零律}\\
=&A\quad\mbox{同一律}\\
&\therefore A\cup (A\cap B)=A
\end{align*}
德摩根律相对形式的证明
\begin{align*}
&A-(B\cup C)\\
=&A\cap\sim (B\cup C)\quad\mbox{补交转换律}\\
=&A\cap(\sim B\cap\sim C)\quad\mbox{德摩根律}\\
=&(A\cap A)\cap (\sim B\cap\sim C)\quad\mbox{幂等律}\\
=&(A\cap\sim B)\cap (A\cap\sim C)\quad\mbox{交换律结合律}\\
=&(A-B)\cap (A-C)\quad\mbox{补交转换律}
\end{align*}
\section{其它集合恒等式}
\subsection{$\oplus$的性质}
\begin{enumerate}
    \item 交换律：$A\oplus B=B\oplus A$
    \item 结合律：$A\oplus (B\oplus C)=(A\oplus B)\oplus C$\\
        分解成基本单位，例如：$A\cap\sim B\cap\sim C,\quad A\cap B\cap\sim C,\quad A\cap B\cap C,\quad\sim A\cap\sim B\cap\sim C$\\
        证明：\\
        首先：
        \begin{align*}
            A\oplus B&=(A-B)\cup (B-A)\quad\mbox{$\oplus$定义}\\
            &=(A\cap\sim B)\cup (B\cap\sim A)\quad\mbox{补交转换律}\\
            &=(A\cap\sim B)\cup(\sim A\cap B)\quad\mbox{$\cap$交换律}\\
        \end{align*}
        其次：
        \begin{align*}
            &A\oplus (B\oplus C)\\
            =&(A\cap\sim(B\oplus C))\cup (\sim A\cap (B\oplus C))\\
            =&(A\cap\sim ((B\cap\sim C)\cup (\sim B\cap C)))\cup\\
            &(\sim A\cap ((B\cap\sim C)\cup (\sim B\cap C)))\\
            =&(A\cap (\sim (B\cap\sim C)\cap\sim (\sim B\cap C)))\cup\\
            &(\sim A\cap ((B\cap\sim C)\cup (\sim B\cap C)))\quad\mbox{德摩根律}\\
            =&(A\cap (\sim (B\cap\sim C)\cap\sim (\sim B\cap C)))\cup\\
            &(\sim A\cap ((B\cap\sim C)\cup (\sim B\cap C)))\\
            =&(A\cap (\sim B\cup C)\cap (B\cup\sim C))\cup (\sim A\cap ((B\cap\sim C)\cup (\sim B\cap C)))\\
            =&(A\cap B\cap C)\cup (A\cap\sim B\cap\sim C)\cup (\sim A\cap B\cap\sim C)\cup (\sim A\cap\sim B\cup\sim C)
        \end{align*}
        同理：
        \begin{align*}
           &(A\oplus B)\oplus C\\
           =&((A\oplus B)\cap\sim C)\cup (\sim (A\oplus B)\cap C)\\
           =&(((A\cap\sim B)\cup (\sim A\cap B))\cap\sim C)\cup (\sim ((A\cap\sim B)\cup (\sim A\cap B))\cap C)\\
           =&(((A\cap\sim B)\cup (\sim A\cap B))\cap\sim C)\cup ((\sim (A\cap\sim B)\cap\sim (\sim A\cap B))\cap C)\\
           =&(A\cap\sim B\cap\sim C)\cup (\sim A\cap B\cap\sim C)\cup (\sim A\cap\sim B\cap C)\cup (A\cap B\cap C)\\
           &\therefore A\oplus\left( B\oplus C \right)=\left( A\oplus B \right)\oplus C
        \end{align*}

    \item 分配律：$A\cap (B\oplus C)=(A\cap B)\oplus (A\cap C)$
    \item 消去律：$A\oplus B=A\oplus C\Eqv B=C$\\
        $A=B\oplus C\Eqv B=A\oplus C\Eqv C=A\oplus B$
    \item 对称差与补：$\sim\left( A\oplus B \right)=\sim A\oplus B=A\oplus\sim B$\\
        $A\oplus B=\sim A\oplus\sim B$
\end{enumerate}
\subsection{特征函数与集合运算}
\begin{enumerate}
    \item $\chi_{A\cap B}(x)=\chi_A(x)*\chi_B(x)$
    \item $\chi_{\sim A}(x)=1-\chi_A(x)$
    \item $\chi_{A-B}(x)=\chi_A(x)\left( 1-\chi_B(x) \right)$
    \item $\chi_{A\cup B}(x)=\chi_{(A-B)\cup B}(x)=\chi_A(x)+\chi_B(x)-\chi_A(x)*\chi_B(x)$
    \item $\chi_{A\oplus B}(x)=\chi_A(x)+\chi_B(x)(\mod 2)=\chi_A(x)\oplus\chi_B(x)$
\end{enumerate}
\subsection{集族的性质}
\begin{enumerate}
    \item $\scr{A}\subseteq\scr{B}\To\bigcup\scr{A}\subseteq\bigcup\scr{B}$
    \item $\scr{A}\in\scr{B}\To\scr{A}\subseteq\bigcup\scr{B}$
    \item $(A\neq\no)\land\scr{A}\subseteq\scr{B}\To\bigcap\scr{B}\subseteq\bigcap\scr{A}$
    \item $\scr{A}\in\scr{B}\To\bigcap\scr{B}\subseteq\scr{A}$
    \item $\scr{A}\neq\no\To\bigcap\scr{A}\subseteq\scr{A}$
\end{enumerate}
证明：$\scr{A}\subseteq\scr{B}\To\bigcup\scr{A}\subseteq\bigcup\scr{B}$
\begin{align*}
    &\A x,\\
    &x\in\bigcup\scr{A}\\
    \Eqv&\E A(A\in\scr{A}\land x\in A)\quad\bigcup\scr{A}\mbox{定义}\\
    \To&\E A(A\in \scr{B}\land x\in A)\quad\mbox{已知}\scr{A}\subseteq\scr{B}\\
    \Eqv&x\in\bigcup\scr{B}\quad\bigcup\scr{B}\mbox{定义}\\
    &\therefore \bigcup\scr{A}\subseteq\bigcup\scr{B}
\end{align*}
证明：$\scr{A}\subseteq\scr{B}\To\scr{A}\subseteq\bigcup\scr{B}$
\begin{align*}
    &\A x,\\
    &x\in\scr{A}\\
    \To&\scr{A}\in\scr{B}\land x\in\scr{A}\quad\mbox{$scr{A}\in\scr{B}$合取}\\
    \To&\E A(A\in\scr{B}\land x\in A)
\end{align*}
\end{document}