当前位置：文档之家 › 第六章 代数系统

第六章 代数系统

  • 格式：doc
  • 大小：579.50 KB
  • 文档页数：42

【计算分析题】

页脚内容1

第六章 代数系统

1. 填空题：f是X上的n元运算的定义是（ ）。

2. 判断正误，并说明原因：自然数集合N上的减法运算“－” 是个封闭的运算。

3. 判断正误，并说明原因：实数集合R上的除法运算“” 是个封闭的运算。

4.填空题：代数系统的定义是：（ ）。

5. 填空题：*是X上的二元运算，*具有交换性，则它的运算表的特征是（ ）。

6.填空题：*是X上的二元运算，*具有幂等性，则它的运算表的特征是（ ）。

7. 简答题：*是X上的二元运算，*具有幺元，如何在它的运算表上判定哪个元素是幺元？

8. 简答题：*是X上的二元运算，*具有零元，如何在它的运算表上判定哪个元素是零元？

9. 简答题：*是X上的二元运算，*具有幺元，如何判定哪个元素是元素x的逆元？

10 令N4={0,1,2,3}，N4上定义运算+4：

任何x,y∈N4 , x+4 y=(x+y)(mod 4) 。 例如2+43=(2+3)(mod 4) =5(mod 4)＝1 请列出的运算表。然后判断+4 运算是否有交换性、有幺元、有零元、各个元素是否有逆元？如果有上述这些元素，请指出这些元素都是什么。

11. 判断正误，并说明原因：对于整集合I上的减法运算“－”来说， 0是幺元。

12. 填空题：E是全集，E={a,b}，E的幂集P(E)上的交运算的幺元是（ ）。零元是（ ）。有逆元的元素是（ ），它们的逆元分别是（ ）。

13. 填空题：E是全集，E={a,b}，E的幂集P(E)上的并运算的幺元是（ ）。零元是（ ）。有逆元的元素是（ ），它们的逆元分别是（ ）。

14. 填空题：E是全集，E={a,b}，E的幂集P(E)上的对称差运算的幺元是（ ）。零元是（ ）。有逆元的元素是（ ）。它们的逆元分别是（ ）。 【计算分析题】

页脚内容2

15. 填空题：对于自然数集合N上的加法运算“＋”，13＝（ ）。

16. 填空题：你所知道的满足吸收律的运算有（ ）。

17. 填空题：你所知道的具有零元的运算有（ ），其零元是（ ）。

18. 设是X上的二元运算，如果有左幺元 eL∈X，也有右幺元 eR∈X，则 eL= eR

=e ，且幺元 e 是唯一的。

19. 设是X上的二元运算，如果有左零元θL∈X，也有右零元θR∈X，则θL=θR =θ,且零元θ是唯一的。

20. 设是X上有幺元e且可结合的二元运算，如果 x∈X，x的左、右逆元都存在，则x的左、右逆元必相等。且x的逆元是唯一的。

21. 设是X上且可结合的二元运算，如a∈X，且a-1∈X，则a是可消去的，即

任取x,y∈X，设有ax=ay 则x=y。

22. 对于实数集合R，给出运算如下：＋是加法、—是减法、是乘法、max是两个数中取最大的、min是两个数中取最小的、|x-y|是x与y差的绝对值。判断这些运算是否满足表中所列的性质。如果满足就写“Y”,否则写“N”。

＋ － max min |x-y|

可结合性

可交换性

存在幺元

存在零元

23. 设R是实数集合，在R上定义二元运算* 如下：任取x,y∈R，

x*y=xy－2x－2y＋6

1．验证运算* 是否满足交换律和结合律。

2．求运算*是否有幺元和零元，如果有请求出幺元和零元。

3．对任何实数x，是否有逆元？如果有，求它的逆元，如果没有，说明原因。

【计算分析题】

页脚内容3

24.设是X上有幺元e且可结合的二元运算，求证如果x∈X，都存在左逆元，则x的左逆元也是它的右逆元。

25. .给定下面4个运算表如下所示。分别判断这些运算的性质，并用“Y”表示“有”，用“N”表示“无”填下面表。如果运算有幂等元、有幺元、有零元、有可逆元素，要指出这些元素是什么。

交换性 幂等元 幂等性 有幺元 有零元 有可逆元素

a)

b)

c)

d)

26. 分别说明什么叫做两个代数系统同态、满同态、单一同态、同构、自同构？

27. 什么叫做同态核？

28.请举同构的两个代数系统的例子，并说明它们同构的理由。

29. 给出集合A＝{0,1,2,3}和A上的二元运算“*”。集合B＝{S,R,A,L}和B上的二元运算“o”。 它们的运算表如下面所示。验证与同构。 a b c

a

b

c

a b c

b c a

c a b

a)

a b c

a

b

c

a b c

b a c

c c c

b)

a b c

a

b

c

a b c

a b c

a b c

c)

a b c

a

b

c

a b c

b b c

c c b

d)

【计算分析题】

页脚内容4

30令S={|X是集合，*是X上的二元运算}，即S是所有含有一个二元运算的代数系统构成的集合。是S中的代数系统间的同构关系。求证，是S中的等价关系。

31. 令A={0,1,2,3,4,…},B={1,2,4,8,16,…}，+表示加法，*表示乘法， 问和是否同构？为什么？

32 已知代数系统和，其中S={a,b,c} P={1,2,3} 二元运算表如下所示：

试证明它们同构。

a b c

a

b

c

a b c

b b c

c b c · 1 2 3

1

2

3

1 2 1

1 2 2 1 2 3

*

0 1 2 3

0 0 1 2 3

1 1 2 3 0

2 2 3 0 1

3 3 0 1 2

* S R A L

S S R A L

R R A L S

A A L S R

L L S R A

o 【计算分析题】

页脚内容5 33给定两个代数系统，：R+是正实数，×是R+上的乘法运算；： R是实数集合，＋是R上的加法运算。它们是否同构？对你的回答给予证明或者举反例说明之。

34. 已知代数系统与同构，即 X Y。并设f：XY是同构映射,

请证明如果运算可结合，则运算也可结合。

35. 已知代数系统与同构，即 X Y。并设f：XY是同构映射, 请证明如果运算可交换，则运算也可交换。

36. 已知代数系统与同构，即 X Y。并设f：XY是同构映射,

请证明如果运算有幺元e ，则运算也有幺元e ，且f(e )= e 。

37. 已知代数系统与同构，即 X Y。并设f：XY是同构映射,

请证明如果运算有零元θ ，则运算也有零元θ ，且f(θ)=θ 。

38 已知代数系统与同构，即 X Y。并设f：XY是同构映射, 请证明如果中每个x∈X可逆，即x-1∈X, 则中每个y∈Y也可逆，即y-1∈Y。 且如果y=f(x) ，则 y-1= (f(x))-1 =f(x-1)。(x映像的逆元=x逆元的映像)

39集合A上两个同余关系R、S, 证明R∩S也是同余关系.

40. 考察代数系统,定义I上如下关系R是同余关系？

a).∈R当且仅当(x<0∧y<0)∨(x≥0∧y≥0)

b). ∈R当且仅当|x-y|<10

c). ∈R当且仅当(x=y=0)∨(x0∧y0)

d). ∈R当且仅当x≥y

合集下载

离散数学第二版屈婉玲

离散数学第二版屈婉玲

离散数学第二版屈婉玲

简介

《离散数学第二版》是由屈婉玲编写的离散数学教材。离散数学是计算机科学中的一门基础课程，主要研究离散对象及其结构、性质和相互关系。这本教材系统地介绍了离散数学的各个方面，具有循序渐进、清晰易懂的特点，适合计算机科学及相关专业本科生使用。

目录

• 离散数学概论

– 离散数学的基本概念

– 命题逻辑

– 谓词逻辑与推理

– 集合与命题逻辑的应用

• 图论基础

– 图的基本概念

– 有向图与无向图

– 图的遍历

– 最短路径

• 关系与函数

– 二元关系

– 关系的闭包与等价关系

– 函数与映射关系

– 函数的复合与反函数

• 计数原理

– 基本计数原理

– 排列与组合

– 生成函数

– 容斥原理

• 离散数学中的数论

– 整数与整除性

– 模运算与同余关系

– 素数与因子分解

– 公约数与最大公约数

• 离散结构中的代数系统

– 代数系统的基本概念 – 半群与幺半群

– 群与子群

– 环与域

内容概述

离散数学概论

第一章介绍了离散数学的基本概念和离散对象的性质。包括集合论、命题逻辑和谓词逻辑等内容。后续讲解了命题逻辑的推理规则，以及如何应用集合论和命题逻辑解决实际问题。

图论基础

第二章介绍了图论的基本概念和图的表示方法。包括有向图和无向图的概念、图的遍历算法和最短路径算法。通过实例讲解了如何使用图论解决实际问题。

关系与函数

第三章介绍了关系与函数的概念和性质。包括二元关系的定义和性质、关系的闭包和等价关系的概念，以及函数与映射关系的概念和性质。通过实例讲解了如何使用关系和函数解决实际问题。

计数原理

第四章介绍了计数原理的基本概念和计数方法。包括基本计数原理、排列与组合、生成函数和容斥原理等内容。通过实例讲解了如何使用计数原理解决实际问题。

离散数学中的数论

第五章介绍了离散数学中的数论知识。包括整数与整除性、模运算与同余关系、素数与因子分解、公约数与最大公约数等内容。通过实例讲解了如何使用数论知识解决实际问题。

2017年中国科学技术大学0812计算机科学与技术考研专业目录及考试科目

2017年中国科学技术大学0812计算机科学与技术考研专业目录及考试科目

新祥旭 2017年中国科学技术大学0812计算机科学与技术考研专业目录及考试科目

一、报考说明：接收推免生及统考生。

二、专业介绍：

本学科培养学生德、智、体全面发展，适合于在高等学校、科研机构、企事业单位从事计算机系统结构相关领域的教学、科研和应用开发等工作的高层次专门人才。掌握计算机学科方面坚实的基础理论和系统的专门知识，了解本学科的发展方向及前沿动向，具备较强的综合运用所学理论知识从事科学研究工作和独立承担专门技术工作的能力，有严谨求实的科学作风和良好的科研道德，开拓进取的创新精神，团队合作和敬业精神。熟练掌握一门外国语，能阅读本专业的外文资料并撰写专业领域外文文章。具有较强的综合能力、语言表达能力及写作能力；具有健康的体魄和良好的心理素质。

本学科点具有计算机系统结构、计算机软件与理论、计算机应用技术以及信息安全4个二级学科。相应的研究方向如下：

1、计算机系统结构

计算机系统结构是计算机科学技术最活跃的研究领域之一，特别是最近几年，随着高性能计算机的广泛研究和应用、计算机整体设计关键技术的突破、计算机网络体系结构的迅速发展，计算机系统结构的研究出现了新的热点和重大进展。

在微处理芯片体系结构方面主要研究新型微处理芯片体系结构及其编程技术，可重构的片上并行体系结构，通用微处理芯片设计技术，指令级并行关键技术和嵌入式系统整体设计方法，多处理器体系结构等；在计算机体系结构方面主要研究新型高效能并行计算机体系结构、模型及其关键技术，包括软件技术、超

新祥旭 高扩展高密度计算技术、高可用集群中间件技术、可重构计算等，“并行结构-并行算法-并行编程”研究一体化；在网络及分布式计算方面主要研究新型网络体系结构和协议，网格计算平台及应用，对等网络、无线网络和移动计算等。

2、计算机软件与理论

离散数学定义

离散数学定义

第一章 命题逻辑

原子命题：不包含任何联结词的命题叫做原子命题。

复合命题：至少包含一个联结词的命题称作复合命题。

重言式：给定一个命题公式，若无论对分量作怎样的指派，其对应的真值用为T。

蕴含：当且仅当P→Q是一个重言式时，我们称“P蕴含Q”，并记作P⇒Q

对偶：在给定的命题公式中，将联结词⋁换成⋀，将⋀换成⋁，若有特殊边缘F和T亦相互取代，所得公式A*称为A的对偶式。

主析取范式：对于给定的命题公式，如果有一个等价公式，它仅小项的析取所组成，则该等价式称作原式的主析取范式。

主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。 第二章 谓词逻辑

不可满足的：一个谓词公式wff A，如果在所有赋值下都为假，则称该wff A为不可满足的。

可满足的：一个谓词公式wff A，如果至少在一种赋值下为真，则称该wff A为可满足的。

前束范式：一个公式，如果两次均在全式的开头，它们的作用域，延伸到整个公式末尾，则该公式叫做前束范式。

第三章 集合与关系

包含：设A，B是任意两个集合，假如A的每一个元素是B的成员，则称A为B的子集，或A包含在B内，或B包含A。记作A⊆B，或B⊇A。

真子集：如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集，记作A⊂B。

幂集：给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集。

集合的交：设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作A⋂B。

集合的并：设任意两个集合A和B，所有属于A或属于B的元素组成的集合S，称为A和B的集合，记作A⋃B。

集合的绝对补：设E为全集，对任一集合A关于E的补E-A，称为集合A的绝对补，记作~A。

对称差：设A，B为任意两个集合，A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A又属于B，记作A⊕B。

离散数学重点难点

离散数学重点难点

第一篇 数理逻辑

用数学方法来研究推理的规律称为数理逻辑。这里所指的数学方法，就是引进一套严格定义的符号体系的方法，即建立一套形式语言，来研究形式逻辑。所以数理逻辑又称作符号逻辑，它是从量的侧面来研究思维规律的。

现代数理逻辑可分为逻辑演算，证明论，模型论，递归函数论，公理化集合论。这里介绍的是数理逻辑基本的内容：逻辑演算中的命题逻辑和谓词逻辑。数理逻辑与数学的其它分支、计算机科学、人工智能、语言学等学科均有密切联系。

第一章命题逻辑 (11学时)

本章是以“命题”为中心，主要讨论：命题的表示、命题的演算；命题演算中的公式，及其应用；命题逻辑推理的方法。

本章要求

1.逻辑联结词，要熟练掌握联结词的真值表定义以及它们在自然语言中的含义。其中特别要注意“∨”和“→”的用法。

2.会命题符号化。

3.掌握永真式的证明方法：

(1).真值表。

(2).等价变换，化简成Ｔ。

(3).主析取范式。

4.掌握永真蕴含式的证明方法，熟练记忆并会应用

43页中表1-8.3中的永真蕴含式。

5.掌握等价公式的证明方法，熟练记忆并会应用

43页表1-8.4中的等价公式。

6.熟练掌握范式的写法及其应用。

7.熟练掌握三种推理方法。

本章主要内容

本章主要有以下章节：

第一节．命题及其表示法

第二节．联结词

第三节．命题公式及命题符号化

第四节．重言式与重言蕴含式

第五节．等价公式

第六节．范式

第七节．命题逻辑推理

本章重点、难点 联结词在自然语言中的含义，命题符号化

永真式、永真蕴含式、等价公式的证明方法，相关公式的熟练应用

范式的写法及其应用

命题逻辑的三种推理方法

第二章谓词逻辑 (9学时)

在第一章命题逻辑中，把命题作为演算的基本单位，一个原子命题只用一个字母表示，而不再对命题中的句子成分及其内部结构进行分析。这样就无法研究命题的更深层次的结构与意义，鉴于上述局限性，使得我们对于一些常见而又简单的命题无法进行解释与推理。所以就要考虑解决这个问题的方法：在表示命题时，既表示出主语（主词），也表示出谓语（谓词），就可以解决上述问题。这就提出了谓词的概念。