《离散数学》教案 第一章集合与关系 集合是数学中最基本的概念,又是数学各分支、自然科学及社会科学各领域的最普 遍采用的描述工具。集合论是离散数学的重要组成部分,是现代数学中占有独特地位的 一个分支。 G. Cantor( 康脱 ) 是作为数学分支的集合论的奠基人。1870 年前后,他关于无穷序列的研究导致集合论的系统发展。 1874 年他发表了关于实数集合不能与自然数集合建立 一一对应的有名的证明。 1878 年,他引进了两个集合具有相等的“势”的概念。然 而,朴素集合论中包含着悖论。第一个悖论是布拉利 - 福尔蒂的最大序数悖论。 1901 年罗素发现了有名的罗素悖论。 1932 年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908 年策梅罗所发表的一组公理,经过弗兰克尔的加工,这个系统称 为策梅罗 - 弗兰克尔集合论( ZF),其中包括 1904 年策梅罗引入的选择公理。另外一种系 统是冯·诺伊曼 - 伯奈斯 - 哥德尔集合论。公理集合论中一个有名的猜想是连续统假设(CH)。哥德尔证明了连续统假设与策梅罗 - 弗兰克尔集合论的相容性,科恩证明了连续统假设与策梅罗 - 弗兰克尔集合论的独立性。现在把策梅罗 - 弗兰克尔集合论与选择公理一起称为 ZFC系统。 一、学习目的与要求 本章目的是介绍集合的基本概念,讲授集合运算的基本理论,关系的定义与运算。 通过本章的学习,使学生了解集合是数学的基本语言,掌握主要的集合运算方法和关系运 算方法,为学习后续章节打下良好基础。 二、知识点 1.集合的基本概念与表示方法; 2.集合的运算; 3.序偶与笛卡尔积; 4.关系及其表示、关系矩阵、关系图; 5.关系的性质,符合关系、逆关系; 6.关系的闭包运算; 7.集合的划分与覆盖、等价关系与等价类;相容关系; 8.序关系、偏序集、哈斯图。
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体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) 证任取
2006-2007学年第2学期 2005级《离散数学2》期末考试试题(A卷) 考试时间:2007年6月班级_______________________ 学号_____________________ 姓名_____________________ 请将答案写在答题纸上,写明题号,不必抄题,字迹工整、清晰; 请在答题纸和试题纸上都写上你的班级,学号和姓名,交卷时请将试题纸、答题纸和草纸一并交上来。 一.综合体(30分,每题3分) 1. 求( 1 3 5 ) (2 5 4 ) (3 4 ) 2. 只有两个生成元的循环群一定是有限循环群吗?并说明理由。 3. 有限循环群中是否一定存在周期与群的元数相等的元素? 4. 下面哪个是域GF( 16)的真子域 (A)GF (6) ;(B)GF ⑷;(C)GF(8);(D)GF(16) 5. 有限布尔代数的元素个数必定是如下哪个形式? (A)2n;(B)n 2 ;(C)2 n;(D)4n. 6. 下列代数系统(S, *)中,哪个是群? (A) S={0,1,3,5},* 是模7的乘法;(B) S是有理数集合,*运算是普通乘法; (C) S是整数集合,*是普通乘法;(D) S={1,3,4,9},* 是模11的乘法。 7. 设A={0,1,2,3,4},运算为模5加法,请给出A的所有子群。 8. n元恒等置换是奇置换还是偶置换?对换呢? 9?请给出一个有余,但不是分配格的例子。 10.设R是模12的整数环,R={0,1,2,…,11},下面哪一个是极大理想: (A) 6R; (B)2R; (C)4R; (D)8R 二.计算题(25分,每题5分) 1. 计算分圆多项式①24(X). 2. 设(Z,+)为整数加法群,(C*,??)为非零复数的乘法群,令 f: n -i n ,是Z到C*中的同态映射,请求出f的同态核。 3. 在R上求出x+2除2X5+4X3+3X2+1所得的商式和余式。 4. 设G是3次对称群,H是由I和(13)作成的子群,求H得所有右陪集。 5. 设A={0,1,2,3,4,5}, 运算为模6加法,请给出A中所有元素的周期。 三.(10分)证明或者反驳:f(x)=3x 5+5X2+1 四.(10分)设(G, *)是群,(A, *)和(B,*)是它的两个子群,C={a*b|a € A, b€ B}.证明:若*满足交换律,则(C, *)也是(G,*)的子群。 五.(10分)设Z是整数集合,X={(a,b)|a,b € Z},定义X上的二元运算①和。 如下:对任意(ab) ,(a 2,b2)€ X,有: (a1b"e (a2,b2)= (a+a?,b1+b2), (a1bJ O (a2,b2)= (ax a2,b 1X b),其中,+,x分别是整数加法与乘法。 证明:(X,?,O)是环,如果此环有零因子请给出它们
本科高等数学离散数学试题及答案 一、填空题 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变成完全图。
学习目标: 1.深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、(最大)相容类、偏序关系、极大元、极小元、上(下)界、上(下)确界、最大(小)元、全序关系、良序关系等概念; 2.掌握集合的交、并、差、补、对称差的运算及其运算规律; 3.掌握关系的交、并、逆、复合运算、闭包运算及其性质; 4.掌握关系的矩阵表示与关系图; 5.深刻理解关系的自反性、反自反性、对称性、反对称性与传递性,掌握其判别方法; 6.掌握集合的覆盖与划分的联系与区别; 7.掌握偏序关系的判别及其哈斯图的画法;会求偏序集中给定集合的极大元、极小元、上(下)界、上(下)确界、最大(小)元。 主要内容: 1.集合的基本概念及其运算 2.序偶与笛卡尔积 3.关系及其表示 4.关系的性质及其判定方法 5.复合关系与逆关系 6.关系的闭包运算 7.等价关系与相容关系 8.偏序关系 重点: 1.关系的性质及其判别; 2.关系的复合运算及其性质; 3.等价关系与等价类、等价关系与集合的划分的联系; 4.偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点: 1.关系的传递性及其判别; 2.等价关系的特性; 3.偏序关系的哈斯图的画法;偏序集中特异位置元素的求法。 教学手段: 通过多个实例的精讲帮助同学理解重点与难点的内容,并通过大量的练习使同学们巩固与掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题: 习题3、1:4,6;习题3、2:3(8),4(12),6(m);习题3、4:1 (2)、(4),3;习题3、5:1,4;习题3、6:2,5,6;习题3、7:2,5,6;习题3、8:1(1)-(6);习题3、9:3(2)、(4),4(3);习题3、10:1 ,4,5。
《离散数学》+答案 一、选择或填空: 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
一、填空题 1设集合A,B,其中A={1,2,3}, B= {1,2}, 则A - B=__{3}__________________; ρ(A) - ρ(B)=___________________{3},{1,3},{2,3},{123}______ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = _____2^(n^2)_____________________. 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)}, R2= {(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变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除,写成与之对应的命题公
学习目标: 1.深刻理解序偶、笛卡尔积、关系、集合的划分与覆盖、等价关系、等价类、商集、相容关系、(最大)相容类、偏序关系、极大元、极小元、上(下)界、上(下)确界、最大(小)元、全序关系、良序关系等概念; 2.掌握集合的交、并、差、补、对称差的运算及其运算规律; 3.掌握关系的交、并、逆、复合运算、闭包运算及其性质; 4.掌握关系的矩阵表示和关系图; 5.深刻理解关系的自反性、反自反性、对称性、反对称性和传递性,掌握其判别方法; 6.掌握集合的覆盖与划分的联系与区别; 7.掌握偏序关系的判别及其哈斯图的画法;会求偏序集中给定集合的极大元、极小元、上(下)界、上(下)确界、最大(小)元。 主要内容: 1.集合的基本概念及其运算 2.序偶与笛卡尔积 3.关系及其表示 4.关系的性质及其判定方法 5.复合关系和逆关系 6.关系的闭包运算 7.等价关系与相容关系 8.偏序关系 重点: 1.关系的性质及其判别; 2.关系的复合运算及其性质; 3.等价关系与等价类、等价关系与集合的划分的联系; 4.偏序关系判别及其哈斯图的画法、偏序集中特异位置元素的理解。 难点: 1.关系的传递性及其判别; 2.等价关系的特性; 3.偏序关系的哈斯图的画法;偏序集中特异位置元素的求法。 教学手段: 通过多个实例的精讲帮助同学理解重点和难点的内容,并通过大量的练习使同学们巩固和掌握关系的性质及其判别、关系的复合运算及其性质、等价关系的特性、偏序关系的哈斯图的画法及偏序集中特异位置元素的求法。 习题:
习题 3.1:4,6;习题 3.2:3(8),4(12),6(m );习题 3.4:1 (2)、 (4),3;习题 3.5:1,4;习题 3.6:2,5,6;习题 3.7:2,5,6;习题 3.8:1(1)-(6);习题3.9:3(2)、(4),4(3);习题3.10:1 ,4,5。 3.1 集合的基本概念 集合(set)(或称为集)是数学中的一个最基本的概念。所谓集合,就是指具有共同性质的或适合一定条件的事物的全体,组成集合的这些“事物”称为集合的元素。 集合常用大写字母表示,集合的元素常用小写字母表示。若A 是集合,a 是A 的元素,则称a 属于A ,记作a A ∈;若a 不是A 的元素,则称a 不属于A ,记作。若组成集合的元素个数是有限的,则称该集合为有限集(Finite Set),否则称为无限集(Infinite Set)。 常见集合专用字符的约定: N —自然数集合(非负整数 集) I (或Z )—整数集合(I +,I -) Q —有理数集合(Q +,Q -) R —实数集合(R +,R -) F —分数集合(F +,F -) 脚标+和-是对正、负的区分 C —复数集合 P —素数集合 O —奇数集合 E —偶数集合 幂集 定义 3.1.1 对于每一个集合A ,由A 的所有子集组成的集合,称为集合A 的幂集(Power Set),记为 ()P A 或2A .即(){}P A B B A =?。 例如:{,,}A a b c =, (){,{},{},{},{,},{,},{,},{,,}}P A a b c a b b c a c a b c φ=。 定理3.1.1 如果有限集A 有n 个元素,则其幂集()P A 有2n 个元素。 证明 A 的所有由k 个元素组成的子集数为从n 个元素中取k 个的组合数。 (1)(2)(1)! k n n n n n k C k ---+= L 另外,因A φ?,故()P A 的元素个数N 可表示为 1 201n k n k n n n n n k N C C C C C ==++++++=∑L L 又因 0()n n k k n k n k x y C x y -=+= ∑ 令 1x y == 得 02n n k n k C ==∑ 故()P A 的元素个数是2n 。 人们常常给有限集A 的子集编码,用以表示A 的幂集的各个元素。具体方法是: 设12{,,,}n A a a a =L ,则A 子集B 按照含i a 记1、不含i a 记0(1,2,,)i n =L 的规定
第一章 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规则 第五章
离散数学作业4 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次,容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习,基本上是按照考试的题型(除单项选择题外)安排练习题目,目的是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握.本次形考书面作业是第二次作业,大家要认真及时地完成图论部分的综合练习作业. 要求:学生提交作业有以下三种方式可供选择: 1. 可将此次作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,完成作业后交给辅导教师批阅. 2. 在线提交word文档 3. 自备答题纸,将答题过程手工书写,并拍照上传. 一、填空题 1.已知图G中有1个1度结点,2个2度结点,3个3度结点,4个4度结点,则G的边数是15 . 2.设给定图G(如右由图所示),则图G的点割集是 { f },{ e,c} . 3.设G是一个图,结点集合为V,边集合为E,则 G的结点度数之和等于边数的两倍. 4.无向图G存在欧拉回路,当且仅当G连通且不含奇数度结 点. 5.设G=
8.结点数v与边数e满足e=v - 1 关系的无向连通图就是树. 9.设图G是有6个结点的连通图,结点的总度数为18,则可从G中删去条边后使之变成树. 10.设正则5叉树的树叶数为17,则分支数为i = 4 . 二、判断说明题(判断下列各题,并说明理由.) 1.如果图G是无向图,且其结点度数均为偶数,则图G存在一条欧拉回路. 答:错误。应叙述为:“如果图G是无向连通图,且其结点度数均为偶数,则图G存在一条欧拉回路。” 2.如下图所示的图G存在一条欧拉回路. 答:错误。因为图中存在奇数度结点,所以不存在欧拉回路。 3.如下图所示的图G不是欧拉图而是汉密尔顿图.
离散数学课后答案 习题一 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
全国2010年7月自学考试离散数学试题 课程代码:02324 一、单项选择题(本大题共15小题,每小题1分,共15分) 在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.下列句子不是..命题的是( D ) A .中华人民共和国的首都是北京 B .张三是学生 C .雪是黑色的 D .太好了! 2.下列式子不是..谓词合式公式的是( B ) A .(?x )P (x )→R (y ) B .(?x ) ┐P (x )?(?x )(P (x )→Q (x )) C .(?x )(?y )(P (x )∧Q (y ))→(?x )R (x ) D .(?x )(P (x ,y )→Q (x ,z ))∨(?z )R (x ,z ) 3.下列式子为重言式的是( ) A .(┐P ∧R )→Q B .P ∨Q ∧R →┐R C .P ∨(P ∧Q ) D .(┐P ∨Q )?(P →Q ) 4.在指定的解释下,下列公式为真的是( ) A .(?x )(P (x )∨Q (x )),P (x ):x =1,Q (x ):x =2,论域:{1,2} B .(?x )(P (x )∧Q (x )),P (x ):x =1,Q (x ):x =2,论域: {1,2} C .(?x )(P (x ) →Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} D .(?x )(P (x )→Q (x )),P (x ):x >2,Q (x ):x =0,论域:{3,4} 5.对于公式(?x ) (?y )(P (x )∧Q (y ))→(?x )R (x ,y ),下列说法正确的是( ) A .y 是自由变元 B .y 是约束变元 C .(?x )的辖域是R(x , y ) D .(?x )的辖域是(?y )(P (x )∧Q (y ))→(?x )R (x ,y ) 6.设论域为{1,2},与公式(?x )A (x )等价的是( ) A .A (1)∨A (2) B .A (1)→A (2) C .A (1)∧A (2) D .A (2)→A (1) 7.设Z +是正整数集,R 是实数集,f :Z +→R , f (n )=log 2n ,则f ( ) A .仅是入射 B .仅是满射 C .是双射 D .不是函数 8.下列关系矩阵所对应的关系具有反对称性的是( ) A .???? ? ?????001110101 B .???? ? ?????101110001
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={