第一章
定律证明:
(1) A?B=B?A (交换律)
证?x x∈A?B
? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A
得证A?B?B?A.
同理可证B?A?A?B.
(2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C)
? x∈A或(x∈B且x∈C )
?(x∈A或x∈B)且(x∈A或x∈C)
?x∈(A?B)?(A?C)
得证A?(B?C)?(A?B)?(A?C).
类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律)
证根据并的定义, 有E?A?E.
根据全集的定义, 又有A? E?E. (4) A?E=A (同一律)
证根据交的定义, 有A?E?A.
又, ?x x∈A,
根据全集E的定义,
x∈E, 从而x∈A且x∈E,
?x∈A?E
得证A?A?E.
例4 证明A?(A?B)=A（吸收律）
证利用例3证明的4条等式证明
A?(A?B)
= (A?E)?(A?B) (同一律)
= A?(E?B) (分配律)
= A?(B?E) (交换律)
= A?E (零律)
= A (同一律)
例5 证明(A-B)-C=(A-C)-(B-C)
证(A-C)-(B-C)
= (A ?~C) ? ~(B ? ~C) (补交转换律)
= (A ?~C) ? (~B ? ~~C) (德摩根律)
= (A ?~C) ? (~B ? C) (双重否定律)
= (A ?~C? ~B)?(A ?~C? C) (分配律)
= (A ?~C? ~B)?(A ??) (矛盾律)
= A ?~C? ~B (零律,同一律)
= (A ?~B) ? ~C (交换律,结合律)
= (A – B) –C (补交转换律)
例6 证明(A?B)⊕(A?C)= (B⊕C) - A
证(A?B)⊕(A?C)
=((A?B) - (A?C))?((A?C) - (A?B))
=((A?B)?~A?~C)?((A?C)?~A?~B)
= (B?~A?~C)?(C?~A?~B)
=((B?~C)?(C?~B))?~A
=((B-C)?(C-B))?~A
= (B⊕C) - A
例7 设A,B为任意集合, 证明:
若A?B, 则P(A)?P(B)
证?x x∈P(A) ?x?A
?x?B (已知A?B)
?x∈P(B)
例8 证明A⊕B=A?B-A?B.
A⊕B=(A?~B)?(~A?B)
=(A?~A)?(A?B)?(~B?~A)?(~B?B)
=(A?B)?(~B?~A)
=(A?B)?~(A?B)
=A?B-A?B
直接法若n是奇数, 则n2也是奇数.
假设n是奇数, 则存在k∈N, n=2k+1.
于是n2 = (2k+1)2 = 2(2k2+2k)+1
得证n2是奇数.
间接法若n2是奇数, 则n也是奇数.
只证:若n是偶数, 则n2也是偶数.
假设n是偶数, 则存在k∈N, n=2k.
于是n2 = (2k)2= 2(2k2)
得证n2是偶数.
归谬法若A-B=A, 则A?B=?
证用归谬法, 假设A?B≠?, 则存在x,使得x∈A?B ?x∈A且x∈B
?x∈A-B且x∈B(A-B=A)
? (x∈A且x?B)且x∈B
?x?B且x∈B, 矛盾
构造性对每正整数n, 存n个连的正合数. 证令x=(n+1)! +1
考虑如下n个连续正整数：x+1, x+2,…, x+n，
对于i（i=1,2,3,…,n），x+i=(n+1)! +(1+i),
此式含有因子1+i，而1+i不等于1也不等于x+i，因此x+i是合数。所以x+1, x+2,…,
x+n是n个连续的正合数。
非构造性对每个正整数n, 存在大于n的素数.
令x等于所有小于等于n的素数的乘积加1,
则x不能被所有小于等于n的素数整除.
于是, x或者是素数, 或者能被大于n的素数整除.
因此,存在大于n的素数.
数学归：对所有n≥1, 1+3+5+ … +(2n-1)=n2
归纳基础. 当n=1时, 1=12, 结论成立.
归纳步骤. 假设对n(n≥1)结论成立,
则考虑n+1的情况有
1+3+5+ … +(2n-1)+(2n+1)=n2 +(2n+1) = (n+1)2
得证当n+1时结论也成立.
第二数学归任>=2的整数均可表成素数的乘积
证归纳基础. 对于2, 结论显然成立.
归纳步骤. 假设对所有的k(2≤k≤n)结论成立, 要证结论
对n+1也成立. 若n+1是素数, 则结论成立; 否则n+1=ab, 2≤a,b 命题为假的证明——举反例 例11 证明下述命题不成立: 若A?B=A?C, 则B=C. 证明反例: 取A={a,b}, B={a,b,c}, C={a,b,d}, 有A?B=A?C = {a,b} 但B≠C, 故命题不成立. 第二章 例3 证明p→(q→r) ? (p∧q)→r 证p→(q→r) ??p∨(?q∨r) （蕴涵等值式） ? (?p∨?q)∨r（结合律） ??(p∧q)∨r（德摩根律） ? (p∧q) →r（蕴涵等值式） (1) q∧?(p→q) 解q∧?(p→q) ?q∧?(?p∨q) （蕴涵等值式） ?q∧(p∧?q) （德摩根律） ?p∧(q∧?q) （交换律，结合律） ?p∧0 （矛盾律） ? 0 （零律） 该式为矛盾式. (2) (p→q)?(?q→?p) 解(p→q)?(?q→?p) ? (?p∨q)?(q∨?p) （蕴涵等值式） ? (?p∨q)?(?p∨q) （交换律） ? 1 该式为重言式. ?(p→q)∨?r 的析取范式与合取范式 解?(p→q)∨?r ??(?p∨q)∨?r ? (p∧?q)∨?r析取范式 ? (p∨?r)∧(?q∨?r) 合取范式 ?(p→q)∨?r 的主析取范式主合取范式 解(1) ?(p→q)∨?r? (p∧?q)∨?r p∧?q? (p∧?q)∧1 同一律 ? (p∧?q)∧(?r∨r) 排中律 ? (p∧?q∧?r)∨(p∧?q∧r) 分配律 ?m4∨m5 ?r ? (?p∨p)∧(?q∨q)∧?r 同一律, 排中律 ? (?p∧?q∧?r)∨(?p∧q∧?r)∨(p∧?q∧?r)∨(p∧q∧?r) ?m0∨m2∨m4∨m6 分配律 得?(p→q)∨?r?m0∨m2∨m4 ∨m5 ∨m6 可记作?∑(0,2,4,5,6) (2) ?(p→q)∨?r? (p∨?r)∧(?q∨?r) p∨?r?p∨0∨?r 同一律 ?p∨(q∧?q)∨?r 矛盾律 ? (p∨q∨?r)∧(p∨?q∨?r)分配律 ?M1∧M3 ?q∨?r? (p∧?p)∨?q∨?r 同一律, 矛盾律 ? (p∨?q∨?r)∧(?p∨?q∨?r) 分配律 ?M3∧M7 得?(p→q)∨?r?M1∧M3∧M7 可记作?∏(1,3,7) 快速求A ? (?p∧q)∨(?p∧?q∧r)∨r的主析取范式(1) ?p∧q? (?p∧q∧?r)∨(?p∧q∧r) ?m2∨m3 ?p∧?q∧r?m1 r?(?p∧?q∧r)∨(?p∧q∧r)∨(p∧?q∧r)∨(p∧q∧r) ?m1∨m3∨m5∨m7 得A?m1∨m2∨m3∨m5∨m7 ?∑(1,2,3,5,7) (2) 求B??p∧(p∨q∨?r)的主合取范式 解?p? (?p∨q∨r)∧(?p∨q∨?r)∧ (?p∨?q∨r)∧(?p∨?q∨?r) ?M4∧M5∧M6∧M7 p∨q∨?r?M1 得B?M1∧M4∧M5∧M6∧M7 ?∏(1,4,5,6,7) 例3 用主析取范式判断公式的类型: (1) A??(p→q)∧q (3) C? (p∨q)→r A??(?p∨q)∧q ? ( p∧?q)∧q ? 0 矛盾式(2) B?p→(p∨q) B??p∨(p∨q) ? 1 ?m0∨m1∨m2∨m3重言式 (3) C? (p∨q)→r C ??(p∨q)∨r ? (?p∧?q)∨r ? (?p∧?q∧r)∨(?p∧?q∧?r)∨(?p∧?q∧r) ∨(?p∧q∧r)∨(p∧?q∧r)∨(p∧q∧r) ? m0∨m1∨m3∨m5∨m7非重言式的可满足式 用主析取范式判断下面2组公式是否等值: (1) p与(?p∨q)→(p∧q) 解p ?p∧(?q∨q) ? (p∧?q)∨(p∧q) ?m2∨m3 (?p∨q)→(p∧q) ??(?p∨q)∨(p∧q) ? (p∧?q)∨(p∧q) ?m2∨m3 故p ? (?p∨q)→(p∧q) (2) (p∧q)∨r 与p∧(q∨r) 解(p∧q)∨r? (p∧q∧?r)∨(p∧q∧r) ∨(?p∧?q∧r)∨ (?p∧q∧r)∨(p∧?q∧r)∨(p∧q∧r) ? m1∨m3∨m5∨m6∨m7 p∧(q∨r) ? (p∧q)∨(p∧r) ?(p∧q∧?r)∨(p∧q∧r)∨(p∧?q∧r)∨(p∧q∧r) ? m5∨m6∨m7 故(p∧q)∨r 不等于p∧(q∨r) 例5 某单位要从A,B,C三人中选派若干人出国考察, 需满足下述条件: (1) 若A去, 则C必须去; (2) 若B去, 则C不能去; (3) A和B必须去一人且只能去一人. 问有几种可能的选派方案? 解记p:派A去, q:派B去, r:派C去 (1) p→r, (2) q→?r, (3) (p∧?q)∨(?p∧q) 求下式的成真赋值 A=(p→r)∧(q→?r)∧((p∧?q)∨(?p∧q)) 求A的主析取范式 A=(p→r)∧(q→?r)∧((p∧?q)∨(?p∧q)) ? (?p∨r)∧(?q∨?r)∧((p∧?q)∨(?p∧q)) ? ((?p∧?q)∨(?p∧?r)∨(r∧?q)∨(r∧?r)) ∧((p∧?q)∨(?p∧q)) ? ((?p∧?q)∧(p∧?q))∨((?p∧?r)∧(p∧?q)) ∨((r∧?q)∧(p∧?q))∨((?p∧?q)∧(?p∧q)) ∨((?p∧?r)∧(?p∧q))∨((r∧?q)∧(?p∧q)) ? (p∧?q∧r)∨(?p∧q∧?r) 成真赋值:101,010 结论: 方案1 派A与C去方案2派B去 A=(?p∧?q∧r)∨(?p∧q∧r)∨(p∧q∧r)的主合取范式解 A ?m1∨m3∨m7 ?M0∧M2∧M4∧M5∧M6 第二章 判断若今天是1号, 则明天是5号. 今天是1号. 所以, 明天是5号. 解设p: 今天是1号, q: 明天是5号 推理的形式结构为(p→q)∧p→q 证明用等值演算法 (p→q)∧p→q??((?p∨q)∧p)∨q ? ((p∧?q)∨?p)∨q ??p∨?q∨q? 1 得证推理正确 判断若下午气温超过30度, 则小燕必去游泳，若她去游泳她就不去看电影了. 所以若小燕没去看电影, 下午气温必定超过了30度. m1 解设p: 下午气温超过30度, q: 小燕去游泳，r: 小燕去看电影. 推理的形式结构为((p→q)∧(q→? r) )→(? r→p) 证明主析取范式法 ((p→q)∧(q→? r) )→(? r→p) ?p∨ r ?m1∨m3∨m4∨m5∨m6 ∨m7 主析取范式中缺少m0，m2，不是重言式，不正确。 前提: p∨q, q→r, p→s, ?s结论: r∧(p∨q) 直接证明法 证明①p→s 前提引入 ②? s 前提引入 ③? p ①②拒取式 ④p∨q 前提引入 ⑤q③④析取三段论 ⑥q→r 前提引入 ⑦r⑤⑥假言推理 ⑧r∧(p∨q) ⑦④合取 推理正确r∧(p∨q)是有效结论 构造推理的证明: 若明天是星期一或星期三, 我就有 课. 若有课, 今天必需备课. 我今天下午没备课. 所以, 明天不是星期一和星期三. 解设p:明天是星期一, q:明天是星期三， r:我有课，s:我备课 前提: (p∨q)→r, r→s, ?s 结论: ?p∧?q 前提: (p∨q)→r, r→s, ?s 结论: ?p∧?q 证明 ①r→s前提引入 ③?r①②拒取式 ④(p∨q)→r前提引入 ⑤?(p∨q) ③④拒取式 ⑥?p∧?q⑤置换 结论有效, 即明天不是星期一和星期三 例4前提: ?p∨q, ?q∨r, r→s结论: p→s 证明①p 附加前提引入 ②?p∨q 前提引入 ③q①②析取三段论 ④?q∨r 前提引入 ⑤r③④析取三段论 ⑥r→s 前提引入 ⑦s⑤⑥假言推理 推理正确p→s是有效结论 例5前提: ?(p∧q)∨r, r→s, ?s, p结论: ?q 证明用归缪法 ①q结论否定引入 ②r→s前提引入 ③?s前提引入 ⑤?(p∧q)∨r前提引入 ⑥?(p∧q) ④⑤析取三段论 ⑦?p∨?q⑥置换 ⑧?p①⑦析取三段论 ⑨p前提引入 ⑩?p∧p⑧⑨合取 推理正确?q是有效结论 例6前提: (p→q)→r, r→s, ?s结论: p∧?q 归结证明法 解(p→q)→r ? ?(?p∨q)∨r ? (p∧?q)∨r ? (p∨r)∧(?q∨r) r→s ? ?r∨s ?(p∧?q) ? ?p∨q 把推理的前提改写成 前提p∨r, ?q∨r, ?r∨s, ?s, ?p∨q (结论均为0, 不必写出) 前提p∨r, ?q∨r, ?r∨s, ?s , ?p∨q 证明①p∨r 前提引入 ②?p∨q 前提引入 ③q∨r ①②归结 ④?q∨r 前提引入 ⑤r③④归结 ⑥?r∨s前提引入 ⑦s⑤⑥归结 ⑧?s前提引入 ⑨0 ⑦⑧合取 第三章 将下述命题用0元谓词符号化, 并讨论它们的真值: (1) 根2是无理数, 而根3是有理数 (2) 如果2>3，则3<4 解(1) 设F(x): x是无理数, G(x): x是有理数 符号化为 真值为0 (2) 设F(x,y): x>y, G(x,y): x 符号化为F(2,3)→G(3,4) 真值为1 例3 在一阶逻辑中将下面命题符号化: (1)人都爱美; (2) 有人用左手写字 个体域分别取(a) 人类集合, (b) 全总个体域 . 解: (a) (1) 设F(x): x爱美, 符号化为?x F(x) (2) 设G(x): x用左手写字, 符号化为?x G(x) (b) 设M(x): x为人，F(x), G(x)同(a)中 (1) ?x (M(x)→F(x)) (2) ?x (M(x)∧G(x)) 例4 将下列命题符号化, 并讨论其真值: (1) 对任意的x, 均有x2-3x+2=(x-1)(x-2) (2) 存在x, 使得x+5=3 分别取(a) 个体域D1=N, (b) 个体域D2=R 解记F(x): x2-3x+2=(x-1)(x-2), G(x): x+5=3 (a) (1) ?x F(x) 真值为1 (2) ?x G(x) 真值为0 (b) (1) ?x F(x) 真值为1 (2) ?x G(x) 真值为1 例5 将下面命题符号化: (1) 兔子比乌龟跑得快 (2) 有的兔子比所有的乌龟跑得快 (3) 并不是所有的兔子都比乌龟跑得快 (4) 不存在跑得一样快的兔子和乌龟 解用全总个体域，令F(x): x是兔子, G(y): y是乌龟, H(x,y): x比y跑得快, L(x,y): x和y跑得一样快 (1) ?x?y(F(x)∧G(y)→H(x,y)) (2) ?x(F(x)∧(?y (G(y)→H(x,y))) (3) ??x?y(F(x)∧G(y)→H(x,y)) (4) ??x?y(F(x)∧G(y)∧L(x,y)) 例6 公式?x(F(x,y)→?yG(x,y,z)) ?x的辖域:(F(x,y)→?yG(x,y,z))，指导变元为x ?y的辖域:G(x,y,z)，指导变元为y x的两次出现均为约束出现 y的第一次出现为自由出现, 第二次出现为约束出现 z为自由出现. 例7 公式?x(F(x)→?xG(x)) ?x的辖域:(F(x)→?xG(x))，指导变元为x ?x的辖域:G(x)，指导变元为x x的两次出现均为约束出现. 但是, 第一次出现的x是?x中的x,第二次出现的x是?x中的x. 例1 消去公式中既约束出现、又自由出现的个体变项 (1) ?xF(x,y,z) →?yG(x,y,z) ??uF(u,y,z) →?yG(x,y,z) 换名规则 ??uF(u,y,z) →?vG(x,v,z) 换名规则 (2) ?x(F(x,y) →?yG(x,y,z)) ??x(F(x,y) →?tG(x,t,z)) 换名规则 例2 设个体域D={a,b,c}, 消去下面公式中的量词: (1) ?x(F(x)→G(x)) ? (F(a)→G(a))∧(F(b)→G(b))∧(F(c)→G(c)) (2) ?x(F(x)∨?yG(y)) ??xF(x)∨?yG(y) 量词辖域收缩?(F(a)∧F(b)∧F(c))∨(G(a)∨G(b)∨G(c)) (3) ?x?yF(x,y) ??x(F(x,a)∧F(x,b)∧F(x,c)) ? (F(a,a)∧F(a,b)∧F(a,c))∨(F(b,a)∧F(b,b)∧F(b,c)) ∨(F(c,a)∧F(c,b)∧F(c,c)) 例4 证明下列等值式: ??x(M(x)∧F(x)) ??x(M(x)→?F(x)) 证左边??x ?(M(x)∧F(x)) 量词否定等值式 ??x(?M(x)∨?F(x)) ??x(M(x)→?F(x)) 例5 求公式的前束范式 (1) ?xF(x)∧??xG(x) 解1 ??xF(x)∧?x?G(x) 量词否定等值式 ??x(F(x)∧?G(x)) 量词分配等值式 解2 ??xF(x)∧??yG(y) 换名规则 ??xF(x)∧?y?G(y) 量词否定等值式 ??x(F(x)∧?y?G(y)) 量词辖域扩张 ??x?y(F(x)∧?G(y)) 量词辖域扩张 第四章 笛卡儿积 A={0, 1}, B={a, b, c} A?B={<0,a>,<0,b>,<0,c>,<1,a>,<1,b>,<1,c>} B?A ={ (1) R={ ={<0,0>, <0,1>, <0,2>, <1,0>, <1,1>, <2,0>} (2) C={ C是直角坐标平面上点的横、纵坐标之间的关系， 离散数学必备知识点总 结 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、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材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：他用功，命题“他虽聪明但不用功”的符号化正确的是（） 《离散数学》考试题库及答案 一、 填空 10% （每小题 2分） 1、 若P ，Q 为二命题，Q P ?真值为1，当且仅当 。 2、 对公式),()),(),((y x xR z x zQ y x yP ?∨?∧?中自由变元进行代入的 公 式 为 。 3、 )) (()(x xG x xF ??∧?的 前 束 范 式为 。 4、 设x 是谓词合式公式A 的一个客体变元，A 的论域为D ，A （x ）关于y 的自由的， 则 被称为全称量词消去规则，记为US 。 5、 与非门的逻辑网络为 。 二、 选择 30% （每小题 3分） 1、 下列各符号串，不是合式公式的有（ ）。 A 、R Q P ?∧∧)(； B 、)()((S R Q P ∧→→； C 、R Q P ∧∨∨； D 、S R Q P ∨∧∨?))((。 2、 下列语句是命题的有（ ）。 A 、2是素数； B 、x+5 > 6； C 、地球外的星球上也有人； D 、这朵花多好看呀！。 3、 下列公式是重言式的有（ ）。 A 、)(Q P ??； B 、Q Q P →∧)(； C 、P P Q ∧→?)(； D 、P Q P ?→)( 4、 下列问题成立的有（ ）。 A 、 若C B C A ∨?∨，则B A ?； B 、若C B C A ∧?∧，则B A ?； C 、若B A ???，则B A ?； D 、若B A ?，则B A ???。 5、 命题逻辑演绎的CP 规则为（ ）。 A 、 在推演过程中可随便使用前提； B 、在推演过程中可随便使用前面演绎出的某些公式的逻辑结果； C 、如果要演绎出的公式为C B →形式，那么将B 作为前提，设法演绎出C ； 离散数学复习注意事项： 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.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.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r); 数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x 存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作 不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取 第一章 定律证明: (1) A?B=B?A (交换律) 证?x x∈A?B ? x∈A 或x∈B, 自然有x∈B 或x∈A ? x∈B?A 得证A?B?B?A. 同理可证B?A?A?B. (2) A?(B?C)=(A?B)?(A?C) (分配律) 证?x x∈A?(B?C) ? x∈A或(x∈B且x∈C ) ?(x∈A或x∈B)且(x∈A或x∈C) ?x∈(A?B)?(A?C) 得证A?(B?C)?(A?B)?(A?C). 类似可证(A?B)?(A?C)?A?(B?C). (3) A?E=E (零律) 证根据并的定义, 有E?A?E. 根据全集的定义, 又有A? E?E. (4) A?E=A (同一律) 证根据交的定义, 有A?E?A. 又, ?x x∈A, 根据全集E的定义, x∈E, 从而x∈A且x∈E, ?x∈A?E 得证A?A?E. 例4 证明A?(A?B)=A（吸收律） 证利用例3证明的4条等式证明 A?(A?B) = (A?E)?(A?B) (同一律) = A?(E?B) (分配律) = A?(B?E) (交换律) = A?E (零律) = A (同一律) 例5 证明(A-B)-C=(A-C)-(B-C) 证(A-C)-(B-C) = (A ?~C) ? ~(B ? ~C) (补交转换律) = (A ?~C) ? (~B ? ~~C) (德摩根律) = (A ?~C) ? (~B ? C) (双重否定律) = (A ?~C? ~B)?(A ?~C? C) (分配律) = (A ?~C? ~B)?(A ??) (矛盾律) = A ?~C? ~B (零律,同一律) = (A ?~B) ? ~C (交换律,结合律) 离散数学课程总结 姓名： 学号： 班级：级计科系软件工程（）班 近年来，计算机科学与技术有了飞速发展，在生产与生活的各个领域都发挥着越来越重要的作用。离散数学是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程。 一、课程总结 本书的主要内容有数理逻辑、集合论、代数结构、组合数学、图论以及初等数论六部分，而我们主要学习的有第一部分数理逻辑、第二部分集合论以及第五部分图论，第三部分代数结构也学习了一部分。第一部分：数理逻辑 数理逻辑是研究推理的数学分支，推理有一些列的陈述句组成。在数理逻辑中，主要学习了命题逻辑的基本概念、命题逻辑的等值演 算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理。 1.在命题逻辑的基本概念中学习了命题的真值及真值表、命题与联 结词、命题及其分类、联结词与复合命题、命题公式及其赋值。2.在命题逻辑的等值演算中主要学习了等值式与基本的等值式模式、 等值演算与置换规则、析取范式与合取范式，极大值和极小值，主析取范式与主合取范式、联结词完备集。 3.在命题逻辑的推理理论中主要学习了推理的正确与错误、推理的 形式结构、判断推理正确的方法、推理定律；自然推理系统P、形式系统的定义与分类、自然推理系统P，在P中构造证明：直接证明法、附加前提证明法、归谬法。 4.在一阶逻辑基本概念中主要学习了一阶逻辑命题符号化、个体词、 谓词、量词、一阶逻辑公式及其解释、一阶语言、合式公式及合式公式的解释、永真式、矛盾式、可满足式。 5.在一阶逻辑等值演算与推理中主要学习了一阶逻辑等值式与基本 等值式、置换规则、换名规则、代替规则、前束范式、自然推理系统N及其推理规则。 第二部分：集合论 在集合论中，主要学习了集合代数、二元关系和函数。 1.在集合代数中，学习了集合的基本概念：属于、包含、空集、元 集、幂集、全集；集合的基本运算：并、交、补相对、对称差等； 集合恒等式：集合运算的主要算律、恒等式的证明方法。 数理逻辑部分 第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 是简单命题 . 说明: 离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若 总结离散数学知识点 第二章命题逻辑 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={离散数学必备知识点总结
离散数学复习要点
《离散数学》考试题库及答案(三)
离散数学期末练习题-(带答案)
离散数学知识点整理
离散数学习题
离散数学第二章一阶逻辑知识点总结
离散数学第四章二元关系和函数知识点总结
离散数学例题整理
离散数学课程总结
离散数学第一章命题逻辑知识点总结
离散数学题目大汇总
(完整word版)离散数学必备知识点总结.docx
大学离散数学期末重点知识点总结(考试专用)
相关主题
文本预览