、基本等值式
⑴双重否定律 A A
⑵籍等律 A A A A A V A A
⑶交换律 A A B BA A A V B BV A
⑷结合律 A V (B V C) (A V B) V C A A (B A C) (A A B) A C
⑸分配律 A V (B A C) (A V B) A (A V C) A A (B V C) (A A B) V (A A
C)
(6)德摩根律(A V B) AA B (A A B) AV B
⑺吸收律 A
(8)零律A
⑼同一律 A
(10) 排中律 A
(11) 矛盾律 A
(12) 蕴含等值式A
(13) 等价等值式A V (A A B)
V1 1
A1 A
V A 1
A A 0
B AV
B (A
A A
A
A
B
B) A (B A)
A (A V B)
A 0 0
V 0 A
A
A B (AV B) A (A V B)
A B (A A B) V ( AA B )
(14) 假言易位ABBA
(15) 等价否定等值式ABA B
(16)归谬论(A B) A (A B) A
一、推理定律里口编涵式
1.A ( A B) 附加律
2.( A B) A 化简律
3.( A B) A B 假言推理
4.( A B) B A 拒取式
5.( A B) B A 析取三段论
6.( A B) (B C) (A 假言三段论
7.( A B) (B Q (A C) 等价三段论
8.( A B) (C D) (A C) (B D) 构造性二难
(A B) ( A B) B 构造性二难(特殊形式)
9.( A B) (C D) ( B D) ( A Q 破坏性二难
三、量词辖域收缩与扩张
x(A(x) V B) xA(x) VB
x(A(x) A B) xA(x) AB
x(A(x) —B) xA(x) F
x(B t A(x)) B T xA(x)
x(A(x) V B) xA(x) VB
x(A(x) A B) xA(x) A B
x(A(x) —B) xA(x) F
x(B t A(x)) B T xA(x)
四、量词分配
x(A(x) A B(x)) xA(x) A xB(x)
x(A(x) V B(x)) xA(x) V xB(x)
x(A(x) V B(x)) xA(x) V xB(x)
x(A(x) V B(x)) xA(x) V xB(x)
个体域为全体自然数；A(x): x 是偶数，B(x): x 是奇数；左1,右0 x(A(x) A B(x)) xA(x) A xB(x)
x(A(x) A B(x)) xA(x) A xB(x)
个体域为全体自然数；A(x): x 是偶数
B(x): x 是奇数；左0,右1
应用高等数学等价替换公式 1、无穷小量： 设0）x （g lim ）x （f lim 0 x x x x ==→→ *1）若0） x （g ） x （f lim x x =→，f （x ）是g （x ）的 高阶 无穷小 *2）若∞=→） x （g ） x （f lim x x ，f （x ）是g （x ）的 低阶 无穷小 *3）若c ） x （g ） x （f lim x x =→，f （x ）是g （x ）的 同阶 无穷小 *4）若1） x （g ） x （f lim x x =→，f （x ）是g （x ）的 等价 无穷小 *5）若0） x （g ） x （f lim k x x 0 =→，f （x ）是g （x ）的 k 阶 无穷小 2、等价替换： 若x →x 0，f （x ）~ f 1（x ），g （x ）~ g 1（x ） 则=→）x （g ） x （f lim x x ） x （g ）x （f lim 11x x 0→ 6、常用等价形式： 当f （x ）→0时 *1）sinf （x ）~ f （x ） *2）arc sinf （x ）~ f （x ） *3）tanf （x ）~ f （x ）
*4）arc tanf （x ）~ f （x ） *5）In （1+f （x ））~ f （x ） *6）e f （x ）-1~ f （x ） *7）1-cosf （x ）~ 2 ） x （f 2 *8）（1+f （x ））α -1~ αf （x ） 二、函数的连续： 1、间断点： *1）第一类间断点：f -（x 0）、f +（x 0）均 存在的 间断点 ⑴跳跃间断点： f -（x 0）≠f +（x 0） ⑵可去间断点： f -（x 0）=f +（x 0） *2）第二类间断点：f -（x 0）、f +（x 0）至少有一个 不存在的 间断点 ⑴无穷间断点： f -（x 0）、f +（x 0）中至少有一个为 ∞ ⑵振荡间断点： f -（x 0）、f +（x 0）中至少有一个 振荡不存在 三、导数： 1、定义：）x （f '= x △） x （f -）x △x （f lim 000 x △+→ 2、导数的常见形式： *1） 0 0x x 0x -x ） x （f -）x （f lim ）x （f 0 →=' *2） h ） x （f -）h x （f lim ）x （f 000 h +='→
《离散数学》符号表 全称量词（任意量词） 存在量词 ├断定符（公式在L 中可证） ╞满足符（公式在 E 上有效，公式在 E 上可满足）┐命题的“非”运算 ∧命题的“合取”（“与”）运算 ∨命题的“析取”（“或”，“可兼或”）运算 →命题的“条件”运算 命题的“双条件”运算的 A B命题A与B等价关系 A B 命题 A 与 B 的蕴涵关系 A 公式 A的对偶公式 wff 合式公式 iff 当且仅当 V 命题的“不可兼或”运算（“异或门” ） ↑命题的“与非” 运算（“与非门”） ↓命题的“或非”运算（“或非门” ） □模态词“必然” ◇模态词“可能” φ空集 ∈属于（不属于） A （·）集合 A 的特征函数 P（A）集合 A 的幂集 A 集合 A 的点数 A A A （A n）集合A的笛卡儿积
R 2 R R ( R n R n 1 ) 关系 R 的“复合” R 阿列夫零 阿列夫 包含 真包含 ∪ 集合的并运算 ∩ 集合的交运算 - （～） 集合的差运算 集合的对称差运算 m m 同余加 m m 同余乘 〡 限制 [ x] R 集合关于关系 R 的等价类 A/ R 集合 A 上关于 R 的商集 R ( A) 集合 A 关于关系 R 的划分 R (A) 集合 A 关于划分 的关系 [a] 元素 a 产生的循环群 [a] R 元素 a 形成的 R 等价类 C r 由相容关系 r 产生的最大相容类 I 环，理想 Z /( n) 模 n 的同余类集合 a b(mod k) a 与 b 模 k 相等 r ( R) 关系 R 的自反闭包 s( R) 关系 R 的对称闭包
、基本等值式 ⑴双重否定律 A A ⑵籍等律 A A A A A V A A ⑶交换律 A A B BA A A V B BV A ⑷结合律 A V (B V C) (A V B) V C A A (B A C) (A A B) A C ⑸分配律 A V (B A C) (A V B) A (A V C) A A (B V C) (A A B) V (A A C) (6)德摩根律(A V B) AA B (A A B) AV B ⑺吸收律 A (8)零律A ⑼同一律 A (10) 排中律 A (11) 矛盾律 A (12) 蕴含等值式A (13) 等价等值式A V (A A B) V1 1 A1 A V A 1 A A 0 B AV B (A A A A A B B) A (B A) A (A V B) A 0 0 V 0 A A A B (AV B) A (A V B) A B (A A B) V ( AA B ) (14) 假言易位ABBA (15) 等价否定等值式ABA B (16)归谬论(A B) A (A B) A 一、推理定律里口编涵式 1.A ( A B) 附加律 2.( A B) A 化简律 3.( A B) A B 假言推理 4.( A B) B A 拒取式 5.( A B) B A 析取三段论 6.( A B) (B C) (A 假言三段论 7.( A B) (B Q (A C) 等价三段论 8.( A B) (C D) (A C) (B D) 构造性二难 (A B) ( A B) B 构造性二难(特殊形式) 9.( A B) (C D) ( B D) ( A Q 破坏性二难 三、量词辖域收缩与扩张 x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) AB x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) x(A(x) V B) xA(x) VB x(A(x) A B) xA(x) A B x(A(x) —B) xA(x) F x(B t A(x)) B T xA(x) 四、量词分配 x(A(x) A B(x)) xA(x) A xB(x) x(A(x) V B(x)) xA(x) V xB(x) x(A(x) V B(x)) xA(x) V xB(x)
离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8.
C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D=
D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为
离散数学基础试题（二） 一、判断题（每题2分，共12分） 1.在命运题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的。（） 2.与是不等值的（） 3.设是非连通平面图G的对偶图，设分别为的顶点数，边数和面数，则它们之间满足欧拉公式：。（） 4.设无向图G具有割点，则G中一定不存在哈密尔顿通路。（） 5.设，A上的恒等关系既是A上的等价关系也是A上的偏序关系。（） 6.设A,B,C,D均为非空的集合，已知A*B且C*D，则一定有。（） 二、填空题（每小题3分，共30分） 1.设p:小王走路,q:小王听音乐,在命题逻辑中，命题“小王边走路边听音乐”的符号化形式为___________________。 2.设F(x):x是人，H(x,y):x与y一样高，在一阶逻辑中，命题“人都不一样高”的符号化形式为_________________。 3.的成真赋值为________________________。 4.设G是n阶无向带权边通图，各变的权均为a(a>0),设T是G的一棵最小生成树，则T的权W(T)=_______________________。 5.设G1,G2,G3,G4都是4阶3条边的无向简单图，则它们之间至少有 ___________________个是同构的。 6．设G是n（n2）阶二部图，又是平面图，则命题“G的对偶图是欧拉图”的真值为_______________________。 7.设为整数集，，则f的值域ranf=___________。 8.设则A上共有____________个不同的等价关系。 9.设，恒等关系IA的传递闭包t(IA)=_________________。
无穷小 极限的简单计算 【教学目的】 1、理解无穷小与无穷大的概念； 2、掌握无穷小的性质与比较 会用等价无穷小求极限； 3、不同类型的未定式的不同解法。 【教学内容】 1、无穷小与无穷大； 2、无穷小的比较； 3、几个常用的等价无穷小 等价无穷小替换； 4、求极限的方法。 【重点难点】 重点是掌握无穷小的性质与比较 用等价无穷小求极限。 难点是未定式的极限的求法。 【教学设计】首先介绍无穷小和无穷大的概念和性质（30分钟），在理解无穷小与无穷大的概念和性质的基础上,让学生重点掌握用等价无穷小求极限的方法（20分钟）。最后归纳总结求极限的常用方法和技巧（25分钟），课堂练习（15分钟）。 【授课内容】 一、无穷小与无穷大 1.定义 前面我们研究了∞→n 数列n x 的极限、∞→x （+∞→x 、+∞→x ）函数() x f 的极限、0x x →（+→0x x 、- →0x x ）函数()f x 的极限这七种趋近方式。下面 我们用 →x ＊表示上述七种的某一种趋近方式，即 ＊{ } - + →→→-∞→+∞→∞→∞→∈00 x x x x x x x x x n 定义：当在给定的→x ＊下，()f x 以零为极限，则称()f x 是→x ＊下的无穷小，即()0lim =→x f x ＊ 。 例如, ,0sin lim 0 =→x x Θ .0sin 时的无穷小是当函数→∴x x ,01lim =∞→x x Θ .1 时的无穷小是当函数∞→∴x x ,0)1(lim =-∞→n n n Θ .})1({时的无穷小是当数列∞→-∴n n n 【注意】不能把无穷小与很小的数混淆；零是可以作为无穷小的唯一的数，任何 非零常量都不是无穷小。
目录 数学符号起源 (1) 数学符号种类 (2) 数学符号读法 (10) 数学符号起源 数学除了记数以外，还需要一套数学符号来表示数和数、数和形的相互关系。数学符号的发明和使用比数字晚，但是数量多得多。现在常用的有200多个，初中数学书里就不下20多种。它们都有一段有趣的经历。 例如加号曾经有好几种，现在通用"+"号。 "+"号是由拉丁文"et"（"和"的意思）演变而来的。十六世纪，意大利科学家塔塔里亚用意大利文"più"（加的意思）的第一个字母表示加，草为"δ"最后都变成了"+"号。 "-"号是从拉丁文"minus"（"减"的意思）演变来的，简写m，再省略掉字母，就成了"-"了。 到了十五世纪，德国数学家魏德美正式确定："+"用作加号，"-"用作减号。 乘号曾经用过十几种，现在通用两种。一个是"3"，最早是英国数学家奥屈特1631年提出的；一个是"2"，最早是英国数学家赫锐奥特首创的。德国数学家莱布尼茨认为："3"号象拉丁字母"X"，加以反对，而赞成用"2"号。他自己还提出用"п"表示相乘。可是这个符号现在应用到集合论中去了。 到了十八世纪，美国数学家欧德莱确定，把"3"作为乘号。他认为"3"是"+"斜起来写，是另一种表示增加的符号。 平方根号曾经用拉丁文“Radix”（根）的首尾两个字母合并起来表示，十七世纪初叶，法国数学家笛卡儿在他的《几何学》中，第一次用“ⅳ”表示根号。“ⅳ”是由拉丁字线“r”变，“——”是括线。 "÷"最初作为减号，在欧洲大陆长期流行。直到1631年英国数学家奥屈特用"："表示除或比，另外有人用"-"（除线）表示除。后来瑞士数学家拉哈在他所著的《代数学》里，才根据群众创造，正式将"÷"作为除号。
离散数学自学笔记命题公式及其真值表 我们把表示具体命题及表示常命题的p，q，r，s等与f，t统称为命题常元（proposition constant）。深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。相同符号的不同意义，容易从上下文来区别，在未指出符号所表示的具体命题时，它们常被看作变元。 命题常元、变元及联结词是形式描述命题及其推理的基本语言成分，用它们可以形式地描述更为复杂的命题。下面我们引入高一级的语言成分——命题公式。 定义1.1 以下三条款规定了命题公式（proposition formula）的意义： （1）命题常元和命题变元是命题公式，也称为原子公式或原子。 （2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A？B）也是命题公式。 （3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。 命题公式简称公式，常用大写拉丁字母A，B，C等表示。公式的上述定义方式称为归纳定义，第四章将对此定义方式进行讨论。 例1.8 （┐（p→（q∧r）））是命题公式，但（qp），p→r，p1∨p2∨…均非公式。 为使公式的表示更为简练，我们作如下约定： （1）公式最外层括号一律可省略。 （2）联结词的结合能力强弱依次为┐，（∧，∨），→，？，（∧，∨）表示∧与∨平等。 （3）结合能力平等的联结词在没有括号表示其结合状况时，采用左结合约定。湖南省自考网：https://www.doczj.com/doc/022681112.html,/整理 例如，┐p→q∨（r∧q∨s）所表示的公式是（（┐p）→（q∨（（r∧q）∨s））） 设A是命题公式，A1是A 的一部分，且A1也是公式，则A1称为公式A的子公式。
离散数学公式
————————————————————————————————作者: ————————————————————————————————日期： ?
基本等值式 1．双重否定律A?┐┐A ２．幂等律 A ? A∨A,?A ?A∧A 3．交换律?Ａ∨Ｂ?B∨A，?A∧B ?B∧A 4.结合律??（Ａ∨Ｂ)∨Ｃ? A∨（B∨Ｃ) ?(A∧B)∧C ? A∧(Ｂ∧Ｃ) ５.分配律Ａ∨(B∧C）?（Ａ∨B)∧(Ａ∨C）(∨对∧的分配律）??A∧(B∨Ｃ）?(A∧B）∨（A∧Ｃ) (∧对∨的分配律) 6.德·摩根律?┐(A∨B) ?┐A∧┐B ┐（A∧Ｂ）?┐A∨┐B 7.吸收律?Ａ∨(Ａ∧Ｂ) ?A,A∧(A∨B) ?Ａ 8．零律?A∨１?1,A∧0 ?０ ９.同一律?A∨0 ?A，A∧1?Ａ 10．排中律A∨┐A ?１ 11．矛盾律?A∧┐Ａ? 0 12.蕴涵等值式Ａ→B?┐A∨B １3．等价等值式??Ａ?Ｂ?(A→B）∧(Ｂ→Ａ) １4.假言易位A→Ｂ?┐Ｂ→┐A 15.等价否定等值式 A?B ?┐Ａ?┐Ｂ 16.归谬论(A→Ｂ)∧（A→┐B)?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2）否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (３）利用分配律：利用∧对∨的分配律求析取范式,∨对∧的分配律求合取范式。 推理定律-－重言蕴含式 (１）A ?(A∨B) 附加律 (2) （A∧B）? A ?化简律 （3） (Ａ→B)∧Ａ? B ??假言推理 (４) (Ａ→B)∧┐Ｂ?┐A 拒取式 （5）(A∨B）∧┐B? A ?析取三段论 (6) (A→B) ∧（Ｂ→C)?（A→C) ?假言三段论 (7) (Ａ?B) ∧（B?C) ? (Ａ? C)?等价三段论 （8) (A→B)∧（Ｃ→Ｄ）∧(A∨Ｃ) ?(B∨Ｄ) 构造性二难 (A→B)∧(┐Ａ→B)∧(Ａ∨┐A) ?Ｂ构造性二难（特殊形式) （9)(A→B)∧(Ｃ→Ｄ)∧(┐B∨┐D) ?(┐Ａ∨┐C) 破坏性二难
这个问题很多人都搞不明白，很多自认为明白的人也不负责任地说一句“乘除可以，加减不行”，包括不少高校教师。其实这种讲法是不对的！关键是要知道其中的道理，而不是记住结论。 1.做乘除法的时候一定可以替换，这个大家都知道。 如果f(x)～u(x)，g(x)～v(x)，那么lim f(x)/g(x) = lim u(x)/v(x)。关键要记住道理 lim f(x)/g(x) = lim f(x)/u(x) * u(x)/v(x) * v(x)/g(x) 其中两项的极限是1，所以就顺利替换掉了。 2.加减法的时候也可以替换！但是注意保留余项。 f(x)～u(x)不能推出f(x)+g(x)～u(x)+g(x)，这个是很多人说不能替换的原因，但是如果你这样看： f(x)～u(x)等价于f(x)=u(x)+o(f(x))，那么f(x)+g(x)=u(x)+g(x)+o(f(x))，注意这里是等号，所以一定是成立的！ 问题就出在u(x)+g(x)可能因为相消变成高阶的无穷小量，此时余项o(f(x))成为主导，所以不能忽略掉。当u(x)+g(x)的阶没有提高时，o(f(x))仍然是可以忽略的。 比如你的例子，ln(1+x)+x是可以替换的，因为 ln(1+x)+x=[x+o(x)]+x=2x+o(x)， 所以ln(1+x)+x和2x是等价无穷小量。 但是如果碰到ln(1+x)-x，那么 ln(1+x)+x=[x+o(x)]-x=o(x)， 此时发生了相消，余项o(x)成为了主导项。此时这个式子仍然是成立的！只不过用它来作为分子或分母的极限问题可能得到不定型而无法直接求出来而已。 碰到这种情况也不是说就不能替换，如果你换一个高阶近似： ln(1+x)=x-x^2/2+o(x^2) 那么 ln(1+x)-x=-x^2/2+o(x^2) 这个和前面ln(1+x)-x=o(x)是相容的，但是是更有意义的结果，此时余项o(x^2)可以忽略。也就是说用x-x^2/2作为ln(1+x)的等价无穷小量得到的结果更好。
《离散数学》符号表 ? 全称量词（任意量词） ? 存在量词 ├ 断定符（公式在L 中可证） ╞ 满足符（公式在E 上有效，公式在E 上可满足） ┐ 命题的“非”运算 ∧ 命题的“合取”（“与”）运算 ∨ 命题的“析取”（“或”，“可兼或”）运算 → 命题的“条件”运算 ? 命题的“双条件”运算的 B A ? 命题A 与 B 等价关系 B A ? 命题A 与B 的蕴涵关系 *A 公式A 的对偶公式 wff 合式公式 iff 当且仅当 V 命题的“不可兼或”运算（ “异或门” ） ↑ 命题的“与非” 运算（ “与非门” ） ↓ 命题的“或非”运算（ “或非门” ） □ 模态词“必然” ◇ 模态词“可能” φ 空集 ? 属于（?不属于） A μ（·） 集合A 的特征函数 P （A ） 集合A 的幂集 A 集合A 的点数 n A A A ??? （n A ） 集合A 的笛卡儿积
R R R =2 )(1R R R n n -= 关系R 的“复合” 0? 阿列夫零 ? 阿列夫 ? 包含 ? 真包含 ∪ 集合的并运算 ∩ 集合的交运算 - （～） 集合的差运算 ⊕ 集合的对称差运算 m + m 同余加 m ? m 同余乘 〡 限制 R x ][ 集合关于关系R 的等价类 A /R 集合A 上关于R 的商集 )(A R π 集合A 关于关系R 的划分 )(A R π 集合A 关于划分π的关系 ][a 元素a 产生的循环群 R a ][ 元素a 形成的R 等价类 r C 由相容关系r 产生的最大相容类 I 环，理想 )/(n Z 模n 的同余类集合 )(mod k b a ≡ a 与 b 模k 相等 )(R r 关系R 的自反闭包 )(R s 关系R 的对称闭包
基本等值式 1.双重否定律 A ?┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律A∨B ? B∨A， A∧B ? B∧A 4.结合律(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) 5.分配律A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律┐(A∨B) ?┐A∧┐B ┐(A∧B) ?┐A∨┐B 7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A 8.零律A∨1 ? 1,A∧0 ? 0 9.同一律A∨0 ? A，A∧1 ? A 10.排中律A∨┐A ? 1 11.矛盾律A∧┐A ? 0 12.蕴涵等值式A→B ?┐A∨B 13.等价等值式A?B ? (A→B)∧(B→A) 14.假言易位A→B ?┐B→┐A 15.等价否定等值式 A?B ?┐A?┐B 16.归谬论(A→B)∧(A→┐B) ?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。 推理定律--重言蕴含式 (1) A T (A∨B) 附加律 (2) (A∧B) T A 化简律 (3) (A→B)∧A T B 假言推理 (4) (A→B)∧┐B T┐A 拒取式 (5) (A∨B)∧┐B T A 析取三段论 (6) (A→B) ∧(B→C) T (A→C) 假言三段论 (7) (A?B) ∧(B?C) T (A ? C) 等价三段论 (8) (A→B)∧(C→D)∧(A∨C) T(B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A) T B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) T(┐A∨┐C)破坏性二难
理学院
《离散数学基础》实验教学大纲 课程名称：离散数学基础实验 课程编号：080J21A 课程总学时：51 实验学时数：17 课程总学分：2.5 实验学分：0.5 开设实验项目数：5 一、实验教学目的 面向离散数学在计算机中的应用，通过实验操作，使学生掌握研究计算机科学的基础理论，进一步提高学生的抽象思维与逻辑推理能力，增强实际应用能力。 二、实验项目内容、基本要求与学时分配 注：1、实验类型：演示、验证、操作、综合、设计、研究。2、实验要求：指必做、选做。 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 推荐教材：《离散数学》（修订版），耿素云屈婉玲编著，高等教育出版社，2004年。 主要参考书：《离散数学导论》第二版，徐洁磬编著，高等教育出版社，1997年。 《离散数学》， [美]S.利普舒尔茨， M.利普森，周兴和、孙志人、张学斌译, 科学出版社和麦格劳-希尔教育出版集团, 2001年。
《计算方法》实验教学大纲 课程名称：计算方法实验 课程编号：080J22B 课程总学时：85 实验学时数：34 课程总学分：4 实验学分：1 开设实验项目数：5 一、实验教学目的 本课程以MATLAB或C为编程语言，将《计算方法》课程中的常用算法用MATLAB语言描述并上机进行数值实验。通过实验，使学生进一了解各个算法的特点及适用范围，提高学生用计算机解决实际问题的能力。 二、实验项目内容、基本要求与学时分配 三、实验考核方式与标准 实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实验态度占10%、实验理论占15%；操作技能占50%；实验报告占25%。 四、实验教材与参考书 1、《计算机数值方法》（第二版），施吉林等，高教出版社出版，2005年 2、《计算方法引论》（第二版），徐翠薇、孙绳武，高等教育出版社，2002
├断定符（公式在L中可证） ╞满足符（公式在E上有效，公式在E上可满足）┐命题的“非”运算 ∧命题的“合取”（“与”）运算 ∨命题的“析取”（“或”，“可兼或”）运算 → 命题的“条件”运算 A<=>B 命题A 与B 等价关系 A=>B 命题A与B的蕴涵关系 A* 公式A 的对偶公式 wff 合式公式 iff 当且仅当 ↑ 命题的“与非” 运算（“与非门” ） ↓ 命题的“或非”运算（“或非门” ） □模态词“必然” ◇模态词“可能” φ 空集 ∈属于（??不属于） P（A）集合A的幂集 |A| 集合A的点数 R^2=R○R [R^n=R^(n-1)○R] 关系R的“复合” ∪集合的并运算 ∩集合的交运算
- （～）集合的差运算 〡限制 [X](右下角R) 集合关于关系R的等价类 A/ R 集合A上关于R的商集 [a] 元素a 产生的循环群 I (i大写) 环，理想 Z/(n) 模n的同余类集合 r(R) 关系R的自反闭包 s(R) 关系的对称闭包 CP 命题演绎的定理（CP 规则） EG 存在推广规则（存在量词引入规则） ES 存在量词特指规则（存在量词消去规则）UG 全称推广规则（全称量词引入规则）US 全称特指规则（全称量词消去规则） R 关系 r 相容关系 R○S 关系与关系的复合 domf 函数的定义域（前域） ranf 函数的值域 f:X→Y f是X到Y的函数 GCD(x,y) x,y最大公约数 LCM(x,y) x,y最小公倍数
aH(Ha) H 关于a的左（右）陪集 Ker(f) 同态映射f的核（或称f同态核）[1，n] 1到n的整数集合 d(u,v) 点u与点v间的距离 d(v) 点v的度数 G=(V,E) 点集为V，边集为E的图 W(G) 图G的连通分支数 k(G) 图G的点连通度 △（G) 图G的最大点度 A(G) 图G的邻接矩阵 P(G) 图G的可达矩阵 M(G) 图G的关联矩阵 C 复数集 N 自然数集（包含0在内） N* 正自然数集 P 素数集 Q 有理数集 R 实数集 Z 整数集 Set 集范畴 Top 拓扑空间范畴 Ab 交换群范畴
离散数学基本知识 体积和表面积三角形的面积,底×高?2。公式S= a×h?2 正方形的面积,边长×边长公式 S= a2 长方形的面积,长×宽公式S= a×b 平行四边形的面积,底×高公式S= a×h 梯形的面积,(上底+下底)×高?2 公式 S=(a+b)h?2 内角和:三角形的内角 和,180度。 长方体的表面积,(长×宽，长×高，宽×高) ×2 公 式:S=(a×b+a×c+b×c)×2 正方体的表面积,棱长×棱长×6 公式: S=6a2 长方体的体积,长×宽×高公式:V = abh 长方体(或正方体)的体积,底面积×高公式:V = abh 正方体的体积,棱长×棱长×棱长公式:V = a3 圆的周长,直径×π公式:L,πd,2πr 1 圆的面积,半径×半径×π公式:S,πr2 圆柱的表(侧)面积:圆柱的表(侧)面积等于底面的周长乘高。公 式:S=ch=πdh,2πrh 圆柱的表面积:圆柱的表面积等于底面的周长乘高再加上两头的圆的面积。公式:S=ch+2s=ch+2πr2 圆柱的体积:圆柱的体积等于底面积乘高。公式:V=Sh 圆锥的体积,1/3底面×积高。公式:V=1/3Sh 算术 1、加法交换律:两数相加交换加数的位置，和不变。 2、加法结合律:a + b = b + a 3、乘法交换律:a × b = b × a
4、乘法结合律:a × b × c = a ×(b × c) 5、乘法分配律:a × b + a × c = a × b + c 6、除法的性质:a ? b ? c = a ?(b × c) 7、7、除法的性质:在除法里，被除数和除数同时扩大(或缩小)相同的倍数，商不变。 O除以任何不是O的数都得O。简便乘法:被乘数、乘数末尾有O的乘法，可以先把O前面的相乘，零不参加运算，有几个零都落下，添在积的末尾。 8、 8、有余数的除法: 被除数,商×除数+余数方程、代数与等式 2 9、等式:等号左边的数值与等号右边的数值相等的式子叫做等式。等式的基本性质:等式两边同时乘以(或除以)一个相同的数，等式仍然成立。 10、方程式:含有未知数的等式叫方程式。一元一次方程式:含有一个未知数，并且未知数的次数是一次的等式叫做一元一次方程式。学会一元一次方程式的例法及计算。即例出代有χ的算式并计算。 11、代数: 代数就是用字母代替数。代数式:用字母表示的式子叫做代数式。如:3x =ab+c 分数:把单位“1”平均分成若干份，表示这样的一份或几分的数,叫做分数。 分数大小的比较:同分母的分数相比较，分子大的大，分子小的小。异分母的分数相比较，先通分然后再比较;若分子相同，分母大的反而小。 分数的加减法则:同分母的分数相加减，只把分子相加减，分母不变。异分母的分数相加减， 先通分，然后再加减。 分数乘整数，用分数的分子和整数相乘的积作分子，分母不变。 分数乘分数，用分子相乘的积作分子，分母相乘的积作为分母。 3
离散数学考试题(后附详细答案) 一、命题符号化(共6小题,每小题3分,共计18分) 1.用命题逻辑把下列命题符号化 a)假如上午不下雨,我去瞧电影,否则就在家里读书或瞧报。 设P表示命题“上午下雨”,Q表示命题“我去瞧电影”,R表示命题“在家里读书”,S表示命题“在家瞧报”,命题符号化为:(?P?Q)∧(P?R∨S) b)我今天进城,除非下雨。 设P表示命题“我今天进城”,Q表示命题“天下雨”,命题符号化为:?Q→P或?P→Q c)仅当您走,我将留下。 设P表示命题“您走”,Q表示命题“我留下”,命题符号化为: Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不就是有理数 设R(x)表示“x就是实数”,Q(x)表示“x就是有理数”,命题符号化为: ?x(R(x) ∧?Q(x)) 或??x(R(x) →Q(x)) b)对于所有非零实数x,总存在y使得xy=1。 设R(x)表示“x就是实数”,E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为: ?x(R(x) ∧?E(x,0) →?y(R(y) ∧E(f(x,y),1)))) c) f 就是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B,使得f(a)=b、 设F(f)表示“f就是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为:F(f)??a(A(a)→?b(B(b) ∧ E(f(a),b) ∧?c(S(c) ∧ E(f(a),c) →E(a,b)))) 二、简答题(共6道题,共32分) 1.求命题公式(P→(Q→R))?(R→(Q→P))的主析取范式、主合取范式,并写出所有成真赋 值。(5分) (P→(Q→R))?(R→(Q→P))?(?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) ∨(?P∨?Q∨R)) ?(P∨?Q∨?R) ∧(?P∨?Q∨R) 这就是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 (?P∧?Q∧?R)∨(?P∧?Q∧R)∨(?P∧Q∧?R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) 2.设个体域为{1,2,3},求下列命题的真值(4分) a)?x?y(x+y=4) b)?y?x (x+y=4) a) T b) F 3.求?x(F(x)→G(x))→(?xF(x)→?xG(x))的前束范式。(4分) ?x(F(x)→G(x))→(?xF(x)→?xG(x)) ??x(F(x)→G(x))→(?yF(y)→?zG(z))??x(F(x)→G(x))→?y?z(F(y)→G(z)) ??x?y?z((F(x)→G(x))→ (F(y)→G(z))) 4.判断下面命题的真假,并说明原因。(每小题2分,共4分) a)(A?B)－C=(A-B) ?(A-C) b)若f就是从集合A到集合B的入射函数,则|A|≤|B| a) 真命题。因为(A?B)－C=(A?B)?~C=(A?~C)?(B?~C)=(A-C)?(B-C) b) 真命题。因为如果f就是从集合A到集合B的入射函数,则|ranf|=|A|,且ranf?B,故命题 成立。
离散数学笔记 第一章命题逻辑 合取 析取 定义 1. 1.3否定：当某个命题为真时，其否定为假，当某个命题为假时，其否定为真定义 1. 1.4条件联结词，表示“如果……那么……”形式的语句 定义 1. 1.5双条件联结词，表示“当且仅当”形式的语句 定义 1.2.1合式公式 (1)单个命题变元、命题常元为合式公式，称为原子公式。 (2)若某个字符串A 是合式公式，则?A、(A)也是合式公式。 (3)若A、B 是合式公式，则A ∧B、A∨B、A→B、A?B 是合式公式。 (4)有限次使用(2)~(3)形成的字符串均为合式公式。 1.3等值式 1.4析取范式与合取范式
将一个普通公式转换为范式的基本步骤
1.6推理 定义 1.6.1 设 A 与 C 是两个命题公式， 若 A → C 为永真式、 重言式，则称 C 是 A 的有 效结论，或称 A 可以逻辑推出 C ，记为 A => C 。（用等值演算或真值表） 第二章 谓词逻辑 2.1、基本概念 ?：全称量词 ?：存在量词 一般情况下， 如果个体变元的取值范围不做任何限制即为全总个体域时， 带 “全称量词”的谓词公式形如"?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)) 2.2、谓词公式及其解释 定义 2.2.1、 非逻辑符号： 个体常元(如 a,b,c)、 函数常元(如表示22 y x 的 f(x,y))、 谓词常元(如表示人 类的 H(x))。 定义 2.2.2、逻辑符号：个体变元、量词(??)、联结词(﹁∨∧→?)、逗号、括号。 定义 2.2.3、项的定义：个体常元、变元及其函数式的表达式称为项(item)。 定义 2.2.4、原子公式：设 R(n x x ... 1)是 n 元谓词，n t t ...1是项，则 R(t)是原子公式。原子公式中的个体变元，可以换成个体变元的表达式(项)，但不能出现任何联结词与量词，只能为单个的谓词公式。 定义 2.2.5 合式公式：(1)原子公式是合式公式；(2)若 A 是合式公式，则(﹁A)也是合式公式；(3)若 A,B 合式，则 A ∨B, A ∧B, A →B , A ?B 合式(4)若 A 合式，则?xA 、?xA 合式(5)有限次使用(2)~(4)得到的式子是合式。 定义 2.2.6 量词辖域：?xA 和?xA 中的量词?x/?x 的作用范围，A 就是作用范围。 定义 2.2.7 约束变元：在?x 和?x 的辖域 A 中出现的个体变元 x ，称为约束变元，这是与量词相关的变元，约束变元的所有出现都称为约束出现。 定义 2.2.8 自由变元：谓词公式中与任何量词都无关的量词，称为自由变元，它的每次出现称为自由出现。一个公式的个体变元不是约束变元，就是自由变元。 注意：为了避免约束变元和自由变元同名出现，一般要对“约束变元”改名，而不对自由变元改名。 定义 2.2.9 闭公式是指不含自由变元的谓词公式
怎样学好离散数学 最常和理论计算机科学放在一起的一个词是什么？答：离散数学。这两者的关系是如此密切，以至于它们在不少场合下成为同义词。（这一点在前面的那本书中也有体现）传统上，数学是以分析为中心的。数学系的同学要学习三四个学期的数学分析，然后是复变函数，实变函数，泛函数等等。实变和泛函被很多人认为是现代数学的入门。在物理，化学，工程上应用的，也以分析为主。 随着计算机科学的出现，一些以前不太受到重视的数学分支突然重要起来。人们发现，这些分支处理的数学对象与传统的分析有明显的区别：分析研究的问题解决方案是连续的，因而微分，积分成为基本的运算；而这些分支研究的对象是离散的，因而很少有机会进行此类的计算。人们从而称这些分支为“离散数学”。“离散数学”的名字越来越响亮，最后导致以分析为中心的传统数学分支被相对称为“连续数学”。 《离散数学》作为一个单独的分枝，在世界上出现的时间并不久，不过几十年，但它的各部分内容中有相当一部分却早已出现在数学中。为什么将各个数学分支中的一些内容集中起来加以研究，并且冠上一个新的名称——离散数学呢？这主要是因为计算机科学的产生和发展。正如恩格斯所说：“……科学的状况还更多的从属于技术的状况和需要。倘若社会上有了一种技术上的需要，那就比十个大学还更能推动科学前进。”①计算机的出现，在很大程度上影响到了人们的思想和生活，对社会生产起了重大作用。为了研究计算机科学的理论基础，离散数学也就应运而生。因此，如果我们不从纯数学的角度，而从应用数学的角度来考虑，也许给离散数学换一个名称一一计算机科学的数学基础——更能说明问题。 正是因为这个原因，在计算机科学系。信息管理系都将离散数学作为必须学习的基础课程。而实践证明这种做法是正确的。 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。 随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现
离散数学 练习题 一、填空题 1. 仅用∨和┐写出下列表达式的等价形式 a) R Q P ?∧∨?)(? b) )(E D A ?∨→?? 2. 仅用∧和┐写出下列表达式的等价形式 a) R Q P ?∧∨?)(? b) ?∧→?)(Q P Q ； 3. 构造公式Q Q P P ?∨∧)(的真值表 。 4. 公式A 有三个命题变元P 、Q 、R 组成，其主合取范式为A ?710M M M ∧∧，则 其主析取范式为： 5. 公式A 有三个命题变元P 、Q 、R 组成，其主析取范式为A ?6520m m m m ∨∨∨，则其主合取范式为： 6. 设{}A d c b a A ,,,,=上的二元关系： {}><><><><><=c c a c d b b a a a R ,,,,,,,,,，{}><><><><><=d d c c b c b b c a S ,,,,,,,,, 则=-R S 1 =S R =)(R r =)(R s =)(S t 7. 给定如图所示的二元树： 按先根次序遍历访问结点的顺序为： 。 按中根次序遍历访问结点的顺序为： 。 按后根次序遍历访问结点的顺序为： 。 8. 2},,{},2,1{B A b a B A ?=== 9. 设解释I 如下： B F
确定下列各式的真值： )2,(x xP ? ___ __; ),1(y yP ? __ ___; ),(y x yP x ??) __ ___。??x yP x y (,) ___; 10. 集合}}2{},2,{{Φ=A 的幂集=)(A ρ 。 11. 设全集U={1,2,3,4,5,6,7,8,9,10}, A={1,2,4,5,6}, B={2,4,6,8,10}, 则：(A ∪B)-B = , B A -= , B ⊕A= , B ?A= 12. B A b a B A ?==},,{}},2,1{{= 。 13. 给定集合S={a,b,c,d}，S 上的等价关系R 能产生划分{{a},{b},{c,d}}，则R ＝ 14. 指出下列映射是单射、满射、双射还是既非单射也非满射： a) x x f R Z f ln )(, :=→+； (Z+: 表示正整数集) 。 b) +→R R f :，1)(2+=x x f （+R 表示不小于0的实数） 。 c) +→R R f :，2)(x x f = （+R 表示不小于0的实数） 。 d) :,:,f A B g B C g f →→ 是双射，则 f 是 e) R R f →:，2 1 32)(+= x x f (a)： (b)： (c)： (d)： 16. 某单位装配了30辆汽车，其中15辆有录音机，8辆有空调，6辆有座位调节，三种 设备都有的有2辆，问这三种设备都不具备的汽车至少有 辆？ 17. 设无向图中有6条边，有一个3度结点和一个5度结点，其余结点的度数为2，则该 图的结点数为： 。 二、命题符号化： 18. 李明和王平是大学同学。 19. 不是所有的哺乳动物都是胎生的。 20. 任何一个公式总存在一个与之等价的主析取范式。 21. 有些人对某些药品过敏。 22. 参加考试的人不一定取得好成绩。