2021FALL《离散数学》笔记

内容纲要

第一章集合论

基本概念

朴素集合论：直观描述集合的概念；
公理集合论：用一组公理刻画集合的性质。

集合的表示

枚举法：{1,2,3}，{1,2,3,…}，{1,2,…,100}；
谓词法：{x|p(x)}：满足性质p的所有元素所构成的集合；
文氏图：用来示意集合的图形，可直观地表示集合间的关系；矩形表示全集，圆表示其他集合，点表示元素。

集合之间的关系

平凡子集：任意集合 $A$ 都有两个平凡子集： $A$ 和 $\varnothing$ 。

集合族

集合中的每个元素都是集合。
下标集：集合族中的元素用带下标的字母表示，所有下标组成的集合称为该集合族的下标集。

幂集

集合A的所有子集所组成的集合称为A的幂集，记为P(A)。

n元组和笛卡尔积

集合：若干对象组合成的整体，无序组合。
序列：若干对象组合成的整体，有序组合。
n元组： $n \in N$ ，由 $n$ 个对象组成的序列(串) $a_1,a_2,\dots,a_n$ 称为n元组，记为 $(a_1, a_2,\dots, a_n)$ ； $a_i$ 称为该n元组的第 $i$ 个坐标。
二元组也称为有序偶。

笛卡尔积： $n \in N$ ，集合 $D_1, D_2, ..., D_n$ ， $\{(d_1, d_2,...,d_n)|1 \leqslant i \leqslant n, d_i \in D_i\}$ 称为集合 $D_1, D_2,..., D_n$ 的笛卡尔积。

$A\timesB=B\timesA$ 的充要条件是： $A=\varnothing || B= \varnothing || A=B$ 。

广义并交

无限多个集合的并和交不能从多个集合的并和交运算简单地推广，正如无穷级数求和不能从多个实数的和运算简单地推广。

集合族A的广义并：所有A的元素中的元素所组成的集合，记为 $\cup A$ 。
集合族A的广义交：A中所有元素的共公元素所组成的集合，记为 $\cap A$ 。

$\cup \varnothing = \varnothing$ ；
$\cap \varnothing$ 无定义。

集合运算的基本恒等式

幂等律： $A \cup A = A, A \cap A = A$
同一律： $A \cup \varnothing = A, A \cap U = A$
零律： $A \cap \varnothing = \varnothing, A \cup U = U$
排中律： $A \cup \overline{A} = U$
矛盾律： $A \cap \overline{A} = \varnothing$
双重否定： $\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)$
吸收律： $A\cup (A \cap B) = A, A\cap (A \cup B) = A$
德摩根律： $\overline{A \cup B} = \overline{A} \cap \overline{B}, \overline{A \cap B} = \overline{A} \cup \overline{B}$
差律： $A - B = A \cap \overline{B}$

对偶原理

对偶命题：若 $P$ 是关于集合的命题，其中至多包含并、交和补三种集合运算（不含差运算）， $P^*$ 是将 $P$ 中的 $\cup 、\cap 、\varnothing 、U$ 分别替换为 $\cap 、\cup 、U、\varnothing$ 而得到的命题，则称 $P$ 与 $P^*$ 互为对偶命题。若 $P=P^*$ ，则称 $P$ 为自对偶命题。
对偶原理： $P = P^*$

有限集合的计数

对于有限集合 $A$ 、 $B$ ，以下命题恒为真：
(1) $|A \cup B|=|A|+|B|-|A \cap B|$ （容斥原理）
(2) $|A \times B| = |A|\cdot|B|$
(3) $|P(A)| = 2^{|A|}$

罗素悖论

朴素集合论中存在悖论
罗素: $S=\{x|x\notin x\}$

习题

1.1-1 给出集合{-3,-2,-1,0,1,2,3}的谓词表示法。

解： $\{x|x\in Z, -3 \leqslant x \leqslant 3\}$

1.1-2 判断2和{2}是否是下列集合的元素。
（1）{x|x是大于1的整数}
（2）{x|x是某整数的平方}
（3）{2,{2}}
（4）{{2},{{2}}}
（5）{{2},{2,{2}}}
（6）{{{2}}}

解：
(1) 2是；{2}不是。
(2) 都不是。
(3) 都是。
(4) 2不是；{2}是。
(5) 2不是；{2}是。
(6) 都不是。

1.1-3 下列哪些命题成立？哪些不成立？为什么？
(1) $\varnothing \in \{\varnothing, \{\varnothing\}\}$
(2) $\varnothing \subseteq \{\varnothing, \{\varnothing\}\}$
(3) $\{\varnothing\} \subseteq \{\varnothing, \{\varnothing\}\}$
(4) $\{\{\varnothing\}\} \subseteq \{\varnothing, \{\varnothing\}\}$

解：
(1) T
(2) T
(3) T
(4) T

1.2-1 设A是ECNU二年级学生的集合，B是ECNU必须学习离散数学的学生的集合。请用A和B表示ECNU不必学习离散数学的二年级的学生的集合。

解： $A-B$

1.2-2 设A是集合，下列命题是否必定成立?
（1） $A\in P(A)$
（2） $A\subseteq P(A)$
（3） $\{A\}\in P(A)$
（4） $\{A\}\subseteq P(A)$

解：
(1) 成立。
(2) 不成立。
(3) 不成立。
(4) 成立。

1.2-3 设A和B是任意集合，证明 $P(A)\cap P(B)=P(A\cap B)$ 。

证明： $\forall X \in P(A)\cap P(B)，X \in P(A) \&\& X\in P(B), X\subseteq A \&\& X\subseteq B, X\subseteq A\cap B, X \in P(A\cap B)$ ；

1.2-4 设A是任意集合， $A^3=(A\timesA)\timesA=A\times(A\timesA)$ 是否成立？为什么？

解： $(A×A) \neq A$ ，不满足交换律成立的充分条件，所以不成立。

1.2-5 设A、B、C和D是集合，证明：若A、B、C和D均非空集，且 $A\timesB=C\timesD$ ，那么 $A=C$ 且 $B=D$ 。

证明： $\forall x_1 \in A, \forall x_2 \in B$ ， $(x_1, x_2) \in A×B$ ，又因为 $A\timesB=C\timesD$ ，所以 $(x_1, x_2) \in C×D$ ，从而有 $x_1 \in C, x_2 \in D$ ，则 $A\subseteq C, B\subseteq D$ 。同理可证明 $C\subseteq A, D\subseteq B$ ，得到结论 $A=C$ 且 $B=D$ 。

1.2-6 编写一个程序，输入任意一个自然数n，输出 $P({1,2,\dots,n})$ 的所有元素。

解：使用01进制的思路，n个元素化为n位01进制数，0表示不将此位元素加入集合，1表示将此位元素加入集合。比如4个元素，0000代表 $\varnothing$ ，0001代表 $\{a_4\}$ ，1011代表 $\{a_1, a_3, a_4\}$ ，只要把从到 $2^n-1$ 中间的所有数的二进制表示求出来，就能求出所有的子集了。最后调整一下输出格式就行了。

#include <bits/stdc++.h>
using namespace std;

void printPowerSet(char *set, int set_size) {
    int pow_set_size = pow(2, set_size);
    int counter, j;
    for (counter = 0; counter < pow_set_size; counter++) {
        for (j = 0; j < set_size; j++) {
            if (counter & (1 << j))
                cout << set[j];
        }
        cout << endl;
    }
}

int main() {
    int n;
    cin >> n;
    char set[10001] = {'\0'};
    for (int i = 0; i < n; i++)
        set[i] = i + '1';
    printPowerSet(set, n);
    return 0;
}

1.3-1 设A、B和C是集合，证明：若 $A\cap B=\varnothing$ ，则 $A-B=A$ 。

证明：
$A-B = A \cap \overline{B} = (A \cap \overline{A}) \cup (A\cap \overline{B}) = A \cap (\overline{A} \cup \overline{B}) = A \cap \overline{A\cap B} = A \cap U = A。$

1.3-2 设A、B和C是集合，请给出 $(A-B)\cap (A-C)=\varnothing$ 成立的充要条件。

解：
$(A-B)\cap (A-C)$
$=(A\cap \overline{B})\cap(A\cap \overline{C})$
$=A\cap \overline{B} \cap A \cap \overline{C}$
$=A\cap \overline{B} \cap \overline{C}$
$=A\cap \overline{B\cup C}$
充要条件为 $A \subseteq B\cup C$ 。

1.3-3 设A和B是集合，定义集合运算对称差 $\oplus$ 如下： $A⊕B=(A-B)\cup (B-A)$ 。证明 $A⊕B=(A\cup B)-(A\cap B)$ 。

证明：
$(A-B)\cup (B-A)$
$=(A\cap \overline{B})\cup(B\cap \overline{A})$
$=((A\cap \overline{B})\cup B)\cap ((A\cap \overline{B})\cup \overline{A})$
$=(A\cup B) \cap (\overline{B} \cup \overline{A})$
$=(A\cup B) \cap \overline{A\cap B}$
$=(A\cup B)-(A\cap B)$

1.3-4 设A、B、C和D是任意集合，证明 $(A×C)\cap (B×D) = (A\cap B)×(C\cap D)$ 。

证明：
$A×C = \{(x_1, x_3)|x_1 \in A, x_3 \in C\}, B×D = \{(x_2, x_4)|x_2 \in B, x_4 \in D\}$
$(A×C)\cap (B×D) = \{(x, y)|x \in A \&\& x \in B, y\in C \&\& y \in D\} = \{(x, y)|x\in A \cap B, y \in C \cap D\}=(A\cap B)×(C\cap D)$

1.3-5 证明： $\overline{\underset{\beta \in B}{\cup} A_\beta} = \underset{\beta \in B}{\cap}\overline{A_\beta}$

证明：
$\forall x, x\in \overline{\underset{i\in I}{\cup}A_i} \Leftrightarrow \forall x, x\notin \underset{i\in I}{\cup}A_i \Leftrightarrow \forall i, i\in I, x\notin A_i \Leftrightarrow \forall i, i\in I, x\in \overline{A_i} \Leftrightarrow x\in \underset{i\in I}{\cap}\overline{A_i}.$ 证毕。

1.3-6 证明： $\forall n \in N$ ， $A_n是集合$ ，令 $B_n = A_n - \cup ^{n-1}_{k=1}A_k$ ，有 $\underset{n\in N}{\cup}A_n = \underset{n \in N}{\cup}B_n$ 。

证明：
$B_n = A_n - \cup ^{n-1}_{k=1}A_k \Rightarrow B_n \subseteq A_n \Rightarrow \underset{n\in N}{\cup}B_n \subseteq \underset{n \in N}{\cup}A_n$ .
$\forall x, x\in \underset{n \in N}{\cup}A_n \Rightarrow \exist n\in N, x\in A_n.$
$\exist n_0\in N, x\in A_n.$
$\forall x, x\in \underset{n \in N}{\cup}A_n\Rightarrow \forall x, x\in A_{n_0}, x\notin \cup ^{n0-1}_{k=1}A_k \Rightarrow x\in B_{n_0}\Rightarrow x\in \underset{n \in N}{\cup}B_n\Rightarrow \underset{n\in N}{\cup}A_n \subseteq \underset{n \in N}{\cup}B_n$ .
证毕。

1.4-1 以1开头或者以00结束的不同的字节（8位的二进制串）有多少个?

解:
$|A| = 2^7, |B| = 2^6, |A\cap B| = 2^5, |A\cup B| = |A| + |B| - |A\cap B| = 2^7 +2^6 - 2^5 = 5 × 32 = 160$

1.4-2 在1~200的正整数中,
(1) 能被3或5整除, 但不能被15整除的正整数共有多少个？
(2)与15互素的正整数(即与15之间的最大公因子为1的那些正整数)共有多少个？

解：
(1) $66+40-13-13=80$ .
(2) $200-66-40+13 =107$ .

第二章数论基础

初等数论的几个基本事实

整除和带余除法

b整除a：存在整数 $q$ 使得 $a=bq$ ，记为 $b|a$ (否则 $b∤a$ )
b是a的因数(约数、因子)，a是b的倍数： $b|a$
b是a的真因数：且 $a\neqb$

任何非零整数整除0，0不整除任何整数(未定义)
任何整数都是0的因数，0不是任何整数的因数(未定义)
0是任何整数的倍数，0没有倍数(未定义0倍数)

带余除法：整数 $a$ 和 $b$ ， $b\neq0$ 。存在整数 $q$ 和 $r$ ，使 $a=bq+r (0\leqr<|b|)$ ，并且 $q$ 和 $r$ 由 $a$ 和 $b$ 唯一决定)

a被b除的不完全商：q
a被b除的余数：r，记为a mod b

素数

素数(质数)：整数，大于1，只有1和自身两个正因数
合数：整数，大于1，非素数

$p|a_1a_2..a_n -> p|a_1$ 或 $p|a_2$ ... $p|a_n$
任何大于1的整数可以被唯一地分解为素数之积。

素数的个数无穷。
证明：
假设素数只有 $p_1,p_2,...,p_n$ 。
考虑正整数 $m=p_1p_2..p_n+1$ ， $m>1$ ，那么 $m$ 有大于1的素因数 $p$ 且为 $p_1,p_2,...,p_n$ 中的一个，与 $m$ 能被 $p$ 整除矛盾。

大于1的整数a除了1以外的最小正因数q必为素数。

欧拉函数： $f(n): n\in N$ ，不大于n并与n互素的正整数的个数。
$f(n) = n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_n})$

第三章命题逻辑

命题

命题：能判断真假的陈述句。
命题的真值：命题的判断结果，只有0和1两种。
原子命题和复合命题：
(1) 一个命题若不能被分解成最简单的陈述句, 则称为简单命题或原子命题；
(2) 若一个命题是由几个简单陈述句通过联结词联结而成的, 则称为复合命题。

逻辑联结词

命题符号化：将简单命题用字母表示。
逻辑联结词：联结简单命题组成复合命题的联结符号，有自己特殊的逻辑关系涵义。

基础的逻辑联结词

否定式
合取式
析取式
蕴含式
等价式

命题公式

将命题变量用联结词和括号按一定逻辑关系联结起来的符号串称为合式公式或命题公式。
合式公式定义如下：

单个命题变量是合式公式, 称为原子命题公式。
若A是合式公式, 则(┐A)也是合式公式。
若A,B是合式公式, 则(A∧B), (A∨B), (A→B), (A↔B)也是合式公式。
只有有限次地应用(1)～(3)形成的符号串才是合式公式。
设A是合式公式，B是A中的一部分，若B是合式公式，则称B为A的子公式。

n元命题公式：将 $p_1,...,p_n$ 用若干逻辑联结词组合而成的命题公式，记作 $A(p_1,...,p_n)$ 。

赋值：将 $n$ 个0，1作为一组n元命题公式的输入，如果这组输入使得命题 $A=1$ ，则称其为 $A$ 的成真赋值，反之则为成假赋值。

设A是一个命题公式：

若A在各种赋值下取值总为1, 则称A是永真式或重言式。
若A在各种赋值下取值总为0, 则称A是永假式或矛盾式。
若A不是矛盾式, 则称A为可满足式。

注：

A是可满足式当且仅当A至少存在一个成真赋值。
重言式必是可满足式, 但反之不真。
可用真值表来判断公式的类型：
(1) 若真值表最后一列全为1, 则公式为重言式;
(2) 若真值表最后一列全为0, 则公式为矛盾式;
(3) 若真值表最后一列至少有一个1, 则公式为可满足式。

等值演算

等值：两个命题公式的任意赋值都有一样的真值。
有相同的真值表，说明等价式为重言式。

等值演算的基本恒等式

范式

简单析取式合简单合取式：

命题变量及其否定统称作文字。
仅由有限个文字构成的析取式称作简单析取式;
仅由有限个文字构成的合取式称作简单合取式。

析取范式与合取范式：

由有限个简单合取式构成的析取式称为析取范式;
由有限个简单析取式构成的合取式成为合取范式;
析取范式与合取范式统称为范式。

范式存在定理：任一命题公式都存在着与之等值的析取范式与合取范式。

求给定公式的范式的步骤：
(1) 消去联结词→和↔; (蕴涵和等价恒等式)
(2) 否定号┐的消去(双重否定)或内移(德摩根律);
(3) 利用∨对∧的分配律求合取范式;利用∧对∨的分配律求析取范式。

极小项：在含有n个命题变量的命题公式A[简单合取式]中, 若每个命题变量和它的否定式恰好出现一个且仅出现一次, 并且命题变量或其否定式按下标从小到大或按字典序排列), 则称公式A[简单合取式]为极小项。

极大项：在含有n个命题变量的命题公式A[简单析取式]中, 若每个命题变量和它的否定式恰好出现一个且仅出现一次, 并且命题变量或其否定式按下标从小到大或按字典序排列), 则称公式A[简单析取式]为极大项。

主范式：如果由n个命题变量构成的析取范式(合取范式)中所有的简单合取式(简单析取式)都是极小项(极大项), 则称该析取式(合取式)为主析取范式(主合取范式)。

主范式定理：

设 $m_i$ 与 $M_i$ 是命题变量 $p_1, p_2, \dots,p_n$ 形成的极小项和极大项, 则 $\neg m_i =M_i, \neg M_i = m_i$ 。
任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是唯一的。

主范式的求法：

真值表
(1) 构造命题公式的真值表;
(2) 找到成真(假)赋值, 转化为极小(大)项;
(3) 把极小(大)项联结为主析取(合取)范式。
等值演算
(1) 先通过等值推演将所给的命题公式化为析取范式(合取范式);
(2) 补齐变量；
(3) 消去重复变量和矛盾式。

主范式可以判断公式的类型，并判断两个公式是否等值。
设公式A中含n个变量, 则
(1) A为重言式当且仅当A的主析取范式含全部2n 个极小项；
(2) A为矛盾式当且仅当A的主析取范式不含任何极小项。(此时，记A的主析取范式为0)；
(3) A为可满足式当且仅当A的主析取范式中至少含一个极小项。

联结词的完备集

定理:S = {┐,∧,∨}是联结词完备集。 {┐,∨}和{┐,∧}是极小的.

逻辑推理的基本模型

(1)逻辑推理就是从若干前提(命题)依据一些推理规则推出一个结论(命题);
(2)逻辑推理的正确性取决于前提和结论的构成形式, 与具体内容无关;
(3)数理逻辑将日常推理中的结构(形式)抽取出来建立数学模型, 这个模型适用于所有学科;
(4)正确的推理形式对应于一个永真的蕴含式, 其前件是所有前提的合取, 其后件是结论。

数学模型：
$H_1,H_2,...,H_n,C$ 命题公式
(1) $(H_1\wedge H_2\wedge ...\wedge H_n)\rightarrow C$ 是永真公式
(2)前提： $H_1,H_2,...,H_n$ ;结论： $C$ 。

推理正确, 并不能保证结论C一定为真。因为前提可能是假的。

推理正确性的方法：
(1)验证蕴含式是否是永真公式(不能实际使用)
(2)给出从前提推出结论的形式证明

常用推理规则：
(1)置换规则： $\forall 命题公式A,B, 若A=B, 则A \Rightarrow B$
(2)假言推理规则： $p,p\rightarrow q \Rightarrow q$
(3)附加规则： $p \Rightarrow p\vee q$
(4)化简规则： $p\wedge q \Rightarrow p$
(5)拒取式规则： $\neg q,p\rightarrow q \Rightarrow \neg p$
(6)假言三段论规则： $p\rightarrow q,q\rightarrow r \Rightarrow p\rightarrow r$
(7)析取三段论规则： $\neg q,p\vee q \Rightarrow p$
(8)构造性二难推理规则： $p\vee s,p\rightarrow q,s\rightarrow t \Rightarrow q\vee t$
(9)破坏性二难推理规则： $\neg q\vee \neg t,p\rightarrow q,s\rightarrow t \Rightarrow \neg p\vee \neg s$
(10)合取引入规则： $p,q \Rightarrow p\vee q$

习题

3.1-1 下列哪些语句是命题？
(1) 2是正数吗？
(2) $x^2+x+1=0$
(3) 我要上学。
(4) 明年2月1日下雨。
(5) 如果股票涨了，那么我就赚钱。

解：
4，5是命题。

3.1-2 将当当网的图书高级搜索符号化：http://search.dangdang.com/AdvanceSearch/AdvanceSearch.aspx?c=0

解：
$A(p_1,p_2,...,p_n)=p_1 \wedge p_2 \wedge ... \wedge p_n$ .

3.1-3 请将语句“除非你已满16周岁, 否则只要你身高不足1.2米就不能乘公园的滑行铁道。”符号化。

解：
p:你满16周岁。
q:你身高足够1.2米。
r:你能乘公园的滑行铁道。
$(\neg p \wedge \neg q)\rightarrow \neg r$ .

3.1-4 p, q, r为如下命题：p：你得流感了；q：你错过了最后的考试；r：这门课你通过了。请用自然语言表达命题 $(p\rightarrow \neg r)\vee (q\rightarrow \neg r)$ .

解：
如果你得流感了，或者你错过了最后的考试，那么你这门课不通过。

3.1-5 判断下列命题的真值
(1)若1+1=3, 则2+2=4
(2)若鸟会飞, 则1+1=3

解：
1，0

3.1-6 构造一个只含命题变量p, q和r的命题公式A, 满足：p, q和r的任意一个赋值是A的成真赋值当且仅当p, q和r中恰有两个为真。

解：
$(p\wedge q\wedge \neg r)\vee(p\wedge r\wedge \neg q)\vee(r\wedge q \wedge \neg p)$ .

3.2-1 将下列两个命题符号化,并分别用真值表和等值演算的方法证明所得到的那两个命题公式是等值的。
(1)你不会休息所以就不会工作,你没有丰富的知识所以你就不会工作；
(2)你会工作所以一定会休息并具有丰富的知识。

解：
p:你会休息；q:你会工作；r:你有丰富的知识。
$A= (\neg p \rightarrow \neg q)\vee (\neg r\rightarrow \neg q) = (\neg p \vee \neg r)\rightarrow \neg q = q\rightarrow(p\wedge r)= B$ .

3.2-2 用等值演算的方法证明命题恒等式 $p\rightarrow (q\rightarrow p) = \neg p\rightarrow (p\rightarrow \neg q)$ .

证明：
$p\rightarrow (q\rightarrow p) = \neg(\neg p \rightarrow \neg q)\rightarrow \neg p = \neg (p \vee \neg q)\rightarrow \neg p = (\neg p \wedge q)\rightarrow \neg p = (p\vee \neg q)\vee \neg p;$
$\neg p\rightarrow (p\rightarrow \neg q) = p\vee (\neg p \vee \neg q);$
上述两式相等，证毕。

3.2-3 一教师要从3名学生A,B和C中选派1～2人参加市级科技竞赛,需满足以下条件：
(1)若A去,则C同去；
(2)若B去,则C不能去；
(3)若C不去,则A或B可以去。
问该如何选派？

解：
$A\rightarrow C.$
$B\rightarrow \neg C.$
$\neg C\rightarrow (A\vee B).$

方案1： $A=1 \Rightarrow C=1, B=0.$
方案2： $B=1 \Rightarrow C=0 \Rightarrow (A\vee B)=0 \Rightarrow A=0.$
方案3： $C=1 \Rightarrow B=0$ ， $A$ 可以取0.

第四章一阶逻辑

命题逻辑的推理模型过于简单，无法全面描述实际的逻辑推理。
命题逻辑最基本的元素是原子命题, 无法描述原子命题的内部结构及其相互之间的逻辑关系。
命题逻辑无法反映苏格拉底三段论的正确性。

一阶逻辑是比命题逻辑更精细的推理模型。

谓词和量词

原子命题的分解：

个体词，命题中独立存在的个体，主语。
- 个体常量：具体、特定的个体词。常用小写字母a, b等等表示。
- 个体变量：抽象或泛指某个体的个体词。常用小写字母x, y等等表示。
- 个体域：所有个体的集合, 即个体变量的取值集合。
- 全总个体域：宇宙间所有个体所组成个体域, 默认个体域。
谓词，刻画个体的性质或者它们之间的关系，谓语。
- n元谓词：关于n个个体词的谓词。谓词常用大写字母表示。

注：命题可视为0元谓词。

量词：

全称判断，表示个体域所有的元素都具有某个性质。
特称判断，表示个体域部分的元素具有某个性质。

谓词公式

项的递归定义：

个体词是项
若 $f(x_1,x_2,...,x_n)$ 是n元函数， $t_1,t_2,...,t_n$ 是项，则 $f(t_1,t_2,...,t_n)$ 是项
所有的项都是通过有限次使用上述规则后得到的符号串

在谓词公式 $\forall xA$ 和 $\exist xA$ 中, x为称指导变量, 量词的辖域为A。辖域中的变量x称为约束变量。A中的非约束变量称为自由变量。

谓词公式的解释I由下面四部分组成：
(1)非空个体域集合D
(2)分别指定公式中的自由变量和常量符号为D中的元素
(3)指定公式中的n元函数符号为 $D_n$ 到D的函数
(4)指定公式中的n元谓词符号为 $D_n$ 到{0,1}的函数

谓词公式可以用命题公式代换。

谓词公式的等值演算和前束范式

一阶逻辑的推理

涉及量词的推理规则：

US规则
UG规则
ES规则
EG规则

第五章关系

二元关系

设 $X$ 和 $Y$ 是集合：

X到Y的二元关系： X×Y的子集
X上的二元关系： X到X的二元关系
XY满足关系R(xRy)： $(x,y)\in R$ ，x是y的前件, y是x的后件

X到Y的空关系： $\varnothing$
X到Y的全关系：X×Y
X上的恒等关系： $I_x:\{(x,x)|x\in X\}$

函数：X到Y的函数f(f：X→Y)是X到Y的二元关系, 且具有下列性质：

$dom(f)=X$
$\forall x\in X, y_1,y_2\in Y,(x,y_1)\in f \wedge (x,y_2)\in f\rightarrow y_1=y_2$ 成立

二元关系的表示：

表示集合的方法
关系图
关系矩阵

关系矩阵和关系图的性质：
(1)关系矩阵的元素之和=关系的基数
(2)关系矩阵的元素之和=关系图中的箭头的个数
(3)集合上的关系的关系矩阵必定是方阵
(4)关系成为函数的充要条件：

关系图中, 左边每个顶点的出度均为1
关系矩阵中, 每行有且仅有一个1

关系的基本运算

关系的逆：Y-X的关系
关系的复合：R是X到Y的关系, S是Y到Z的关系， $R^oS$ 是X到Z的关系
关系的幂：R与R的多次复合

关系的基本运算定理

关系的特殊性质及其闭包

关系的特殊性质：

自反关系
对称关系
传递关系

关系的性质与关系矩阵的性质：
(1)关系自反：其矩阵对角线全1
(2)关系反自反：其矩阵对角线全0
(3)关系对称：其矩阵对称
(4)关系反对称：其矩阵任意对称位置上至少有一个0

关系的闭包：包含R、具有性质P最小的X上的关系。

闭包的存在性问题：关系R的P闭包可能不存在，反自反闭包、反对称闭包可能不存在。

一	二	三	四	五	六	日
« 1月
1	2	3	4	5	6	7
8	9	10	11	12	13	14
15	16	17	18	19	20	21
22	23	24	25	26	27	28
29	30

第一章 集合论