文档库 最新最全的文档下载
当前位置:文档库 › 等价关系习题

等价关系习题

等价关系习题
等价关系习题

习题十:等价关系与等价类

1.设R 和‘R 是集合A 上的等价关系,用例子证明R ‘R 不一定是等价关系。

2.试问由4个元素组成的有限集上所有的等价关系的个数为多少?

3.给定集合S ={1,2,3,4,5},找出S 上的等价关系R ,此关系R 能够产生划分{{1,2},{3},{4,5}}并画出关系图。

4.设R 是一个二元关系,设=S {??b a ,|对于某一c ,有R c a ∈??,且R b c ∈??,} ,证明若R 是一个等价关系,则S 也是一个等价关系。

5.设正整数的序偶集合A ,在A 上定义的二元关系R 如下:,,,,R v u y x ∈??????当且仅当yu xv =,证明R 是一个等价关系。

6.设R 是集合A 上的对称和传递关系,证明如果对于A 中的每一个元素a ,在A 中同时也存在一个b ,使??b a ,在R 之中,则R 是一个等价关系。

7.设21R R 和是非空集合A 上的等价关系,确定下述各式,哪些是A 上的等价关系,对不是的提供反例证明。

a)1)(R A A -?

b)21R R -

c)21R

d))(21R R r -(即21R R -的自反闭包)。

8.设*C 是实数部分非零的全体复数组成的集合,*C 上关系R 定义为:0)()>?++ac d c R b a i i (,证明R 是等价关系,并给出关系R 的等价类的几何说明。

9.设π和‘π是非空集合A 上的划分,并设R 和‘

R 是分别由π和π'诱导的等价关系,那么,π'细分π的充要条件是R '?R 。

10.设j R 表示I 上的模j 等价关系,k R 表示I 上的模k 等价关系,证明I /k R 细分I /j R 当且仅当k 是j 的整数倍。

11.A ,B 是全集E 的子集,各命题及由这些命题构成的集合X 如下所示。 {}z y w v u t s r q p X ,,,,,,,,,=,其中

p: E B A = ; q: B B A = ; r: B A ?; s: c c B A ?; t: B A c ?;

u: c c A B ?; v: Φ=B A ; w: B B A = ; y: c B A ?; z: A B ?.

又R 是X 上的命题间的等价关系,求商集X/R (c

A 表示A 的绝对补集)。

12. R 为集合X 上的二元关系,{}7,6,5,4,3,2,1=X ,{}><><><><><><=1,7,6,6,3,6,4,2,2,1,1,1R ,求

(1) R 的等价闭包*R (即包含R 的最小的等价关系);

(2) 求*R X /。

13. 设R 是集合A 上的等价关系,S 是A 上的对称关系,试问()()R S S R --~~ 是否是

A 上的等价关系?若是,请给出证明;若不是,请具体分析它具有哪些性质,并对

不成立的性质举出反例。

14.设R 是A 上的二元关系,定义()()(){

}R b c R c a A c b a S ∈∈∈?=,,,,,,证明:若R 是

A 上的等价关系,则S 也是等价关系,且S=R 。

15. 设R 和S 是集合A 上的关系,证明或否定下面结论:

(1) 若R ,S 是传递的,则S R 传递的充分必要条件是R S S R =;

(2) 若R ,S 是等价关系,则S R 是等价关系的充分必要条件是R S S R =。 16. 知R ,S 是集合A 上等价关系,且商集为:{}{}{}

{}f g e d c b a R A ,,,,,,/=,{}{}{}{}g f g d b c a S A ,,,,,,/=,显然,S R 也是等价关系,先画出S R 有向图,再写出商集S R A /。

17.证明定义在实数集合R 上的关系?

?????

-∈><=是整数3,,,y x R y x y x S 是一个等价关 系。

18. 设1R 是A 上的等价关系,2R 是B 上的等价关系,Φ≠A 且Φ≠B 。关系R 满足: R y x ,y ,x 2,211∈>?<>?<当且仅当121R x ,x >∈<且221R y ,y >∈<。

试证明:R 是B A ?上的等价关系。

19. 设N 是自然数集合,定义N 上的二元关系R :

{}

是偶数y x N y N x y x R +∈∈><=,,,

(1) 证明R 是一个等价关系;

(2) 求关系R 的等价类;

(3) 试设计一个从N 到N 的函数f ,使得由f 诱导的等价关系就是关系R 。

20. 设R 是集合A 上的一个具有传递和自反性质的关系,T 是A 上的关系,使得,R a ,b ,,>∈<>∈?<>∈<且R b a T b a 证明T 是一个等价关系。

21. 设R 是集合X 上的关系,对所有的X z y x ∈,,来说,如果有xRy 和yRz 就有zRx ,则称关系R 是循环关系,试证明:当且仅当R 是一个等价关系,R 才是自反和循环的。

22. 设R 是A 上的二元关系,1-R 是R 的逆关系。证明:R 是传递的当且仅当1-R 是传递的。

23. 给定{}6,5,4,3,2,1=X ,R 是X 上关系,其生成矩阵如下。

?????????

? ??100000000001000000000000001000

000100 问:)(R ts 是否为X 上等价关系?如是,写出商集)(/R ts X ,如不是,说明原因。()(R ts 是R 的对称、传递闭包)

24. 已知集合X 上的二元关系R 的关系矩阵为:

?????????

? ??=000001010000000000000001000100

010010R M 求(1)()R t M ; (2)()R rst M 。

25. 集合{}8,7,6,5,4,3,2,1=A ,R 为A 上二元关系,

{}。

><><><><><><><><><><><><><><><><><><=8,8,3,8,7,7,6,6,4,6,2,6,5,5,1,5,6,4,4,4,2,4,8,3,3,3,6,2,4,2,2,2,5,1,1,1R 求R A 。

测试用例编写之等价类划分法

测试用例编写之等价类划分法 一、概念 等价类划分法指把所有可能的输入数据,即程序的输入域分成若干个部分(子集)后,从每个子集中选取少数具有代表性的数据作为测试用例的方法。是一种重要且常用的黑盒测试的测试用例设计方法。 二、等价类划分 等价类可分为两种情况:有效等价类与无效等价类。有效等价类是指:对程序的规格说明是有意义的、合理的输入数据所构成的集合;无效等价类意义与之相反。 三、确定等价类的规则 如何确定等价类,这是使用等价类划分方法的一个重要问题。等价类的划分在很大程度上是试探性的,一般规则如下: 1)如果输入条件规定了取值的范围或取值的个数([0,99]),则可确定一个有效等价类和两个无效等价类(<0 ;[0,99];>99); 2)如果一个输入条件说明了一个“必须成立的”情况(如变量名必须以字母开头),则可划分一个有效等价类(以字母开头)和一个无效等价类(不以字母开头); 3)如果输入条件规定了输入数据的一组可能的值,而且程序是用不同的方式处理每一种值,则可为每一种值划分一个有效等价类,并划分一个无效等价类; 4)如果某个输入条件规定了一个输入值得离合(即离散值),且程序对不同的输入值做不同的处理,那么每个允许的值确定为一个有效等价类,另外还有一个无效等价类。(任意一个不允许输入的值、)例:优、良、中、差,则此时有4个有效等价类和1个无效等价类(非优、良、中、差的值就为无效) 5)如果某个输入条件规定输入数据是整型,那么可以确定3个有效等价类(正整数、零、负整数)和一个无效等价类(非整数)。 6)如果某个输入条件规定处理的对象是表格,那么可确定一个有效等价类(表有1项或多项)和一个无效等价类(空表)。 7)如果能够确知,已划分的某等价类中的各元素在程序中的处理方式是不同的,则应据此将此等价类进一步划分成更小的等价类。 四、建立步骤 根据已列出的等价类表,按以下步骤确定测试用例: 1) 为每个等价类规定一个唯一的编号; 2) 设计一个测试用例,使其尽可能多地覆盖尚未覆盖的有效等价类,重复这一步,最后使得所有的有效等价类都被测试用例所覆盖;

等价关系

“关系”一词,在日常生活中十分常见,在学校,有同学关系、师生关系、同事关系等; 在家庭中,有兄弟姐妹关系,父子关系、母女关系等;在一般的工作单位,有师徒关系、上 下级关系等等。在研究科学中也有很多关系,如数学中的数的大小比较关系、整数中整除关 系、函数关系、集合中的包含关系;计算机软件的程序与其子程序关系等。 为了数学的方法来研究这类关系,我们将用集合论的观点来描述这类关系。 例如,集合{}e d c b a A ,,,,=,为五个人组成的集合,其中他们中,a 是b 的父亲,c 是d 的 父亲,c 也是e 的父亲。现将集合A 的父子关系用有序对表示,即为),(),,(),,(e c d c b a 。把 这三个有序对组成一个集合{}),(),,(),,(e c d c b a R =,我们把R 这种由集合A 导出的有序 对组成的集合R ,叫做A 上关系 R 。 我们称集合R 为集合A 的父子关系集合(简称关系)。 我们把13个数组成的集合{}10,,3,2,1 =A 也建立几个关系。 二、建立关系举例: 1、 它们之间的小于等于关系R ; ()()()()()()(){},13,13,13,12,,3,2,2,2,3,1,2,1,1,1 =R 2、 它们除以3以后余数相同的关系1R ; ()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()()? ?????=,10,10,7,10,4,10,1,10,9,9,6,9,3,9,8,8,5,8,2,8,10,7,7,7,4,7,1,7,9,6,6,6,3,6,8,5,5,5,2,5,10,4,7,4,4,4,1,4,9,3,6,3,3,3,8,2,5,2,2,2,10,1,7,1,4,1,1,12R 3、它们之间的整除关系2R ; ()()()()()()()()()()()()()()()()()()()()? ?????=10,10,9,9,8,8,7,7,6,6,10,5,5,5,8,4,4,4,9,3,6,3,3,3,10,2,8,2,6,2,4,2,2,2,10,1,2,1,1,13 R 注意:关系有两大类关系:A 到B 的关系,A 上的关系;我们主要讨论A 上的关系。 三、关系的几种表示方法: 1、图形表示; 2、表格表示; 3、矩阵表示; 比如:{ }5,4,3,2,1=A 上的R 关系为()()()()()()(){},4,5,2,4,5,3,3,3,3,2,2,22,1=R 则??????? ? ??=01000000101010000110 00010R A

《离散数学》考试题库及答案(三)

《离散数学》考试题库及答案 一、 填空 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.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);

《离散数学》试题和答案及解析

一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B={3} ; ρ(A) - ρ(B)={3},{1,3},{2,3},{1,2,3}} . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 2 2n. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 . 4. 已知命题公式G=?(P→Q)∧R,则G的主析取范式是(P∧?Q∧R) 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为12,分枝点数为3. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B={4} ; A?B={1,2,3,4}; A-B={1,2} . 7.设R是集合A上的等价关系,则R所具有的关系的三个特性是自反性, 对称性传递性. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0) 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则 R1?R2 ={(1,3),(2,2),(3,1)} , R2?R1 = {(2,4),(3,3),(4,2)} _ R12 ={(2,2),(3,3). 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 = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} , A∩B ={x | 0≤x≤1, x∈R} , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除关系,则R以集合形式(列举法)记为 {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} . 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束范式是?x(?P(x)∨Q(x)) . 15.设G是具有8个顶点的树,则G中增加21 条边才能把G变成完全图。(完全图的边 数 2)1 (- n n ,树的边数为n-1) 16.设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除,写成与之对应的命题公式是_ (R(a)∧R(b))→(S(a)∨S(b)) _. 17. 设集合A={1, 2, 3, 4},A上的二元关系R={(1,1),(1,2),(2,3)}, S={(1,3),(2,3),(3,2)}。则

离散数学例题整理

第一章 定律证明: (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 (交换律,结合律)

【离散数学】知识点及典型例题整理

【半群】G非空,·为G上的二元代数运算,满足结合律。 【群】(非空,封闭,结合律,单位元,逆元)恰有一个元素1适合1·a=a·1=a,恰有一个元素a-1适合a·a-1=a-1·a=1。 【Abel群/交换群】·适合交换律。可能不只有两个元素适合x2=1 【置换】n元置换的全体作成的集合Sn对置换的乘法作成n 次对称群。 【子群】按照G中的乘法运算·,子集H仍是一个群。单位子群{1}和G称为平凡子群。 【循环群】G可以由它的某元素a生成,即G=(a)。a所有幂的集合an,n=0,±1,±2,…做成G的一个子群,由a生成的子群。若G的元数是一个质数,则G必是循环群。 n元循环群(a)中,元素ak是(a)的生成元的充要条件是(n,k)=1。共有?(n)个。【三次对称群】{I(12)(13)(23)(123)(132)} 【陪集】a,b∈G,若有h∈H,使得a =bh,则称a合同于b(右模H),a≡b(右mod H)。H有限,则H的任意右陪集aH的元数皆等于H的元数。任意两个右陪集aH和bH或者相等或者不相交。 求右陪集:H本身是一个;任取a?H而求aH又得到一个;任取b?H∪aH而求bH又一个。G=H∪aH∪bH∪… 【正规子群】G中任意g,gH=Hg。(H=gHg-1对任意g∈G都成立) Lagrange定理G为有限群,则任意子群H的元数整除群G的元数。 1有限群G的元数除以H的元数所得的商,记为(G:H),叫做H在G中的指数,H的指数也就是H的右(左)陪集的个数。 2设G为有限群,元数为n,对任意a∈G,有an=1。 3若H在G中的指数是2,则H必然是G的正规子群。证明:此时对H的左陪集aH,右陪集Ha,都是G中元去掉H的所余部分。故Ha=aH。 4G的任意多个子群的交集是G的子群。并且,G的任意多个正规子群的交集仍是G的正规子群。 5 H是G的子群。N是G的正规子群。命HN为H的元素乘N的元素所得的所有元素的集合,则HN是G的子群。 【同态映射】K是乘法系统,G到K的一个映射σ(ab)=σ(a)σ(b)。 设(G,*),(K,+)是两个群,令σ:x→e,?x∈G,其中e是K的单位元。则σ是G到K 内的映射,且对a,b∈G,有σ(a*b)=e=σ(a)+ σ(b)。即,σ是G到K的同态映射,G~σ(G)。σ(G)={e}是K的一个子群。这个同态映射是任意两个群之间都有的。 【同构映射】K是乘法系统,σ是G到σ(G)上的1-1映射。称G与σ(G)同构,G?G′。同构的群或代数系统,抽象地来看可以说毫无差别。G和G′同态,则可以说G′是G的一个缩影。 【同态核】σ是G到G′上的同态映射,核N为G中所有变成G′中1′的元素g的集合,即N=σ-1(1′)={g∈G∣σ(g)=1′}。 N是G的一个正规子群。对于Gˊ的任意元素aˊ,σ-1(aˊ)={x|x∈G ,σ(x)= aˊ}是N在G 中的一个陪集。Gˊ的元素和N在G中的陪集一一对应。 设N是G的正规子群。若A,B是N的陪集,则AB也是N的陪集。 【环】R非空,有加、乘两种运算 a+b=b+a2)a+(b+c)=(a+b)+c, 3)R中有一个元素0,适合a+0=a, 4)对于R中任意a,有-a,适合a+(-a)=0, 5)a(bc)=(ab)c,

离散数学题目大汇总

离散数学试题一(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分)若是群,H 是G 的非空子集,则的子群对任意的a 、b ∈H 有 a * b -1∈H 。 八、(15分)(1)若无向图G 中只有两个奇数度结点,则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点,它们一个可达另一个结点或互相可达吗 离散数学试题一(B 卷答案) 一、(15分)设计一盏电灯的开关电路,要求受3个开关A 、B 、C 的控制:当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。 u v w

离散数学习题答案

离散数学习题答案 习题二及答案:(P38) 5、求下列公式的主析取范式,并求成真赋值: (2)()()p q q r ?→∧∧ 解:原式()p q q r ?∨∧∧q r ?∧()p p q r ??∨∧∧ ()()p q r p q r ??∧∧∨∧∧37m m ?∨,此即公式的主析取范式, 所以成真赋值为011,111。 6、求下列公式的主合取范式,并求成假赋值: (2)()()p q p r ∧∨?∨ 解:原式()()p p r p q r ?∨?∨∧?∨∨()p q r ??∨∨4M ?,此即公式的主合取范式, 所以成假赋值为100。 7、求下列公式的主析取范式,再用主析取范式求主合取范式: (1)()p q r ∧∨ 解:原式()(()())p q r r p p q 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 p q r p q r p q r ??∧?∧∨?∧∧∨∧?∧∨∧∧?∨∧∧ 13567m m m m m ? ∨∨∨∨,此即主析取范式。 主析取范式中没出现的极小项为0m ,2m ,4m ,所以主合取范式中含有三个极大项0M ,2M ,4M ,故原式的主合取范式024M M M ?∧∧。 9、用真值表法求下面公式的主析取范式: (1)()()p q p r ∨∨?∧ 解:公式的真值表如下:

由真值表可以看出成真赋值的情况有7种,此7种成真赋值所对应的极小项的析取即为主析取范式,故主析取范式 1234567m m m m m m m ?∨∨∨∨∨∨ 习题三及答案:(P52-54) 11、填充下面推理证明中没有写出的推理规则。 前提:,,,p q q r r s p ?∨?∨→ 结论:s 证明: ① p 前提引入 ② p q ?∨ 前提引入 ③ q ①②析取三段论 ④ q r ?∨ 前提引入 ⑤ r ③④析取三段论 ⑥ r s → 前提引入 ⑦ s ⑤⑥假言推理

离散数学练习题

离散数学练习题 一、填空题 1. 命题Q →P 的真值为0,当且仅当 。 2. 构造公式S R S R →∨∧)(的真值表 。 3. 仅用∧和┐写出下列表达式的等价形式 a) R Q P ?→∨?? b) P Q ∨? 4. 仅用∨和┐写出下列表达式的等价形式 a) )()(D C B A ∨→∨? 。 b) )(E D A ?→→?? 5. 公式A 有三个命题变元P 、Q 、R 组成,其主析取范式为A 6531m m m m ∨∨∨?,则其主合取 范式为: 6. 公式A 有三个命题变元P 、Q 、R 组成,其主合取范式为A ?65310M M M M M ∧∧∧∧,则 其主析取范式为: 。 7. 设解释I 如下: D={n ,m} P(n ,n) P(n ,m) P(m ,n) P(m ,m) 1 1 0 0 8. 确定下列各式的真值: ),(m x xP ? ___ ___; ),(y n yP ? __ ___; ),(y x yP x ??) __ ___。 ),(n x xP ? ___ ___; ),(y m yP ? __ ___; ),(y x yP x ??) __ ___。 9. 谓词合式公式)()(x xQ x xP ?→?的前束范式为 。 10. 某集合有101个元素,则有 个子集的元素为奇数。 11. 某班有32个学生,其中14个人选择艺术,7个人选择生物,6个人选择音乐,三门课都选的有 2人,问这三门课都没选的至少有 人? 12. 设全集U={1,2,3,4,5,6,7,8,9,10}, A={1,2,3,5,6}, B={2,4,6,8,9}, 则:A ∩B= , B ⊕A= , B A ?= ; (A ∪B)-B = , (A ∪B)-(B ∩C)= 13. =Φ=)(},,a {A A ρ 。 14. B A b a B A ×==2},,{},1{= =×B A )(ρ

离散数学试题与答案

试卷二试题与参考答案 一、填空 1、 P :你努力,Q :你失败。 2、 “除非你努力,否则你将失败”符号化为 ; “虽然你努力了,但还是失败了”符号化为 。 2、论域D={1,2},指定谓词P 则公式x ??真值为 。 3设A={2,3,4,5,6}上的二元关系}|,{是质数x y x y x R ∨<><=,则 R= (列举法)。 R 的关系矩阵M R = 。 4、设A={1,2,3},则A 上既不是对称的又不是反对称的关系 R= ;A 上既是对称的又是反对称的关系R= 。 5、设代数系统,其中A={a ,b ,c}, 则幺元是 ;是否有幂等 性 ;是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。

8、n 个结点的无向完全图K n 的边数为 ,欧拉图的充要条件是 。 二、选择 1、在下述公式中是重言式为( ) A .)()(Q P Q P ∨→∧; B .))()(()(P Q Q P Q P →∧→??; C .Q Q P ∧→?)(; D .)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为( ),成真赋值的个数为( )。 A .0; B .1; C .2; D .3 。 3、设}}2,1{},1{,{Φ=S ,则 S 2 有( )个元素。 A .3; B .6; C .7; D .8 。 4、设} 3 ,2 ,1 {=S ,定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生 的S S ?上一个划分共有( )个分块。 A .4; B .5; C .6; D .9 。 5、设} 3 ,2 ,1 {=S ,S 上关系R 的关系图为 则R 具有( )性质。 A .自反性、对称性、传递性; B .反自反性、反对称性; C .反自反性、反对称性、传递性; D .自反性 。

等价关系与偏序关系复习题答案

第5章 等价关系与偏序关系 一、选择题(每题3分) 1、设Z 为整数集,下面哪个序偶不够成偏序集( A ) A 、)(,小于关系:<>< 关系:整除 D 、,()Z M M <>关系:整倍数 2、序偶(),A ρ<>?必为( B ) A 、非偏序集 B 、偏序集 C 、线序集 D 、良序集 3、设≤小于等于关系:Z 为整数集,下面哪个序偶能够成良序集( D ) A 、,()R R + <>≤:正实数集 B 、,()Q Q ++<≤>有理数集:正 C 、,()Z Z ++<≤> 整数集:正 D 、,()N N <≤>:自然数集 4、设{,{1},{1,3},{1,2,3}}A =?,则A 上包含关系“?”的哈斯图为( C ) 5、集合{ 1, 2, 3,4 }A =上的偏序关系图为 则它的哈斯图为( A ) 6、某人有三个儿子,组成集合123{ , , }A S S S =,则在A 上的兄弟关系一定不是( D ) A 、偏序关系 B 、线序关系 C 、良序关系 D 、等价关系 7、有一个人群集合12{ , , , }n A P P P = ,则在A 上的同事关系一定是( D ) A 、偏序关系 B 、线序关系 C 、良序关系 D 、等价关系 8、设A 为非空集合,则下列A 上的二元关系中为等价关系的是( D ) A 、空关系 B 、全域关系 C 、恒等关系 D 、上述关系都是 9、设{ 1, 2, 3 }A =,则A 上不同等价关系的个数为( C ) A 、3 B 、4 C 、5 D 、6 10、设{ 1, 2, 3, 4 }A =,则A 上不同等价关系的个数为( C ) A 、13 B 、14 C 、15 D 、16 注:除了等价关系可以对空集定义,而划分不能外,等价关系与划分是相同概念的不同描述. 11、设{ 1, 2 }S =,“?”为S 中元素的普通乘法,定义S S ?上的等价关系 {,,, | ,,,,}R a b c d a b S S c d S S a d b c =<<><>><>∈?<>∈??=?, 则由R 产生的S S ?上一个划分的分块数为( D ) A 、1 B 、2 C 、3 D 、4 提示:记12341,1,1,2,2,1,2,2a a a a =<>=<>=<>=<>, 则由R 的关系图易知1234{{},{},{},{}}S S a a a a ?=.

离散数学题库及答案

数理逻辑部分 选择、填空及判断 ?下列语句不是命题的( A )。 (A) 你打算考硕士研究生吗?(B) 太阳系以外的星球上有生物。 (C) 离散数学是计算机系的一门必修课。(D) 雪是黑色的。 ?命题公式P(P P)的类型是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A是重言式,那么A的否定式是( A ) A. 矛盾式 B. 重言式 C. 可满足式 D.不能确定 ?以下命题公式中,为永假式的是( C ) A. p→(p∨q∨r) B. (p→┐p)→┐p C. ┐(q→q)∧p D. ┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值是( D ) A. 00,11 B. 00,01,11 C.10,11 D. 10 ?谓词公式) x R xP∧ ?中,变元x是( B ) ) x ( , (y A. 自由变元 B. 既是自由变元也是约束变元 C. 约束变元 D. 既不是自由变元也不是约束变元 ?命题公式P(Q Q)的类型是( A )。 (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?设B不含变元x,) x→ ?等值于( A ) A (B ) ( x

A. B x xA →?)( B. ))((B x A x ∨? C. B x xA →?)( D. B x A x ∧?)(( ? 下列语句中是真命题的是( D )。 A .你是杰克吗? B .凡石头都可练成金。 C .如果2+2=4,那么雪是黑的。 D .如果1+2=4,那么雪是黑的。 ? 从集合分类的角度看,命题公式可分为( B ) A. 永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 ? 命题公式﹁p ∨﹁q 等价于( D )。 A. ﹁p ∨q B. ﹁(p ∨q) C. ﹁p ∧q D. p →﹁q ? 一个公式在等价意义下,下面写法唯一的是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ? 下列含有命题p ,q ,r 的公式中,是主析取范式的是 ( D )。 (A) (p q r) (p q) (B) (p q r) (p q) (C) (p q r) (p q r) (D) (p q r) (p q r) ? 设个体域是整数集合,P 代表x y ((x y )(x y x )),下面描述正确的是 ( C )。 (A) P 是真命题 (B) P 是假命题 (C) P 是一阶逻辑公式,但不是命题 (D) P 不是一阶逻辑公式 ? 对一阶逻辑公式((,)(,))(,)x y P x y Q y z xP x y ??∧∧?的说法正确的是( B ). (A) x 是约束的,y 是约束的,z 是自由的; (B) x 是约束的,y 既是约束的又是自由的,z 是自由的; (C) x 是约束的,y 既是约束的又是自由的,z 是约束的;

离散数学试题及答案

离散数学试题及答案 一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=_____{3}______________; ρ(A) - ρ(B)= ____{{3},{1,3},{2,3},{1,2,3}}__________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = ___2^(n^2)________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是____A1 = {(a,1), (b,1)}, A2 = {(a,2), (b,2)}, A3 = {(a,1), (b,2)}, A4 = {(a,2), (b,1)},_________ _____________, 其中双射的是______A3, A4__________. 4. 已知命题公式G=?(P→Q)∧R,则G的主析取式是____P∧?Q∧R (m5)____. 5.设G是完全二叉树,G有7个点,其中4个叶点,则G的总度数为___12______,分枝点数为_______3_________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B=______{4}______; A?B=____{1,2,3,4}_________;A-B=______{1,2}_______ . 7. 设R是集合A上的等价关系,则R所具有的关系的三个特性是______自反性____________, _________对称性_________, _________传递性_____________. 8. 设命题公式G=?(P→(Q∧R)),则使公式G为真的解释有_____(1,0,0)__________, ______(1,0,1)________, ________(1,1,0)________. 9. 设集合A={1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1?R2= ___{(1,3),(2,2),(3,1)}____,R2?R1 =_____{(2,4), (3,3), (4,2)}_____, R12=_______{(2,2), (3,3)}_________. 10. 设有限集A, B,|A| = m, |B| = n, 则| |ρ(A?B)| = ______2^(m*n)___________. 11设A,B,R是三个集合,其中R是实数集,A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = _____{x | -1 ≤x < 0, x ∈R}_______ , B-A = ______{x | 1 < x < 2, x ∈R}_____ , A∩B = ______{x | 0 ≤x ≤1, x ∈R}__________ , . 13.设集合A={2, 3, 4, 5, 6},R是A上的整除,则R以集合形式(列举法)记为___________ ________{(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)}_________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x),则G的前束式是_____?y?x(P(y)→Q(x))________ _____.

自考离散数学02324真题含答案(2009.4-2016.4年整理版)

全国2009年4月自学考试离散数学试题(附答案) 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列为两个命题变元P,Q的小项是() A.P∧Q∧? P B.? P∨Q C.? P∧Q D.? P∨P∨Q 2.下列语句中是真命题的是() A.我正在说谎B.严禁吸烟 C.如果1+2=3,那么雪是黑的D.如果1+2=5,那么雪是黑的 3.设P:我们划船,Q:我们跑步。命题“我们不能既划船又跑步”符号化为() A.? P∧? Q B.? P∨? Q C.?(P?Q)D.?(? P∨? Q) 4.命题公式(P∧(P→Q))→Q是() A.矛盾式B.蕴含式 C.重言式D.等价式 5.命题公式?(P∧Q)→R的成真指派是() A.000,001,110,B.001,011,101,110,111 C.全体指派D.无 6.在公式(x ?)F(x,y)→(?y)G(x,y)中变元x是() A.自由变元B.约束变元 C.既是自由变元,又是约束变元D.既不是自由变元,又不是约束变元 7.集合A={1,2,…,10}上的关系R={|x+y=10,x∈A,y∈A},则R的性质是() A.自反的B.对称的 C.传递的、对称的D.反自反的、传递的 8.若R和S是集合A上的两个关系,则下述结论正确的是() A.若R和S是自反的,则R∩S是自反的 B.若R和S是对称的,则R S是对称的 C.若R和S是反对称的,则R S是反对称的 D.若R和S是传递的,则R∪S是传递的 9.R={<1,4>,<2,3>,<3,1>,<4,3>},则下列不是 ..t(R)中元素的是() A.<1,1> B.<1,2> C.<1,3> D.<1,4>

离散数学例题

离散数学例题 一、证明对任意集合A,B,C,有 a)A-B)-C=A-(B∪C); b)(A-B)-C=(A-C)-B; c)(A-B)-C=(A-C)-(B-C)。 证明 a)(A-B)-C=(A∩~B)∩~C =A∩(~B∩~C) =A∩~(B∩C) =A-B∪C) b)(A-B)-C= A∩~B∩~C = A∩~C∩~B =(A-C)-B c)(A-C)-(B-C) =(A∩~C)∩~(B∩~C) =(A∩~C)∩(~B∪C) =(A∩~C∩~B)∪(A∩~C∩C) = A∩~B∩~C =(A-B)-C 二、设命题公式G = (P→Q)∨(Q∧(P→R)),求G的主析取范式 G = (P→Q)∨(Q∧(P→R)) = (P∨Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧(P∨R)) = (P∧Q)∨(Q∧P)∨(Q∧R) = (P∧Q∧R)∨(P∧Q∧∨(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) = m3∨m4∨m5∨m6∨m7 = (3, 4, 5, 6, 7). 三、假设f和g是函数,证明f∩g也是函数。 证明 f∩g={| x∈dom f∧x∈dom g∧y=f(x)∧y=g(x)} ={| x∈dom f∩dom g∧y=f(x)=g(x)}

令h=f∩g,则 dom h={ x | x∈dom f∩dom g,f(x)=g(x)} 若y1 =y2 ,因为f是函数,故必有y1 =/f(x1 ),y2 =/f(x2 ),且x1 ≠x2 ,所以h=f∩g 是一个函数。 因为dom h存在且y1 ≠y2 时x1 ≠x2 ,即h={| x∈ Dom h,y=h(x)=f(x)=g(x)} 四、设函数f:R→R,若x≤y=>f(x)≤f(y),则称函数f是单调递增的。设f和g是在R 上单调递增,证明 1)若(f十g)(x)=f(x)+g(x),则f+g是单调递增; 2)复合函数f○g是单调递增: 3)f和g的乘积不一定是单调递增。 证明 1)因为f和g是单调递增,若x≤y,则有f(x)≤f(y),g(x) ≤g (y), (f+g)(x)=f(x)十g(x) ≤f(y)+g(y)=(f十g)(y) 所以f+g是单调递增。 2)若x≤y,则f(x)≤f(y)且g(x) ≤ g(y), f○g(x)=f(g(x)) ≤f(g(y))=f○g(y) 所以f○g是单凋递增。 3)令f(x)=g(x)=x,则f和g是单调递增,但其积函数 g*g(x)=f(x)*g(x)=x2 在R上不是单凋递增。 五、设R和S是集合A={a, b, c, d}上的关系,其中R={(a, a),(a, c),(b, c),(c, d)}, S={(a, b),(b, c),(b, d),(d, d)}. 计算R?S, R∪S, R-1, S-1?R-1. R?S={(a, b),(c, d)}, R∪S={(a, a),(a, b),(a, c),(b, c),(b, d),(c, d),(d, d)}, R-1={(a, a),(c, a),(c, b),(d, c)}, S-1?R-1={(b, a),(d, c)}. 六、若f:A→B是双射,则f-1 :B→A是双射。 证明 因为f:A→B是双射,则f-1 是B到A的函数。下证f-1是双射。 对任意x∈A,必存在y∈B使f(x)=y,从而f-1 (y)=x,所以f-1 是满射。

《离散数学(第三版)》期末复习知识点总结含例题(呕心沥血整理).doc

T 是 系、空关系、全关系、恒等关 P (A )-p (B ) = {{3},{1,3}, {2,券,;{陶鮮餐的集合衣示、关 系矩阵和矣系图、关系的运 算。 2、 学握求复合关系与逆关系 的方法。 3. 理解关系的性质(自反性. 对称性、反对称性、传递性) ? 掌握其判别方法(定义、矩阵、 图)。 4、 掌握求关系的闭包(自反 闭包、对称闭包、传递闭包) 的 方法。 5、 理解等价关系和偏序关系 的概念,学握等价类的求法和 偏序关系做哈斯图的方法,极 人/小元、最人/小元、上/卜?界、 最小上界、最人下界的求法。 6、 理解函数概念:函数、函 数相等、复介畅数和反畅数。 7、 理解单射、满射、双射等 概念,学握其判别方法。 [木章重点习题] P25, 1; P32?33, 4, 8, 10; P43, 2, 3, 5; (Au~ B )c (~ 注J 8)P59, 1, 2; P64, 3 ; P74?75, 2, 4, 6, 7; P81, 5, 7: = ((An ?A 曲鑑咖血c 肛(~ 3 c B )) =(①遊:縱璇憾") =(An 圧皿細扇渤洋輕):元关系 世概念及关系矩阵、 图表 示。 2、关系的性质及其判定 关系的性质既是对关系 概念的加深理解与学握,乂是 关系的闭包、 等价关系、半序 关系的基础。对丁?四种性质的 判定,可以依据教材中P49上 总结的规律。这其中对传递性 的判定,难度稍大一点,这里 要提及两点:一是不破 坏传递 性定义,可认为具有传递性。 如空关系具冇传递性,同时空 关系具有对称性与反对称性,但是不具有自反性。另一点是 介绍-?种判定传递性的“跟踪 法” , 即 若 (a l9a 2)e R. \a 2,a 3)e R, ,则(R 。如若 (a,b )w R, R , 则有,且 (b,b )w R 。例题 一、各章复习要求与重点 第一章集合 [复习知识点] 1、 集合、元索、集合的表示 方法、子集、空集、全集、集 合的包含、相等、幕集 2、 集合的交、并、差、补等 运算及其运算律(交换律、结 合律、分配律、吸收律、De Morgan 律等),文氏(Venn ) 图 3、 序偶与辿卡尔积 本章重点内容:集合的概 念.集合的运算性质、集合恒 等式的证明 [复习要求] 1、 理解集合、元素、子集、 空集、全集、集合的包含、相 等、幕集等基本概念。 2、 学握集合的表示法和集合 的交、并、差、补等基本运算。 3、 掌握集合运算基本规律, 证明集合等式的方法。 4、 了解序偶与迪卡尔积的概 念,掌握辿卡尔积的运算。 [疑难解析] 1、 集合的概念 因为集合的概念学生在 中学阶段已经学过,这里只多 了一个幕集概念,重点对幕集 加以掌握,一是掌握幕集的构 成.一是掌握幕集元数为2"。 2、 集合恒等式的证明 通过对集合恒等式证明 的练习?既町以加深对集介性 质的理解与学握;又可以为第 三章命题逻辑中公式的基本 等价式的应用打下良好的基 础。实际上,本章做题是一种 基本功训练,尤其要求学生重 视吸收律利重耍等价式在 A — B = A c ~ B 证明中 的特殊作用。 [例题分析] 例1设A, B 是两个集合, A={1, 2, 3}, B={1, 2),则 p (A ) — p (B ) = 例 2 A = {a,b,{a 9b},}, 求: (1) A-{a,b} ⑵ A -① ⑶ A - {O}; ⑷{{tz,/?}} — A ⑸ ①一 A ⑹{①} - A 。 解 (1) A-{a,b} = {{a,b}^} ⑵ A -①=A ⑶ >4-{o} = (4) {{a,b}}-A =① ⑸ ①一 4二① (6) A 二① 例 3 试证明 第二章二元关系 [复习知识点] 1、 关系、关系矩阵与关系图 2、 复合关系与逆关系 3、 关系的性质(自反性.对 称性、 反对称性、传递性) 4、 关系的闭包(自反闭包、 对称闭包、传递闭包) 5、 等价关系与等价类 6、 偏序关系与哈斯图 (Hasse ) >极大/小元.最大/ 小元、上/下界、最小上界、最 大 下界 7、 函数及其性质(单射、满 《离散数学(第三版)》 期末复习知识点总结含 解 P (A ) = {0,{1},{2},{3},{1,2},{1|删{辆,曲3 料序关系、 映射 的概念 p (B )二{0,{1},{2},{1,2}}[复习要求] 1、理解关系的概念:二元关 证明 P86, 1, 2o 射、双射) 8、复合函数与反函数 木章重点内容:二元关系 的 概念、关系的性质、关系的 (Au ?B)c(?AuS)= ((Au^ff