离散复习资料
作者：。。。
第一章 考点：
1、证明一个公式的真值？
方法：第一，真值表
第二，等值演算
例题：判断(p → q ) ∧ (r → s ) → (p ∧ r → q ∧ s )的真值？
)()()(s q r p s r q p ∧→∧→→∧→
s q r p s r q p ∧→∧∧∨?∧∨??)()(
s q r s r p q p ∧→∧∨?∧∧∨??)()( 1?∧→∧∧∧?s q r s p q
2、通过等值演算求一个公式的主范式？
例题：
3、证明一个完全集是极小完全集？
见课本18页定理1.8
第二章 考点
1、将一组命题符号化？
例题：见课本51页
1、每个人都有自己喜欢的职业。
取论域为所有事物的集合。令
x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。
“每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→?
2、有些职业是所有人都喜欢的。
取论域为所有事物的集合。令
x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。
“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。
2、给定一组解释和赋值，计算出公式的真值？
带入解释和赋值
例题：
给定解释I 和I 中赋值v 如下：
}2,1{=I D ，1=I a ，2=I b ，2)1(=I f ，1)2(=I f
1)2,1()1,1(==I I P P ，0)2,2()1,2(==I I P P ，1)(=x v ，1)(=y v
计算下列公式在解释I 和赋值I 中v 下的真值。
(1) )),(())(,())(,(x y f P b f x P x f a P ∧∧ 答案：0
(2) ),(x y yP x ?? 答案：1
3、判断一个公式是否为永真式？
方法一：对于蕴含式，取一组解释和赋值，让命题的前件为1，判断命题的后件
例题：判断))()(()()(x Q x P x x xQ x xP ∨?→?∨?是否为永真式？
解答： 若解释I 使得1))()((=?∨?x xQ x xP I ，则1))((=?x xP I 或1))((=?x xQ I 。 ① 若1))((=?x xP I ，则存在I D d ∈使得1)(=d P I ，1)()(=∨d Q d P I I 。
② 若1))((=?x xQ I ，则存在I D d ∈使得1)(=d Q I ，1)()(=∨d Q d P I I 。
因此，1)))()(((=∨?x Q x P x I 。
对于等值式
例子：(2) A x xA ?????
任取解释I 和I 中赋值v ，
1))((=??v xA I
当且仅当 0))((=?v xA I
当且仅当 存在I D d ∈使得0])/[)((=d x v A I
当且仅当 存在I D d ∈使得1])/[)((=?d x v A I 当且仅当 1))((=??v A x I
这表明A x xA ?????是永真式。
方法二：对于蕴含式，取一组解释和赋值，让命题的后件为0，判断命题的前件 例题：判断))()(())()((x xQ x xP x Q x P x ?→?→→?是否为永真式？
若解释I 使得0)))()(((=?→?x xQ x xP I ，则1))((=?x xP I 且0))((=?x xQ I 。存在I D d ∈使得1)(=d P I ，又因为0))((=?x xQ I ，所以0)(=d Q I ，0)()(=→d Q d P I I 。因此，0)))()(((=→?x Q x P x I 。
原式为永真式。
方法三：试着取几组解释和赋值做实验，若取得一组解释，使得命题为假，则命题为非永真
式。
例题： 判断))()(()()(x Q x P x x xQ x xP ∧?→?∧?是否为永真式。
给定解释I 如下
}{d D I =， 1)(=d P I ， 1)(=d Q I
则1)))()(()()((=∧?→?∧?x Q x P x x xQ x xP I 。
给定解释I '如下
},{b a D I ='，1)(='a P I ，0)(='b P I ，0)(='a Q I ，1)(='b Q I
则0)))()(()()((=∧?→?∧?'x Q x P x x xQ x xP I 。
原式为非永真可满足式。
方法四：对于嵌套的蕴含式，也采取去解释让前件为一的方法
例题：判断)()(xB A B A x ?→→→?，其中x 不是A 的自由变元。是否为永真式？ 任取解释I 和I 中赋值v ，若1))(()))(((==→?v A I v B A x I ，则对于每个I D d ∈，1)]/[)((=→d x v B A I ，因为x 不是A 的自由变元，所以1))(()]/[)((==v A I d x v A I ，因此1)]/[)((=d x v B I ，1))((=?v xB I 。这表明)()(xB A B A x ?→→→?是永真式。
第三章 考点：
1、用公理系统的方法证明一个公式是永真式（带谓词的公式）
方法：构造重言式，并且应用5条公理（见课本60页）
例题：证明：A x A i x t i ?→-|，其中t 对于A 中的i x 是可代入的。
i x t i A A x ?→??-| 公理四
)()(|A x A A A x i x t x t i i i ???→→?→??- 重言式 即A x A i x t i ?→-|
注意：课后题的结论以及习题的结论都可以直接应用！
第四章 考点：
1、用归结法证明一个公式是永真式（带谓词的公式）
重点：谓词逻辑的归结法
例题： 1、证明：))()((x Q x P x ∨?/|=)()(x xQ x xP ?∨?
由语句))()((x Q x P x ∨?得到子句)()(x Q x P ∨，由语句))()((x xQ x xP ?∨??得到子句)(a P ?和)(b Q ?。显然，由这三个子句只能归结出子句)(a Q 和)(b P 。因此，
))
)
(
xQ
x
?
∨
xP?
?/|=)
(x
(
)
x∨
(x
(
Q
P
x
2、（重点）任何喜欢步行的人都不喜欢乘汽车。每个人或者喜欢乘汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因此，有的人不喜欢步行。
解首先将前提和结论符号化。取个体域为人的集合。
W(x)：x喜欢步行。C(x)：x喜欢乘汽车。B(x)：x喜欢骑自行车。
“任何喜欢步行的人都不喜欢乘汽车”符号化为
?x(W(x) →?C(x))
“每个人或者喜欢乘汽车或者喜欢骑自行车”符号化为
?x(C(x) ∨ B(x))
“有的人不喜欢骑自行车”符号化为?x?B(x)。
“有的人不喜欢步行”符号化为?x?W(x)。
需要证明
?x(W(x) →?C(x))，?x(C(x) ∨ B(x))，?x?B(x) |=?x?W(x)
将?x(W(x) →?C(x)) 化为斯科伦范式?x(?W(x) ∨?C(x))，
得出子句?W(x) ∨?C(x)。
?x(C(x) ∨ B(x)) 本身即是斯科伦范式，得出子句C(x) ∨ B(x)。
将?x?B(x) 化为斯科伦范式?B(a)，得出子句?B(a)。
将??x?W(x) 化为斯科伦范式?xW(x)，得出子句W(x)。
构造子句集{?W(x) ∨?C(x)，C(x) ∨ B(x)，?B(a)，W(x)} 的一个反驳如下：
①?W(x) ∨?C(x)
②C(x) ∨ B(x)
③?B(a)
④W(x)
⑤?C(x) 由①和④
⑥B(x) 由②和⑤
⑦□由③和⑥{x/a}
第五章考点：
1、证明两个集合相等？
方法一:若对于任意X，X∈A<-->X∈B,则两个集合相等
方法二：若对于任意X，X∈A——>X∈B ∧X∈B——>X∈A=1，则两个集合相等
方法三：集合的运算性质（最主要的是补交转换律）
方法四：集合的特征函数（不建议用）。
第六章考点
1、给定一个关系图，写出它具有的性质（或给定一个关系，画出它的关系图）
例题：5．设A = {1, 2, 3}，A上的关系R1, R2, R3, R4, R5分别由图6.17给出，试
问：R1, R2, R3, R4, R5各有哪些性质？
解
R 1：自反、对称、反对称、传递。
R 2：对称。
R 3：反自反、反对称。
R 4：反自反、对称、反对称、传递。
R 5：自反、传递。
2、给定一个关系，判断它是否为偏序，若为偏序（那是肯定的），写出它的8个元素（最大元、最小元、极大元、极小元、上界、下界，上确界、下确界），并可以画出哈斯图。 偏序定义：集合X 上的关系R 称为X 上的偏序关系或偏序，当且仅当R 是自反的、反对称的和传递的。
例题：18. 对于下列集合上的整除关系，画出哈斯图。对于集合｛2，3，4｝，求它的8个元素
(1) A = {1, 2, 3, 4, 6, 8, 12, 24}
(2) B = {1, 2, 3,…, 12}
(1) {2, 3, 4}没有最大元、最小元，极大元为3和4，极小元为2和3，上界为12和24，上确界为12，下界为1，下确界为1。
(2) {2, 3, 4}没有最大元、最小元，极大元为3和4，极小元为2和3，上界为12，上确界为12，下界为1，下确界为1。
3、给定一个关系，判断是偏序关系还是等价关系，若是等价关系，可以找出由其中某一元素代表的等价类。
等价关系定义：设R 是非空集合上的关系，如果R 是自反的，对称的和传递的，则称R 为等价关系。
例题：25. 正整数集合上的关系R 被定义为n i Rn j n i / n j 能够被表达成2m 的指数形式，其中m 是任意整数。
(1) 证明关系R 是等价关系。
(2) 等价类是什么？
解(1) 任取正整数x，x / x = 1 = 20，所以xRx，R是自反的。
若xRy，则有整数m使得x / y = 2m，y / x = 2-m，-m也是整数，所以yRx，R是对称的。
若xRy且yRz，则有整数m, n使得x / y = 2m，y / z = 2n，
x / z = (x / y)*( y / z) = 2m* 2n = 2m+n
m + n也是整数，所以xRz，R是传递的。R是等价关系。
(2) 对于每个正奇数k，{ x | ?m (m∈N ∧x = k ? 2m)}是等价类。
[1]R = {1, 2, 4, 8, 16,…}
[3]R = {3, 6, 12, 24, 48,…}
…
第七章考点：
1、给定一个函数，判断函数究竟是单射，满射，双射？
例题：1. f : N →N , f (x) = 2x ，是单射，不是满射，因
为奇数不在值域中。
2. f : N →N , f (x) = x + 1，是单射，不是满射，
因为0 不在值域中。
3. f : I →I , f (x) = x + 1，是双射。
4. f : N →N ×N ，f (x) = < x, x > ，是单射，不是
满射，因为< 0, 1 > 不在值域中。
5. f : R →I，f (x) = ?x?，不是单射，因为
f (1) = f (1.5)；是满射。
6. f : I →I , f (x) = | x | ，不是满射，因为负整数
不在值域中；不是单射，因为f (1) = f (?1) 。
7. f : R→R , f (x) = 2x + 3， f 是双射。
8．f : R→R , f (x) = x2 ，不是单射也不是满射，更不是双射。
2、函数的运算（非常重要，尤其是后面这道题）
定义7.7 设f : X →X，f n 定义如下：
1. f 0(x) = x
2. f n+1(x) = f ( f n(x))
定理7.1 若f : X →Y 且g : Y →Z ，则函数的复合g °f 是
一个从X到Z的函数，即g °f : X →Z ，且对所有的
x∈X，( g °f )(x) = g (f (x))。
例7.15设f : R→R 定义为f (x) = x + 2 ，
设g : R→R 定义为g (x) = x ?2 ，
设h : R→R 定义为h (x) = 3x ，
则g °f (x) = x + 2 ?2 = x
f °
g (x) = x ?2 + 2 = x
f °f (x) = x + 2 + 2 = x + 4
g °g (x) = x ?2 ?2 = x ?4
f °h (x) = 3x + 2
h °g (x) = 3(x ?2) = 3x ?6
h °f (x) = 3(x + 2) = 3x + 6
f °h °
g (x) = 3(x ?2) + 2 = 3x ?4
重要题目：课本140页第6题
第八章考点：（第八章不考）
1、证明两个集合等势？
概念：两个集合A和B是等势的，当且仅当A和B的元素是一一对应的，记作A~B、
方法一：集合是有穷的，当且仅当它与某个自然数等势。（每个自然数是比它小的所有自然数的集合）
方法二：构造函数，将集合一一对一映射到集合二上，使两集合元素一一对应。
例一：设N=｛0，1，2……｝，E=｛0，2，4……｝，求证N~E
提示：建立函数关系f:N→E由f（n）=2n给定，这里n∈N
函数f是双射函数，在N和E之间建立起一一对应，因此，N~E
例二：自然数集合N与有理数集合Q等势
见课本146页例8.6
例三：开区间（0，1）与实数集合R等势，证明：
提示：构造函数f（x）=tgπ（2x-1）/2, f把（0，1）一对一并且连续的映射到R上。
注意：：两集合的一一对应的关系不是唯一的。
方法三：自然数集合的基数以及有理数、整数、奇数、偶数集的基数都是阿列夫零实数集的基数是C=2^阿列弗0 自然数集合的幂集的基数和实数集基数相等
注意：不存在最大的集合。。
离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；
离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
第一章，0命题逻辑 素数 = 质数，合数有因子 和或假必真同为真 (p→q)∧(q←→r)，(p∧q)∧┐r，p∧(q∧┐r)等都是合式公式，而pq→r，（p→(r→q)等不是合式公式。若公式A是单个的命题变项，则称A为0层合式 (┐p∧q)→r，(┐(p→┐q))∧((r∨s)┐p)分别为3层和4层公式 【例】求下列公式的真值表，并求成真赋值和成假赋值。 (┐p∧q)→┐r 公式(1)的成假赋值为011，其余7个赋值都是成真赋值 第二章，命题逻辑等值演算 （1）双重否定律??A?A （2）等幂律 A∧A?A ； A∨A?A （3）交换律 A∧B?B∧A ； A∨B?B∨A （4）结合律（A∧B）∧C?A∧（B∧C）；（A∨B）∨C?A∨（B∨C） （5）分配律（A∧B）∨C?（A∨C）∧（B∨C）；（A∨B）∧C?（A∧C）∨（B∧C） （6）德·摩根律?（A∨B）??A∧?B ；?（A∧B）??A∨?B （7）吸收律 A∨（A∧B）?A；A∧（A∨B）?A （8）零一律 A∨1?1 ； A∧0?0 （9）同一律 A∨0?A ； A∧1?A （10）排中律 A∨?A?1 （11）矛盾律 A∧?A?0 （12）蕴涵等值式 A→B??A∨B （13）假言易位 A→B??B→?A （14）等价等值式 A?B?（A→B）∧（B→A） （15）等价否定等值式 A?B??A??B??B??A （16）归缪式（A→B）∧（A→?B）??A
A i(i=1,2,…,s)为简单合取式，则A=A1∨A2∨…∨A s为析取范式 (p∧┐q)∨(┐q∧┐r)∨p A=A1∧A2∧…∧A s为合取范式 (p∨q∨r)∧(┐p∨┐q)∧r 一个析取范式是矛盾式当且仅当它的每个简单合取式都是矛盾式 一个合取范式是重言式当且仅当它的每个简单析取式都是重言式 主范式【∧小真，∨大假】 ∧成真小写 【例】(p→q)→(┐q→┐p) = ┐(┐p∨q)∨(q∨┐p) (消去→) = (p∧┐q)∨┐p∨q (┐内移) (已为析取范式) = (p∧┐q)∨(┐p∧┐q)∨(┐p∧q)∨(┐p∧q)∨(p∧q) （*） = m2∨m0∨m1∨m1∨m3 = m0∨m1∨m2∨m3 (幂等律、排序) (*)由┐p及q派生的极小项的过程如下： ┐p = ┐p∧(┐q∨q) = (┐p∧┐q)∨(┐p∧q) q = (┐p∨p)∧q = (┐p∧q)∨(p∧q) 熟练之后，以上过程可不写在演算过程中。 该公式中含n=2个命题变项，它的主析取范式中含了22=4个极小项，故它为重言式， 00，01，10，11全为成真赋值。 【例】(p→q)∧┐p = (┐p∨q)∧┐p (消去→) = ┐p∨(┐p∧q) (分配律、幂等律) 已为析取范式
离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8.
C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D=
D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为
离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证
二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式x((A(x)B(y，x))z C(y，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式x A和x A中，称x为指导变元，A为量词的辖域。在x A和x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x 为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！
离散数学笔记（特级教师精心整理） 第一章命题逻辑 内容： 命题及命题联结词、命题公式的基本概念，真值表、基本等价式及永真蕴涵式，命题演算的推理理论中常用的直接证明、条件证明、反证法证明等方法教学目的： 1．熟练掌握命题、联结词、复合命题、命题公式及其解释的概念。 2．熟练掌握常用的基本等价式及其应用。 3．熟练掌握（主）析/合取范式的求法及其应用。 4．熟练掌握常用的永真蕴涵式及其在逻辑推理中的应用。 5．熟练掌握形式演绎的方法。 教学重点： 1．命题的概念及判断 2．联结词，命题的翻译 3．主析（合）取范式的求法 4．逻辑推理 教学难点： 1．主析（合）取范式的求法 2．逻辑推理 1.1命题及其表示法 1.1.1 命题的概念 数理逻辑将能够判断真假的陈述句称作命题。 1.1.2 命题的表示 命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。A1:我是一名大学生.[10]：我是一名大学生。R：我是一名大学生。 1.2命题联结词
（1） P↑P?﹁（P∧P）?﹁P； （2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。 （1）P↓P?﹁（P∨Q）?﹁P；
（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q； （3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。 1.3 命题公式、翻译与解释 1.3.1 命题公式 定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P 是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、 P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。 例如，下面的符号串都是公式： （（（（﹁P）∧Q）→R）∨S） （（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R 以下符号串都不是公式： （（P∨Q）?（∧Q））（∧Q） 1.3.2 命题的翻译 可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。 命题翻译时应注意下列事项： （1）确定所给句子是否为命题。 （2）句子中联结词是否为命题联结词。 （3）要正确的选择原子命题和合适的命题联结词。 例：假如上午不下雨，我去看电影，否则就在家里读书或看报。 解：设P：上午下雨；Q：我去看电影；R：我在家里读书；S：我在家里看报。 本例可表示为：（?P→Q）∧（P→（R∨S））。 1.3.3 命题公式的解释定义 设P1，P2，…，P n是出现在命题公式G中的全部命题变元，指定P1，P2，…，P n的一组真值，称这组真值为G的一个解释或赋值，记作I，公式G在I下的真值记作T I（G）。 例如， 是G的一个解释，在这个解释下G的真值为1，即T I（G）=1。 1.4 真值表与等价公式 1.4.1 真值表 定义将公式G在其所有解释下所取得的真值列成一个表，称为G的真值表。 构造真值表的方法如下： （1）找出公式G中的全部命题变元，并按一定的顺序排列成P1，P2，…，P n。
离散数学习题参考答案 第一章集合 １.分别用穷举法,描述法写出下列集合 （１）偶数集合 (２)36的正因子集合 (３)自然数中3的倍数 (４)大于１的正奇数 (1)E={?,-6,-4,-2,0,2,4,6,?} ={2 i | i∈I } (2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3) N3= { 3, 6, 9, ```} = { 3n | n∈N } (4) A d= {3, 5, 7, 9, ```} = { 2n+1 | n∈N } ２.确定下列结论正确与否 (１)φ∈φ× (２)φ∈｛φ｝√ (３)φ?φ√ (４)φ?｛φ｝√ (５)φ∈｛ａ｝× (６)φ?｛ａ｝√ (７)｛ａ,ｂ｝∈｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝× (８)｛ａ,ｂ｝?｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝√(９)｛ａ,ｂ｝∈｛ａ,ｂ,｛｛ａ,ｂ｝｝｝× (１０)｛ａ,ｂ｝?｛ａ,ｂ,｛｛ａ,ｂ｝｝｝√ ３.写出下列集合的幂集 (１)｛｛ａ｝｝ {φ, {{ a }}} ( 2 ) φ {φ} (３)｛φ,｛φ｝｝ {φ, {φ}, {{φ}}, {φ,{φ}} } (４)｛φ,ａ,｛ａ,ｂ｝｝ {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}, {a, {a b }}, {φ,a,{ a, b }} } (５)Ｐ(Ｐ(φ)) {φ, {φ}, {{φ}}, {φ,{φ}} } ４.对任意集合Ａ,Ｂ,Ｃ,确定下列结论的正确与否(１)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ∈Ｃ√
(２)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ?Ｃ× (３)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ∈Ｃ× (４)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ?Ｃ × ５.对任意集合Ａ,Ｂ,Ｃ,证明 右 分配差差左=--=--)C A ()B A ()C B (A M .D )C B (A )C B (A ) C A ()B A ()C B (A )1(I Y I Y I I I I I Y 右 差分配差左右差的结论差左=--=-------=-)C A ()B A ()C A ()B A () C B (A M . D )C B (A )2)C A ()B A ()C A ()B A ()1()C B (A )1) C A ()B A ()C B (A )2(Y I Y I Y I I I Y I Y Y I 右 交换结合幂等差左=--=-)C A ()B A (,)C B ()A A () C B (A M . D )C B (A ) C A ()B A ()C B (A )3(I I I I I I I I Y I I Y ))B )B (A ())B B ()B A ((,)B )B A (()B )B A ((B )B A (B A B )B A )(4(I I Y I Y I I Y I I Y --⊕=⊕+结合分配对称差差左 右 零一互补==φ-φ-)B A ()B A () A ()U ) B A ((Y Y I I Y
离散数学复习题及答案文件排版存档编号：[UYTR-OUPT28-KBNTL98-UYNN208]
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： 5. 构造下列推理的论证：p ∨q, p →r, s →t, s →r, t q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →((r ∧s)→q), p, s q 7. 请将下列命题符号化： 所有鱼都生活在水中。 ) ()(R P Q P ∨∧∧?
答案： 令F( x )：x是鱼 W( x )：x生活在水中 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y，都有x+y≥x。 答案： 令P(x):x是正实数 S(x,y): x+y≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x是人 Q(y): y是课外活动 S(x,y):x参加y 12. 请将下列命题符号化： 某些人对某些药物过敏。 答案：
令P(x):x是人 Q(y): y是药 S(x,y):x对y过敏13. 求) ( )) ( ) ( (y yR y Q x P y? → → ?的对偶式: 答案： 14. 求下列谓词公式的前束范式： 答案： 15. 证明： 答案： 16. 用反证法证明： x(P(x)∧Q(x)) , xP(x) xQ(x) 答案： 17. 证明： 前提： x(C(x)W(x)∧R(x)), x(C(x)∧Q(x)). 结论： x(Q(x)∧R(x)). 答案： (1) x(C(x)∧Q(x)) 前提引入 (2) C(a)∧Q(a) (1)ES (3) C(a) (2)化简规则 (4) x(C(x)W(x)∧R(x)) 前提引入 (5) C(a)W(a)∧R(a) (4)US (6) W(a)∧R(a) (3)(5)假言推理 (7) R(a) (6)化简规则 (8) Q(a) (2)化简规则 ) , , ( )) , ( ) , ( (u y x uQ z y P z x zP y x? → ∧ ? ? ?
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明:
《离散数学》综合复习资料参考答案 一、判断题 1．命题逻辑中任何命题公式的主析取范式如果存在一定是唯一的。（） 2．A、B、C是任意集合，如果A?B及B∈C，则A?C。（） 3．整数集是不可数集。（） 4．代数系统
7． 设树T 有17条边，有12片树叶，2个3度结点，求4度结点数。 8． 设A={1,2}，试构成集合P(A)?A 。 9. 设*运算是有理数集Q 上的二元运算，对于任意的a,b ∈Q ，a*b=a+b-a ?b ，问运算*是否可交换、可结合的？ 10.试求下面有向图的强分图、单侧分图和弱分图。 11、将下列命题符号化 （1）他即聪明又用功。（P ∧Q ） （2）仅当你走我才留下。（Q → P ） （3）所有老的国家选手都是运动员。（(?x)(R(x)→Q(x))） （4）某些教练是年老的，但是健壮的。（(?x)(P(x)∧Q(x) ∧R(x))） 12、设A 是一个非空集合，*是A 上的二元运算，对于任意a,b ∈A ，有a*b=b ，判定*运 算是否可结合的、可交换？ 13、试求下面有向图的强分图、单侧分图和弱分图 三、证明题 1． 设
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项 (m) 之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为 0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项 时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R 的顺序依次写； 6.真值表中值为 1 的项为极小项，值为0 的项为极大项； 7.n 个变元共有2n个极小项或极大项，这2n为(0~ 2n -1)刚好为化简完 后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法 (=>) ：真值表法；分析法 (假定前键为真推出后键 为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则， T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取 ^;
3.既有存在又有全称量，先消存在量，再消全称量； 第四章集合 1.N ，表示自然数集， 1,2,3 ??，不包括 0； 2.基：集合 A 中不同元素的个数， |A|； 3.集：定集合 A，以集合 A 的所有子集元素成的集合，P(A) ； 4.若集合 A 有 n 个元素，集 P(A) 有2 n个元素， |P(A)|= 2| A| = 2 n； 5.集合的分划： (等价关系 ) ①每一个分划都是由集合 A 的几个子集构成的集合； ② 几个子集相交空，相并全(A)； 6.集合的分划与覆盖的比： 分划：每个元素均出且出一次在子集中； 覆盖：只要求每个元素都出，没有要求只出一次； 第五章关系 1.若集合 A 有 m 个元素，集合 B 有 n 个元素，笛卡 A×B 的基数mn， A 到 B 上可以定2mn种不同的关系； 2.若集合 A 有 n 个元素， |A ×A|= n2，A 上有2n2个不同的关系； 3.全关系的性：自反性，称性，性； 空关系的性：反自反性，反称性，性；
1.常用公式 p ∧(P →Q)=>Q 假言推论 ┐Q ∧(P →Q)=>┐P 拒取式 ┐p ∧(P ∨Q)=>Q 析取三段式 (P →Q) ∧(Q →R)=>P →R 条件三段式 (PQ) ∧(QR)=>PR 双条件三段式 (P →Q)∧(R →S)∧(P ∧R)=>Q →S 合取构造二难 (P →Q)∧(R →S)∧(P ∨R)=>Q ∨S 析取构造二难 (?x)((Ax)∨(Bx)) <=>( ?x)(Ax)∨(?x)(Bx) (?x)((Ax)∧(Bx)) <=>(?x)(Ax)∧(?x)(Bx) —┐(?x)(Ax) <=>(?x)┐(Ax) —┐(?x)(Ax) <=>(?x)┐(Ax) (?x)(A ∨(Bx)) <=>A ∨(?x)(Bx) (?x)(A ∧(Bx)) <=>A ∧(?x)(Bx) (?x)((Ax)→(Bx)) <=>(?x)(Ax)→(?x)(Bx) (?x)(Ax) →B <=>(?x) ((Ax)→B) (?x)(Ax) →B <=>(?x) ((Ax)→B) A →(?x)(Bx) <=>(?x) (A →(Bx)) A →(?x)(Bx) <=>(?x) (A →(Bx)) (?x)(Ax)∨(?x)(Bx) =>(?x)((Ax)∨(Bx)) (?x)((Ax)∧(Bx)) =>(?x)(Ax)∧(?x)(Bx) (?x)(Ax)→(?x)(Bx) =>(?x)((Ax)→(Bx)) 2.命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P ,Q,R 的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n 个变元共有n 2个极小项或极大项，这n 2为(0~n 2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则，T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 3.谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 4.集合 1.N ，表示自然数集，1,2,3……，不包括0； 2.基：集合A 中不同元素的个数，|A|； 3.幂集：给定集合A ，以集合A 的所有子集为元素组成的集合，P(A)； 4.若集合A 有n 个元素，幂集P(A)有n 2个元素，|P(A)|=||2A =n 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A 的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 5.关系 1.若集合A 有m 个元素，集合B 有n 个元素，则笛卡尔A ×B 的基数为mn ，A 到B 上可以定义mn 2种不同的关系； 2.若集合A 有n 个元素，则|A ×A|=2n ，A 上有22n 个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全封闭环的性质：自反性，对称性，反对称性，传递性； 4.前域(domR)：所有元素x 组成的集合； 后域(ranR)：所有元素y 组成的集合； 5.自反闭包：r(R)=RU Ix ; 对称闭包：s(R)=RU 1-R ; 传递闭包：t(R)=RU 2R U 3R U …… 6.等价关系：集合A 上的二元关系R 满足自反性，对称性和传递性，则R 称为等价关系； 7.偏序关系：集合A 上的关系R 满足自反性，反对称性和传递性，则称R 是A 上的一个偏序关系； 8.covA={