MainPage/Discrete Mathematics/Discrete Mathematics

离散数学

第一章 基础：逻辑和证明

§1.1 命题逻辑

• 命题定义：命题是一个陈述语句，它或真或假，但不能既真又假
• 命题变量（语句变量）
  • 定义：即表示命题的变量
  • 表示方法：习惯上用字母 $p,q,r,s,···$ 表示命题变量
  • 真值
    • 定义：表示命题的真假，如果一个命题为真，则真值为真，用 $T$ 表示，如果一个命题为假，则真值为假，用 $F$ 表示
• 原子命题
  • 定义：不能用简单的命题来表示的命题称为原子命题，顾名思义，即不包含其他命题作为其组成部分，无法被拆分出其他更简单命题的命题
  • 特点：不带有：非，或，且，如果，那么 等联结词
• 命题演算（命题逻辑）
  • 定义：涉及命题的逻辑领域称为命题演算或命题逻辑
• 复合命题
  • 逻辑运算符
    • 定义：将语句联结成更为复杂的复杂语句的符号或词语称为逻辑运算符，（又称联结词）
    • 分类（按优先级顺序排列）
      1. 非（$\lnot$）
      2. 合取（$\land$）
      3. 析取（$\lor$）
      4. 蕴含（$\rightarrow$）
      5. 双向蕴含（$\leftrightarrow$）
  • 定义：由已知命题用逻辑运算符（又称联结词）组合而来的新命题称为复合命题
  • 命题的否定
    • 定义：令 $p$ 为一命题，则 $p$ 的否定，记作 $\lnot p$（或 $\overline{p}$），指 “不是 $p$ 所指的情形” ，读作 “非 $p$”
    • 真值：命题否定的真值与原命题相反 | $p$ | $\lnot p$ | |:-:|:-:| |T|F| |F|T|
  • 命题的合取
    • 定义：令 $p$ 和 $q$ 为命题，$p$ 并且 $q$ 即为命题 $p$、$q$ 的合取，记作 $p \land q$
    • 真值：当 $p$ 和 $q$ 都为真，则 $p \land q$ 为真，否则为假
  • 命题的析取
    • 定义：令 $p$ 和 $q$ 为命题，$p$ 或 $q$ 即为命题 $p$、$q$ 的析取，记作 $p \lor q$
    • 真值：当 $p$ 和 $q$ 都为假，则 $p \lor q$ 为假，否则为真
  • 命题的异或
    • 定义：令 $p$ 和 $q$ 为命题，$p$ 和 $q$ 的异或是这样一个命题：当 $p$ 和 $q$ 中恰好只有一个为真时命题为真，否则为假，记作 $p \oplus q$
    • 真值：当 $p$ 和 $q$ 真值相同时为假，不同时为真
  • 复合命题真值表 | 命题 $p$ | 命题 $q$ | 命题 $p \land q$ | 命题 $p \lor q$ | 命题 $p \oplus q$ | |:—:|:—:|:———–:|:———-:|:————:| | T | T | T | T | F | | T | F | F | T | T | | F | T | F | T | T | | F | F | F | F | F |
  • 条件语句
    • 定义：令 $p$ 和 $q$ 为命题，命题 “如果 $p$，那么$q$” 即为 $p$ 到 $q$ 的条件语句（又称蕴含），记作 $p \rightarrow q$
    • 真值：当 $p$ 为真，$q$ 为假时，$p \rightarrow q$ 为假，否则为真
    • 由条件语句可引申出的新的条件语句：
      • 逆命题：命题 $p \rightarrow q$ 的逆命题为 $q \rightarrow p$
      • 逆否命题：命题 $p \rightarrow q$ 的否命题为 $\lnot q \rightarrow \lnot p$
      • 反命题：命题 $p \rightarrow q$ 的反命题为 $\lnot p \rightarrow \lnot q$ 其中：只有逆否命题的真值总与原命题相同
    • 条件语句的真值表 | 命题 $p$ | 命题 $q$ | 原命题 $p \rightarrow q$ | 逆命题 $q \rightarrow p$ | 逆否命题 $\lnot q \rightarrow \lnot p$ | 反命题 $\lnot p \rightarrow \lnot q$ | |:—:|:—:|:———————–:|:———————–:|:————————————-:|:———————————:| | T | T | T | T | T | T | | T | F | F | T | F | T | | F | T | T | F | T | F | | F | F | T | T | T | T |
    • 双条件语句（双向蕴含）
      • 定义：令 $p$ 和 $q$ 为命题，命题 $p$ 当且仅当 $q$ 即为 $p$ 和 $q$ 的双条件语句，又称双向蕴含，记作 $p \leftrightarrow q$
      • 真值：
        • 当 $p$ 和 $q$ 真值相同时为真，否则为假
        • 当 $p \rightarrow q$ 与 $p \leftarrow q$ 都为真时，$p\leftrightarrow q$ 为真，否则为假

        命题 $p$	命题 $q$	原命题 $p \rightarrow q$	逆命题 $q \rightarrow p$	双条件命题 $p \leftrightarrow q$
        T	T	T	T	T
        T	F	F	T	F
        F	T	T	F	F
        F	F	T	T	T

      • 常见表达：
        • $p$ 当且仅当 $q$
        • 如果 $p$，那么 $q$，反之亦然
        • $p$ 是 $q$ 的充分必要条件
  • 复合命题的等价
    • 判断依据：当两个复合命题总是具有相同的真值时，无论命题变量的真值是什么，我们称这两个复合命题是等价的
    • 实例：
      • 条件语句和它的逆否命题是等价的
      • 条件语句的逆命题与反命题是等价的
• 逻辑的比特运算
  • 比特
    • 定义：比特是一个具有两个可能性的符号，其含义来自于二进制数字
    • 取值：比特的取值只有两种
      • 0 - 表示假（F）
      • 1 - 表示真（T）
  • 布尔变量
    • 定义：值或为真或为假的变量，可以用一比特表示
  • 比特运算（位运算）
    • 概念：用 0 表示 假，1 表示 真，根据逻辑运算符的法则进行的逻辑运算

§1.2 命题逻辑的应用

• 语句翻译
  • 概念：指将自然语言翻译成由命题变量和逻辑联结词组成的表达式，消除人类语言的二义性造成的歧义
• 系统规范说明
  • 概念：描述硬件系统和软件系统时，往往需要将自然语言语句翻译成逻辑表达式系统和软件工程师根据自然语言描述的需求，生成精确而无二义性的规范说明，这种说明称为系统规范说明
  • 要求：
    1. 精确、无二义性
    2. 一致性，即系统规范说明不应该包含可能导致矛盾的相互冲突的需求（不一致时就不能开发出一个满足所有规范说明的系统）**
  • 作用：可作为系统开发的基础
• 布尔搜索
  • 概念：采用命题逻辑技术的搜索，称为布尔搜索
  • 联结词的使用：
    • AND：匹配同时包含两个搜索项的记录；
    • OR：匹配包含其中一项或两项都匹配的记录；
    • NOT(AND NOT)：用于排除特定某项；
  • 应用：
    • 网页搜索：大部分的 Web 搜索引擎支持布尔搜索技术，有助于寻找特定主题的网页
• 逻辑谜题
  • 定义：可以用逻辑推理解决的谜题，称为 逻辑谜题
  • 意义：
    1. 求解逻辑谜题可以实践逻辑规则
    2. 用于逻辑推理的计算机程序可以通过求解逻辑谜题来演示它的能力
• 逻辑电路（数字电路）
  • 逻辑电路是一种离散信号的传递和处理，以二进制为原理、实现数字信号逻辑运算和操作的电路。
  • 复杂的数字电路可以由从三种简单的基本电路构造而来。
    • 逆变器（非门）：接受一个输入位 $p$ 产生 $\lnot p$ 作为输出。
    • 或门：接受两个输入信号 $p$ 和 $q$，每个一位，产生信号 $p \lor q$ 作为输出。
    • 与门：接受两个输入信号 $p$ 和 $q$，每个一位，产生信号 $p \land q$ 作为输出。

§1.3 命题等价式

• 永真式（重言式）
  • 定义：一个真值永远是真的复合命题称为永真式（并不是指苇名国某药师的剑术招式[doge]），也称为重言式
• 矛盾式
  • 定义：一个真值永远为假的复合命题称为矛盾式
• 可能式
  • 定义：既不是永真式又不是矛盾式的复合命题称为可能式
• 逻辑等价式
  • 定义：如果两个复合命题 $p,q$ 在所有可能的情况下真值都相同，即 $p \leftrightarrow q$ 式永真式，则复合命题 $p,q$ 是等价的，记作 $p \equiv q$ 注：
    • 符号 $\equiv$ 不是逻辑联结词
    • $p \equiv q$ 不是一个复合命题，而是代表 $p \leftrightarrow q$ 是永真式这个语句
    • 有时候会用符号 $\Leftrightarrow$ 来代替符号 $\equiv$ 表示逻辑等价
  • 一般命题的逻辑等价式 | 名称 | 等价式 | |:—-:|:—–:| |恒等律|$p \land T \equiv p$
    $p \lor F \equiv p$| |支配律|$p \lor T \equiv T$
    $p \land F \equiv F$| |幂等律|$p \lor p \equiv p$
    $p \land p \equiv p$| |双重否定律|$\lnot(\lnot p)\equiv p$| |交换律|$p \lor q \equiv q \lor p$
    $p \land q \equiv q \land p$| |结合律|$(p \lor q) \lor r \equiv p \lor (q \lor r)$
    $(p \land q) \land r \equiv p \land (q \land r)$| |分配律|$p \lor (q \land r) \equiv (p \lor q) \land (p \lor r)$
    $p \land (q \lor r) \equiv (p \land q) \lor (p \land r)$| |德·摩根律|$\lnot(p \land q) \equiv \lnot p \lor \lnot q$
    $\lnot(p \lor q) \equiv \lnot p \land \lnot q$| |吸收律|$p \lor (p \land q) \equiv p$
    $p \land (p \lor q) \equiv p$| |否定律|$p \lor \lnot p \equiv T$
    $p \land \lnot p \equiv F$| 注：德·摩根律可扩展为： \(\lnot(p_1 \lor p_2 \lor \cdots \lor p_n) \equiv (\lnot p_1 \land \lnot p_2 \land \cdots \land \lnot p_n)\\ \lnot(p_1 \land p_2 \land \cdots \land p_n) \equiv (\lnot p_1 \lor \lnot p_2 \lor \cdots \lor \lnot p_n)\) 可简介写为： \(\lnot(\bigvee_{j=1}^n p_j) \equiv \bigwedge_{j=1}^n \lnot p_j\\ \lnot(\bigwedge_{j=1}^n p_j) \equiv \bigvee_{j=1}^n \lnot p_j\)
  • 条件命题的逻辑等价式
    • $p \rightarrow q \equiv \lnot p \lor q$
    • $p \rightarrow q \equiv \lnot q \rightarrow \lnot p$
    • $p \lor q \equiv \lnot p \rightarrow q$
    • $p \land q \equiv \lnot(p \rightarrow \lnot q)$
    • $\lnot(p \rightarrow q) \equiv p \land \lnot q$
    • $(p \rightarrow q) \land (p \rightarrow r) \equiv p \rightarrow (q \land r)$
    • $(p \rightarrow r) \land (q \rightarrow r) \equiv (p \lor q) \rightarrow r$
    • $(p \rightarrow q) \lor (q \rightarrow r) \equiv (p \land q) \rightarrow r$
    • $(p \rightarrow q) \lor (p \rightarrow r) \equiv p \rightarrow (q \lor r)$
  • 双条件命题的逻辑等价式
    • $p \leftrightarrow q \equiv (p \rightarrow q) \land (p \rightarrow q)$
    • $p \leftrightarrow q \equiv \lnot p \leftrightarrow \lnot q$
    • $p \leftrightarrow q \equiv (p \land q) \lor (\lnot p \land \lnot q)$
    • $\lnot(p \leftrightarrow q) \equiv p \leftrightarrow \lnot q$
  • 定理：如果 $p \equiv q$，并且 $q \equiv r$，那么 $p \equiv r$
• 可满足性
  • 可满足：对于一个复合命题，如果存在一个对其变量的真值赋值可以使其为真（即该复合命题为永真式或可满足式），则这个复合命题称为可满足的
  • 不可满足：对于一个复合命题，如果不存在一个对其变量的真值赋值可以使其为真（即该复合命题为矛盾式），则这个复合命题称为不可满足的

§1.4 谓词和量词

• 谓词逻辑
  • 谓词
    • 定义：跟语言学中的谓词概念相似，表示语句的客体具有某种性质，或者某种关系的词项 我们用几个例子来说明：
      • “$x$ 大于 3” 其中 “大于 3” 就是谓词，这整句话可以用 $P(x)$ 表示，其中：
        • $x$为变量，当变量一旦被赋值，则语句 $P(x)$ 就成为了一个命题，就存在了真值
        • $P$ 为谓词，其本身不是命题
        • $P(x)$ 相当于一个 命题函数，在变量为 $x$ 处的值
    • $n$ 位谓词（ $n$ 元谓词）
      • 定义：一般地，涉及 $n$ 个变量 $x_1,x_2,\cdots,x_n$ 的语句可以表示成 \(P(x_1,x_2,x_3,\cdots,x_n)\) 形式为 $P(x_1,x_2,x_3,\cdots,x_n)$ 的语句是 命题函数 $P$ 在 $n$ 元组 $(x_1,x_2,\cdots,x_n)$ 的值，$P$ 也称为 $n$ 位谓语或 $n$ 元谓语 我们可以使用谓词来验证计算机程序，证明当给定合法输入时计算机程序总能产生所期望的输出，其中：
        • 描述合法输入的语句称为 前置条件
        • 程序运行的输出应该满足的条件称为 后置条件
  • 量词
    • 量化：表示在何种程度上谓词对于一定范围的个体成立，在自然语言中，“所有、某些、许多、没有、少量” 等词语都可以用在量化上
    • 论域
      • 定义：数学命题断言某一性质对于变量在某一特定域内所有值均为真，这一特定域称为变量的论域（或 全体域），简称 域

        注意：论域规定了变量 $x$ 所有可能取得值。在使用量词的时候必须指定论域，否则语句的量化就是无定义的

    • 量化类型：
      • 全称量化：一个谓词在所考虑范围内对每一个个体都为真，即对于命题函数 $P(x)$ 在其论域中任取 $x$，$P(x)$ 都为真
        • 定义：$P(x)$ 的 全称量化 是语句 \(P(x) 对x在其论域的所有值为真\)
        • 表示：$P(x)$ 的全称量化用符号 $\forall xP(x)$ 表示，可读作 “对所有 $x,P(x)$” ，或 “对每个 $x,P(x)$”，其中：
          • $\forall$ 称为 全称量词
          • 一个使 $P(x)$ 为假的个体称为 $\forall xP(x)$ 的反例
      • 存在量化：一个谓词在所考虑范围内的一个或多个个体为真，即对于命题函数 $P(x)$ 在其论域中至少存在一个 $x$，使 $P(x)$ 为真
        • 定义：$P(x)$ 的 存在量化 是命题 “论域中存在一个个体 $x$ 满足 $P(x)$”
        • 表示：$P(x)$ 的存在量化用符号 $\exist xP(x)$ 表示，可读作 “对某个 $x$，$P(x)$” 或 “至少有一个 $x$ 满足 $P(x)$”其中：
          • $\exist$ 称为 存在量词
      • 唯一性量化：一个谓词在所考虑范围内只对唯一一个个体为真，即对于命题函数 $P(x)$ 在其论域中只存在一个 $x$，使 $P(x)$ 为真
        • 定义：$P(x)$ 的 唯一性量化 是命题 “论域中存在唯一一个个体 $x$ 满足 $P(x)$”
        • 表示：$P(x)$ 的唯一性量化用符号 $\exist! xP(x)$ 或 $\exist_1 xP(x)$ 表示，可读作 “存在唯一一个 $x$，使 P(x)”，其中：
          • $\exist!$ 或 $\exist_1$称为 唯一性量词
      • 额外的还有其他的无数种量化及量词，如 “恰好存在两个”、“有不超过三个” 等等
    • 量化表达式的否定（量词的德·摩根律）
      • 全称量化 $\forall xP(x)$ 的否定为 $\exist x \lnot P(x)$，即: \(\lnot \forall xP(x) \equiv \exist x \lnot P(x)\)
      • 存在量化 $\exist xP(x)$ 的否定为 $\forall x \lnot P(x)$，即： \(\lnot \exist xP(x) \equiv \forall x \lnot P(x)\) |否定|等价语句|为真的条件|为假的条件| |:-:|:-:|:-:|:-:| |$\lnot \exist xP(x)$|$\forall x \lnot P(x)$|对每个 $x$，$P(x)$ 为假|有 $x$，使 $P(x)$为真| |$\lnot \forall xP(x)$|$\exist x \lnot P(x)$|有 $x$，使 $P(x)$ 为假|对每个 $x$，$P(x)$为真|
    • 有限域上的量词
      • 当一个量词的域使有限的时候，量化语句就可以用命题逻辑来表达
      • 有限域全称量化的命题逻辑表达
        • 对于论域中元素为 $x_1,x_2,\cdots,x_n$ 其中 $n$ 为正整数，则全称量化 \(\forall xP(x) \equiv P(x_1)\land P(x_2) \land \cdots \land P(n)\)
      • 有限域存在量化的命题逻辑表达
        • 对于论域中元素为 $x_1,x_2,\cdots,x_n$ 其中 $n$ 为正整数，则存在量化 \(\exist xP(x) \equiv P(x_1)\lor P(x_2) \lor \cdots \lor P(n)\)
    • 受限域上的量词
      • 表示：限定一个量词的论域通常采用简写表示法，变量必须满足的条件直接放在量词后
      • 例如 $\forall x<0(x^2>0)$ 表示对于每一个满足 $x<0$ 的实数 有 $x^2>0$ 注：受限的全称量化和一个条件语句的全称量化等价，比如 $\forall x<0(x^2>0)$ 等价于 $\forall x(x<0\rightarrow x^2>0)$
    • 量词优先级（按高到低排列）
      1. $\forall,\exist$
      2. 其他逻辑运算符
    • 变量绑定
      • 约束：当量词作用于变量 $x$ 时，我们称变量的这次出现是约束的
      • 自由：如果变量的出现没有被量词约束，或设置为某特定值时，我们说变量的这次出现为自由的
    • 涉及量词的逻辑等价
      • 定义：当且仅当无论用什么谓词带入语句，也无论这些命题函数的变量指定什么论域，它们都有相同的真值，我们称它们为逻辑等价的，用符号 $\equiv$ 表示

§1.5 嵌套量词

• 嵌套量词
  • 定义：一个量词出现在另一个量词的作用域内，如 \(\forall x \exists y(x+y=0)\) 量词范围内的一切都可以认为是一个命题函数，即 $\forall x \exists y(x+y=0)$ 等同于 $\forall x Q(x)$，其中：
  • $Q(x)$ 表示 $\exist yP(x,y)$
  • $P(x,y)$
• 量词嵌套顺序
  • 两个变量的不同量化式 |语句|何时为真|何时为假| |:-:|-|-| |$\forall x\forall y P(x,y)$ $\forall y\forall xP(x,y)$|对每一对 $x、y，P(x,y)$ 均为真|存在一对 $x、y$,使得 $P(x,y)$为假 |$\forall x\exists y P(x,y)$|对每个 $x$,都存在一个 $y$ 使得 $P(x,y)$ 为真|存在一个 $x$,使得 $P(x,y)$ 对每个 $y$ 总为假| |$\exists x\forall yP(x,y)$|存在一个 $x$,使得 $P(x,y)$ 对所有 $y$ 均为真|对每个 $x$,存在一个 $y$ 使得 $P(x,y)$ 为假| |$\exists x\exists y P(x,y)$ $\exists x \exists y P(x,y)$|存在一对 $x、y$,使 $P(x,y)$ 为真|对每一对 $x、y,P(x,y)$ 均为假|
  • 多个变量的不同量化式遵循的规则与两个变量的相同，但要注意量词的使用顺序，如果量词顺序不同，含义也可能不同

    补充概念——乘法逆元：一个实数 $x$ 的乘法逆元是使 $xy=1$ 的实数 $y$

• 嵌套量词的否定
  • 带嵌套量词语句的否定可以通过连续地应用单个量词语句的否定规则得到，即连续地应用量词的 德·摩根律
  • 实例：否定语句 $\forall x \exist y(xy=1)$ \(\begin{aligned} &\neg\forall x \exist y(xy=1)\\ \equiv&\exist x\neg\exist y(xy=1)\\ \equiv&\exist x\forall y\neg(xy=1)\\ \equiv&\exist x\forall y(xy\neq1) \end{aligned}\)

§1.6 推理规则

• 数学证明
  • 概念：数学中的证明是建立数学命题真实性的有效论证，其中：
    • 论证：是指一连串的命题并以结论为最后的命题
    • 有效性：指结论或论证的最后一个命题必须根据论证过程前面的命题或前提的真实性推理得出，即一个论证是有效的当且仅当不可能出现所有前提为真而结论为假的情况
  • 命题逻辑的有效论证
    • 定义 1
      • 命题逻辑中的一个论证是一连串的命题。除了论证中最后一个命题外都叫做前提，最后那个命题叫做结论。一个论证是有效的，如果它的所有前提为真蕴涵着结论为真。
      • 命题逻辑中的论证形式是一连串涉及命题变元的复合命题。无论用什么特定命题来替换其中的命题变元，如果前提均真时结论为真，则称该论证形式是有效的
    • 实例
      • 令 $p,q$ 为命题变量，因为语句 $((p\rightarrow q) \land p)\rightarrow q$ 为永真式，当 $p\rightarrow q$ 和 $p$ 都为真时，必然可以得出 $q$ 为真，因此，语句的这种论证形式是有效的
      • 并且，其中的永真式 $((p\rightarrow q) \land p)\rightarrow q$ 是称为 假言推理 或 分离规则 的推理规则的基础
    • 表达形式： \(\begin{aligned} &命题1\\ &\underline{命题2}\\ \therefore &命题3(结论) \end{aligned} \quad 等同于逻辑表达式: \quad (命题1 \land 命题2) \rightarrow 命题3(结论)\)
  • 命题逻辑的推理规则
    • 消解律
      • 基础：该推理规则基于永真式 $((p\lor q)\land (\lnot p\lor r))\rightarrow(q\lor r)$
      • 消解式：消解规则最后的析取式 $q\lor r$ 称为消解式
      • 变式：
        • 对于永真式：$((p\lor q)\land (\lnot p\lor r))\rightarrow(q\lor r)$
        • 令 $q=r$，可得 $((p\lor q)\land (\lnot p\lor q))\rightarrow q$
        • 令 $r=F$，可得 $(p\lor q)\land(\neg p)\rightarrow q$ 这是永真式，析取三段论规则就基于此式
    • 推理规则表 | 推理规则 | 永真式 | 名称 | |—-|—–|—–| |$p$
      $\underline{p\rightarrow q}$
      $\therefore q$|$(p\land (p \rightarrow q)\rightarrow q)$|假言推理| |$\lnot p$
      $\underline{p\rightarrow q}$
      $\therefore \lnot q$|$(\lnot q\land (p \rightarrow q)\rightarrow \lnot p)$|取拒式| |$p\rightarrow q$
      $\underline{q\rightarrow r}$
      $\therefore p\rightarrow r$|$((p\rightarrow q)\land (q\rightarrow r))\land (p\rightarrow r)$|假言三段论| |$p\lor q$
      $\underline{\lnot p\quad}$
      $\therefore q$|$((p\lor q)\land \lnot p)\rightarrow q$|析取三段论| |$\underline{p\qquad}$
      $\therefore p\land q$|$p\rightarrow (p\lor q )$|附加律| |$\underline{p \land q}$
      $\therefore p$|$(p\land q)\rightarrow p$|化简律| |$p$
      $\underline{q\qquad}$
      $\therefore p\land q$|$((p)\land (q))\rightarrow (p\land q)$|合取律| |$p\lor q$
      $\underline{\lnot p\lor r}$
      $\therefore q\land r$|$((p\lor q)\land (\lnot p\lor r))\rightarrow(q\lor r)$|消解律|
  • 量化命题的推理规则
    • 全称实例
      • 对于给定前提 “ $\forall xP(x)$ 为真”，若 $c$ 为其论域内 任意 的某个元素，则我们可以推出 $P(c)$ 为真
    • 全称引入
      • 对于给定前提 “对论域里的 任意 元素 $c$ 都有 $P(c)$ 为真” ，我们可以推出 $\forall xP(x)$ 为真
    • 存在实例
      • 对于给定前提 “ $\exist xP(x)$ 为真”，我们可以推出其论域内存在 特定 的某个元素 $c$，使 $P(c)$ 为真，但一般我们不知道这个 $c$ 具体是什么，只知道它存在，所以可以给它一个名称 $(c)$ 然后继续论证
    • 存在引入
      • 对于给定前提 “已知论域内有一 特定 的 $c$ 使 $P(c)$ 为真” ，我们可以推出 $\exist xP(x)$ 为真
    • 推理规则表 |推理规则|名称| |-|-| |$\underline{\forall xP(x)}$
      $P(c)$|全称实例| |$\underline{P(c)，任意 c}$
      $\forall xP(x)$|全称引入| |$\underline{\exist xP(x)~~~~~~~~~~~~~~~~~}$
      $P(c)对某个元素 c$|存在实例| |$\underline{P(c)对某个元素 c}$
      $\exist xP(x)$|存在引入|
  • 全称假言推理
    • 定义：既用了全称实例(量化命题推理规则)也用了假言推理(命题推理规则)，我们称这种推理为全称假言推理
    • 规则：如果 $\forall x(P(x)\rightarrow Q(x))$ 为真，并且如果 $P(a)$ 对在全称量词论域中的一个特定元素 $a$ 为真，那么 $Q(a)$ 也肯定为真
    • 描述： \(\begin{aligned} &\forall x(P(x)\rightarrow Q(x))\\ &\underline{P(a),其中 a 是论域中一个特定的元素}\\ \therefore\quad&Q(a) \end{aligned}\) 称为全称假言推理
  • 谬误：
    • 概念：是错误的推理，直接导致无效论证
    • 特征：谬误看上去像是推理规则，但是它们是基于可满足式而不是永真式，这是其与正确有效的推理之间的区别
    • 常见谬误
      • 肯定结论的谬误
        • 论证基础：$((p\rightarrow q)\land q)\rightarrow p$，不是永真式，当 $p=F,q=T$ 时，此逻辑表达式为假，因此基于此式的论证是谬误
      • 否定假设的谬误
        • 论证基础：$((p\rightarrow q)\land\neg p)\rightarrow\neg p$，不是永真式，当 $p=F,q=T$ 时，此逻辑表达式为假，因此基于此式的论证是谬误

§1.7 证明导论

• 定理
  • 定义：正式地，一个定理（又称事实，结论）是一个能够被证明是真的语句。在数学描述中，定理一词通常是用来专指那些被认为至少有些重要的语句，对于不太重要的定理，一般称之为命题
• 证明
  • 定义：证明就是建立定理真实性的一个有效论证。我们通过证明来展示一个定理是真的
  • 分类
    • 形式化证明：在 第六节 中涉及命题和量化命题为真的论证是形式化证明，其中提供了所有步骤，并给出论证中每一步所用到的规则，一般产生自计算机的自动推理系统，在实际的证明过程中，这种方式较复杂且难以理解
    • 非形式化证明：其中每个步骤会用到多于一条的推理规则，有些步骤会被省略，不会显式地列出所用到的假设公理和推理规则，更简单且容易理解
  • 规定：
    • 证明过程中用到的语句可以包括：
      • 公理(或假设)：这些是我们假定为真的语句，可以采用无须定义的原始术语来陈述
      • 定理的前提(如果有的话)
      • 和以前已经被证明的定理
    • 在定理和证明中除公理外所有的其他术语都必须是有定义的。推理规则和其术语的定义一起用于从其他的断言推出结论，并绑定在证明中的每个步骤
  • 方法
    • 直接证明法：从前提开始以结论结束来证明定理的方法叫做直接证明法
      • 条件语句 $p \rightarrow q$ 的直接证明法的构造：
        • 第一步假设 $p$ 为真
        • 第二步用推理规则构造
        • 而第三步表明 $q$ 必须也为真
      • 思路：通过证明如果 $p$ 为真，那么 $q$ 也肯定为真，这样 $p$ 为真且 $q$ 为假的情况永远不会发生从而证明条件语句 $p\rightarrow q$ 为真
    • 间接证明法：不采用直接证明法，即不从前提开始以结论结束来证明这类定理的方法叫做间接证明法
      • 反证法
        • 反证法利用了条件语句 $p\rightarrow q$ 等价于它的逆否命题 $\neg q\rightarrow\neg p$ 这意味着条件语句 $p\rightarrow q$ 的证明可以通过证明它的逆否命题 $\neg q\rightarrow\neg p$ 为真来完成
        • 条件语句 $p \rightarrow q$ 的反证法构造：
          • 将 $\neg q$ 作为前提
          • 再用公理、定义和前面证明过的定理，以及推理规则，证明 $\neg p$ 必须成立

            小策略：当想要证明形如 $\forall x(P(x)\rightarrow Q(x))$ 的命题时，首先评估直接证明法是否可行。可以通过展开前提中的定义开始。然后使用这些前提，加上公理和可用的定理进行推理。如果直接证明法得不到什么结果，尝试反证法，在反证中要假定条件语句的结论为假，并使用直接证明法来证明这蕴含着前提必为假

      • 归谬证明法
        • 假设我们要证明命题 $p$ 是真的。再假定我们能找到一个矛盾式 $q$ 使得 $\neg p\rightarrow q$ 为真。因为 $q$ 是假的，而 $\neg p\rightarrow q$ 是真的 ，所以我们能够得出结论 $\neg p$ 为假，这意味着 $p$ 为真
        • 无论命题 $r$ 是什么，命 题 $r \land\neg r$ 就是矛盾式，所以如果我们能够证明对某个命题 $r$, $\neg p\rightarrow(r\land\neg r)$ 为真，就能证明 $p$ 是真的，这种类型的证明称为归谬证明法
      • 等价证明法
        • 为了证明一个双条件命题的定理，即形如 $p\leftrightarrow q$ 的语句，我们证明 $p\rightarrow q$ 和 $q\rightarrow p$ 都是真的。这个方法的有效性是建立在重言式的基础上： \((p\leftrightarrow q)\leftrightarrow(p\rightarrow q)\land(q\rightarrow p)\)
      • 反例证明法
        • 要证明形如 $\forall xP(x)$ 的语句为假，只要能寻找一个反例，即存在一个例子 $x$ 使 $P(x)$ 为假
        • 当我们遇到一个形如 $\forall xP(x)$ 的语句时，而我们又相信它是假的，或者所有的证明尝试都失败了，就可以寻找一个反例

§1.8 证明的方法和策略

• 分情形证明法
  • 证明如下条件语句 \((p_1\lor p_2\lor\cdots\lor p_n)\rightarrow q\)
  • 推理规则：基于永真式 \([(p_1\lor p_2\lor\cdots\lor p_n)\rightarrow q]\leftrightarrow[(p_1\rightarrow q)\land(p_2\rightarrow q)\land\cdots\land(p_n\rightarrow q)]\) | $p_1$ | $p_2$ | $q$ | $(p_1\lor p_2)\rightarrow q$ | $(p_1\rightarrow q)\land(p_2\rightarrow q)$ | |—-|—-|—|————|—————–| | T | T | T | T | T | | T | T | F | F | F | | T | F | T | T | T | | T | F | F | F | F | | F | T | T | T | T | | F | T | F | F | F | | F | F | T | T | T | | F | F | F | T | T |
  • 思路：
    • 通过分别考虑定理中可能出现的所有情况来证明定理
    • 分别证明每个条件语句 $p_i\rightarrow q(i=1,2,\cdots,n)$ 来证明由命题 $p_1,p_2,\cdots,p_n$ 的析取式组成前提的原条件语句
    • 为了证明条件语句 $p\rightarrow q$ 为真 ，方便的做法是用析取式 $p_1\lor p_2\lor\cdots\lor p_n$ 代替 $p$ 作为条件语句的前提，其中 $p$ 与 $p_1\lor p_2\lor\cdots\lor p_n$ 是等价的
  • 应用情境
    • 当一个证明不可能同时顾及所有情形时，应该考虑采用分情形证明法
    • 当没有明显的思路开始一个证明，而每一种情形的额外信息又能推进证明时，可以寻求分情形证明法
  • 穷举证明法
    • 穷举证明是分情形证明的特例，因为这种证明是要穷尽所有可能性的，所以一般用穷举证明法证明的定理所含的情形较少，能被穷举
  • 不失一般性（缩写为 WLOG）：在分情形证明的过程中，当一些情形经过一些简单的操作后，可以得到与其他的情形相同，那么我们可以省略这种情形，从而缩短证明篇幅，用不失一般性的假设，将几种情形合在一起，用相同的论证完成证明
  • 常见错误：
    • 从个例中得出不正确结论。不管考虑了多少不同的个例，除非每一种可能情况都覆盖了，否则都不能从个例来证明定理
    • 做出了莫须有的假设导致在分情形证明中没有考虑到所有情形
• 存在性证明
  • 定义：形如 $\exist xP(x)$ 的命题，其中 $P$ 是谓词，这类命题的证明称为存在性证明
  • 构造性证明：通过找出一个使得 $P(a)$ 为真的元素 $a$（称为一个物证）来给出 $\exist xP(x)$ 的存在性证明
  • 非构造性证明：即不是找出使 $P(a)$ 为真的元素 $a$，而是以某种其他方式来证明 $\exist xP(x)$ 为真，常用方法是使用归谬证明
• 唯一性证明
  • 某些定理断言具有特定性质的元素唯一存在，要证明这类语句，需要证明存在一个具有此性质的元素，以及没有其他元素具有此性质，唯一性证明的两个部分如下：
    • 存在性：证明存在某个元素 $x$ 具有期望的性质
    • 唯一性：证明如果 $y\neq x$，则 $y$ 不具有期望的性质 我们也可以等价地证明如果 $x$ 和 $y$ 都具有期望的性质，则 $x=y$

      证明存在唯一元素 $x$ 使得 $P(x)$ 为真等同于证明语句 $\exist x(P(x)\land\forall y(y\neq x)\rightarrow\neg P(y)))$

• 证明策略
  • 正向推理
    • 定义：从前提开始，利用这些前提以及公理和已知定理，用导向结论的一系列步骤来构造证明，这类推理称为正向推理
    • 常见应用：证明相对简单结论
  • 反向推理
    • 定义：从结论开始，用一系列步骤来得出前提
  • 改编现有证明
    • 因为现有证明能为新证明提供线索，所以在寻找可用于证明语句方法时，一个很好的思路是利用类似结论现有的证明。一个现有的证明通常可以改编用于证明其他结论。即使不是这样，现有证明中的一些想法也会有所帮助
  • 寻找反例
    • 当面对一个猜想时，可以先试图去证明这个猜想，如果尝试没有成功，可以试图寻找一个反例
  • 开放问题
    • 费马大定理：只要 $n$ 是满足 $n>2$ 的整数，方程 $x^n+y^n=z^n$ 就没有满足 $xyz\neq 0$ 的整数解 $x$、$y$ 和 $z$
  • 其他证明方法
    • 数学归纳法
    • …

第二章 基本结构：集合、函数、序列、求和和矩阵

§2.1 集合

林鹏版

• 定义1：集合是对象的一个无序的聚集，对象也称为集合的元素(element)或成员 (member)。集合包含(contain)它的元素。我们用 $a\in A$ 来表示 $a$ 是集合 $A$ 中一个元素。而记号 $a\notin A$ 表示 $a$ 不是集合 $A$ 中的一个元素。
  • 花名册方法：用 ${}$ 列出所有元素
  • 集合构造器：我们通过描述作为集合的成员必须具有的性质来刻画集合中的那些元素

    如:O={O|O是小于十的自然数} C，复数集

• 定义2：两个集合相等当且仅当它们拥有同样的元素。所以，如果 $A$ 和 $B$ 是集合，则 $A$ 和 $B$ 是相等的当且仅当 $\forall x\in A\longleftrightarrow x\in B)$ 如果 $A$ 和 $B$ 是相等的集合，就记为 $A=B$。
• 空集：有一个特殊的不含任何元素的集合，这个集合称为空集(empty set或null set)，并用表示。空集也可以用 ${}$ 表示(这里我们用一对花括号来表示空集)。经常具有一定性质的元素组成的集合其实就是空集。
• 单元素集：只有一个元素的集合叫做单元素集(singleton set)。
• 朴素集合论
• 定义3：集合 $A$ 是集合 $B$ 的子集当且仅当 $A$ 的每个元素也是 $B$ 的元素。我们用记号 $A\subseteq B$ 表示集合 $A$ 是集合 $B$ 的子集。
• 定理1：对于任意集合 $S$ 都有：
  • （1）$\varnothing \subseteq S$
  • （2）$S \subseteq S$

• 定义4：$S$ 为集合。如果 $S$ 中恰有 $n$ 个不同的元素，这里 $n$ 是非负整数，我们就说 $S$ 是有限集，而 $n$ 是 $S$ 的基数。$S$ 的基数记为 $

  S

  $。

• 定义5：一个集合称为无限的如果它不是有限的。
• 定义6：给定集合 $S$，$S$ 的幂集(power set)是集合 $S$ 所有子集的集合。$S$ 的幂集记为 $\mathcal{P}(S)$。
• 定义7：有序 $n$ 元组(ordered n-tuple) $(a_1,a_2,\cdots,a_n)$ 是以 $a_1$为第1个元素，$a_2$ 为第2个 元素，$\cdots，a_n$ 为第 $n$ 个元素的有序聚集。
  • 序偶：两个有序 $n$ 元组是相等的当且仅当每一对对应的元素都相等。换言之，$(a_1,a_2,\cdots,a_n)=(b_1,b_2,\cdots,b_n)$ 当且仅当对于 $i=1,2,\cdots,n$ 有 $a_1=b_2$。特别地，有序二元组称为序偶(ordered pair)。序偶 $(a，b)$ 和 $(c，d)$ 相等当且仅当 $a=c$ 和 $b=d$。注意 $(a，b)$ 和 $(b，a)$ 不相等，除非 $a=b$。
• 定义8：令 $A$ 和 $B$ 为集合。$A$ 和 $B$ 的笛卡儿积(Cartesian product)用 $A×B$ 表示，是所有序偶 $(a，b)$ 的集合，其中 $a\in A$ 且 $b\in B$。于是， \(A×B=\{(a,b)|a\in A \land b\in B\}\)
• 定义9：集合 $A_1,A_2,\cdots ,A_n$ 的笛卡儿积用 $A_1×A_2×\cdots ×A_n$ 表示，是有序 $n$ 元组 $(a_1,a_2,\cdots ,a_n)$ 的集合，其中 $a_i$ 属于 $A_i$,$i=1,2,\cdots ,n$ 换言之， \(A_1\times A_2\times \cdots A_n=\{(a_1,a_2,\cdots a_n)|a_i\in A_i,i=1,2,\cdots ,n\}\)

• 真值集：给定谓词 $P$ 和论域 $D$，定义 $P$ 的真值集(truth set)为 $D$ 中使 $P(x)$ 为真的元素 $x$ 组成的集合。$P(x$ )的真值集记为${x\in D

  P(x)}$

Tolia 版

• 集合定义：集合是对象的一个无序的聚集，对象也称为集合的元素（element）或成员 （member）。集合包含它的元素。我们用 $a\in A$ 来表示 $a$ 是集合 $A$ 中一个元素。而记号 $a\notin A$ 表示 $a$ 不是集合 $A$ 中的一个元素

  集合可以把其他的集合当做自己的成员

• 表示：通常我们用大写字母来表示集合，用小写字母表示集合中的元素
• 描述：
  • 花名册方法：用 ${}$ 列出集合的所有元素
  • 集合构造器：通过描述作为集合的成员必须具有的性质来刻画集合中的那些元素，当不可能列出集合中所有元素时我们常用这类记法来描述集合
• 文氏图
  • 概念：集合的一种图像表示方法
  • 规则：
    • 全集(universal set) $U$，包含所考虑的全部对象，用矩形框来表示
    • 在矩形框内部，圆形或其他几何图形用于表示集合
    • 有时候用点来表示集合中特定的元素
  • 应用：常用于表示集合之间的关系

    例：$O={x

    x<10,x\in Z^+}$

• 常用集合 集合名称 | 集合表示 ———|——— 自然数集|$N={1,2,3,\cdots}$ 整数集|$Z={\cdots,-2,-1,0,1,2,\cdots}$ 正整数集|$Z^+={1,2,3,\cdots}$ 有理数集|$Q={\frac{p}{q}\mid p\in Z,q\in Z,q\neq0}$ 实数集|$R$ 正整数集|$R^+$ 复数集|$C$
• 特殊集合
  • 空集：不含任何元素的集合，称为空集（empty set或null set），并用 $\varnothing$ 表示。也可以用 ${}$ 表示
  • 单元素集：只有一个元素的集合叫做单元素集（singleton set）

    计算机科学中的数据类型或类型的概念是建立在集合这一概念上。特别地，数据类型或类型是一个集合的名称，连同可以作用在集合对象上的一组操作的集合

• 集合关系
  • 集合相等
    • 定义：两个集合相等当且仅当它们拥有同样的元素。所以，如果 $A$ 和 $B$ 是集合，则 $A$ 和 $B$ 是相等的当且仅当 $\forall x\in A\leftrightarrow x\in B)$ 如果 $A$ 和 $B$ 是相等的集合，就记为 $A=B$
    • 相等证明：要想证明两个集合 $A$ 和 $B$ 相等，就证明 $A\subseteq B$ 和 $B\subseteq A $
  • 集合包含（子集）
    • 定义：集合 $A$ 是集合 $B$ 的子集当且仅当 $A$ 的每个元素也是 $B$ 的元素。我们用记号 $A\subseteq B$ 表示集合 $A$ 是集合 $B$ 的子集
    • 定理：对于任意集合 $S$ 都有：
      1. $\varnothing \subseteq S$
      2. $S \subseteq S$
    • 子集证明：
      • 证明 $A$ 是 $B$ 的子集：要证明 $A\subseteq B$，需要证明如果： $x$ 属于 $A$ 则 $x$ 也属于 $B$
      • 证明 $A$ 不是 $B$ 的子集：要证明 $A\nsubseteq B$，需要找到一个 $x\in A$ 但 $x\notin B$
• 集合大小
  • 有限集合

    • 定义：$S$ 为集合。如果 $S$ 中恰有 $n$ 个不同的元素，这里 $n$ 是非负整数，我们就说 $S$ 是有限集，而 $n$ 是 $S$ 的基数。$S$ 的基数记为 $

      S

      $

  • 无限集合
    • 定义：一个集合称为无限的如果它不是有限的
• 幂集
  • 作用：检查一个集合的元素的所有可能组合看它们是否满足某种性质
  • 定义：给定集合 $S$，$S$ 的幂集（power set）是集合 $S$ 所有子集的集合。$S$ 的幂集记为 $\mathcal{P}(S)$
• 笛卡尔积
  • 有序 $n$ 元组
    • 意义：有时候元素聚集中其次序是很重要的。由于集合是无序的，所以就需要用一种不同的结构来表示有序的聚集。这就是有序 $n$ 元组
    • 定义：有序 $n$ 元组（ordered n-tuple） $(a_1,a_2,\cdots,a_n)$ 是以 $a_1$为第1个元素，$a_2$ 为第2个 元素，$\cdots，a_n$ 为第 $n$ 个元素的有序聚集
    • 有序 $n$ 元组相等：两个有序 $n$ 元组是相等的当且仅当每一对对应的元素都相等，即$(a_1,a_2,\cdots,a_n)=(b_1,b_2,\cdots,b_n)$ 当且仅当对于 $i=1,2,\cdots,n$ 有 $a_i=b_i$
    • 序偶：特别地，有序二元组称为序偶（ordered pair）。序偶 $(a,b)$ 和 $(c，d)$ 相等当且仅当 $a=c$ 和 $b=d$。注意 $(a,b)$ 和 $(b,a)$ 不相等，除非 $a=b$
  • 两个集合的笛卡尔积定义：令 $A$ 和 $B$ 为集合。$A$ 和 $B$ 的笛卡儿积(Cartesian product)用 $A×B$ 表示，是所有序偶 $(a，b)$ 的集合，其中 $a\in A$ 且 $b\in B$。于是： \(A×B=\{(a,b)|a\in A \land b\in B\}\)
  • 多个集合的笛卡尔积定义：集合 $A_1,A_2,\cdots ,A_n$ 的笛卡儿积用 $A_1×A_2×\cdots ×A_n$ 表示，是有序 $n$ 元组 $(a_1,a_2,\cdots ,a_n)$ 的集合，其中 $a_i$ 属于 $A_i$,$i=1,2,\cdots ,n$ 换言之， \(A_1\times A_2\times \cdots A_n=\{(a_1,a_2,\cdots a_n)|a_i\in A_i,i=1,2,\cdots ,n\}\)

• 真值集：给定谓词 $P$ 和论域 $D$，定义 $P$ 的真值集(truth set)为 $D$ 中使 $P(x)$ 为真的元素 $x$ 组成的集合。$P(x)$ 的真值集记为${x\in D

  P(x)}$

• 朴素集合论（可了解）

§2.2 集合运算

• 并集
  • 定义：令 $A$ 和 $B$ 为集合。集合 $A$ 和 $B$ 的并集，用 $A\cup B$ 表示，是一个集合，它包含 $A$ 或 $B$ 中或同时在 $A$ 和 $B$ 中的元素 一个元素 $x$ 属于 $A$ 和 $B$ 的并集当且仅当 $x$ 属于 $A$ 或 $x$ 属于 $B$，即： \(A\cup B=\{x\mid x\in A\lor x\in B\}\)
  • 扩展并集
    • 定义：一组集合的并集是包含那些至少是这组集合中一个集合成员的元素的集合 \(A_1\cup A_2\cup\cdots\cup A_n=\bigcup_{i=1}^nA_i\)
• 交集
  • 定义：令 $A$ 和 $B$ 为集合。集合 $A$ 和 $B$ 的交集，用 $A\cap B$ 表示，是一个集合，它包含同时在 $A$ 和 $B$ 中的那些元素 一个元素 $x$ 属于 $A$ 和 $B$ 的交集当且仅当 $x$ 属于 $A$ 而且 $x$ 属于 $B$，即： \(A\cap B=\{x\mid x\in A\land x\in B\}\)
  • 不相交：两个集合称为是不相交的，如果它们的交集为空集
  • 扩展交集
    • 定义：一组集合的交集是包含那些属于这组集合中所有成员集合的元素的集合 \(A_1\cap A_2\cap\cdots\cap A_n=\bigcap_{i=1}^nA_i\)
• 容斥原理
  • 概念：在计数时，必须注意没有重复，没有遗漏。为了使重叠部分不被重复计算，人们研究出一种新的计数方法，这种方法的基本思想是：先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理

    将在第 6 章和第 8 章详细讨论这一原理和其他的计数技术

• 差集（补集）
  • 定义：令 $A$ 和 $B$ 为集合。$A$ 和 $B$ 的差集，用 $A-B$ 表示（有时候也记为 $A\setminus B$ ），是一个集合，它包含属于 $A$ 而不属于 $B$ 的元素。$A$ 和 $B$ 的差集也称为 $B$ 相对于 $A$ 的补集 一个元素 $x$ 属于 $A$ 和 $B$ 的差集当且仅当 $x\in A$ 且 $x\notin B$，即 \(A-B=\{a\mid x\in A\land x\notin B\}\)
• 补集
  • 定义：令 $U$ 为全集。集合 $A$ 的补集，用 $\overline{A}$ 表示，是 $A$ 相对于 $U$ 的补集。所以，集合A的补集是 $U—A$ 一个元素 $x$ 属于 $\overline{A}$ 当且仅当 $x\notin B$，即 \(\overline{A}=\{x\in U\mid x\notin A\}\)
• 集合恒等式 恒等式 | 名称 ——-|—– $A\cap U=A$
  $A\cup \varnothing=A$ | 恒等律 $A\cup U=U$
  $A\cap \varnothing=\varnothing$ | 支配律 $A\cup A=A$
  $A\cap A=A$ | 幂等律 $\overline{(\overline{A})}=A$ | 补律 $A\cup B=B\cup A$
  $A\cap B=B\cap A$ | 交换律 $A\cup(B\cup C)=(A\cup B)\cup C$
  $A\cap(B\cap C)=(A\cap B)\cap C$ | 结合律 $A\cup(B\cap C)=(A\cup B)\cap (A\cup C)$
  $A\cap(B\cup C)=(A\cap B)\cup (A\cap C)$ | 分配律 $\overline{A\cap B}=\overline{A}\cup\overline{B}$
  $\overline{A\cup B}=\overline{A}\cap\overline{B}$ | 德·摩根律 $A\cup(A\cap B)=A$
  $A\cap(A\cup B)=A$ | 吸收律 $A\cup\overline{A}=U$
  $A\cap\overline{A}=\varnothing$ | 互补律

  注：由于集合的并集和交集满足结合律，所以只要 $A$、$B$、$C$ 为集合，则 $A\cup B\cup C$和$A\cap B\cap C$ 均有定义，即这样的记号是无二义性的。也就是说，我们不需要用括号来指明哪个运算在前，因为 $A\cup(B\cup C) = (A\cup B)\cup C$ 及 $A\cap(B\cap C)=(A\cap B )\cap C$

  • 集合相等证明：证明集合相等的一种方法是证明每一个是另一个的子集。为了证明一个集合是另一个集合的子集，可以通过证明一个元素如果属于第一个集合，必定属于第二个集合。通常用直接证明法来证明
    • 成员表
      • 集合恒等式还可以通过成员表来证明。我们考虑一个元素可能属于的集合的每一种组合，并验证在相同集合组合中的元素同属于恒等式两边的集合。用 1 表示元素属于一个集合，用 0 表示元素不属于一个集合
      • 例：分配律的成员表 | $A$ | $B$ | $C$ | $B\cup C$ | $A\cap(B\cup C)$ | $A\cap B$ | $A\cap C$ | $A(\cap B)\cup(A\cap C)$ | |—|—|—|—–|———-|—–|——|————–| | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | 1 | 1 | 0 | 1 | 1 | 1 | 0 | 1 | | 1 | 0 | 1 | 1 | 1 | 0 | 1 | 1 | | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
• 集合的计算机表示
  • 无序存储：把集合的元素无序地存储起来
    • 弊端：进行集合的并集、交集或差集等运算时会非常费时
  • 全集有序表示
    • 假定全集 $U$ 是有限的（而且大小合适，使 $U$ 的元素个数不超过计算机能使用的内存量）。首先为 $U$ 的元素任意规定一个顺序，例如$a_1,a_2,\cdots,a_n$。于是可以用长度为 $n$ 的位串来表示 $U$ 的子集 $A$ ：其中位串中第 $i$ 位 是 1，如果 $a_i$ 属于 $A$；是 0，如果 $a_i$ 不属于 $A$

§2.3 函数

• 定义：令 $A$ 和 $B$ 为非空集合。从 $A$ 到 $B$ 的函数 $f$ 是对元素的一种指派，对 $A$ 的每个元素恰好指派 $B$ 的一个元素。如果 $B$ 中元素 $b$ 是唯一由函数 $f$ 指派给 $A$ 中元素 $a$ 的，则我们就写成 $f(a)=b$。如果 $f$ 是从 $A$ 到 $B$ 的函数，就写成 $f:A\rightarrow B$。

  评注 函数有时也称为映射（mapping）或者变换（transformation）

• 定义域、陪域、像、原像和值域
  • 定义：如果 $f$ 是从 $A$ 到 $B$ 的函数，我们说 $A$ 是 $f$ 的定义域(domain)，而 $B$ 是 $f$ 的陪域(codomain)。如果 $f(a)=b$，我们说 $b$ 是 $a$ 的像(image)，而 $a$ 是 $b$ 的原像(preimage)。$f$ 的值域 (range)或像是A中元素的所有像的集合。如果 $f$ 是从 $A$ 到 $B$ 的函数，我们说 $f$ 把 $A$ 映射 (map)到 $B$。
  • 当两个函数有相同的定义域、陪域，定义域中的每个元素映射到陪域中相同的元素时，这两个函数是相等的。
  • 实值函数与整数值函数
    • 定义：一个函数称为是实值函数如果其陪域是实数集合，称为整数值函数如果其陪域是整数集合。
    • 特点：具有相同定义域的两个实值函数或两个整数值函数可以相加和相乘。
• $f_1,f_2$ 的运算
  • 令 $f_1$ 和 $f_2$ 是从 $A$ 到 $R$ 的函数，那么 $f_1十f_2$ 和 $f_1f_2$ 也是从 $A$ 到 $R$ 的函数，其定义为对于任意 $x\in A$ \((f_1+f_2)(x)=f_1(x)+f_2(x)\\ (f_1f_2)(x)=f_1(x)f_2(x)\) $f_1十f_2$ 和 $f_1f_2$ 的定义是利用 $f_1$ 和 $f_2$ 在 $x$ 的值来计算它们在 $x$ 的值。
• 定义域的子集和陪域的子集的关系
  • 令 $f$ 为从 $A$ 到 $B$ 的函数，$S$ 为 $A$ 的一个子集。$S$ 在函数 $f$ 下的像是由 $S$ 中元素的 像组成的 $B$ 的子集。我们用 $f(S)$ 表示 $S$ 的像，于是： \(f(S)=\{t|\exist s\in S(t=f(s))\}\)
• 单射函数
  • 函数 $f$ 称为是一对一(one-to-one)或单射函数(injection)，当且仅当对于 $f$ 的定义域中的所有 $a$ 和 $b$ 有 $f(a)=f(b)$ 蕴含 $a=b$。一个函数如果是一对一的，就称为是单射的(injective)
• 满射函数
  • 一个从 $A$ 到 $B$ 的函数 $f$ 称为映上(onto)或满射(surjection)函数，当且仅当对每个 $b\in B$ 有元素 $a\in A$ 使得 $f(a)=b$。一个函数 $f$ 如果是映上的就称为是满射的(surjective)。
• 双射函数
  • 函数f是一一对应(one-to-one correspondance)或双射 (bijection)函数，如果它既 是一对一的又是映上的。这样的函数称为是双射的(bijective)。
• 函数的递增和递减（定义域和陪域都是实数集子集的函数）
  • 递增:如果对 $f$ 的定义域中的 $x$ 和 $y$，当 $x<y$ 时有 $f(x)\leq f(y)$ 称为是递增的;
  • 严格递增：如果当 $x<y$ 时 有$f(x)<f(y)$ 称为是严格递增的;
  • 递减：如果对 $f$ 的定义域中的 $x$ 和 $y$，当 $x<y$ 时有 $f(x)\geq f(y)$ 称为是递减的;
  • 严格递减：如果当 $x<y$ 时有 $f(x)>f(y)$，称为是严格递减的;(定义中严格一词意味着严格不等式)
• 反函数
  • 令 $f$ 为从集合 $A$ 到集合 $B$ 的一一对应。$f$ 的反函数(或逆函数)是这样的函数，它指派给 $B$ 中元素 $b$ 的是 $A$ 中使得 $f(a)=b$ 唯一元素 $a$。$f$ 的反函数用 $f^{-1}$ 表示。于是，当 $f(a)=b$ 时 $f^{-1}(b)=a$。
  • 可逆与不可逆
    • 一一对应关系称为可逆的(invertible)，因为可以定义这个函数的反函数。如果函数不是一 一对应关系，就说它是不可逆的(not invertible)，因为这样的函数不存在反函数。
• 函数的合成
  • 令 $g$ 为从集合 $A$ 到集合 $B$ 的函数，$f$ 是从集合 $B$ 到集合 $C$ 的函数，函数 $f$ 和 $g$ 的合成(composition)，记作 $f\circ g$，定义为对任意 $a\in A$ \((f\circ g)(a)=f(g(a))\)
• 序偶集合

  • 令 $f$ 为从集合 $A$ 到集合 $B$ 的函数，函数 $f$ 的图像是序偶集合 ${(a，b)

    a\in A且f(a)=b)}$

• 下取整函数
  • 下取整函数(floor)指派给实数 $x$ 的是小于或等于x的最大整数。下取整函数在 $x$ 的值用 $[x]$ 表示。上取整函数(ceiling)指派给实数 $x$ 的是大于或等于 $x$ 的最小整数。上取整函数在 $x$ 的值用 $[x]$ 表示。
• 阶乘函数
  • $f(n)=n!$ 阶乘函数（详细可了解）
• 全函数
  • 一个从集合 $A$ 到集合 $B$ 的部分函数(partial function) $f$ 是给 $A$ 的一个子集(成为 $f$ 的定义域(domain of definition))中的每个元素 $a$ 指派唯一的一个 $B$ 中的元素 $b$。集合 $A$ 和 $B$ 分别称为 $f$ 的域和陪域。我们说 $f$ 对于 $A$ 中但不在f的定义域中的元素无定义(undefined)。 当 $f$ 的定义域等于 $A$ 时，就说 $f$ 是全函数(total function)。

    评注：我们写 $f:A\rightarrow B$ 来表示 $f$ 是一个从 $A$ 到 $B$ 的部分函数。注意这个和函数的记号是一致的。该记号的上下文可以用来判断f是部分函数还是全函数。

§2.4 序列与求和

• 序列
  • 概念：序列是一种用来表示有序列表的离散结构。例如 $1,2,3,5,8$ 是一个含有五项的序列，而 $1,3,9,27,81,\cdots,3^n$ 是一个无穷序列
  • 定义：序列（sequence）是一个从整数集的一个子集（通常是集合 ${0,1,2,\cdots}$ 或集合 ${1,2,3,\cdots}$）到一个集合 $S$ 的函数。用记号 $a_n$ 表示整数 $n$ 的像。称 $a_n$ 为序列的一个项（term）
  • 描述：用记号 ${a_n}$ 描述序列，要注意一个序列记号 ${a_n}$与集合 的记号有冲突，因此要注意选择表达序列的字母不要与其他的集合重复
  • 几何级数（等比数列）
    • 定义：几何级数是如下形式的序列 \(a,ar,ar^2,\cdots,ar^n\) 其中初始项 $a_1$ 和公比 $r$ 都是实数

      几何级数是指数函数 $f(x)=ar^x$ 的离散的对应体

  • 算数级数（等差数列）
    • 定义：算术级数是如下形式的序列 \(a,a+d,a+2d,\cdots,a+nd\) 其中初始项 $a$ 和公差 $d$ 都是实数

      注：算术级数是线性函数 $f(x)=dx+a$ 的离散的对应体

  • 特殊的整数序列
    • 离散数学中的一类共性问题是为了构造序列的项而寻找闭公式、递推关系或者某种一般规则
    • 给定初始项，当试图推导出一个可能的公式、递推关系或序列项的某种一般规则时，尝试寻找这些项的一种模式。再观察能否确定一项是如何可以从它前面的项产生得到。我们需要思考这些问题：
      • 是否有相同值连续出现？即相同的值在一行中出现多次。
      • 是否给前项加上某个常量或与序列中项的位置有关的量后就得出后项？
      • 是否给前项乘以特定量就得出后项？
      • 是否按照某种方式组合前面若干项就可以得出后项？
      • 是否在各项之间存在循环？
• 递推关系
  • 定义：关于序列 ${a_n}$ 的一个递推关系（recurrence relation）是一个等式，对所有满足 $n\ge n_0$ 的 $n$，它把 $a_n$ 用序列中前面项即 $a_0,a_1,\cdots,a_{n-1}$ 中的一项或多项来表示，这里 $n_0$ 是一个非负整数。如果一个序列的项满足递推关系，则该序列就称为是递推关系的一个解。（一个递推关系称为递归地定义了一个序列。我们将在第 5 章解释这个不同的术语）
  • 斐波那契数列
    • 定义：斐波那契数列 $f_0,f_1,f_2,\cdots$ 由初始条件 $f_0=0,f_2=1$ 和下列递推关系所定义 \(f_n=f_{n-1}+f{n-2}\quad n=2,3,4,\cdots\)
  • 闭公式（显式公式）
    • 当我们为序列的项找到一个显式公式，称为闭公式（closed formula）时，我们就说解决了带有初始条件的递推关系
    • 未找到准确的概念解释，猜测为通项公式一类，存疑
  • 迭代
    • 定义：重复执行一系列运算步骤，从前面的量依次求出后面的量的过程，称为迭代
    • 正向替换：从初始条件出发找到连续的项直到 $a_n$ 为止
    • 反向替换：从 $a_n$ 开始迭代时将其表示为序列中前面的项直到可以用 $a_1$ 来表示
• 求和
  • 概念：对于数列 $a_n$ 中项 $a_m,a_m+1,\cdots,a_n$ 的和，我们用求和记号来描述 \(\sum_{j=m}^n a_j\quad或\quad\sum_{m\le j\le n}a_j\) 来表示，读作 $a_j$ 从 $j=m$ 到 $j=n$ 的和，其中变量 $j$ 称为求和下标
  • 定理：如果 $a$ 和 $r$ 都是实数且 $r\neq O$ ，则 \(\sum_{j=0}^nar^j= \begin{cases} \frac{ar^{n+1}-a}{r-1}\quad(r\neq1)\\ (n+1)a\quad r=1\\ \end{cases}\)
  • 一些常用求和公式： 和 | 闭形式 —|——- $\sum_{k=0}^nar^k(r\neq0)$ | $\frac{ar^{n+1}-a}{r-1},(r\neq1)$ $\sum_{k=1}^nk$ | $\frac{n(n+1)}{2}$ $\sum_{k=1}^nk^2$ | $\frac{n(n+1)(2n+1)}{6}$ $\sum_{k=1}^nk^3$ | $\frac{n^2(n+1)^2}{4}$ $\sum_{k=0}^\infty x^k,|x|<1$ | $\frac{1}{1-x}$ $\sum_{k=1}^\infty x^{k-1},|x|<1$ | $\frac{1}{(1-x)^2}$

集合的基数

• 集合相等

  • 定义：对于有限集合 $A$ 和 $B$ 有相同的基数（cardinality），当且仅当存在从 $A$ 到 $B$ 的 一个一一对应。当 $A$ 和 $B$ 有相同的基数时，就写成 $

    A

    =

    B

    $

• 集合比较

  • 定义：如果存在一个从 $A$ 到 $B$ 的一对一函数，则 $A$ 的基数小于或等于 $B$ 的基数，并写成 $

    A

    \le

    B

    $。再者，当 $

    A

    <

    B

    $ 并且 $A$ 和 $B$ 有不同的基数时，我们说 $A$ 的基数小于 $B$ 的基数，并写成 $

    A

    <

    B

    $

• 可数与不可数集合：
  • 现在把无限集分为两组，一组是与自然数集合有相同的基数，另一组是具有不同的基数

  • 定义：一个集合或者是有限集或者与自然数集具有相同的基数，这个集合就称为可数的（countable）。一个集合不是可数的，就称为不可数的（uncountable）。如果一个无限集 $S$ 是可数的，我们用符号 $\alef$。来表示集合 $S$ 的基数。写作 $

    S

    =\alef_0$，并说 $S$ 有基数“阿里夫零”

  • 集合可数的证明：证明集合是可数的，就要给出这个集合与正整数集合之间的一个一一对应。无限集是可数的当且仅当可以把集合中的元素排列成序列（下标是正整数）。这是因为从正整数集合到集合 $S$ 的一一对应关系 $f$ 可以用序列 $a_1,a_2,\cdots,a_n,\cdots$ 表示，其中 $a_1=f(1),a_2=f(2),\cdots,a_n=f(n),\cdots$
  • 不可数集合的证明：我们可以假定集合是可数的，然后试图导出一个矛盾
  • 定理：
    • 如果 $A$ 和 $B$ 是可数集合，则 $A\cup B$ 也是可数集合

    • 如果 $A$ 和 $B$ 是集合且 $

      A

      \le

      B

      $ 和 $

      B

      \le

      A$，则 $

      A

      =

      B

      $。换言之，如果存在一对一函数 $f$ 从 $A$ 到 $B$ 和 $g$ 从 $B$ 到 $A$，则存在 $A$ 和 $B$ 之间的一一对应函数

• 可计算与不可计算函数
  • 定义：—个函数称为是可计算的（computable）, 如果存在某种编程语言写的计算机程序 能计算该函数的值。如果一个函数不是可计算的，就说是不可计算的（umcomputable）
  • 连续统假设

    • 可以证明 $Z^+$ 的幂集和实数集 $R$ 具有相同的基数。换言之，我们知道 $

      \mathcal{P}(Z^+)

      =

      R

      =c$，这里 $c$ 表示实数集的基数

    • 康托的一个重要定理表明一个集合的基数总是小于其幂集的基数。故有 $

      Z^+

      <

      \mathcal{P}(Z^+)

      $。我们将这个结论重写为 $\alef_0<2^\alef$，这里用记号 $2^{

      S

      }$ 表示集合 $S$ 的备集的基数。还有，注意关系 $

      \mathcal{P}(Z^+)

      =

      R

      $ 可以表示为 $2^\alef=c$

    • 这就导致了著名的连续统假设（contimuun hypothesis），它阐述了不存 在介于 $\alef_0$ 和 $c$ 之间的基数 $X$。换言之，连续统假设说明了不存在集合 $A$ 使得正整数集合的基数小于 $

      A

      $ 而 $

      A

      $ 又小于实数集的基数 $c$。可以证明最小的无限基数形成一个无限序列 $\alef_0<\alef_1<\alef_2<\cdots$。如果我们假定连续统假设为真，就可以得出结论 $c=\alef_1$，故有 $2^\alef=\alef_1$

矩阵

• 矩阵
  • 定义：
    • 矩阵 （matrix） 是矩形状的数组。$m$ 行 $n$ 列的矩阵称为 $m\times n$ 矩阵。行数和列数相 同的矩阵称为方阵（square）。如果两个矩阵有同样数量的行和列且每个位置上的对应项都相等，则这两个矩阵是相等的
    • 令 $m$ 和 $n$ 是正整数，并令 \(\bm A= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n}\\ a_{21} & a_{22} & \cdots & a_{2n}\\ \vdots & \vdots & & \vdots\\ a_{m1} & a_{m2} & \cdots & a_{mn}\\ \end{bmatrix}\)
      • $\bm A$ 的第 $i$ 行是 $1\times n$ 矩阵 $\begin{bmatrix}a_{i1} & a_{i2} & \cdots & a_{in}\end{bmatrix}$
      • $\bm A$ 的第 $j$ 列是 $m\times 1$ 矩阵 $\begin{bmatrix}a_{1j}\ a_{2j}\ \vdots\ a_{mj}\\end{bmatrix}$
      • $\bm A$ 的第 $(i,j)$ 元素（element） 或项（entry） 是元素 $a_{ij}$ 即 $\bm A$ 的 第 $i$ 行第 $j$ 列位置上的数
      • 矩阵 $\bm A$ 的一个方便的简写符号是写成 $\bm A=[a_{ij}]$，表示 $\bm A$ 是其第 $(i,j)$ 元素为 $a_{ij}$ 的矩阵
• 矩阵算数
  • 矩阵的和：令 $\bm A=[a_{ij}]$ 和 $\bm B=[b_{ij}]$ 为 $m\times n$ 矩阵。$\bm A$ 和 $\bm B$ 的和，记 作 $\bm A+\bm B$，是其第 $(i,j)$ 元 素为 $a_{ij}+b_{ij}$ 的矩阵。换言之，$\bm A+\bm B=[a_{ij}+b_{ij}]$
  • 矩阵的积：令 $\bm A$ 为矩阵，$\bm B$ 为 $k\times n$ 矩阵。$\bm A$ 和 $\bm B$ 的乘积，记作 $\bm {AB}$，是一个 $m\times n$ 矩阵，其第 $(i,j)$ 元素等于 $A$ 的第 $i$ 行与 $B$ 的第 $j$ 列对应元素的乘积之和。换言之，如果 $\bm{AB}=[c_{ij}]$，则 \(c_{ij}=a_{i1}b_{1j}+a_{i2}{b_{2j}}+\cdots+a_{ik}b_{kj}\)
• 矩阵转置
  • 定义：令 $\bm A=[a_{ij}]$ 为 $m\times n$ 矩阵。$\bm A$ 的转置（transpose），记作 $A^T$ 是通过交换 $\bm A$ 的行和列所得到的 $m\times n$ 矩阵。换言之，如果 $\bm A^T=[b_{ij}]$，则 $b_{ij}=a_{ji},i-1,2,\cdots,n;j=1,2,\cdots,m$
• 矩阵对称：一个矩阵是对称的当且仅当它是方阵且相对于主对角线（对所有 $i$，由第 $i$ 行第 $j$ 列的元素组成）是对称的
• 0-1 矩阵
  • 定义：所有元素非 0 即 1 的矩阵称为 0-1 矩阵
  • 矩阵的并与交
    • 令 $\bm A = [a_{ij}]$ 和 $B = [b_{ij}]$ 为 $m\times n$ 阶 0-1 矩阵。$\bm A$ 和 $\bm B$ 的并是 0-1 矩阵，其 $(i,j)$ 元素为 $a_{ij}\lor b{ij}$。$\bm A$ 和 $\bm B$ 的并记作 $\bm A\lor\bm B$ $\bm A$ 和 $\bm B$ 的交是 0-1 矩阵，其 $(i,j)$ 元素是 $a_{ij}\land b_{ij}$。$\bm A$ 和 $\bm B$ 的交记作 $\bm A\land\bm B$
  • 布尔积
    • 定义：令 $\bm A=[a_{ij}]$ 为 $m\times k$ 阶 0-1 矩阵，$\bm B=b_{ij}$ 为 $k\times n$ 阶 0-1 矩阵。$\bm A$ 和 $\bm B$ 的布尔积 （Boolean product），记作 $A\odot B$，是 $m\times n$ 矩阵 $[c_{ij}]$，其中 \(c_{ij}=(a_{i1}\land b_{ij})\lor(a_{i2}\land b_{2j})\lor\cdots\lor(a_{ik}\land b{kj})\)

      注意A 和B 的布尔积的计算方法类似于这两个矩阵的普通乘积，但要用运算 $\lor$ 代替加法,用运算 $\land$ 代替乘法

第3章 算法

3.1算法

3.1.1引言

定义 1 算法是进行一项计算或解决一个问题的准确指令的有限序列。

算法的性质算法一般都共有一些性质。当描述算法时牢记这些性质是有益的。这些性质是：

• 输入 算法从一个指定的集合得到输入值。
• 输出 对每个输入值集合，算法都要从一个指定的集合中产生输出值。输出值就是问题的解。
• 确定性 算法的步骤必须是准确定义的。
• 正确性 对每一组输入值，算法都应产生正确的输出值。
• 有限性 对任何输入算法都应在有限（可能很多）步之后产生期望的输出。
• 有效性 算法的每一步都应能够准确地在有限时间内完成。
• 通用性 算法过程应该可以应用于期望形式的所有问题，而不只是用于一组特定的输入值。

3.1.2搜索算法

线性搜索 算法称为线性搜索或顺序搜索算法。线性搜索算法从比较 x 和 $a_1$ 开始。如果 $x = a_1$，那么解就是 $a_1$ 的位置，即 1。当 $x \neq a_1$ 时，比较 x 和 $a_2$。如果 $x = a_2$，解就是 $a_2$ 的位置，即 2。当 $x \neq a_2$ 时，比较 x 与 $a_3$。继续这一过程，逐一比较 $x$ 和表中的每一项直到找到匹配为止，这里解就是该项的位置除非没有匹配。如果已搜索了整个表却不能定位 x，那么解是 0。

二分搜索 当表中各项以升序出现时可以用这一算法（例如，如果项为数值，则按从最小到最大顺序排列；如果是单词，则可以按字典序或字母序排列）。这个算法称为二分搜索算法。它是通过比较要搜索的元素与表的中间项进行的。然后此表就分成两个较小的长度相等的子表，或其中较短的列表比另一个少一项。根据与中间项的比较结果， 可以将搜索局限于一个合适的子表继续进行。

3.1.3排序

假定有一个集合元素的列表。再假设有一种方式可以给集合的元素排序。排序(sorting)就是把这些元素排成一个列表，其中元素按照升序排列。

冒泡排序 冒泡排序(bubblesort)是最简单的，但不是最有效的排序算法之一。冒泡排序通过连续比较相邻的元素，如果相邻元素顺序不对就交换相邻元素，从而把一个表排列成升序。 为了实现冒泡排序，我们执行基本操作，即交换一个较大元素与紧跟其后的较小元素，从表头开始完整地执行一遍。迭代这个过程直到排序完成。

插入排序 插入排序（insert sort）是一种简单的排序算法，但通常不是最有效的。为了给 n 个元素的表排序，插入排序从第二个元素开始。插入排序将这第二个元素与第一个元素比较：如果它不大于第一个元素，就把它插入到第一个元素前面；如果它大于第一个元素，就把它插入到第一个元素后面。此时前两个元素顺序正确。然后第三个元素与第一个元素比较，如果它大于第一个元素，再与第二个元素比较；它将插入到前三个元素中的正确位置上。

3.1.4贪婪算法

一种最简单的方法常常能导致最优化问题的一个解。这种方法在每一步都选择最好的选项，而不是通盘考虑可能导致最优解的全部步骤序列。在每一步都选择看起来“最好的”选项的算法称为贪婪算法（greedyalgorithm）。一旦贪婪算法求出了一个可行解，就要确定它是否找到了一个最优解。为此，要么证明这个解是最优的，要么证明该算法产生了一个非最优解的反例。

3.1.5停机问题

停机问题 (halting problem) 它询问是否存在一个过程(procedure)能做这件事：该过程以一个计算机程序以及该程序的一个输入作为输入，并判断该程序在给定输入运行时是否最终能停止。显然，如果真的存在，有这样一个过程是非常方便的。在编写或者调试程序的时候，能够判断一个程序是否进入无限循环是非常有帮助的。然而，1936年图灵证明这样的过程是不存在的。

3.2函数的增长

3.2.2大O记号

定义 1 令 f 和 g 为从整数集或实数集到实数集的函数。如果存在常数 C 和 k 使得只要当 $x > k$ 时就有 \(\lvert f(x) \rvert \le C\lvert g(x)\rvert\) 我们就说 $f(x)$ 是 $O(g(x))$ 的。这个可以读作 $f(x) 是大 Og(x)的$ 评注 直觉上，$f(x)$ 是 $O(g(x))$ 的定义是说当 x 无限增长时，$f(x)$ 的增长慢于 $g(x)$ 的某个固定的倍数。

大 O 记号定义中的常数 C 和 k 称为 f(x) 是 O(g(x)) 的关系的凭证(witness)。为了建立 f(x) 是 O(g(x))，我们只需要这一关系的一对凭证。即要证明 f(x) 是 O(g(x)) 的，我们需要找出一对常数 C 和 k，即凭证，使得只要当 $x > k$ 时就有 $\lvert f(x) \rvert \le C\lvert g(x) \rvert$。

注意当有 $f(x)$ 是 $O(g(x))$ 的关系的一对凭证时，就会有无限多对凭证。要明白这一点，注意如果 C 和 k 是一对凭证，那么任意一对 C’ 和 k’（其中 $C < C’$ 和 $k < k’$ 也是一对凭证，因为只要当 $x > k’ > k$ 时就有 $\lvert f(x) \rvert \le C\lvert g(x) \rvert \le C’ \lvert g(x) \rvert$。 评注 f(x）是 O(g(x)) 的事实有时写作 f(x) = O(g(x))。不过这一写法中的等号并不代表真正的相等，而是告诉我们对于这些函数定义域中足够大的数而言，函数 f 和 g 的值之间有不等式成立。然而，$f(x) \in O(g(x))$ 这样的写法也是可接受的，因为 $O(g(x))$ 可以表示那些是 $O(g(x))$ 函数的集合。

3.2.3一些重要函数的大O估算

定理 1 令 $f(x) = a_n^n + a_{n-1}x^{n-1} + \cdots + a_1x +a_0$，其中 $a_0, a_1, \cdots, a_{n-1},a_n$ 为实数。那么 f(x) 是 $O(x^n)$ 的。

3.2.4函数组合的增长

定理 2 假定 $f_1(x)$ 是 $O(g_1(x))$ 的，$f_2(x)$ 是 $O(g_2(x))$ 的，那么 $(f_1+f_2)(x)$ 是 $O(max\lvert g_1(x)\rvert, \lvert g_2(x)\rvert))$ 的。 推论 1 假定 $f_1(x)$ 和 $f_2(x)$ 都是 $O(g(x))$ 的，那么 $(f_1+f_2)(x)$ 也是 $O(g(x))$ 的。

定理 3 假定 $f_1(x)$ 是 $O(g_1(x))$ 的，$f_2(x)$ 是 $O(g_2(x))$ 的。那么 $(f_1f_2)(x)$ 是 $O(g_1(x)g_2(x))$ 的。

3.2.5大 $\Omega$ 与大 $\Theta$ 记号

大 O 记号广泛用于描述函数的增长，但它也有局限性。特别是，当 f(x) 是 O(g(x)) 时，我们只有用 g(x) 来估计对于大 x 值的 f(x) 大小的一个上限。可是，大 O 记号不能提供对大 x 值的 f(x) 大小的一个下限。为此，我们使用大 $\Omega$ 记号。当希望给出函数 f(x) 的相对于参照函数 g(x) 的上限和下限时，我们使用大 $\Theta$ 符号。

定义 2 令 f 和 g 为从整数集合或实数集合到实数集合的函数。如果存在正常数 C 和 k 使得当 x>k 时有 \(\lvert f(x) \rvert \ge C\lvert g(x) \rvert\) 我们说 f(x) 是 $\Omega(g(x))$ 的，这个读作 $f(x) 是大 \Omega g(x) 的$。

定义 3 令 f 和 g 为从整数集合或实数集合到实数集合的函数。如果 f(x) 是 $\Theta(g(x))$ 的且 $f(x)$ 是 $\Omega(g(x))$ 的，我们就说 f(x) 是 $\Omega(g(x))$ 的。当 $f(x)$ 是 $\Theta (g(x))$ 时就说 f(x) 是大西塔 g(x)的，即 f(x) 是 g(x) 阶的，或 f(x) 和 g(x) 是同阶的。

定理 4 令 $f(x) = a_n^n + a_{n-1}x^{n-1} + \cdots + a_1x +a_0$，其中 $a_0, a_1, \cdots, a_{n-1},a_n$ 为实数且 $a_n \neq 0$。那么 f(x) 是 $x^n$ 阶的。

3.3算法的复杂度

3.3.5理解算法的复杂度

• 常量复杂度 \(\Theta (1)\)
• 对数复杂度 \(\Theta (\log n)\)
• 线性复杂度 \(\Theta (n)\)
• 线性对数复杂度 \(\Theta (n\log n)\)
• 多项式复杂度 \(\Theta (n^b)\)
• 指数复杂度 \(\Theta (b^n), b>1\)
• 阶乘复杂度 \(\Theta (n!)\)

Powered by HTML, markdown, LaTeX
Copyright © 2020 | Tolia
All Rights Reserved.