离散数学例题
离散数学例题
一、证明对任意集合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＝{
＝{
令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＝{
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 是满射。
对任意的y1、y2∈B，若f－1 (y1)＝f－1 (y2)＝x，则f(x)＝y1，f(x)＝y2。因为f：A→B 是函数，则y1＝y2。所以f－1 是单射。
综上可得，f－1 ：B→A是双射。
七、设函数g：A→B，f：B→C，则：
(1)f。g是A到C的函数；
(2)对任意的x∈A，有fg(x)＝f(g(x))。
证明
(1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使
对任意的x∈A，若存在y1、y2∈C，使得
综上可知，f。g是A到C的函数。
(2)对任意的x∈A，由g：A→B是函数，有
离散数学题库及答案
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B 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 )。
离散数学复习要点
离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 8．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）
《离散数学》考试题库及答案(三)
《离散数学》考试题库及答案 一、 填空 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、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式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、设代数系统
二、选择 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.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。
离散数学必备知识点总结
离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT
总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；
2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；
离散数学习题
第一章习题 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);
离散数学习题三 含答案
离散数学习题三 11、填充下面推理证明中没有写出的推理规则。 前提：p s r r q q ,,,p →∨?∨? 结论：s 证明：① p 前提引入 ②q ∨?p 前提引入 ③ q （①②析取三段论） ④r q ∨? 前提引入 ⑤ r （③④析取三段论） ⑥s r → 前提引入 ⑦ s （⑤⑥假言推理） 12、填充下面推理证明中没有写出的推理规则。 前提：s)(r q r),(q p →→→→ 结论：s q)(p →∧ 证明：①q)(p ∧ （附加前提） ② p （①化简规则） ③ q （①化简规则） ④r)(q p →→ 前提引入 ⑤r q → （②④假言推理） ⑥ r （③⑤假言推理） ⑦s)(r q →→ 前提引入 ⑧s)(r → （③⑦假言推理） ⑨ s （⑥⑧假言推理） 13、前提：s r ,q p q,q)p (→∨∧→? 结论1：r 结论2：s 结论3：s ∨r （1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。 （2）证明从此前提出发，推任何结论的推理都是正确的。 证明：（1）①r s))r (q)(p q)q)p (((→→∨∨∨∧→? 1r s))r (q)p (q)q)p ((?∨?∧∨?∧?∨?∨∨??
②s ∨ → ∨ → ? ((→ ∨ ∧ s)) p( q) r( q) q) (p ∧ ? ? ∨ ∨ ∧ ? ? ? ∨ ∨ ? q) r( q) ∨ s 1 p s)) p ( q) ((? ③s) ∨ ∨ → ∨ ?r → → ∧ (p q) s)) ((∨ ( r( q) q) p( ? ∧ ∨ ∧ ? ? ? ?r ∨ ∨ ? ∨ ∨ r( q) ∨ s 1 p s)) ((? p q) ( q) 即结论1，结论2，结论3的推理都是正确的。 （2）s) ∨ ∧ ∧ ∧ → (→ ? r( p( (p q) q) q) ∧ ? ∨ ? ∧ ? ∨ ∧ ∧ ∧ ? ? ? ∨ ? ∨ ∧ ∧ (∨ (p q) p( q) ( s) r s) q r p ( q) q) ( q) (p ∨ ? ∧ 0? ? ∨ ∧ s) (p r ( q) 即推任何结论的推理都是正确的。 14、在自然推理系统P中构造下面推理的证明： （1）前提：q → p， → (q r) p, r→ 结论：s 证明：①r) →前提引入 p→ (q ②p 前提引入 ③r) (q→①②假言推理 ④q 前提引入 ⑤r③④假言推理 r→⑤附加律 ⑥s 15、在自然推理系统P中用附加前提法证明下面的推理： 前提：q → ， →s p→ (q p, r) s→ 结论：r 证明： ①s 附加前提引入 ②p s前提引入 → ③p①②假言推理 ④r) →前提引入 p→ (q ⑤r q→③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理 即根据附加前提证明法，推理正确。
离散数学第四章二元关系和函数知识点总结
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体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) 证任取
离散数学例题整理
第一章 定律证明: (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 (交换律,结合律)
离散数学试题及答案(1)
离散数学试题及答案 一、填空题 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.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。
谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证
二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。
离散数学题目大汇总
离散数学试题一（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分）若
离散数学复习题及标准答案
1. 写出命题公式 ﹁（P →（P ∨ Q)）的真值表。 答案： 2.证明 答案: 3. 证明以下蕴涵关系成立： 答案： ４. 写出下列式子的主析取范式: 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P)(Q P)P (Q)(Q Q)P (P)Q)P ((Q)Q)P (P) Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5． 构造下列推理的论证:p ∨q, ｐ→?r ， s →t, ?s →ｒ， ?t ? ｑ 答案: ①s →ｔ 前提 ②t 前提 ③ｓ ①②拒取式I12 ④s →ｒ 前提 ⑤ｒ ③④假言推理I １１ ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论Ｉ10 6. 用反证法证明:ｐ→(?(r ∧s ）→?q ）, p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??) )(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
７. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F （ x )：ｘ是鱼 Ｗ（ x )：x 生活在水中 ))((W(x)F(x)x →? 8． 请将下列命题符号化: 存在着不是有理数的实数。 答案: 令 Q ( ｘ ):x 是有理数 R （ x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令Ｍ(ｘ)：x 是人 Ｃ（x):x 是聪明的 则上述命题符号化为 １０. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥ｘ。 答案: 令P(x):x 是正实数 Ｓ（ｘ,y): x+y ≥x １１． 请将下列命题符号化： 每个人都要参加一些课外活动。 答案: 令P(x ）:x 是人 Q （ｙ）: y 是课外活动 S(ｘ,ｙ）:ｘ参加y ))) ()((())()((x C x M x x C x M x →??∧∧?)) ,()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学章练习题及答案
离散数学练习题 第一章 一．填空 1.公式) ∨ ? ∧的成真赋值为 01；10 ? p∧ ( (q ) p q 2.设p, r为真命题，q, s 为假命题，则复合命题) ? ? →的真值为 0 p→ ( q (s ) r 3.公式) ∨ ? p∧ q ?与共同的成真赋值为 01；10 ? ∧ p ( ) ) (q q p ( 4.设A为任意的公式，B为重言式，则B A∨的类型为重言式 5．设p, q均为命题，在不能同时为真条件下，p与q的排斥也可以写成p与q的相容或。 二．将下列命题符合化 1. 7不是无理数是不对的。 解：) ? ?，其中p: 7是无理数；或p，其中p: 7是无理数。 (p 2.小刘既不怕吃苦，又很爱钻研。 解：其中 ?p: 小刘怕吃苦，q：小刘很爱钻研 p∧ ,q 3.只有不怕困难，才能战胜困难。 解：p →，其中p: 怕困难，q: 战胜困难 q? 或q →，其中p: 怕困难， q: 战胜困难 p? 4.只要别人有困难，老王就帮助别人，除非困难解决了。 解：) → ?，其中p: 别人有困难，q:老王帮助别人，r: 困难解决了 p (q r→ 或：q ?) (，其中p:别人有困难，q: 老王帮助别人，r: 困难解决了r→ ∧ p 5.整数n是整数当且仅当n能被2整除。 解：q p?，其中p: 整数n是偶数，q: 整数n能被2整除 三、求复合命题的真值 P：2能整除5， q：旧金山是美国的首都， r：在中国一年分四季 1. )) p∧ → q ∨ r → ∧ ((q r ( ) ( ) p 2.r ?) → (( → (( ∨ ) ( )) p r p ∨ p q ? ∧ ? q∧ 解：p, q 为假命题，r为真命题 1.)) p∧ → q ∨的真值为0 r → ∧ ( ) ( ) ((q p r
离散数学第二章一阶逻辑知识点总结
数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x
存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中
离散数学复习题及答案
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
离散数学第一章命题逻辑知识点总结
数理逻辑部分 第1章命题逻辑 命题符号化及联结词 命题: 判断结果惟一的陈述句 命题的真值: 判断的结果 真值的取值: 真与假 真命题: 真值为真的命题 假命题: 真值为假的命题 注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。 简单命题(原子命题)：简单陈述句构成的命题 复合命题：由简单命题与联结词按一定规则复合而成的命题 简单命题符号化 用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示 简单命题 用“1”表示真，用“0”表示假 例如，令p：是有理数，则p 的真值为 0 q：2 + 5 = 7，则q 的真值为 1 联结词与复合命题 1.否定式与否定联结词“” 定义设p为命题，复合命题“非p”（或“p的否定”）称 为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假. 2.合取式与合取联结词“∧” 定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真 注意：描述合取式的灵活性与多样性 分清简单命题与复合命题 例将下列命题符号化. (1) 王晓既用功又聪明. (2) 王晓不仅聪明，而且用功. (3) 王晓虽然聪明，但不用功. (4) 张辉与王丽都是三好生. (5) 张辉与王丽是同学. 解令p：王晓用功，q：王晓聪明，则 (1) p∧q (2) p∧q (3) p∧q. 令r : 张辉是三好学生，s :王丽是三好学生 (4) r∧s. (5) 令t : 张辉与王丽是同学，t 是简单命题 . 说明:
《离散数学》试习题及答案
欢迎共阅 一、填空题 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.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题
- 离散数学练习题
- 《离散数学》习题汇总
- 离散数学习题汇总
- 《离散数学(第三版)》方世昌 的期末复习知识点总结含例题
- 离散数学练习题(含答案)(最新整理)
- 离散数学 例题分析共37页
- 离散数学练习题含答案
- 自考离散数学02324真题含答案(2009.4-2016.4年整理版)
- 《离散数学》测试题答案
- 离散数学题目大汇总
- (完整版)自考离散数学02324真题含答案(2009.4-2016.4年整理版),推荐文档
- 离散数学习题答案
- 离散数学选择题
- 离散数学例题整编
- 离散数学例题整理
- (完整版)离散数学[屈婉玲版]第一章部分习题汇总
- 离散数学选择题汇总题库及其规范标准答案
- 【离散数学】知识点典型例题整理
- 电大 离散数学 期末考试历届真题试卷 整理版
- 【离散数学】知识点及典型例题整理