吉大网院 离散数学 大作业及答案 201903

《离散数学》试题及答案一、选择题（每题5分，共25分）1. 设集合A={1,2,3,4,5}，B={2,4,6,8,10}，则A∩B的结果是（）A. {1,2,3,4,5}B. {2,4}C. {1,3,5}D. {1,2,3,4,5,6,8,10}答案：B2. 下列关系中，哪个是等价关系？（）A. ≤B. ≠C. |D. ≠答案：A3. 设图G有5个顶点，每两个顶点之间都有一条边相连，则图G的边数是（）A. 5B. 10C. 15D. 20答案：C4. 下列哪一个图是欧拉图？（）A. 无向图B. 有向图C. 树D. 环答案：D5. 下列哪一个命题是正确的？（）A. 若p→q为真，则p为真B. 若p∧q为假，则p为假C. 若p∨q为真，则q为真D. 若p→q为假，则p为假答案：B二、填空题（每题5分，共25分）1. 设集合A={a,b,c,d}，B={c,d,e}，则A-B=________。

答案：{a,b}2. 设p是命题“今天是晴天”，q是命题“我去公园玩”，则命题“如果今天不是晴天，那么我不去公园玩”可以表示为________。

答案：¬p→¬q3. 设图G有n个顶点，e条边，则图G的度数之和为________。

答案：2e4. 一个连通图至少有________个顶点。

答案：25. 设图G的邻接矩阵为A，则A的转置矩阵表示________。

答案：图G的转置图三、判断题（每题5分，共25分）1. 离散数学是研究离散结构的数学分支。

（）答案：正确2. 两个集合的笛卡尔积是这两个集合的直积。

（）答案：正确3. 有向图中，顶点u和顶点v之间的长度为2的路径是指路径上有3条边。

（）答案：错误4. 树是一种无向图。

（）答案：正确5. 哈夫曼编码是一种贪心算法。

（）答案：正确四、应用题（每题25分，共50分）1. 设集合A={1,2,3,4,5}，B={2,4,6,8,10}，C={3,6,9,12,15}，求A∪(B∩C)。

(精华版)国家开放大学电大本科《离散数学》网络课形考网考作业及答案(精华版)国家开放大学电大本科《离散数学》网络课形考网考作业及答案 100%通过考试说明：2020年秋期电大把该网络课纳入到“国开平台”进行考核，该课程共有5个形考任务，针对该门课程，本人汇总了该科所有的题，形成一个完整的标准题库，并且以后会不断更新，对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

课程总成绩 = 形成性考核×30% + 终结性考试×70% 形考任务1 单项选择题题目1 若集合A＝{ a，{a}，{1，2}}，则下列表述正确的是（）．选择一项：题目2 若集合A＝{2，a，{ a }，4}，则下列表述正确的是( )．选择一项：题目3 设集合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的（）闭包．选择一项：B. 对称题目4 设集合A={1, 2, 3}，B={3, 4, 5}，C={5, 6, 7}，则A∪B–C=( )．选择一项：D. {1, 2, 3, 4} 题目5 如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．选择一项：C. 2 题目6 集合A={1, 2, 3, 4}上的关系R={<x，y>|x=y且x, y∈A}，则R的性质为（）．选择一项：D. 传递的题目7 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )．选择一项：题目8 设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）．选择一项：C. 8 题目9 设A={1, 2, 3, 4, 5, 6, 7, 8}，R是A上的整除关系，B={2, 4, 6}，则集合B的最大元、最小元、上界、下界依次为 ( )．选择一项：B. 无、2、无、2 题目10 设集合A ={1 , 2, 3}上的函数分别为：f = {<1, 2>，<2, 1>，<3, 3>}，g = {<1, 3>，<2, 2>，<3, 2>}，h = {<1, 3>，<2,1>，<3, 1>}，则h =（）．选择一项：D. f◦g 判断题题目11 设A={1, 2}上的二元关系为R={<x, y>|xA，yA, x+y =10}，则R的自反闭包为{<1, 1>, <2, 2>}．（）选择一项：对题目12 空集的幂集是空集．（）选择一项：错题目13 设A={a, b}，B={1, 2}，C={a, b}，从A到B的函数f={<a, 1>, <b, 2>}，从B到C的函数g={<1, b>, <2, a >}，则g° f ={<1，2 >, <2，1 >}．（）选择一项：错题目14 设集合A={1, 2, 3, 4}，B={2, 4, 6, 8}，下列关系f = {<1, 8>, <2, 6>,<3, 4>, <4, 2,>}可以构成函数f：．（）选择一项：对题目15 设集合A={1, 2, 3}，B={2, 3, 4}，C={3, 4, 5}，则A∩(C-B )= {1, 2, 3, 5}．（）选择一项：错题目16 如果R1和R2是A上的自反关系，则、R1∪R2、R1∩R2是自反的．（）选择一项：对题目17 设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有反自反性质．（）选择一项：对题目18 设集合A={1, 2, 3}，B={1, 2}，则P(A)-P(B )={{3},{1,3},{2,3},{1,2,3}}．（）选择一项：对题目19 若集合A = {1，2，3}上的二元关系R={<1, 1>，<1, 2>，<3, 3>}，则R是对称的关系．（）选择一项：错题目20 设集合A={1, 2, 3, 4 }，B={6, 8, 12}， A到B的二元关系R＝那么R－1＝{<6, 3>，<8,4>}．（）选择一项：对形考任务2 单项选择题题目1 无向完全图K4是（）．选择一项：C. 汉密尔顿图题目2 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为( )．选择一项：D. 5 题目3 设无向图G的邻接矩阵为则G的边数为( )．选择一项：A. 7 题目4 如图一所示，以下说法正确的是 ( ) ．选择一项：C. {(d, e)}是边割集题目5 以下结论正确的是( )．选择一项：C. 树的每条边都是割边题目6 若G是一个欧拉图，则G一定是( )．选择一项：B. 连通图题目7 设图G＝<V, E>，v∈V，则下列结论成立的是 ( ) ．选择一项：题目8 图G如图三所示，以下说法正确的是 ( )．选择一项：C. {b, c}是点割集题目9 设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是( )．选择一项：A. （a）是强连通的题目10 设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是( )．选择一项：D. （d）只是弱连通的判断题题目11 设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．( ) 选择一项：对题目12 汉密尔顿图一定是欧拉图．( ) 选择一项：错题目13 设连通平面图G的结点数为5，边数为6，则面数为4．( ) 选择一项：错题目14 设G是一个有7个结点16条边的连通图，则G为平面图．( ) 选择一项：错题目15 如图八所示的图G存在一条欧拉回路．( ) 选择一项：错题目16 设图G如图七所示，则图G的点割集是{f}．( ) 选择一项：错题目17 设G是一个图，结点集合为V，边集合为E，则( ) 选择一项：对题目18 设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去6条边后使之变成树．( ) 选择一项：错题目19 如图九所示的图G不是欧拉图而是汉密尔顿图．( ) 选择一项：对题目20 若图G=<V, E>，其中V={ a, b, c, d }，E={ (a, b), (a, d),(b, c), (b, d)}，则该图中的割边为(b, c)．( ) 选择一项：对形考任务3 单项选择题题目1 命题公式的主合取范式是( )．选择一项：题目2 设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为( )．选择一项：题目3 命题公式的主析取范式是( )．选择一项：题目4 下列公式成立的为( )．选择一项：题目5 设A（x）：x是书，B（x）：x是数学书，则命题“不是所有书都是数学书”可符号化为（）．选择一项：题目6 前提条件的有效结论是( )．选择一项：B. ┐Q 题目7 命题公式(P∨Q)→R的析取范式是 ( )．选择一项：D. (┐P∧┐Q)∨R 题目8 下列等价公式成立的为( )．选择一项：题目9 下列等价公式成立的为( )．选择一项：题目10 下列公式中 ( )为永真式．选择一项：C. ┐A∧┐B ↔ ┐(A∨B) 判断题题目11 设个体域D＝{1, 2, 3}，A(x)为“x小于3”，则谓词公式(∃x)A(x) 的真值为T．( ) 选择一项：对题目12 设P：小王来学校， Q：他会参加比赛．那么命题“如果小王来学校，则他会参加比赛”符号化的结果为P→Q．( ) 选择一项：对题目13 下面的推理是否正确．( ) (1) (∀x)A(x)→B(x) 前提引入(2) A(y)→B(y) US (1) 选择一项：错题目14 含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式(P∧Q∧R)∨(P∧Q∧┐R)．( ) 选择一项：对题目15 命题公式P→(Q∨P)的真值是T．( ) 选择一项：对题目16 命题公式┐P∧P的真值是T．( ) 选择一项：错题目17 谓词公式┐(∀x)P(x)(∃x)┐P(x)成立．( ) 选择一项：对题目18 命题公式┐(P→Q)的主析取范式是P∨┐Q．( ) 选择一项：错题目19 设个体域D＝{a, b}，则谓词公式(∀x)(A(x)∧B(x))消去量词后的等值式为(A(a)∧B(a))∧(A(b)∧B(b))．( ) 选择一项：对题目20 设个体域D＝{a, b},那么谓词公式(∃x)A(x)∨(∀y)B(y)消去量词后的等值式为A(a)∨B(b)．( ) 选择一项：错形考任务4 要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档. 3. 自备答题纸张，将答题过程手工书写，并拍照上传形考任务 5 网上学习行为（学生无需提交作业，占形考总分的10%）附：元宇宙（新兴概念、新型虚实相融的互联网应用和社会形态）元宇宙（Metaverse）是整合了多种新技术而产生的新型虚实相融的互联网应用和社会形态，通过利用科技手段进行链接与创造的，与现实世界映射与交互的虚拟世界，具备新型社会体系的数字生活空间。

吉林大学网络教育学院2019-2020学年第一学期期末考试《离散数学》大作业学生姓名专业层次年级学号学习中心成绩年月日作业完成要求：大作业要求学生手写，提供手写文档的清晰扫描图片，并将图片添加到word 文档内，最终wod文档上传平台，不允许学生提交其他格式文件（如JPG，RAR等非word 文档格式），如有雷同、抄袭成绩按不及格处理。

一、简答题（每小题7分，共56分）1、什么是命题公式的演绎？答：首先定义了消解复杂性的两种范式:最简范式和文字范式,在此基础上采用演绎方法证明了L中的可判定性定理,并设计了命题公式的演绎判定算法P(F).P(F)的时间复杂度为O(n3),远远小于基于真值表法的O(2n)和基于策略方案HAL的O(n5)。

2、什么是子句？请给出一例。

答：子句是一组包含一个主词和一个动词的关连字。

子句与片语有明显的不同，后者为一组不含主词与动词关系的关连字，如"in the morning" 或"running down the street" 或"having grown used to this harassment."3、什么是短语？请给出一例。

答：短语是由句法、语义和语用三个层面上能够搭配的语言单位组合起来的没有句调的语言单位，又叫词组。

它是大于词而又不成句的语法单位。

简单的短语可以充当复杂短语的句法成分，短语加上句调可以成为句子。

由语法上能够搭配的词组合起来的没有句调的语言单位例如：粮食//丰收（名//动）（什么//怎么样）4、什么是命题逻辑中的文字？答：检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。

针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类。

5、什么是析取范式？请给出一例。

答：在离散数学中，仅由有限个文字构成的合取式称为简单合取式，而由有限个简单合取式构成的析取式称为析取范式。

一、简要回答下列问题：（每小题3分，共30分）1．请给出集合的结合率。

答：结合律(AUB)UC=AU(BUC)x∈(AUB)UC，即 x∈AUB 或 x∈C即 x∈A 或 x∈B 或 x∈C 即 x∈A 或 x∈B∪C即 x∈AU(BUC)说明 (AUB)UC包含于AU(BUC)同理可证AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC)2．请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。

3．设A={1，2}，问A上共有多少个不同的对称关系？答：不同的对称关系有：8种R = ΦR = {<1,1>}R = {<2,2>}R = {<1,1>,<2,2>}R = {<1,2>,<2,1>}R = {<1,1>,<1,2>,<2,1>}R = {<1,2>,<2,1>,<2,2>}R = {<1,1>,<1,2>,<2,1>,<2,2>}4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={2,3}，求M的上界，下界。

5．关于P，Q，R请给出使极小项m0，m4为真的解释。

答：m0= ┐p∧┐q∧┐r m4= p∧┐q∧┐r6．什么是图中的简单路？请举一例。

答：图的通路中，所有边e1,e2,…,ek互不相同，称为简单通路。

7．什么是交换群，请举一例。

答：如果群〈G，*〉中的运算*是可以交换的，则称该群为可交换群，或称阿贝尔群。

如〈I，+〉是交换群。

8．什么是群中右模H合同关系？答：设G是群，H是G的子群，a,b∈G，若有h∈H，使得a =bh，则称a合同于b（右模H），记为a≡b（右mod H）。

9．什么是有壹环？请举一例。

答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，则称e为A中关于运算☆的幺元。

一、1.（1 3 2）（4 5）;2.不一定。

因为无限循环群恰有两个生成元;3.一定;4.B;5.C;6.D;7.一共两个子群，一个是{0}，一个是A;8.偶置换,奇置换;9.A={1，2，4，5，20}，关系是整除;10.B;二、1.x8-x4+1;2.4Z;3.商式：2x4+ x3 + 2x2+ 4x+2;余式：2；4.{I,(1 3)},{(1 2)，（1 3 2）},{(2 3),(1 2 3)}5.0的周期是1；1的周期是6；2的周期是3；3的周期是2；4的周期是3；5的周期是6。

三、证明：如果它可约必为一次式与四次及以下因式乘积或二次式与三次及以下因式乘积的形式。

（1）在R2上3x5+5x2+1是x5+x2+1，而f(0)=f(1)=10，所以它在R2上无一次质因式；（2）在R2上的二次质因式只有x2+x+1，而x5+x2+1=x2（x+1）(x2+x+1)+1，所以它在R2上也无二次质因式，因此它在R2上不可约，从而在R0上不可约。

四、1)由C的定义知C?G2)设(G,*)的单位元为e，则有e A和e B，所以e=e*e C；3)任取x, y C，令x=a1*b1, y=a2*b2，则x*y= (a1*b1)*(a2*b2)，因为*满足结合律和交换律，所以有x*y= (a1* a2)*( b1*b2) C，故*在C上是封闭的。

4)任取c C，令x=a*b，则x-1=(a*b)-1= b-1*a-1= a-1*b-1C，故C中每个元素都有逆元素。

因此结论成立。

五、显然X 非空，如（0，0）属于X根据运算的定义，在X上封闭，且满足交换律与结合律，(X, )的单位元是(0,0)，任取(a,b) X，(a,b)的负元是(-a,-b)。

所以(X, )是交换群。

运算在X上封闭，且满足结合律，所以(X, )是半群。

任取(a1,b1)，(a2,b2) ，(a3,b3) X，有(a1,b1) ((a2,b2) (a3,b3))=(a1a2+a1a3,b1b2+b1b3)((a1,b1) (a2,b2)) ((a1,b1) (a3,b3))= (a1a2+a1a3,b1b2+b1b3)，再根据和满足交第 1 页共 2 页。

一．R，S是集合A上的两个关系。

试证明下列等式：（1）(R•S)-1= S-1•R-1（2）(R-1)-1= R答：（1）对∀∈(R。

S)^(-1)∈R。

S∈R ∧∈S∈S^(-1)∧∈R^(-1)∈S^(-1)。

R^(-1)（2）对∀∈(R^(-1))^(-1)∈R^(-1)∈R二、R，S是集合A上的两个关系。

试证明下列等式：（1）(R∪S)-1= R-1∪S-1（2）(R∩S)-1= R-1∩S-1（1）证相互包含:任意<x,y>∈（R∪S）^(-1),<y,x>∈（R∪S）,<y,x>∈R或者),<y,x>∈S<x,y>∈R^(-1),或者<x,y>∈S^(-1),<x,y>∈R^(-1)∪S^(-1),（R∪S）^(-1)包含于R^(-1)∪S^(-1),任意<x,y>∈R^(-1)∪S^(-1),<x,y>∈R^(-1),或者<x,y>∈S^(-1),<y,x>∈R或者,<y,x>∈S<y,x>∈（R∪S）,<x,y>∈（R∪S）^(-1),R^(-1)∪S^(-1)包含于（R∪S）^(-1),所以（R∪S）^(-1)=R^(-1)∪S^(-1),（2）任意<x,y>∈（R∩S）^(-1),<y,x>∈（R∩S）,<y,x>∈R并且,<y,x>∈S<x,y>∈R^(-1),并且<x,y>∈S^(-1),<x,y>∈（R^(-1)∩S^(-1),（R∩S）^(-1)包含于R^(-1)∩S^(-1),任意<x,y>∈R^(-1)∩S^(-1),<x,y>∈R^(-1),并且<x,y>∈S^(-1),<y,x>∈R并且,<y,x>∈S<y,x>∈（R∩S）,<x,y>∈（R∩S）^(-1),R^(-1)∩S^(-1)包含于（R∩S）^(-1),所以（R∩S）^(-1)=R^(-1)∩S^(-1),三、设R是非空集合A上的关系，如果1）对任意a∈A，都有a R a ；2）若aRb，aRc，则bRc ；对称性：已知aRa,对任意b,如果aRb,那么根据条件2有bRa.传递性：对任意a,b,c,如果aRb且bRc,那么根据对称性有bRa,再根据条件2就有aRc.四、若集合A上的关系R，S具有对称性，证明：R•S具有对称性的充要条件为R•S= S•R。

吉大离散数学试题及答案一、选择题1. 以下哪个选项不是离散数学中的基本概念？A. 集合B. 函数C. 微积分D. 关系答案：C2. 在集合论中，以下哪个操作不是基本的集合运算？A. 并集B. 交集C. 差集D. 微分答案：D3. 逻辑运算中的“与”操作，其结果为真当且仅当两个操作数都为真。

这个操作的符号是：A. ∧B. ∨C. ¬D. →答案：A二、填空题1. 一个集合的幂集包含该集合的所有_________。

答案：子集2. 如果函数f: A → B 是单射的，那么对于 A 中的任意两个不同的元素 a1 和 a2，f(a1) 和 f(a2) 在 B 中是_________的。

答案：不同的三、简答题1. 简述什么是图论中的“图”？答案：图是由顶点（或称为节点）和连接这些顶点的边组成的数学结构。

图可以是有向的或无向的，边可以是有权重的或无权重的。

2. 什么是逻辑中的“真值表”？答案：真值表是一种列出逻辑表达式中所有可能的真值组合及其结果的表格。

它用于展示逻辑表达式在不同输入值下的结果。

四、计算题1. 给定集合 A = {1, 2, 3} 和 B = {2, 3, 4}，请找出 A 和 B 的交集。

答案：A ∩ B = {2, 3}2. 假设有一个函数 f(x) = x^2，计算 f(-3) 和 f(3) 的值。

答案：f(-3) = 9，f(3) = 9五、论述题1. 论述离散数学在计算机科学中的应用。

答案：离散数学是计算机科学的基础，它提供了处理计算机科学问题所需的数学工具和理论。

例如，集合论是数据库理论的基础；图论在网络和算法设计中有着广泛应用；逻辑和布尔代数是计算机硬件设计和编程语言的基础。

2. 讨论命题逻辑和谓词逻辑的区别。

答案：命题逻辑关注简单命题及其逻辑关系，而谓词逻辑则引入了量词和变量，允许表达更复杂的逻辑关系。

命题逻辑使用逻辑连接词（如与、或、非等）来构建表达式，而谓词逻辑则使用量词（如全称量词∀和存在量词∃）来描述涉及个体的命题。

班级：学号：姓名：吉林大学计算机科学与技术学院2003级本科《离散数学I》试题（A）注：考试结束后请将此题签与答题纸一并交回，否则后果自负！（2005-01-07）一、简答题（本大题共20小题，每小题2分，共40分）1、设集合A={ ∅}，求幂集合ρ(ρ(A))。

2、部分序集(A, ≤)中的极大元和最大元是如何定义的？3、请给出有向树的定义。

4、什么是Hamilton回路？Hamilton回路一定是简单路吗？5、什么是完全剩余系？什么是简化剩余系？6、什么是单射？任何映射都存在逆映射吗？7、设命题公式G＝(P∧(Q∨R))→(Q∧(S∨⌝R))，I是G的一个解释：P Q R S1 0 1 0 试确定公式G在I下的真值。

8、蕴含式∃xA(x)→∀xB(x)⇒∀x(A(x)→B(x))是否一定成立？若不成立，请举例说明。

9、有限有向图G是Euler图，则G一定是平衡的吗？一定是连通的吗？10、合同式ax≡b(mod m)在什么条件下有解？11、设集合族C={ ∅, {∅}, {1,2},{a},{d,e},{1,2,3}, N, Z, Q, R }，其中N、Z、Q、R分别为自然数、整数、有理数和实数集合，S＝{(A, B)| A∈C,B∈C, 且|A|=|B|}是C上的等价关系，求C关于S的商集。

12、命题公式G＝(P→(Q→R))↔((P∧Q)→R)是恒真公式吗？若不是，请给出一个弄假G的解释。

13、设G＝∀xP(x)∨∀xQ(x)，H＝∀x(P(x)∨Q(x))，则G与H等价吗？为什么？14、图G一定是其闭合图C(G)的支撑子图吗？G与C(G)有可能同构吗？15、对于两个不同的质数a和b，一定存在整数s和t使sa+tb＝1吗？若a和b都整除n，则ab能整除n吗？16、设集合A={a, b, c, d, e, f, g, h}，C={{a, c, h}, {b}, {d, f}, {e, g}}是A的一个划分，请给出划分C对应的等价关系R C。

第二章命题逻辑§2.2 主要解题方法2.2.1 证明命题公式恒真或恒假主要有如下方法：方法一.真值表方法。

即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。

真值表法比较烦琐，但只要认真仔细，不会出错。

例2.2.1 说明 G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。

解：该公式的真值表如下：表2.2.1由于表2.2.1中对应公式G所在列的每一取值全为1，故G恒真。

方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。

例2.2.2 说明 G= ((P→R) ∨⌝ R)→ (⌝ (Q→P) ∧ P)是恒真、恒假还是可满足。

解：由(P→R) ∨⌝ R=⌝P∨ R∨⌝ R=1，以及⌝ (Q→P) ∧ P= ⌝（⌝Q∨ P）∧ P = Q∧⌝ P∧ P=0知，((P→R) ∨⌝ R)→ (⌝ (Q→P) ∧ P)=0，故G 恒假。

方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。

方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G恒假，若最终结果有1，有0，则是可满足的。

例子参见书中例2.4.3。

方法五. 注意到公式G蕴涵公式H的充要条件是：公式G→H是恒真的；公式G，H等价的充要条件是：公式G↔H是恒真的，因此，如果待考查公式是G→H型的，可将证明G→H 是恒真的转化为证明G蕴涵H；如果待考查公式是G↔H型的，可将证明G↔H是恒真的转化为证明G和H彼此相蕴涵。

第一章集合论基础§1.1 基本要求1. 掌握集合、子集、超集、空集、幂集、集合族的概念。

懂得两个集合间相等和包含关系的定义和性质，能够利用定义证明两个集合相等。

熟悉常用的集合表示方法。

2. 掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基本算律，能够利用它们来证明更复杂的集合等式。

3. 掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质：自反性、对称性、反对称性、传递性。

会做关系的乘积。

了解关系的闭包运算：自反闭包、对称闭包、传递闭包。

4. 掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。

5. 掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最大元、最小元、极大元、极小元、上确界、小确界的定义。

能画出有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。

6. 掌握映射、映像、1-1映射等概念，会做映射的乘积。

了解可数集合的概念，掌握可数集合的判定方法。

7. 了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。

§1.2 主要解题方法1.2.1 证明集合的包含关系方法一.用定义来证明集合的包含关系是最常用也是最基本的一种方法。

要证明A⊆B，首先任取x∈A，再演绎地证出x∈B成立。

由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。

当A是无限集时，因为我们不能对x∈A，逐一地证明x∈B成立，所以证明时的假设“x是任取的”就特别重要。

例1.2.1 设A，B，C，D是任意四个非空集合，若A⊆C，B⊆D，则A×B⊆C×D。

证明：任取(x，y) ∈A×B，往证(x，y) ∈C×D。

由(x，y) ∈A×B知，x∈A，且y∈B。

又由A⊆C，B⊆D知，x∈C，且y∈D，因此，(x，y) ∈C×D。