离散数学公式
离散数学公式
————————————————————————————————作者: ————————————————————————————————日期：
?
基本等值式
1．双重否定律A?┐┐A
２．幂等律 A ? A∨A,?A ?A∧A
3．交换律?Ａ∨Ｂ?B∨A，?A∧B ?B∧A
4.结合律??（Ａ∨Ｂ)∨Ｃ? A∨（B∨Ｃ) ?(A∧B)∧C ? A∧(Ｂ∧Ｃ)
５.分配律Ａ∨(B∧C）?（Ａ∨B)∧(Ａ∨C）(∨对∧的分配律）??A∧(B∨Ｃ）?(A∧B）∨（A∧Ｃ) (∧对∨的分配律)
6.德·摩根律?┐(A∨B) ?┐A∧┐B ┐（A∧Ｂ）?┐A∨┐B
7.吸收律?Ａ∨(Ａ∧Ｂ) ?A,A∧(A∨B) ?Ａ
8．零律?A∨１?1,A∧0 ?０
９.同一律?A∨0 ?A，A∧1?Ａ
10．排中律A∨┐A ?１
11．矛盾律?A∧┐Ａ? 0
12.蕴涵等值式Ａ→B?┐A∨B
１3．等价等值式??Ａ?Ｂ?(A→B）∧(Ｂ→Ａ)
１4.假言易位A→Ｂ?┐Ｂ→┐A
15.等价否定等值式 A?B ?┐Ａ?┐Ｂ
16.归谬论(A→Ｂ)∧（A→┐B)?┐A
求给定公式范式的步骤
(1)消去联结词→、?(若存在)。
(2）否定号的消去(利用双重否定律)或内移(利用德摩根律)。
(３）利用分配律：利用∧对∨的分配律求析取范式,∨对∧的分配律求合取范式。
推理定律-－重言蕴含式
(１）A ?(A∨B) 附加律
(2) （A∧B）? A ?化简律
（3） (Ａ→B)∧Ａ? B ??假言推理
(４) (Ａ→B)∧┐Ｂ?┐A 拒取式
（5）(A∨B）∧┐B? A ?析取三段论
(6) (A→B) ∧（Ｂ→C)?（A→C) ?假言三段论
(7) (Ａ?B) ∧（B?C) ? (Ａ? C)?等价三段论
（8) (A→B)∧（Ｃ→Ｄ）∧(A∨Ｃ) ?(B∨Ｄ) 构造性二难
(A→B)∧(┐Ａ→B)∧(Ａ∨┐A) ?Ｂ构造性二难（特殊形式)
（9)(A→B)∧(Ｃ→Ｄ)∧(┐B∨┐D) ?(┐Ａ∨┐C) 破坏性二难
设个体域为有限集D＝{a１,ａ２,…,an}，则有
(1）?xA(x) ? A(a1)∧Ａ(a２)∧…∧A（aｎ)
（２)?ｘＡ(x）?A(a1)∨Ａ(a2）∨…∨A(ａｎ)
设A（x)是任意的含自由出现个体变项x的公式，则
（１)┐?ｘＡ(x)??x┐A(x)
（2)┐?xＡ(x) ??x┐A(ｘ)
设A(x）是任意的含自由出现个体变项x的公式,B中不含x的出现，则(１) ?ｘ(A(x)∨B) ??xA(x)∨B
???x(A(x)∧B)??xA(x)∧B
??x（A(x）→B)??xA(x）→B
?x(Ｂ→A(x)) ? B→?xA（x)
(2)?x(A(x)∨Ｂ）??xA(x)∨B
?x(A(x)∧B) ??xA(ｘ)∧B
?x(A(x）→B) ??xＡ(ｘ)→Ｂ
?x(B→Ａ(x))? B→?xA（x)
设A(x)，Ｂ(x)是任意的含自由出现个体变项ｘ的公式，则
(１)?x(A（x）∧B(x）)??xＡ（x)∧?xB(x)
(２)?x(Ａ(x）∨B（x）) ??xＡ(x)∨?xB(ｘ)
全称量词“?”对“∨”无分配律。
存在量词“?”对“∧”无分配律。
ＵI规则。
UG规则。
?
ＥG规则。
A(c)
xA(x)
或
A(y)
xA(x)
∴
?
∴
?
xA(x)
A(y)
?
∴
xA(x)
A(c)
?
∴
EI 规则。
A ∪Ｂ＝{x|ｘ∈Ａ∨ｘ∈Ｂ ｝ 、
A ∩Ｂ={x|x ∈A ∧x ∈Ｂ } A －B={x|x ∈A ∧x ?
B ｝ 幂集 P(A)＝{x | x ?A ｝
对称差集 A ⊕B=(Ａ-B)∪（B-Ａ）
A ⊕Ｂ=(Ａ∪B)-(A ∩
B ）
绝对补集 ～Ａ={x|x ? A ｝
广义并 ∪A ＝{x | ?z(z ∈Ａ∧x ∈ｚ）} 广义交 ∩A ＝{x | ?z （z ∈Ａ→ｘ∈ｚ）}
设 A={{a,b,c}，{ａ,ｃ,d}，{a,e,f}} Ｂ=｛{ａ}｝ C ＝{ａ，{c,d}} 则?? ∪A ＝{a,b,c,ｄ，e,f ｝
∪Ｂ＝{a} ∪C=a ∪{c,d} ? ∪?＝? ∩A ＝{a ｝ ? ∩B ＝{a ｝ ? ∩C ＝a ∩{c,d}
集合恒等式 幂等律 A ∪A ＝A A ∩Ａ=A ? 结合律 (A ∪B)∪C=Ａ∪(B ∪Ｃ) ? (A ∩B)∩C=Ａ∩(B ∩C) ?
A(c)xA(x)∴?
交换律A∪Ｂ＝Ｂ∪A A∩Ｂ=B∩A
分配律A∪(B∩C)＝(A∪B)∩（A∪C) Ａ∩(Ｂ∪C）=（A∩B)∪(A∩C)?
同一律Ａ∪?＝A?A∩E＝Ａ
零律A∪E＝ＥA∩?=??
排中律A∪~A=E
矛盾律?Ａ∩～A=?
吸收律A∪（A∩B)＝A A∩(A∪B)=A
德摩根律Ａ－(Ｂ∪Ｃ)＝（A-B)∩(Ａ－Ｃ）Ａ－(B∩C)＝(A-B)∪(A－Ｃ)
～(B∪Ｃ）=～B∩~C～(B∩C)=～B∪~C
~?＝E~E=?
双重否定律?～（～A)=A
集合运算性质的一些重要结果
A∩B?Ａ，Ａ∩Ｂ?B??
A?Ａ∪Ｂ,B?Ａ∪B??
Ａ－B?A
Ａ－B＝A∩~B ?
A∪B＝Ｂ? A?B?Ａ∩B=A ?Ａ－B=?
A⊕Ｂ＝B⊕A?
(A⊕B)⊕C=A⊕（B⊕C)?
Ａ?⊕=A ?
A⊕A=???
Ａ⊕Ｂ=A⊕C ?B＝Ｃ?
对偶(duaｌ)式：一个集合表达式，如果只含有∩、∪、～、?、E、=、?、?,那么同时把∩与∪互换,把?与E互换，把?与?互换，得到式子称为原式的对偶式。
有序对 (２）<ｘ，y>=<ｕ，v>的充分必要条件是x=u且ｙ=v。 笛卡儿积的符号化表示为Ａ×Ｂ＝{ 如果｜A|=m,|Ｂ|=n，则|A×Ｂ｜＝mn。 笛卡儿积的运算性质 (1）对任意集合A,根据定义有 A×?=?，?×A=? （2）一般的说,笛卡儿积运算不满足交换律,即 ?A×B≠B×A ??(当A≠?∧B≠?∧A≠Ｂ时) (3)笛卡儿积运算不满足结合律，即 (A×B)×Ｃ≠Ａ×(Ｂ×C) (当A≠?∧B≠?∧Ｃ≠?时) (４)笛卡儿积运算对并和交运算满足分配律,即 ?A×(Ｂ∪C)=(A×Ｂ)∪（A×C）(B∪C)×A=(B×A)∪(C×A) A×(B∩C)=(A×B)∩（A×C）(B∩C)×A＝(B×A)∩(C×A）(5)Ａ?C ∧Ｂ?D?Ａ×B ?Ｃ×D 常用的关系 对任意集合A ，定义 ?全域关系 EA={ 小于或等于关系：LA={<ｘ，ｙ＞|x,y ∈A ∧x ≤ｙ｝，其中 A ?Ｒ。 整除关系：DB=｛<ｘ,y ＞|x,ｙ∈B ∧x 整除y}，其中 A ?Z* ，Z*是非零整数集 包含关系:R ?＝{＜x ，y>|x,y ∈A ∧x ?y},其中 Ａ是集合族。 关系矩阵和关系图 设 A={１,２，3，4｝，R=｛<1,1＞，<1,2>,<2，3＞,<2,4＞，＜４,2＞}，?则R 的关系矩阵和关系图分别是 ????? ???? ???=00 1 000011000011M R 定义域 ｄo ｍ Ｒ = {x | ?y(＜x,y ＞∈R )} 值域 ｒan R={y ｜ ? x(＜x ，y>∈R)} 域 f ｌd R=d ｏm Ｒ ∪ ｒa ｎ Ｒ 例 求R ＝{<１,2>,<1,3＞，<2，4>，<4,3>}的定义域、值域和域。 解答?ｄom R=｛1，2,4} ran R ＝{2，3,4} ｆld R ＝｛１,２,3,４} 逆 R-1＝{＜x ，ｙ>｜ 右复合 F ?G={ 限制 R ↑A={ 例 设R ＝{<1,2>,＜1，3>，<2，２>,<2,４>，<3,2>} R ↑{1}={<1,２＞，＜1,３>｝ R ↑? =? R ↑｛２,３}={<2,2＞,<2,4>｝，<3，2>} R[{1}]=｛2，3} R[?] =? R[{3｝]＝{2} 设F 是任意的关系,则 (1)(F-1）-１=F (2)dom F －1=ra ｎ Ｆ，ｒan Ｆ-1=ｄｏm F 设F ，G ，H 是任意的关系，则 (1)(F ?Ｇ)?Ｈ＝F ?(G ?H) (2)(F ?Ｇ）－1=Ｇ-1 ? F-1 设R 为A 上的关系,则R ? ＩA=I Ａ? R=R 设F,Ｇ，H 是任意的关系,则 (1） Ｆ?(G ∪H ）＝Ｆ?Ｇ∪F ?H （２）(G∪Ｈ)?Ｆ＝Ｇ?F∪H?F3(?）F?（G∩Ｈ)?F?Ｇ∩F?H4(?) (Ｇ∩H)?F?Ｇ?Ｆ∩H?F 设F为关系,A,Ｂ为集合，则 (1)Ｆ↑（A∪B）=F↑A∪F↑B （２）F［A∪B]=F［A］∪Ｆ[B] (３)F↑(A∩B)＝F↑A∩Ｆ↑B (４) F[A∩B]?Ｆ［A]∩F［B] 关系的幂运算 设R为A上的关系,n为自然数，则R的n次幂定义为: (1)Ｒ0＝{ (2）Rｎ＋１＝Rn ?R 幂运算的性质 设A为ｎ元集,R是A上的关系,则存在自然数s和t,使得Ｒｓ=Rt。 设R是A上的关系，m，n∈Ｎ,则 (１)Ｒm ? Rn＝Rm+n （２)(Rm)ｎ=Rmn 设Ｒ是A上的关系，若存在自然数s，t（ｓ (1) 对任何ｋ∈Ｎ有Rs+k=Ｒt+ｋ (２）对任何k,ｉ∈Ｎ有Ｒｓ+ｋp+ｉ＝Rs+i,其中ｐ=t-s (3) 令S＝{Ｒ０,R１，…,Rt－１},则对于任意的q∈Ｎ有Ｒｑ∈S 自反?ｘ(x∈A→ 反自反?ｘ(ｘ∈A→<ｘ,ｘ＞?R)， 对称?ｘ?y(x,y∈Ａ∧<ｘ,y＞∈Ｒ→ 反对称?x?ｙ(x,y∈A∧ 传递?x?y?z(x,y，ｚ∈A∧ 关系性质的等价描述 设R为Ａ上的关系,则 (1)Ｒ在Ａ上自反当且仅当ＩA? R (２）R在A上反自反当且仅当R∩IA＝? （3)R在Ａ上对称当且仅当Ｒ=R-1 (4）R在A上反对称当且仅当Ｒ∩R-1 ? IA (5)R在A上传递当且仅当R?R?R (1)若R1，R2是自反的和对称的,则R１∪R2也是自反的和对称的。 (２)若R１和R２是传递的，则Ｒ１∩Ｒ2也是传递的。 关系性质的特点 自反性反自反性对称性反对称性传递性 R?Ｒ?R 集合表达式ＩＡ?ＲR∩IA=?R＝Ｒ-1 Ｒ∩R-1 ? IA 关系矩阵主对角线元 素全是１主对角线元素 全是０ 矩阵是对称矩 阵 若rij＝1,且i≠ j，则rjｉ=0 对M２中1所 在位置,M中相 应的位置都是 1 关系图每个顶点都 有环每个顶点都没 有环 如果两个顶点 之间有边,一 定是一对方向 相反的边(无 单边) 如果两点之间 有边，一定是 一条有向边(无 双向边) 如果顶点ｘi 到xj有边，xj 到xk有边，则 从xｉ到xk也 有边 关系的性质和运算之间的关系 自反性反自反性对称性反对称性传递性R1－1 √√√√√ R1∩R2 √√√√√ R１∪Ｒ2 √√√×× R１-R2 ×√√√× R1 ? R2 √×××× 闭包的构造方法 设R为A上的关系，则有 ?(1)自反闭包r（R)=R∪R０ （2）对称闭包s(Ｒ）＝R∪R-1 （3）t(Ｒ)＝R∪Ｒ2∪Ｒ3∪… 关系性质与闭包运算之间的联系 设R是非空集合A上的关系， (１)若R是自反的，则s(R)与t(Ｒ)也是自反的。 ?（2)若R是对称的,则r(R)与t(Ｒ)也是对称的。 ?（3）若Ｒ是传递的,则r(R)是传递的。 等价类的性质 设R是非空集合A上的等价关系，则 (1)?x∈A,[x］是A的非空子集。 （2)?ｘ,ｙ∈A,如果xRy，则[x］＝［y]。 （3)?x,y∈A,如果＜ｘ,y>?Ｒ,则［ｘ]与[y]不交。 （4)∪｛[x]|x∈Ａ}=A。 偏序集中的特殊元素 设＜A,≤>为偏序集,B ?A,y ∈B 。 （１）若?x(ｘ∈Ｂ→y ≤x)成立,则称y 为B 的最小元。 (2)若?ｘ(ｘ∈Ｂ→x ≤ｙ)成立，则称y 为B 的最大元。 (3)若?x(x ∈Ｂ∧x ≤y →x=y)成立,则称y 为Ｂ的极小元。 (４)若?x(x ∈B ∧y ≤x →x=y)成立,则称y 为Ｂ的极大元 B 上界 下界 上确界 下确界 {2,３,６,12,24,36} 无 无 无 无 {６，12} 1２，24,36 2，3,6 12 ６ {2,3,6} ６,1２,24，3６ 无 6 无 ｛6} 6,12,24，36, ２，3,6, 6 6 函数相等 由定义可知，两个函数F 和G 相等, 一定满足下面两个条件: （1)do ｍ F ＝dom Ｇ （2)?ｘ∈ｄom F ＝do ｍ G ，都有 Ｆ（x )＝G(x ) 所有从A 到Ｂ的函数的集合记作BA,读作“B 上A ”，符号化表示为 BA={f | f :A →B} 。 例：设A ＝｛1,2,3｝,B={a,b}，求B Ａ。 ＢA ＝｛ f 0, f 1， f 2, ｆ3， ｆ４， f 5, ｆ6, f ７} 。其中 ｆ 0＝{＜１,a ＞,<2,a>,<3,a ＞｝ f 1=｛<1，ａ>,<2，a ＞，<3，b ＞} f 2=｛<1,ａ>，＜2,b ＞,＜3,a>} f 3={<1,a>,<2,b>,<3,b>} f 4={<1,b>，<2,ａ>,<3,a>} f 5={<１,b>，＜2,a>，<3,b>｝ f 6＝{<1,b ＞,<２,ｂ>，<３,ａ>} f 7＝{<1,b ＞，<2，b ＞，<3,b>} 设f :A →B ，(1)若r ａn ｆ=B ，则称f :Ａ→B 是满射(ｓurj ｅct ｉon )的。 (2）若?y ∈ｒan f 都存在唯一的ｘ∈A 使得ｆ（x )=y,则称 ｆ:A →Ｂ是单射(inj ｅｃtio ｎ)的。 B 最大元 最小元 极大元 极小元 ｛2,３,６,1２,2４,3６} 无 无 24,3６ 2，３ {6,１2} 12 6 12 6 {２,3,6} 6 无 6 ２，３ {6｝ 6 6 ６ 6 36 3 24 2 12 6 (3)若f 既是满射又是单射的,则称f :A →B 是双射(biject ｉｏn ) 单射 双射 函数 满 射 例：判断下面函数是否为单射、满射、双射的，为什么? (1） ｆ:R →R,f(x)= -x ２＋2x －1 (2) f ：Z+→R ，f(x ）＝ｌｎ x,Z+为正整数集 (3) ｆ:R →Z ，ｆ(x)=?x ? （４) f ：R →R ，f(ｘ)=2ｘ+１。 解（１)f 在ｘ=１取得极大值0。既不是单射也不是满射的。 (2）f 是单调上升的，是单射的，但不满射。ran ｆ={ｌn1， ln2， …}。 （３）f 是满射的， 但不是单射的,例如f(1.5)=f(1.２)=1。 （4）f 是满射、单射、双射的,因为它是单调函数并且ran f ＝R 。 例:（1) 给定无向图G=＜Ｖ，Ｅ＞，其中 V=｛v １,v2,ｖ3,v4,v5}，?E=｛(v1,v1),（v1,v ２),(v2，v3）,（v2,v3）,(v2,v5），(ｖ１,v5),(ｖ４,v5)}. （2) 给定有向图D=＜V ,E>，其中 V ＝｛a,b,c,d}， ?E=｛ 邻域:ＮG(v １) ＝{v 2,v ５｝ 后继元集:Г+D (ｄ ) ＝｛ｃ} 闭邻域：NG(v 1) ＝{ｖ１,v 2，ｖ5}? 先驱元集:Г-D （d ) ＝{a ，ｃ} 关联集：IG(v １） ＝{ｅ1，e 2，e 3｝ ? 邻域: ＮD(d ) ＝{a ,c ｝ 闭邻域：ＮＤ(ｄ ） ＝{a ,c ,d } d (v 1）＝4(注意，环提供2度)， 出度：ｄ＋(a ）＝4，入度：d -(a )＝１ △＝４,δ=1, （环 e １提供出度１,提供入度１）， a b c 1 2 3 d a b c 1 2 3 4 a b c 1 2 3 4 d a b c 1 2 3 4 d v４是悬挂顶点,e7是悬挂边。d(ａ)=4+1=５。△＝5,δ=3， △+=4 (在a点达到） 度数列为4,4,2,1,３。δ+=0(在ｂ点达到） △-＝3(在b点达到) δ-＝１(在a和ｃ点达到） 按字母顺序,度数列:5，３,3,3 出度列：4，0,2,1入度列：1,3,1,2 设G= (1)G是树。（2)G中任意两个顶点之间存在唯一的路径。 (3)G中无回路且m＝n-1。（４)G是连通的且m＝n-1。 （5)G是连通的且G中任何边均为桥。 (6)G中没有回路,但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。 例题已知无向树Ｔ中,有1个３度顶点，2个２度顶点，其余顶点全是树叶，试求树叶数，并画出满足要求的非同构的无向树。 解答设有x片树叶，于是结点总数 ?n＝1+2+x=3+x ?由握手定理和树的性质m=n-1可知， ? 2m=2（n-１)=2×(2+x) ??=1×３+２×２+x 解出x=3，故T有3片树叶。 ??故T的度数应为1、1、1、2、2、3。 求最小生成树的算法(避圈法（Kruskal）） (１)设n阶无向连通带权图G= (2)取e１在T中。 (3)依次检查e2,…,em ,若ｅj(j≥2）与已在T中的边不构成回路,取ej也在T中，否则弃去ej。（4)算法停止时得到的T为G的最小生成树为止。 例:求下图所示两个图中的最小生成树。 W(T1)=６W(T２）=12 Ｔ是ｎ（ｎ≥2)阶有向树， (1) Ｔ为根树—T中有一个顶点入度为0，其余顶点的入度均为1 (2）树根——入度为０的顶点 (３)树叶——入度为1，出度为0的顶点 (４) 内点——入度为１,出度不为0的顶点 (５）分支点——树根与内点的总称 （6) 顶点v的层数——从树根到ｖ的通路长度 （7) 树高——T中层数最大顶点的层数 根树的画法：树根放上方，省去所有有向边上的箭头。 树叶——8片内点——6个分支点——7个高度 ——５ 求带权为1、１、2、3、4、5的最优树。 Ｗ(T)=38 中序行遍法:ｂａ(ｆd g) c e前序行遍法：ａｂ(c (d f g)e） 后序行遍法：ｂ((f g d) e c)ａ 、基本等值式 ⑴双重否定律 A A ⑵籍等律 A A A A A V A A ⑶交换律 A A B BA A A V B BV A ⑷结合律 A V (B V C) (A V B) V C A A (B A C) (A A B) A C ⑸分配律 A V (B A C) (A V B) A (A V C) A A (B V C) (A A B) V (A A C) (6)德摩根律(A V B) AA B (A A B) AV B ⑺吸收律 A (8)零律A ⑼同一律 A (10) 排中律 A (11) 矛盾律 A (12) 蕴含等值式A (13) 等价等值式A V (A A B) V1 1 A1 A V A 1 A A 0 B AV B (A A A A A B B) A (B A) A (A V B) A 0 0 V 0 A A A B (AV B) A (A V B) A B (A A B) V ( AA B ) (14) 假言易位ABBA (15) 等价否定等值式ABA B (16)归谬论(A B) A (A B) A 一、推理定律里口编涵式 1.A ( A B) 附加律 2.( A B) A 化简律 3.( A B) A B 假言推理 4.( A B) B A 拒取式 5.( A B) B A 析取三段论 6.( A B) (B C) (A 假言三段论 7.( A B) (B Q (A C) 等价三段论 8.( A B) (C D) (A C) (B D) 构造性二难 (A B) ( A B) B 构造性二难(特殊形式) 9.( A B) (C D) ( B D) ( A Q 破坏性二难 三、量词辖域收缩与扩张 x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) AB x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) A B x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) 四、量词分配 x(A(x) A B(x)) xA(x) A xB(x) x(A(x) V B(x)) xA(x) V xB(x) x(A(x) V B(x)) xA(x) V xB(x) 离散数学公式 ————————————————————————————————作者: ————————————————————————————————日期： ? 基本等值式 1．双重否定律A?┐┐A ２．幂等律 A ? A∨A,?A ?A∧A 3．交换律?Ａ∨Ｂ?B∨A，?A∧B ?B∧A 4.结合律??（Ａ∨Ｂ)∨Ｃ? A∨（B∨Ｃ) ?(A∧B)∧C ? A∧(Ｂ∧Ｃ) ５.分配律Ａ∨(B∧C）?（Ａ∨B)∧(Ａ∨C）(∨对∧的分配律）??A∧(B∨Ｃ）?(A∧B）∨（A∧Ｃ) (∧对∨的分配律) 6.德·摩根律?┐(A∨B) ?┐A∧┐B ┐（A∧Ｂ）?┐A∨┐B 7.吸收律?Ａ∨(Ａ∧Ｂ) ?A,A∧(A∨B) ?Ａ 8．零律?A∨１?1,A∧0 ?０ ９.同一律?A∨0 ?A，A∧1?Ａ 10．排中律A∨┐A ?１ 11．矛盾律?A∧┐Ａ? 0 12.蕴涵等值式Ａ→B?┐A∨B １3．等价等值式??Ａ?Ｂ?(A→B）∧(Ｂ→Ａ) １4.假言易位A→Ｂ?┐Ｂ→┐A 15.等价否定等值式 A?B ?┐Ａ?┐Ｂ 16.归谬论(A→Ｂ)∧（A→┐B)?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2）否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (３）利用分配律：利用∧对∨的分配律求析取范式,∨对∧的分配律求合取范式。 推理定律-－重言蕴含式 (１）A ?(A∨B) 附加律 (2) （A∧B）? A ?化简律 （3） (Ａ→B)∧Ａ? B ??假言推理 (４) (Ａ→B)∧┐Ｂ?┐A 拒取式 （5）(A∨B）∧┐B? A ?析取三段论 (6) (A→B) ∧（Ｂ→C)?（A→C) ?假言三段论 (7) (Ａ?B) ∧（B?C) ? (Ａ? C)?等价三段论 （8) (A→B)∧（Ｃ→Ｄ）∧(A∨Ｃ) ?(B∨Ｄ) 构造性二难 (A→B)∧(┐Ａ→B)∧(Ａ∨┐A) ?Ｂ构造性二难（特殊形式) （9)(A→B)∧(Ｃ→Ｄ)∧(┐B∨┐D) ?(┐Ａ∨┐C) 破坏性二难 《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (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）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44 离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。湖南省自考网：https://www.wendangku.net/doc/0b3563860.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。 基本等值式 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∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧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 ? (A→B)∧(B→A) 14.假言易位A→B ?┐B→┐A 15.等价否定等值式 A?B ?┐A?┐B 16.归谬论(A→B)∧(A→┐B) ?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。 推理定律--重言蕴含式 (1) A T (A∨B) 附加律 (2) (A∧B) T A 化简律 (3) (A→B)∧A T B 假言推理 (4) (A→B)∧┐B T┐A 拒取式 (5) (A∨B)∧┐B T A 析取三段论 (6) (A→B) ∧(B→C) T (A→C) 假言三段论 (7) (A?B) ∧(B?C) T (A ? C) 等价三段论 (8) (A→B)∧(C→D)∧(A∨C) T(B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A) T B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) T(┐A∨┐C)破坏性二难 第一章 1.假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A 和B表示ECNU不必学习离散数学的二年级的学生的集合。 2.试求： (1)P(φ) (2)P(P(φ)) (3)P(P(P(φ))) 3.在1~200的正整数中，能被3或5整除，但不能被15整除的正整数共有多少个？ 能被5整除的有40个， 能被15整除的有13个， ∴能被3或5整除，但不能被15整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 离散数学的基础知识点总结 第一章命题逻辑 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.全称量词用蕴含T,存在量词用合取“； 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0; 2.基：集合A中不同元素的个数，|A|; 3.幕集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幕集P(A)有2°个元素，|P(A)|= 2|A|= 2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔AXB的基数为mn , A到B上可以定义2mn种不同的关系； 2.若集合A有n个元素，则|A X\|= n2, A上有2n个不同的关系； 3.全关系的性质：自反性，对称性，传递性； 空关系的性质：反自反性，反对称性，传递性； 全圭寸闭环的性质：自反性，对称性，反对称性，传递性； 4.前域（domR）:所有元素x组成的集合； 离散数学部分概念和公式总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={ 离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q 总结离散数学知识点 第二章命题逻辑 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个不同的关系； 第2章谓词逻辑 一、教学要求 1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。 2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。 3. 掌握谓词演算的等值式和重言蕴含式(六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词∨，∧，→的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。 4. 了解前束范式的概念，会求公式的前束范式。 5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则) 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。 二、学习辅导 在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如 “凡人要死，张三是人，张三要死” 显然是正确推理. 用命题逻辑解释三段式. 设 P：人要死；Q张三是人；R：张三要死。 表示成复合命题有 P∧Q→R 这不是重言式，即R不是前提P，Q的有效结论. 这反映了命题逻辑的局限性，其原因是把本来有内在联系的命题P，Q，R，视为独立的命题。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。 1. 谓词与量词 学习这一部分要反复理解谓词和量词引入的意义，概念的含义。 在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。例如 (1)(1)ln5是无理数； (2)(2)高可比李木相高4cm； (3) 郑州位于北京和广州之间。 这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“……比……高4cm”，“……位于……和……之间”等都是谓词。 个体词分个体常项(用a,b,c,d,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表 02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={ 5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集 离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式 将一个普通公式转换为范式的基本步骤 1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?x(H(x)→B(x))，即量词的后面为条件式，带“存在量词”的谓词公式形如?x(H(x)∨WL(x))，即量词的后面为合取式 例题 R(x)表示对象 x 是兔子，T(x)表示对象 x 是乌龟， H(x,y)表示 x 比 y 跑得快，L(x,y)表示x 与 y 一样快，则兔子比乌龟跑得快表示为： ?x ?y(R(x)∧T(y)→H(x,y)) 有的兔子比所有的乌龟跑得快表示为：?x ?y(R(x)∧T(y)→H(x,y)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式 离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 图论部分 第七章、图的基本概念 7.1 无向图及有向图 无向图与有向图 多重集合: 元素可以重复出现的集合 无序积: A&B={(x,y) | x∈A∧y∈B} 定义无向图G= 通常用G表示无向图, D表示有向图, 也常用G泛指 无向图和有向图, 用e k表示无向边或有向边. V(G), E(G), V(D), E(D): G和D的顶点集, 边集. n 阶图: n个顶点的图 有限图: V, E都是有穷集合的图 零图: E=? 平凡图: 1 阶零图 空图: V=? 顶点和边的关联与相邻：定义设e k=(v i,v j)是无向图G= 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={ 第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) xF ?，在（a）中为假命题，在(b)中为真命题。 (x (2)在两个个体域中都解释为) ?，在（a）(b)中均为真命题。 xG (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ? x ?? ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F x→ ?? x ) H ( ( (x 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? ∧ y H )) ( , x ( ((y ( ) (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) y F x G y→ ?? ∧ ? H x ) x , ( ( (y ( ( ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x 离散数学基本知识 体积和表面积三角形的面积,底×高?2。公式S= a×h?2 正方形的面积,边长×边长公式 S= a2 长方形的面积,长×宽公式S= a×b 平行四边形的面积,底×高公式S= a×h 梯形的面积,(上底+下底)×高?2 公式 S=(a+b)h?2 内角和:三角形的内角 和,180度。 长方体的表面积,(长×宽，长×高，宽×高) ×2 公 式:S=(a×b+a×c+b×c)×2 正方体的表面积,棱长×棱长×6 公式: S=6a2 长方体的体积,长×宽×高公式:V = abh 长方体(或正方体)的体积,底面积×高公式:V = abh 正方体的体积,棱长×棱长×棱长公式:V = a3 圆的周长,直径×π公式:L,πd,2πr 1 圆的面积,半径×半径×π公式:S,πr2 圆柱的表(侧)面积:圆柱的表(侧)面积等于底面的周长乘高。公 式:S=ch=πdh,2πrh 圆柱的表面积:圆柱的表面积等于底面的周长乘高再加上两头的圆的面积。公式:S=ch+2s=ch+2πr2 圆柱的体积:圆柱的体积等于底面积乘高。公式:V=Sh 圆锥的体积,1/3底面×积高。公式:V=1/3Sh 算术 1、加法交换律:两数相加交换加数的位置，和不变。 2、加法结合律:a + b = b + a 3、乘法交换律:a × b = b × a 4、乘法结合律:a × b × c = a ×(b × c) 5、乘法分配律:a × b + a × c = a × b + c 6、除法的性质:a ? b ? c = a ?(b × c) 7、7、除法的性质:在除法里，被除数和除数同时扩大(或缩小)相同的倍数，商不变。 O除以任何不是O的数都得O。简便乘法:被乘数、乘数末尾有O的乘法，可以先把O前面的相乘，零不参加运算，有几个零都落下，添在积的末尾。 8、 8、有余数的除法: 被除数,商×除数+余数方程、代数与等式 2 9、等式:等号左边的数值与等号右边的数值相等的式子叫做等式。等式的基本性质:等式两边同时乘以(或除以)一个相同的数，等式仍然成立。 10、方程式:含有未知数的等式叫方程式。一元一次方程式:含有一个未知数，并且未知数的次数是一次的等式叫做一元一次方程式。学会一元一次方程式的例法及计算。即例出代有χ的算式并计算。 11、代数: 代数就是用字母代替数。代数式:用字母表示的式子叫做代数式。如:3x =ab+c 分数:把单位“1”平均分成若干份，表示这样的一份或几分的数,叫做分数。 分数大小的比较:同分母的分数相比较，分子大的大，分子小的小。异分母的分数相比较，先通分然后再比较;若分子相同，分母大的反而小。 分数的加减法则:同分母的分数相加减，只把分子相加减，分母不变。异分母的分数相加减， 先通分，然后再加减。 分数乘整数，用分数的分子和整数相乘的积作分子，分母不变。 分数乘分数，用分子相乘的积作分子，分母相乘的积作为分母。 3离散数学基本公式
离散数学公式
《离散数学》及答案
离散数学自学笔记命题公式及其真值表
离散数学公式
离散数学作业答案
离散数学的基础知识点总结
离散数学部分概念和公式总结
离散数学课后答案
离散数学知识点总结
《计算机数学基础(2)—离散数学》 谓词逻辑
离散数学答案
完整word版,离散数学知识汇总,推荐文档
离散数学试题及答案(1)
离散数学第七章图的基本概念知识点总结docx
离散数学部分概念和公式总结(考试专用)
离散数学答案【2】
离散数学基本知识