离散数学期末 · 逻辑、集合与关系
这张图讲什么
「离散数学期末 · 逻辑、集合与关系」是 SeekFlaw 编辑团队整理的思维导图,分 7 个一级分支:命题逻辑基础、范式与推理、谓词逻辑、集合、二元关系的性质与闭包、等价关系与偏序关系、函数,共 76 个节点、75 张记忆卡。
这张图按「命题逻辑基础 → 范式与推理 → 谓词逻辑 → 集合 → 二元关系 → 等价与偏序 → 函数」七块组织。建议先把五个联结词和基本等值式练熟,再做主析取、主合取范式和推理的构造证明;接着学谓词符号化和前束范式;然后做集合运算与容斥原理的计算,再到关系的五种性质与闭包,最后是等价关系、偏序关系的哈斯图和函数的单射、满射。本图不含图论和代数系统,可单独复习。
5 个要点
- 命题逻辑基础:命题逻辑研究命题的真假怎样由简单命题决定。
- 范式与推理:范式把公式化成标准形式,主析取、主合取范式唯一,可用来判断公式类型和等值。
- 谓词逻辑:谓词逻辑能刻画个体和量词。
- 集合:集合运算与恒等式是证明和计算的基础。
- 二元关系的性质与闭包:关系是有序对的集合。
适用:大学期末复习。用法:点开任一节点先自己答,再翻面核对。
发布于
一句话:这张图把「离散数学期末 · 逻辑、集合与关系」整理成 76 个节点、75 张记忆卡;点开节点翻面就能看答案。
覆盖命题与谓词逻辑、等值演算、主范式与推理、集合运算与容斥、二元关系的性质与闭包、等价与偏序、函数,含自编算例,适合期末复习。点开任一节点翻面看答案,登录后可存进自己的空间,按遗忘曲线复习。
SeekFlaw 求瑕是面向初中、高中、考研、考公考前速记的思维导图与记忆卡平台:把课件、讲义变成思维导图,节点翻面就是记忆卡,按遗忘曲线安排复习。
76 个节点 · 75 张记忆卡。作者:SeekFlaw 编辑团队;发布于 2026-11-17。
先看这 3 条
- 什么是命题,哪些语句不是命题:命题是能判断真假的陈述句,真值唯一:非真即假。
- 幂集是什么,有多少个元素:集合 $A$ 的幂集 $P(A)$ 是它的 所有子集 组成的集合;若 $|A|=n$,则幂集有 $2^n$ 个元素,包括空集和 $A$ 本身。
- 什么样的关系是函数:$f$ 是从 $A$ 到 $B$ 的函数,要求:定义域 等于整个集合 A (每个元素都有象),且每个 $x$ 的象 唯一 。
命题逻辑基础
- 什么是命题,哪些语句不是命题:命题是能判断真假的陈述句,真值唯一:非真即假。疑问句、祈使句、感叹句不是命题;含未确定变量的式子(如「$x+1\gt 3$」)和悖论(如「我现在说的这句话是假的」)也 不是命题 。 例 「2 加 2 等于 4」是真命题;「明天是晴天」是命…
- 五个联结词的真值是怎样规定的:否定 $\lnot p$:$p$ 的真值取反;合取 $p\land q$:同真才真;析取 $p\lor q$(相容或):同假才假;条件 $p\to q$: 仅当前件真、后件假时为假 ;双条件 $p\leftrightarrow q$:${…
- 自然语言怎样符号化成条件、双条件:「如果 $p$ 则 $q$」「只要 $p$ 就 $q$」「$p$ 仅当 $q$」都符号化为 $p\to q$;「只有 $p$ 才 $q$」符号化为 $q\to p$( 前后件要颠倒 );「$p$ 当且仅当 $q$」为 $p\leftrig…
- 什么是重言式、矛盾式、可满足式:公式在所有赋值下都为真,称重言式(永真式);在所有赋值下都为假,称矛盾式(永假式);至少有一个赋值使它为真,称可满足式。重言式一定是可满足式;$n$ 个命题变项的真值表有 $2^n$ 行。 例 $p\lor\lnot p$ 是重言式;$p…
- 常用的基本等值式有哪些(一):双重否定 $\lnot\lnot p\Leftrightarrow p$;幂等 $p\lor p\Leftrightarrow p$;交换、结合;分配 $p\land(q\lor r)\Leftrightarrow(p\land q)\l…
- 蕴含等值式、双条件等值式和假言易位是什么:蕴含等值式 $p\to q\Leftrightarrow\lnot p\lor q$;假言易位(逆否)$p\to q\Leftrightarrow\lnot q\to\lnot p$;等价等值式 $p\leftrightarrow q\L…
- 等值演算怎样证明两个公式等值(例一):从一边出发,每步用一个基本等值式,变到另一边。 例 证 $(p\to q)\land(p\to r)\Leftrightarrow p\to(q\land r)$:左边 $\Leftrightarrow(\lnot p\lor q)\la…
- 怎样用等值演算判断重言式(例二):把公式化简成 1 就是重言式,化简成 0 就是矛盾式。 例 判断 $((p\to q)\land p)\to q$:$\Leftrightarrow\lnot((\lnot p\lor q)\land p)\lor q\Leftright…
- 联结词完备集是什么,有哪些常见的:若任何真值函数都可由某个联结词集合表示,这个集合就叫联结词完备集。常见的完备集有 $\{\lnot,\land,\lor\}$、$\{\lnot,\land\}$、$\{\lnot,\lor\}$、$\{\lnot,\to\}$;与非 $…
范式与推理
- 极小项和极大项是什么,怎样编号:含全部 $n$ 个变项的合取式,每个变项或其否定恰好出现一次,称极小项 $m_i$;含全部变项的析取式称极大项 $M_i$。编号:极小项中 变项取 1、否定取 0 ,读成二进制数就是下标;极大项相反。 例 两个变项 ${p,q}$:$m_…
- 怎样用真值表求主析取、主合取范式:由 成真赋值 对应的极小项的析取,得到主析取范式;由 成假赋值 对应的极大项的合取,得到主合取范式。两种范式的下标集合互补。 例 $A=(p\land q)\lor(\lnot p\land r)$(变项 ${p,q,r}$):成真赋值是…
- 怎样用等值演算法求主析取范式:步骤:先化成析取范式;对缺少某变项的简单合取式,乘上 $(q\lor\lnot q)$ 补全,用分配律展开;合并重复的极小项。 例 $p\to q\Leftrightarrow\lnot p\lor q\Leftrightarrow(\l…
- 主范式可以用来做什么:①判断类型:主析取范式含全部 $2^n$ 个极小项是 重言式 ;一个极小项也没有(即 0)是 矛盾式 ;否则是可满足的非重言式。②判断等值:对同一组命题变项,两个公式等值当且仅当它们的 主析取范式相同 。 例 $(p\to q)\land…
- 析取范式和合取范式是什么:简单合取式是若干文字(变项或其否定)的合取,简单析取式是若干文字的析取。 析取范式 是若干简单合取式的析取, 合取范式 是若干简单析取式的合取。每个公式都有析取范式和合取范式,但 不唯一 ;唯一的是后面的主范式。 例 $(p\to q)\…
- 什么是有效推理,怎样判断:由前提 $A_1,\ldots,A_k$ 推出结论 $B$ 的推理是有效的,当且仅当 $(A_1\land\cdots\land A_k)\to B$ 是 重言式 。判断方法有真值表法、等值演算法和构造证明法。 区分 有效推理说的是推理形…
- 常用的推理规则有哪些(一):假言推理:$p\to q,\ p\Rightarrow q$;拒取式:$p\to q,\ \lnot q\Rightarrow\lnot p$;假言三段论:$p\to q,\ q\to r\Rightarrow p\to r$;析取三段论…
- 常用的推理规则有哪些(二):附加:$p\Rightarrow p\lor q$;化简:$p\land q\Rightarrow p$;合取引入:$p,\ q\Rightarrow p\land q$;构造性二难:$p\to q,\ r\to s,\ p\lor r\…
- 构造证明的写法(含附加前提):每一步写明依据:前提引入、结论引入、已有公式用推理规则或置换得到。若结论是条件式 $A\to B$,可把 $A$ 作 附加前提 ,推出 $B$ 后用 CP 规则得结论。 例 前提 $p\to(q\to r),\ q$,证 $p\to r$…
- 什么是归谬法(反证法):归谬法:把结论的 否定 作为附加前提,若能推出矛盾(如 $q\land\lnot q$),则原推理有效。 例 前提 $p\to\lnot q,\ r\to q,\ r$,证 $\lnot p$:①$p$(否定结论,附加);②$p\to\l…
谓词逻辑
- 什么是谓词和量词,个体域有什么影响:谓词描述个体的性质或个体间的关系,如 $F(x)$:$x$ 是偶数。全称量词 $\forall x$ 表示「对所有 $x$」,存在量词 $\exists x$ 表示「存在 $x$」。含量词公式的真值与 个体域 有关。 例 $P(x)$:$…
- 谓词命题符号化有什么固定搭配:全称量词配 蕴含 ,存在量词配 合取 :「所有的 $A$ 都是 $B$」为 $\forall x(A(x)\to B(x))$;「有的 $A$ 是 $B$」为 $\exists x(A(x)\land B(x))$。 例 全总个体域,$C…
- 量词怎样否定:$\lnot\forall xA(x)\Leftrightarrow\exists x\lnot A(x)$;$\lnot\exists xA(x)\Leftrightarrow\forall x\lnot A(x)$。否定时 量词改变,…
- 量词的辖域、约束变元与自由变元有什么区别:量词后面紧跟的最小子公式是它的辖域。在辖域内、与量词指导变元同名的变元是 约束出现 ,其余出现是 自由出现 。约束变元可以换名(量词及其辖域内同名变元一起改),自由变元可以代入。 例 $\forall x(F(x)\to G(x,y))\…
- 有限个体域里量词怎样消去:个体域 $D=\{a_1,\ldots,a_n\}$ 是 有限集 时,全称量词展开成合取,存在量词展开成析取:$\forall xA(x)\Leftrightarrow A(a_1)\land\cdots\land A(a_n)$;$\e…
- 量词对合取、析取的分配有什么规律:$\forall x(A\land B)\Leftrightarrow\forall xA\land\forall xB$;$\exists x(A\lor B)\Leftrightarrow\exists xA\lor\exists x…
- 前束范式怎么求:前束范式:所有量词都在公式最前面、辖域延伸到末尾。步骤:消去 $\to$、$\leftrightarrow$;把否定移到谓词前;必要时对约束变元 换名 ;把量词 提到 公式最前面。 例 $\forall xF(x)\to\exists y…
- 量词推理有哪几条规则:全称特指 UI:$\forall xA(x)\Rightarrow A(c)$($c$ 任意个体);存在特指 EI:$\exists xA(x)\Rightarrow A(c)$($c$ 是使 $A$ 成立的 特定个体 ,且为新引入的);…
- 一阶逻辑公式有哪些类型:一阶逻辑公式在任何个体域、任何解释下都为真,称永真式;都为假,称矛盾式;至少有一个解释使它为真,称可满足式。命题逻辑重言式的 代换实例 (把命题变项换成谓词公式)是永真式。 例 $p\to(q\to p)$ 是重言式,把 $p$ 换成 $…
集合
- 幂集是什么,有多少个元素:集合 $A$ 的幂集 $P(A)$ 是它的 所有子集 组成的集合;若 $|A|=n$,则幂集有 $2^n$ 个元素,包括空集和 $A$ 本身。 例 $A=\{a,b\}$:$P(A)=\{\varnothing,\{a\},\{b\},\…
- 属于关系和包含关系怎样区分:$x\in A$ 表示元素属于集合,$A\subseteq B$ 表示 $A$ 的 每个元素 都在 $B$ 中。空集是任何集合的子集,但 不一定是元素 :$\varnothing\in A$ 要看 $A$ 的元素里有没有 $\varnot…
- 集合的并、交、差、补、对称差怎么算:并 $A\cup B$、交 $A\cap B$、差 $A-B=A\cap\sim B$(属于 $A$ 不属于 $B$)、补集(相对全集 $E$)、对称差 $A\oplus B=(A-B)\cup(B-A)$。 例 $A=\{1,2,3\}…
- 集合有哪些常用的恒等式:交换、结合、分配($A\cup(B\cap C)=(A\cup B)\cap(A\cup C)$);德摩根 $\sim(A\cup B)=\sim A\cap\sim B$;吸收 $A\cup(A\cap B)=A$;$A-B=A\cap…
- 怎样证明集合恒等式:两种方法:①元素法:证两边互相包含,任取元素 $x$ 推导;②代数法:用已知恒等式逐步变换。 例 证 $A-(B\cup C)=(A-B)\cap(A-C)$:代数法:$A-(B\cup C)=A\cap\sim(B\cup C)=A\c…
- 笛卡尔积有什么性质:$A\times B=\{\langle x,y\rangle\mid x\in A,\ y\in B\}$,有序对 有顺序 。$|A\times B|=|A|\cdot|B|$。笛卡尔积 不满足交换律和结合律 ;若 $A$ 或 $B$ …
- 容斥原理怎么用:两个集合:$|A\cup B|=|A|+|B|-|A\cap B|$。三个集合:$|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|$。符号交…
二元关系的性质与闭包
- 二元关系怎样表示,定义域和值域是什么:从 $A$ 到 $B$ 的二元关系是 $A\times B$ 的子集。表示法有集合式、关系矩阵($r_{ij}=1$ 表示 $\langle a_i,b_j\rangle\in R$)和关系图。定义域 $\text{dom}R$ 是所有第…
- 关系的逆和复合怎么算:逆:$R^{-1}=\{\langle y,x\rangle\mid\langle x,y\rangle\in R\}$。复合(本图采用左孝凌版, 先 R 后 S ):$R\circ S=\{\langle x,z\rangle\mid\…
- 关系复合的例子:按本图约定先 $R$ 后 $S$:看 $R$ 的每个有序对 $\langle x,y\rangle$,在 $S$ 中找以 $y$ 开头的有序对来 衔接 。 例 $R=\{\langle1,2\rangle,\langle2,3\rangl…
- 关系的五种性质怎样定义,矩阵和图上怎么看:设 $R$ 是 $A$ 上的关系。自反:$\forall x\in A,\ \langle x,x\rangle\in R$(矩阵主对角线全 1,图中每点有环);反自反:都不在(对角线全 0);对称:$\langle x,y\rangle…
- 关系性质的判断例子:逐条检查五种性质:自反看每个元素的 $\langle x,x\rangle$ 是否都在,对称看有没有「来而无回」,传递看每一条两步路是否有直达边。 例 $A=\{1,2,3\}$,$R_1=\{\langle1,1\rangle,\lan…
- 对称与反对称是对立的吗:对称与反对称 不是对立 的:有的关系既对称又反对称,有的既不对称也不反对称。对称看「有来必有回」,反对称看「来回只能是同一点」。 例 $A=\{1,2\}$,$R=\{\langle1,1\rangle\}$:既对称又反对称,还传递;$R…
- 三种闭包的定义和公式:$R$ 的自反(对称、传递)闭包是包含 $R$ 且具有该性质的 最小 关系:$r(R)=R\cup I_A$;$s(R)=R\cup R^{-1}$;$t(R)=R\cup R^2\cup R^3\cup\cdots$(有限集 $A$ 上…
- 闭包的计算例子:先看缺什么再补:自反闭包补对角线,对称闭包补逆向的有序对,传递闭包反复补两步路得到的有序对。 例 $A=\{1,2,3\}$,$R=\{\langle1,2\rangle,\langle2,3\rangle\}$:$r(R)=R\cup\…
等价关系与偏序关系
- 等价关系和等价类是什么:自反、对称、传递的关系是等价关系。$x$ 的等价类 $[x]_R=\{y\mid\langle x,y\rangle\in R\}$,等价类非空, 两个等价类要么相等要么不交 ,所有等价类的并是 $A$。 例 $A=\{1,2,3,4,5…
- 商集与划分是什么,两者有什么关系:商集 $A/R$ 是所有等价类组成的集合;$A$ 的划分是一组 非空、两两不交 、并为 $A$ 的子集。等价关系与划分一一对应:商集就是一个划分,每个划分也唯一确定一个等价关系。 例 上面模 3 同余的商集 $A/R=\{\{1,4\},…
- 一个有限集上有多少个等价关系:等价关系的个数等于划分的个数(贝尔数)。3 元集有 5 个 划分,所以有 5 个等价关系;4 元集有 15 个。 例 $A=\{a,b,c\}$ 的划分:$\{\{a\},\{b\},\{c\}\}$,$\{\{a,b\},\{c\}\}…
- 怎样判断一个关系是不是等价关系:依次验证自反、对称、传递三条,有一条不成立就不是。 例 $A=\{1,2,3\}$,$R=\{\langle1,1\rangle,\langle2,2\rangle,\langle3,3\rangle,\langle1,2\rangle,…
- 偏序关系是什么,全序是什么:自反、反对称、传递的关系是偏序关系 $\preccurlyeq$,$\langle A,\preccurlyeq\rangle$ 称偏序集。若任意两个元素都 可比 ($x\preccurlyeq y$ 或 $y\preccurlyeq x…
- 哈斯图怎么画:哈斯图是偏序关系的简化图:不画自反环;不画可由传递得到的边(只画「覆盖」关系:$y$ 覆盖 $x$ 指 $x\prec y$ 且两者之间没有别的元素);小元素在下,大元素在上,边不带箭头。 例 $A=\{1,2,3,4,6,12\}$ 上…
- 极大元、极小元与最大元、最小元有什么区别:极小元:没有比它更小的元素;最小元:比所有元素都小。极大元、最大元同理。 最大元一定是极大元,反之不然 ;最小(大)元若存在则唯一,极小(大)元可以有多个。 例 整除关系下 $B=\{2,3,4,6\}$:极小元是 2 和 3,极大元是 …
- 上界、下界、上确界、下确界怎么求:$B\subseteq A$,$y\in A$ 若对 $B$ 中每个元素 $x$ 都有 $x\preccurlyeq y$,称 $y$ 是 $B$ 的上界;上界中的最小元是上确界(最小上界)。下界、下确界反之。 例 整除关系,$A=\{1…
- 极大元、最大元、上界不要混在一起:极大元、最大元是子集 $B$ 里的元素,上界、上确界却 可以不在 B 中 (只要在 $A$ 中)。 例 整除关系,$A=\{1,2,3,4,6,12\}$,$B=\{4,6\}$:上确界 12 不属于 $B$;$B$ 有两个极大元 4 和…
函数
- 什么样的关系是函数:$f$ 是从 $A$ 到 $B$ 的函数,要求:定义域 等于整个集合 A (每个元素都有象),且每个 $x$ 的象 唯一 。 例 $A=\{1,2,3\}$,$B=\{a,b\}$:$\{\langle1,a\rangle,\langle…
- 单射、满射、双射怎样定义:单射:$x_1\ne x_2\Rightarrow f(x_1)\ne f(x_2)$(不同的元素有不同的象);满射:$\text{ran}f=B$($B$ 中每个元素都有原象);双射:既单又满。 例 $f:\{1,2,3\}\to\{a…
- 有限集之间的函数、单射、双射有多少个:$|A|=m$,$|B|=n$:$A\to B$ 的函数有 $n^m$ 个;单射有 $n(n-1)\cdots(n-m+1)$ 个($m\le n$);当 $m=n$ 时双射有 ${n!}$ 个。 例 $|A|=3$,$|B|=4$:函数…
- 判断实数函数的单射、满射要注意什么:定义域和陪域不同,结论就不同,判断前要先看清 $f:A\to B$ 的 $A$ 和 $B$。 例 $f(x)=x^2$:$\mathbb{R}\to\mathbb{R}$ 时既 不是单射 ($f(-1)=f(1)$)也不是满射(负数无原象…
- 复合函数和反函数有什么性质:复合函数 $(g\circ f)(x)=g(f(x))$( 先 f 后 g ,这是函数的通行写法)。设 $f:A\to B$,$g:B\to C$,若 ${f,g}$ 都是单射(满射、双射),则 $g\circ f$ 也是。$f$ 有反函…
- 函数复合与关系复合的记号怎样区别:函数复合 $g\circ f$ 是先 $f$ 后 $g$;关系复合 $R\circ S$ 在本图(左孝凌版)中是先 $R$ 后 $S$,两者 次序相反 。屈婉玲版的关系复合与函数复合一致,都是先右后左。 区分 答题时先写清所采用的约定,再…
- 函数的像和原象是什么:设 $f:A\to B$。$A_1\subseteq A$ 的像 $f(A_1)=\{f(x)\mid x\in A_1\}$;$B_1\subseteq B$ 的原象 $f^{-1}(B_1)=\{x\in A\mid f(x)\in …
本图由 SeekFlaw 编辑团队整理。发现错误,欢迎到学习论坛指出。