chap1.tex

\documentclass{book}
\usepackage{ctex}
\usepackage{amsmath}
\usepackage{amssymb}

\newcommand{\Eqv}{\Leftrightarrow}
\newcommand{\eqv}{\leftrightarrow}
\newcommand{\To}{\Rightarrow}
\newcommand{\A}{\forall}
\newcommand{\E}{\exists}

\begin{document}
\chapter{集合}
\section{命题公式}
\subsection{连接词}
$
\neg 否定连接词
\land 合取
\lor 析取
\to 蕴含(\mbox{可看作小于等于})
\leftrightarrow 等价
$
\subsection{命题公式}
只有有限次运用上述运算符的符号串才是公式\\
例子：\\
$\neg\neg\neg p,\\
p\to (q\to r)\\
(p\to (q\to r))\land p\land q\to r
$
可满足式，矛盾式(永假式)，重言式(永真式)
\section{等值式}
\subsection{等值式}
等值式$A\Leftrightarrow B$: $A\leftrightarrow B$是永真式\\
$p\to q \Leftrightarrow \neg p \lor q$
\subsection{基本等值式}
\begin{enumerate}
\item 幂等律 $A\Leftrightarrow A\lor A$$A \Leftrightarrow A\land A$
\item 交换律
\item 结合律
\item 分配律
\item 德摩根律 $\neg (A\lor B) \Leftrightarrow \neg A\land \neg B$\\
$\neg (A \land B) \Eqv \neg A \land \neg B$
\item 吸收律 $A\lor (A\land B) \Eqv A$\\
$A \land (A\lor B) \Eqv A$
\item 零律 $A\lor 1\Eqv 1, A\land 0\Eqv 0$
\item 同一律 $A\lor 0\Eqv A, A\land 1\Eqv A$
\item 排中律 $A\lor \neg A \Eqv 1$
\item 矛盾律 $A\land \neg A\Eqv 0$
对偶原理:$\lor - \land$互换$0-1$互换不变
\item 双重否定律 $\neg\neg A\Eqv A$
\item 蕴涵等值式 $A\to B \Eqv \neg A\lor B$
\item 等价等值式 $A\eqv B\Eqv (A\to B)\land (B\to A)$ 
\item 等价否定等值式 $A\eqv B \Eqv \neg A\eqv \neg B$
\item 假言易位 $A\to B \Eqv \neg B \to \neg A$
\item 归谬论 $(A\to B)\land (A\to \neg B)\Eqv \neg A$
\end{enumerate}
\subsection{等值演算}
\begin{align*}
p\to (q\to r)\Eqv p\to (\neg q\lor r)\\
\Eqv \neg p\lor(\neg q\lor r)\\
\Eqv (\neg p \lor \neg q)\lor r\\
\Eqv \neg(p\land q)\lor r\\
\Eqv (p\land q)\to r\\
\end{align*}
\section{命题逻辑推理}
\subsection{推理的形式结构}
$(A_1\land A_2\land\dots\land A_k)\to B$
\subsection{重要的推理定律}
推理定律 $A\To B:A\to B$是永真式
\begin{enumerate}
\item 附加律 $A\To (A\lor B)$
\item 化简律$(A\land B)\To A, (A\land B)\To B$
\item 假言推理 $(A\to B)\land A\To B$
\item 拒取式 $(A\to B)\land \neg B\To \neg A$
\item 析取三段论 $(A\lor B)\land \neg A\To B, (A\lor B)\land \neg B\To A$
\item 假言三段论 $(A\to B)\land (B\to C)\To (A\to C)$
\item 等价三段论 $(A\eqv B)\land (B\eqv C)\To (A\eqv C)$
\item 构造性两难 $(A\to B)\land (C\to D)\land (A\lor C)\To (B\lor D)$
\end{enumerate}
\subsection{判断推理正确的方法}
前提：$p\to (q\to r), p, q$\\
结论：$r$\\
方法一：推理的形式结构(形式结构是永真式)\\
\begin{align*}
(p\to (q\to r))\land p \land q\to r\\
\Eqv (\neg p\lor (\neg q\lor r))\land p\land q\to r\\
\Eqv ((\neg p \land p)\lor ((\neg q\lor r)\land p))\land q\to r\\
\Eqv ((\neg q\lor r)\land q)\land p\to r\\
\Eqv ((\neg q\land q)\lor (r\land q))\land p\to r\\
\Eqv (r\land q\land p)\to r\\
\Eqv \neg (r\land q\land p)\lor r\\
\Eqv \neg r\lor \neg q\lor \neg p\lor r\\
\Eqv (\neg r\lor r)\lor \neg q\lor\neg p\\
\Eqv 1
\end{align*}
方法二：从前提推演结论\\
\begin{align*}
(p\to (q\to r))\land p\land q\\
\Eqv ((p\to (q\to r)\land p)\land q\\
\To (q\to r)\land q\\
\To r
\end{align*}
\section{一阶谓词逻辑基本概念与命题符号化}
个体，个体域，全总个体域\\
个体常元：$a,b,c,\dots$;个体变元：$x,y,z,\dots$\\
谓词：$F,G,H,\dots$; 量词：$\A, \E$\\
$\A x(F(x)\to G(x))$\\
$\E x(F(x)\land G(x))$\\
例子：\\
\begin{enumerate}
    \item{人都吃饭}
        $F(x):x$是人，$G(x):x$吃饭 $\A x(F(x)\to G(x))$或(使用全体人作为全总个体域)$\A xG(x)$
    \item{有人喜欢吃糖}
        $\E x(F(x)\land G(x))$
    \item{火车都比汽车快}
        $\A x(F(x)\to \A y(G(y)\to H(x,y)))$\\
    $F(x):x$是火车 $G(x):x$是汽车 $H(x,y):x$比$y$快
    \item{有的汽车比所有火车都快}
        $\E x(G(x)\land \A y(F(y)\to H(x,y)))$
\end{enumerate}
\section{一阶谓词逻辑公式及其分类}
指导变元，辖域，约束出现，自由出现\\
$\A x(F(x)\to \E y(G(y)\land H(x,y,z)))$\\
解释：全总个体域，$F(x):x$是实数，$G(x):x$是整数，$H(x,y,z):x+y=z$\\
永真式，永假式，可满足式
\section{一阶谓词逻辑等值式与基本等值式}
等值式$A\Eqv B: A\eqv B$为永真式
\subsection{有限个体域消去量词}
有限个体域 $D=\{a_1,a_2,\dots,a_n\}$\\
$\A xA(x)\Eqv A(a_1)\land A(a_2)\land \dots \land A(a_n)$\\
$\E xA(x)\Eqv A(a_1)\lor A(a_2)\lor \dots \lor A(a_n)$\\
\subsection{量词否定}
\begin{enumerate}
    \item $\neg\A xA(x)\Eqv \E x\neg A(x)$\\
        $\neg\A xA(x)\eqv\E x\neg A(x)$是永真式\\
        在所有解释下，左右同真假
    \item $\neg\E xA(x)\Eqv\A x\neg A(x)$
\end{enumerate}
\subsection{量词辖域收缩与扩张}
$B$中不含$x$:
\begin{enumerate}
    \item $\A x(A(x)\lor B)\Eqv \A xA(x)\lor B$
    \item $\A x(A(x)\land B)\Eqv \A xA(x)\land B$
    \item $\A x(A(x)\to B)\Eqv \E xA(x)\to B$\\
        $\A x(A(x)\to B)\Eqv \A x(\neg A(x)\lor B)\Eqv  \A x\neg A(x)\lor B\Eqv\neg\E xA(x)\lor B\Eqv \E xA(x)\to B$
    \item $\A x(B\to A(x))\Eqv B\to \A xA(x)$
    \item $\E x(A(x)\lor B)\Eqv\E xA(x)\lor B$
    \item $\E x(A(x)\land B)\Eqv \E xA(x)\land B$
    \item $\E x(A(x)\to B)\Eqv \A xA(x)\to B$
    \item $\E x(B\to A(x))\Eqv B\to \E xA(x)$
\end{enumerate}
\subsection{量词分配}
\noindent
$\A x(A(x)\land B(x))\Eqv \A xA(x)\land \A xB(x)$\\
$\E x(A(x)\lor B(x))\Eqv \E xA(x)\lor \E xB(x)$
\section{前束范式}
\begin{align*}
    &\A xF(x)\lor\neg\E xG(x,y)\\
    \Eqv& \A xF(x)\lor \A x\neg G(x,y)\\
    \Eqv& \A xF(x)\lor\A z\neg G(z,y) (\mbox{换名规则})\\
    \Eqv& \A x(F(x)\lor \A z\neg G(z,y)) (\mbox{辖域扩张})\\
    \Eqv& \A x\A z(F(x)\lor\neg G(z,y)) (\mbox{前束范式})\\
    \Eqv& \A x\A z(G(z,y)\to F(x))
\end{align*}
\section{重要的推理定律}
\begin{enumerate}
    \item $\A xA(x)\lor \A xB(x)\To \A x(A(x)\lor B(x))$
    \item $\E x(A(x)\land B(x))\To \E xA(x)\land \E xB(x)$
    \item $\A x(A(x)\to B(x))\To \A xA(x)\to \A xB(x)$
    \item $\A x(A(x)\to B(x))\To \E xA(x)\to \E xB(x)$
\end{enumerate}
取个体域为全体自然数
$A(x):x$是偶数，$B(x):x$是奇数，代入1，2，此时右端为真左端为假
\end{document}