下载文档原格式
离散数学笔记第一章命题逻辑合取析取定义 1. 否定：当某个命题为真时.其否定为假.当某个命题为假时.其否定为真定义 1. 条件联结词.表示“如果……那么……”形式的语句定义 1. 双条件联结词.表示“当且仅当”形式的语句定义合式公式(1)单个命题变元、命题常元为合式公式.称为原子公式。
(2)若某个字符串 A 是合式公式.则⌝A、(A)也是合式公式。
(3)若 A、B 是合式公式.则 A ∧B、A∨B、A→ B、A↔B 是合式公式。
(4)有限次使用(2)~(3)形成的字符串均为合式公式。
等值式析取范式与合取范式将一个普通公式转换为范式的基本步骤推理定义 设 A 与 C 是两个命题公式. 若 A → C 为永真式、 重言式.则称 C 是 A 的有 效结论.或称 A 可以逻辑推出 C.记为 A => C 。
（用等值演算或真值表）第二章 谓词逻辑、基本概念∀：全称量词 ∃：存在量词一般情况下. 如果个体变元的取值范围不做任何限制即为全总个体域时. 带 “全称量词”的谓词公式形如"∀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))、谓词公式及其解释定义 、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22y x 的 f(x,y))、 谓词常元(如表示人类的 H(x))。
定义 、逻辑符号：个体变元、量词(∀∃)、联结词(﹁∨∧→↔)、逗号、括号。
定义 、项的定义：个体常元、变元及其函数式的表达式称为项(item)。
离散数学-习题集《离散数学》习题集第⼀部分判断题⼀、第⼀章—集合1、（）已知集合A的元素个数为10，则集合A的幂集的基=102。
2、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。
2、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。
3、( ) 已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B={Ф}。
4、（）已知两个集合A={Ф，{Ф}}，B={Ф}，则A∩B=Ф。
5、（）已知两个集合A、B，若A中的元素都是B中的元素，则记为A∈B。
6、（）已知集合A的元素个数为n，则集合A的幂集P（A）的元素个数为n2。
7、（）已知集合A的元素个数为n，则A×A的幂集的元素个数为n2。
8、（）已知两个集合A、B，则A-B是由属于B但不属于A的元素构成的集合。
⼆、第⼆章—⼆元关系1、（）若R是A上的⼆元关系，I A是A上的恒等关系，则当且仅当I A∈R时，R是A上的⾃反关系。
2、（√）若R是集合A上的⼆元关系，且当（a，b）∈R且（a，c）∈R时，就有（b，c）∈R，则R是A 上的可传递关系。
3、（）设A是集合，A1、A2、．．．A n都是A的⾮空⼦集，令S={A1，A2，．．．,A n}，则如果S是集合A的⼀个划分，那么S⼀定是集合A的⼀个完全覆盖；反之亦然。
5、（）R是⾮空集合A上的等价⼆元关系，则A关于R的商集A/R是集合A的⼀个划分，但不是A的⼀个完全覆盖。
6、（）已知集合A有4元素，易知集合A共有24个互不相同的⼦集合，所以在集合A上⼀共可定义24个互不相同的⼆元关系。
7、（）若R1和R2都是集合A上的可传递⼆元关系，则R1∪R2也是A上的传递关系。
8、（）设R是有限的⾮空集合A上的偏序关系，则A必有极⼤（⼩）元和最⼤（⼩）元。
9、（）若R1和R2都是集合A上的相容关系，则R1∩R2也是A上的相容关系。
10、（）若R1和R2都是集合A的可传递⼆元关系，则R1∩R2也是A上的传递关系。
离散习题代数系统部分答案1(共3页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--《离散数学》代数系统1.以下集合和运算是否构成代数系统如果构成，说明该系统是否满足结合律、交换律求出该运算的幺元、零元和所有可逆元素的逆元.1)P(B)关于对称差运算⊕，其中P(B)为幂集.构成代数系统；满足结合律、交换律；幺元φ；无零元；逆元为自身。
2)A={a,b,c}，*运算如下表所示：构成代数系统；满足结合律、交换律；无幺元；无逆元；零元b.2.设集合A={a,b}，那么（1）在A上可以定义多少不同的二元运算（2）在A上可以定义多少不同的具有交换律的二元运算24个不同的二元运算；23个不同的具有交换律的二元运算3.设A={1,2},B是A上的等价关系的集合.1)列出B的元素.2元集合上只有2种划分，因此只有2个等价关系，即B={I A，E A}2)给出代数系统V=<B,∩>的运算表.3)求出V的幺元、零元和所有可逆元素的逆元.幺元E A、零元I A；只有E A可逆，其逆元为E A.4)说明V是否为半群、独异点和群V是为半群、独异点，不是群4.设A={a,b,c}，构造A上的二元运算*，使得a*b=c,c*b=b，且*运算满足幂等律、交换律.1)给出关于*运算的一个运算表.其中表中位置可以是a、b、c。
2)*运算是否满足结合律，为什么不满足结合律；a*（b*b）=c ≠（a*b）*b=b5.设<R，*>是一个代数系统。
*是R上的一个二元运算，使得对于R(实数集合)中的任意元素a,b都有a*b=a+b+a·b(·和+为数集上的乘法和加法).证明：:<R，*> 是独异点.6.如果<S,*>是半群，且*是可交换的.证明：如果S中有元素a,b,使得a*a=a和b*b=b，则(a*b)*(a*b)=a*b.(a*b)*(a*b)= a*(b*a)*b 结合律= a*( a*b)*b 交换律= (a* a)*(b*b)= a*b.7.设<G,·,–1,e>是一个群,则a,b,c∈S。
离散数学中代数系统知识点梳理离散数学作为一门数学学科，研究的是离散化的对象和结构。
代数系统作为离散数学的一个重要分支，是对数学对象的代数性质进行研究的一种形式化工具。
在离散数学中，代数系统的概念和相关知识点是非常重要的。
一、代数系统的基本概念代数系统是指由集合和一组运算构成的数学结构。
其中，集合是代数系统中最基本的概念，可以是有限集或无限集；运算是指对集合中的元素进行操作并得到新的元素。
代数系统主要包括代数结构、代数运算和代数性质三个方面。
1. 代数结构：代数结构由集合和一组运算构成，可以包括加法、减法、乘法、除法等。
常见的代数结构有群、环、域等。
2. 代数运算：代数运算是指对集合中的元素进行操作，可以是二元运算也可以是多元运算。
常见的代数运算有加法、乘法、幂运算等。
3. 代数性质：代数系统具有一些特定的性质，如封闭性、结合律、交换律、单位元素、逆元素等。
二、代数系统的分类根据代数运算的性质，代数系统可以分为群、环、域和向量空间等不同类型。
1. 群：群是一种代数系统，具有封闭性、结合律、单位元素和逆元素等性质。
群分为有限群和无限群，可以是交换群或非交换群。
2. 环：环是一种代数系统，具有封闭性、结合律、交换律和单位元素等性质。
环分为有限环和无限环，可以是可除环或非可除环。
3. 域：域是一种代数系统，具有封闭性、结合律、交换律、单位元素、逆元素和分配律等性质。
域是一种完备的代数系统，可以进行加、减、乘、除运算。
4. 向量空间：向量空间是一种代数系统，具有封闭性、结合律、交换律、单位元素、逆元素和分配律等性质。
向量空间是一种具有线性结构的代数系统。
三、代数系统的应用代数系统作为离散数学的一个重要分支，在计算机科学、密码学、通信工程等领域有着广泛的应用。
1. 计算机科学：代数系统在计算机科学中起到重要的作用，比如在数据库设计、编译原理、算法设计等方面都有应用。
代数系统可以描述和分析计算机系统的运行和性能。
离散数学复习提纲（代数系统）1．（1）相等关系显然是所有代数结构上的同余关系. 同余关系是相等关系的推广。
（2）同余关系也是模k相等关系（数论中也称模k同余关系）的推广。
可证模k相等关系是如上定义的关于整数加、乘运算的同余关系。
设整数x,y,u,v满足x＝y（mod k）, u＝v（mod k）,那么x –y = nk,u –v = mk(n,m 为整数),于是(x+u) – (y+v) = (n+m)k故x+u = y+v（mod k）。
为证 xu＝yv（mod k），将 x = y+nk与u = v+mk两边分别相乘,于是有xu – yv = ymk+vnk+nmk2xu – yv = (ym+vn+nmk)k由于ym+vn+nmk 为整数，xu＝yv（mod k）得证。
模k相等关系关于减运算和一元减运算（添负号运算）也是同余关系，请读者自行验证。
2．设<G，*>为群,G中元素a的阶为k,那么,a n = e当且仅当k整除n .证先证充分性．设 a k ＝ e，k整除n，那么n = kr（r为整数），因为a k ＝ e，所以a n = a kr = (a k )r = e r = e 。
再证必要性．设 a n ＝ e，n = mk＋ r，其中m为n除以 k的商，r为余数，因此0≤ r＜k 。
于是e＝a n＝a mk+r＝a mk*a r＝a r因此,由k的最小性得r = 0，k整除n ．3．有限群G的每个元素都有有限阶,且其阶数不超过群G的阶数| G | .证设a为G的任一元素,考虑 e = a0 ,a1 ,a2 , … ,a│G│这| G |+1个G中元素.由于G中只有| G |个元素,因此它们中至少有两个是同一元素,不妨设a r = a s(0 ≤ r < s ≤ | G | )于是a s-r = e,因此a有有限阶,且其阶数至多是s-r,不超过群G的阶数| G | .4．设<G，*>为群，a为G中任一元素，那么a与a-1具有相同的阶．证只要证 a具有阶n当且仅当a-1具有阶n 。
