《离散数学》双语专业词汇表Abelian group：交换（阿贝尔）群
absorption property：吸收律
acyclic：无（简单）回路的
adjacent vertices：邻接结点
adjacent vertices：邻接结点
adjacent vertices：邻接结点
algorithm verification：算法证明
algorithm：算法
alphabet：字母表
alternating group：交替群
analogous：类似的
analysis of algorithm：算法分析
antisymmetric：反对称的
approach：方法，方式
argument：自变量
associative：可结合的
associative：可结合的
asymmetric：非对称的
backtracking：回溯
base 2 exponential function：以2为底的指数函数
basic step：基础步
biconditional, equivalence：双条件式，等价
bijection, one-to-one correspondence：双射，一一对应
binary operation on a set A：集合A上的二元运算
binary operation：二元运算
binary relation：二元关系
(complete) binary tree：(完全)二元(叉)树
bland meats：未加调料的肉
block, cell：划分块，单元
Boolean algebra：布尔代数
Boolean function：布尔函数
Boolean matrix：布尔矩阵
Boolean polynomial, Boolean expression：布尔多项式（表达式）Boolean product：布尔乘积
bounded lattice：有界格
brace：花括号
bridge：桥，割边
by convention：按常规，按惯例
cancellation property：消去律
capacity：容量
cardinality：基数，势
category：类别，分类
catenation：合并，拼接
ceiling function：上取整函数
certain event：必然事件
characteristic equation：特征方程
characteristic function：特征函数
chromatic number of G：G的色数
chromatic polynomial：着色多项式
circuit design：线路设计
circuit：回路
closed under the operation：运算对…是封闭的
closed with respect to：对…是封闭的
closure：闭包
collision：冲突
coloring graphs：图的着色
column：列
combination：组合
common divisor：公因子
commutative：可交换的
commutative：可交换的
commuter：经常往来于两地的人
comparable：可比较的
compatible with：与…相容
compatible：相容的
complement of B with respect to A：A与B的差集complement：补元
complementary relation：补关系
complete graph：完全图
complete match：完全匹配
complete n-tree：完全n-元树
component sentence：分句
component：分图
composition：复合
composition：关系的复合
compound statement：复合命题
conditional statement, implication：条件式，蕴涵式congruence relation：同余关系
congruent to：与…同余
conjecture：猜想
conjunction：合取
connected：连通的
connected：连通的
connection：连接
connectivity relation：连通性关系consecutively：相继地
consequent, conclusion：结论，后件constructive proof：构造性证明
contain(in)：包含（于）
contingency：可满足式
contradiction, absurdity：永假(矛盾)式contrapositive：逆否命题
conversation of flow：流的守恒converse：逆命题
conversely：相反地
coordinate：坐标
coset：陪集
countable(uncountable)：可数（不可数）counterexample；反例
counting：计数
criteria：标准，准则
custom：惯例
cut：割
cycle：回路
cyclic permutation：循环置换，轮换
de Morgan’s laws：德摩根律declarative sentence：陈述句
degree of a vertex：结点的度
depot：货站，仓库
descendant：后代
diagonal matrix：对角阵
die：骰子
digraph：有向图
dimension：维(数)
direct flight：直飞航班
discipline：学科
disconnected：不连通的
discrete graph(null graph)：零图
disjoint sets：不相交集
disjunction：析取
distance：距离
distinguish：区分
distributive lattice：分配格
distributive：可分配的
distributive：可分配的
division：除法
dodecahedron：正十二面体
domain：定义域
doubly linked list：双向链表
dual：对偶
edge：边
edge：边
element, member：成员，元素
empty relation：空关系
empty sequence(string)：空串
empty set：空集
end point：端点
entry(element)：元素
equally likely：等可能的，等概率的equivalence class：等价类
equivalent relation：等价关系
Euclidian algorithm：欧几里得算法，辗转相除法Euler path(circuit)：欧拉路径(回路)
event：事件
everywhere defined：处处有定义的
excess capacity：增值容量
existence proof：存在性证明
existential quantification：存在量词化
expected value：期望值
explicit：显式的
extensively：广泛地，全面地
extremal element：极值元素
factor：因子
factorial：阶乘
finite (infinite) set：有限（无限）集
finite group：有限（阶）群
floor function：下取整函数
free semigroup generated by A：由A生成的自由半群frequency of occurrence：出现次数(频率) function, mapping, transformation：函数，映射，变换GCD(greatest common divisor)：最大公因子gender：性别
generalize：推广
generic element：任一元素
graduate school：研究生院
graph：(无向)图
graph：无向图
greatest(least) element：最大(小)元
greedy algorithm：贪婪算法
group：群
growth of function：函数增长
Hamiltonian path(circuit)：哈密尔顿路径(回路) hashing function：杂凑函数
Hasse diagram：哈斯图
height：树高
homomorphic image：同态像
homomorphism：同态
hypothesis：假设，前提，前件
idempotent：等幂的
idempotent：幂等的
identity function on A：A上的恒等函数
identity(element)：么（单位）元
identity：么元，单位元
impossible event：不可能事件
inclusion-exclusion principle：容斥原理
in-degree：入度
indirect method：间接证明法
induction step：归纳步
informal brand：不严格的那种
inorder search：中序遍历
intersection：交
intuitively：直觉地
inverse：逆关系
inverse：逆元
inverse：逆元
inverter：反向器
invertible function：可逆函数
involution property：对合律
irreflexive：反自反的
isolated vertex：孤立结点
isomorphism：同构
isomorphism：同构
join：，保联，并
join：并
Karnaugh map：卡诺图
Kernel：同态核
key：键
Klein 4 group：Klein四元群
Konisberg Bridge problem：哥尼斯堡七桥问题Kruskal’s algorithm：Kruskal算法
labeled digraph：标记有向图
lattice：格
LCM(least common multiple)：最小公倍数leaf(leave)：叶结点
least upper(greatest lower) bound：上(下)确界level：层，
lexicographic order：字典序
likelihood：可能性
linear array(list)：线性表
linear graph：线性图
linear homogeneous relation of degree k：k阶线性齐次关系linear order(total order)：线序，全序
linearly ordered set, chain：线（全）序集，链
linked list：链表
linked-list representation：链表表示
logarithm function to the base n：以n为底的对数
logical connective：命题联结词
logically equivalent：（逻辑）等价的
logically follow：是…的逻辑结论
logician：逻辑学家
loop：自回路
lower order：低阶
main diagonal：主对角线
map-coloring problem：地图着色问题
matching function：匹配函数
matching problems：匹配问题
mathematical structure(system)：数学结构（系统）matrix：矩阵
maximal match：最大匹配
maximal(minimal) element：极大(小)元
maximum flow：最大流
meet：保交，交
meet：交
minimal spanning tree：最小生成树
minterm：极小项
modular lattice：模格
modulus：模
modus ponens：肯定律
m odus tollens：否定律
monoid：含么半群，独异点multigraph：多重图
multiple：倍数
multiplication table：运算表
multi-valued function：多值函数mutually exclusive：互斥的，不相交的natural homomorphism：自然同态nearest neighbor：最邻近结点negation：否定（式）
normal subgroup：正规(不变)子群notation：标记
notion：概念
n-tree：n-元树
n-tuple：n-元组
odd(even) permutation：奇（偶）置换offspring：子女结点
one to one：单射，一对一函数onto：到上函数，满射
operation on sets：集合运算
optimal solution：最佳方法
or(and, not) gate：或(与，非)门
order of a group：群的阶
order relation：序关系
ordered pair：有序对，序偶
ordered tree：有序树
ordered triple：有序三元组ordinance：法规
out-degree：出度
parent：父结点
partial order：偏序关系
partially ordered set, poset：偏序集
partition, quotient set：划分，商集
path：路径
path：通路，路径
permutation：置换，排列
pictorially：以图形方式
pigeonhole principle：鸽巢原理
planar graph：(可)平面图
plausible：似乎可能的
pointer：指针
Polish form：（表达式的）波兰表示
polynomial：多项式
positional binary tree：位置二元(叉)树
positional tree：位置树
postorder search：后序遍历
power set：幂集
predicate：谓词
preorder search：前序遍历
prerequisite：预备知识
prescribe：命令，规定
Prim’s algorithm：Prim算法
prime：素（数）
principle of mathematical induction：（第一）数学归纳法probabilistic：概率性的
probability(theory)：概率(论)
product partial order：积偏序
product set, Caretesian set：叉积，笛
product：积
proof by contradiction：反证法
proper coloring：正规着色
propositional function：命题公式
propositional variable：命题变元
pseudocode：伪码（拟码）
pumping station：抽水站
quantifier：量词
quotient group：商群
random access：随机访问
random selection(choose an object at random)：随机选择range：值域
rational number：有理数
reachability relation：可达性关系
reasoning：推理
recreational area：游乐场所
recursive：递归
recycle：回收，再循环
reflexive closure：自反闭包
reflexive：自反的
regular expression：正则表达式
regular graph：正规图，正则图
relation：关系
relationship：关系
relay station：转送站
remainder：余数
representation：表示
restriction：限制
reverse Polish form：（表达式的）逆波兰表示
(left) right coset：(左)右陪集
root：根，根结点
rooted tree：（有）根树
row：行
R-relative set：R相关集
rules of reference：推理规则
running time：运行时间
same order：同阶
sample space：样本空间
semigroup：半群
sensible：有意义的
sensible：有意义的
sequence：序列
sequential access：顺序访问
set corresponding to a sequence：对应于序列的集合set inclusion(containment)：集合包含
set：集合
siblings：兄弟结点
simple cycle：简单回路
simple path(circuit)：基本路径(回路)
simple path：简单路径（通路）
sink：汇
sophisticated：复杂的
source：源
spanning tree：生成树，支撑树
square matrix：方阵
statement, proposition：命题
storage cell：存储单元
string：串，字符串
strong induction：第二数学归纳法
subgraph：子图
subgroup：子群
sublattice：子格
submonoid：子含么半群
subscript：下标
subsemigroup：子半群
subset：子集
substitution：替换
subtree：子树
summarize：总结，概括
symmetric closure：对称闭包
symmetric difference：对称差
symmetric group：对称群
symmetric：对称的
tacitly：默认
tautology：永真(重言)式
tedious：冗长乏味的
terminology：术语
the capacity of a cut：割的容量
topological sorting：拓扑排序
transitive closure：传递闭包
transitive：传递的
transport network：运输网络
transposition：对换
traverse：遍历，周游
tree searching：树的搜索（遍历）
tree：树
truth table：真值表
TSP(traveling salesperson problem)：货郎担问题unary operation：一元运算
undirected edge：无向边
undirected edge：无向边
undirected tree：无向树
union：并
unit element：么(单位)元
universal quantification：全称量词化
universal set：全集
upper(lower) bound：上(下)界value of a flow：流的值
value, image：值，像，应变量
V enn diagram：文氏图verbally：用言语
vertex(vertices)：结点
vertex(vertices)：结点，顶点virtually：几乎
Warshal’s algorithm：Warshall算法weight：权
weight：树
weighted graph：（赋）权图
well-defined：良定，完全确定word：词
zero element：零元
离散数学试题库——填空题 （每空2分） 1 命题: ? ? {{a }} ? {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ . 4. 无孤立点的有限有向图有欧拉路的充分必要条件为: 5.公式))(),(()),()((x S z y R z y x Q x P x →?∨→?的自由变元是 , 约束变元是 . 6.)))()()(()),()(()((x R z Q z y x P y x →?→???的前束范式是 . 7．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶 数） 则 =?B A 。 8．A ，B ，C 。 9．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 10．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 12．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为
则 R= 。 14．图的补图为。15．设A={a，b，c，d} ，A上二元运算如下： 那么代数系统
1.2 逻辑联结词与四种命题 ●知识梳理 1.逻辑联结词 （1）命题：可以判断真假的语句叫做命题. （2）逻辑联结词：“或”“且”“非”这些词叫做逻辑联结词. （3）简单命题与复合命题：不含逻辑联结词的命题叫简单命题；由简单命题和逻辑联结词构成的命题叫做复合命题. （4）真值表：表示命题真假的表叫真值表. 2.四种命题 （1）四种命题 原命题：如果p ，那么q （或若p 则q ）；逆命题：若q 则p ； 否命题：若?p 则?q ；逆否命题：若?q 则?p . （2）四种命题之间的相互关系 这里，原命题与逆否命题，逆命题与否命题是等价命题. ●点击双基 1.由“p :8+7=16，q :π＞3”构成的复合命题，下列判断正确的是 A.p 或q 为真，p 且q 为假，非p 为真 B.p 或q 为假，p 且q 为假，非p 为真 C.p 或q 为真，p 且q 为假，非p 为假 D.p 或q 为假，p 且q 为真，非p 为真 解析：因为p 假，q 真，由复合命题的真值表可以判断，p 或q 为真，p 且q 为假，非p 为真. 答案：A 2.（2004年福建，3）命题p :若a 、b ∈R ，则|a |+|b |＞1是|a +b |＞1的充分而不必要条件； 命题q :函数y =2|1|--x 的定义域是（－∞，－1］∪［3，+∞），则 A.“p 或q ”为假 B.“p 且q ”为真 C. p 真q 假 D. p 假q 真 解析：∵|a +b |≤|a |+|b |， 若|a |+|b |＞1，不能推出|a +b |＞1，而|a +b |＞1，一定有|a |+|b |＞1，故命题p 为假.
离散数学期末考试试卷(A卷) 一、判断题：（每题2分，共10分） （1） （1） （2）对任意的命题公式, 若, 则 （0） （3）设是集合上的等价关系, 是由诱导的上的等价关系，则。（1） （4）任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等价。 （0） （5）设是上的关系，分别表示的对称和传递闭包，则 （0） 二、填空题：（每题2分，共10分） (１) 空集的幂集的幂集为（）。 (２) 写出的对偶式（）。 （３）设是我校本科生全体构成的集合，两位同学等价当且仅当他们在 同一个班，则等价类的个数为（），同学小王所在 的等价类为（）。 （４）设是上的关系，则满足下列性质的哪几条：自反的，对称的，传递的，反自反的，反对称的。 （） (5)写出命题公式的两种等价公式( ）。 三、用命题公式符号化下列命题（１）（２）（３），用谓词公式符号化下列命题（４）（５）（６）。（12分） （１）（１）仅当今晚有时间，我去看电影。 （２）（２）假如上午不下雨，我去看电影，否则就在家里读书。 （3）你能通你能通过考试，除非你不复习。 （４）（４）并非发光的都是金子。 （５）（５）有些男同志，既是教练员，又是国家选手。 （６）（６）有一个数比任何数都大。 四、设，给定上的两个关系和分别是
（１）（１）写出 和 的关系矩阵。（２）求 及 （1２分） 五、求 的主析取范式和主合取范式。（１０分） 六、设 是 到 的关系， 是 到 的关系，证明： （8分） 七、设 是一个等价关系，设 对某一个 ,有 ，证明： 也是一个等价关系。（10分） 八、（1０分）用命题推理理论来论证 下述推证是否有效？ 甲、乙、丙、丁四人参加比赛，如果甲获胜，则乙失败；如果丙获胜，则乙也获 胜，如果甲不获胜，则丁不失败。所以，如果丙获胜，则丁不失败。 九、（１０分） 用谓词推理理论来论证下述推证。 任何人如果他喜欢步行，他就不喜欢乘汽车，每一个人或喜欢乘汽车，或喜欢骑 自行车（可能这两种都喜欢）。有的人不爱骑自行车，因而有的人不爱步行 (论 域是人)。 十、(8分) 利用命题公式求解下列问题。 甲、乙、丙、丁四人参加考试后，有人问他们，谁的成绩最好， 甲说：“不是我，”乙说：“是丁，”丙说：“是乙，” 丁说：“不是我。” 四人的回答只有一人符合实际，问若只有一人成绩最 好，是谁？ 离散数学期末考试试卷答案(A 卷) 一、判断题：（每题2分，共10分） （1）}}{{}{x x x -∈ （ ∨） (2) 对任意的命题公式C B A ,,, 若 C B C A ∧?∧, 则B A ? ( ? ) （3）设R 是集合A 上的等价关系, L 是由 R A 诱导的A 上的等价关系，则L R =。 ( ∨ ) （4） 任意一个命题公式都与某一个只含合取和析取两种联结词的命题公式等 价。 （ ? ） （5）设R 是A 上的关系，)(),(R t R s 分别表示R 的对称和传递闭包，则 )()(R st R ts ? （ ? ） 二、填空题：（每题2分，共10分）
系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷 题 序 一 二 三 四 五 总分 成 绩 签 名 一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}P(A) B ．{a}P(A) C ．{{a}}P(A) D ．{{a}}P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．01 B ．0011100000 C ．00 D ．00 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨q D ．r →p ∨q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ C ） A ．┐(x)A(x)┐A B ．(x)(B →A(x))B →(x)A(x) C ．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D ．(x)(y)(A(x)→B(y))( x)A(x)→(y)B(y) 7、若s={1,2,3,4}，S 上关系R 的关系图为： 则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={
离散数学》双语课程教学大纲 一、课程编号：040510 二、课程类型：必修 课程学时：理论教学 72学时 / 4.5学分。 适用专业：信息与计算科学专业。 先修课程：线性代数、概率论、高等数学等。 后续课程：编译原理、操作系统、数据结构、数据库等。 三、课程性质与任务 《离散数学》是信息与计算科学中基础理论的核心课程。该课程采用双语教学形式，教材是国外原版英语教材。通过本课程的学习，主要培养学生的抽象思维能力、严密的逻辑推理能力、阅读外文科技文献能力和专业英语写作能力。并为学生今后处理离散信息、离散建模、软件开发、计算机硬件系统设计、程序设计的时间和空间复杂度分析等提供理论指导基础，是学生从事信息科学的实际工作必备数学工具。 四、教学主要内容及学时分配
五、教学基本要求 了解离散数学所涵盖的内容及背景思想；理解离散数学组的数学思想和基本概念。掌握离散数学常用的基本方法、手段、技巧，并具备一定的分析论证能力和较强的利用离散数学解决实际问题能力。具体要求有： （1 ）理解子集、空集、全集、集合相等、幂集等基本概念；掌握集合的两种表示法。 （2）熟练掌握集合的交、并、差补运算；能通过文氏图理解与掌握集合的有关运算；了解包含排斥定理及其简单应用。 （3）熟练掌握集合运算的基本定律，并能熟练地应用这些定律证明集合恒等式。（4）掌握逻辑代数的基本理论和方法，理解命题﹑复合命题及真值表的概念，熟练掌握逻辑运算符‘非’﹑‘合取’ ﹑‘析取’﹑‘蕴涵’﹑及 ‘存在’﹑‘任意’等量词的定义及使用；理解条件语句的概念；理解等价。掌握一些常见的逻辑推理方法。
（5）熟练掌握乘法原理﹑加法原理﹑排列﹑组合﹑鸽笼原理及递归式，会用组合计数思想的方法计算简单的古典概率问题。 （6）理解序偶与笛卡尔积的概念；理解 n 元组与 n 个集合笛卡尔集的概念。 深刻理解关系的基本概念；掌握二元关系的关系矩阵与关系图。熟练掌握关系的自反性、对称性、反对称性和传递性四种性质并熟练掌握其求法。 深刻理解二元关系的自反闭包、对称闭包和传递闭包的概念并熟练掌握其求法。熟练掌握等价关系的判定与相关等价类的求法。了解关系的计算机表示﹑关系的运算﹑传递闭包及Warshall算法。 （7）理解映射、满射、单射、双射的概念并熟练掌握其判定方法；了解复合映射与逆映射的概念及求法。 （8）理解有向树，无向树，根数，标定树的定义及性质；掌握极小生成树算法； 了解生成树搜索法。 （9）理解无向图，哈密顿圈及哈密顿路，传输网络，匹配问题，图的着色的定义及性质；掌握欧拉环游及欧拉通路，最大流问题的定义﹑性质及算法。 掌握有关哈密顿图的一些必要和充分条件。 六、对学生课外作业的要求 本课程概念多、比较抽象、定理证明和应用有一定难度，为了学生进一步理解课堂教学内容，拟布置一定数量的课外习题为宜，教师批改作业本的 2/3, 并安排时间上习题课。各章节习题量分布如下： 七、教材及主要参考书
离散数学 一、单项选择题(本大题共7小题，每小题3分，共21分) 1.设p:天下大雨，q:小王乘公共汽车上班，命题“只有天下大雨，小王才乘公共汽车上班”的符号化形式为（） A）p→q B）q→p C）p→┐q D）┐p→q 2.设解释I如下，个体域D={a,b}, F(a,A）=F(b,b)=0,F(a,b)=F(b,A）=1，在解释I 下，下列公式中真值为1的是（) A．VxヨyF(x,y) B. ヨxVyF(x,y) C. VxVyF(x,y) D. ┐ヨxヨyF(x,y) 3．下列命题公式中不．是重言式的是（） A．p→(q→r) B．p→(q→p) C．p→(p→p) D．(p→(q→r))(q→(p→r)) 4. 设个体域是整数集，则下列命题的真值为真的是（） A．y x(x·y=1) B．x y (x·y≠0) C．x y (x·y=y2) D．y x(x·y=x2) 5.永真式的否定是（） (1). 永真式(2). 永假式 (3). 可满足式 (4). (1)--(3)均有可能 6. 设A={1，2，3，4，5}，A上二元关系R={〈1，2〉，〈3，4〉，〈2，2〉}，S={〈2， 4〉，〈3，1〉，〈4，2〉}，则S-1 R-1的运算结果是（） A．{〈4，1〉，〈2，3〉，〈4，2〉} B．{〈2，4〉，〈2，3〉，〈4，2〉} C．{〈4，1〉，〈2，3〉，〈2，4〉} D．{〈2，2〉，〈3，1〉，〈4，4〉} 7. 6阶有限群的任何子群一定不是（）。 (1) 2阶(2) 3 阶 (3) 4 阶(4) 6 阶 二、填空题(每空3分，共18分) 1. 设R是集合A上的等价关系，则R所具有的关系的三个特性是 ____________________. 2 .设P、Q为两个命题，德摩根律可表示为_____________， 吸收律可表示为____________。 3. 设R={<{1},1>，<1,{1}>，<2,{3}>，<{3},{2}>}，则
联结词 ----条件
复合命题是用“联结词”将原子命题联结起来构成的. 归纳自然语言中的联结词，定义了六个逻辑联结词： (1)否定“?” (2)合取“∧” (3) 析取“∨”和异或“” ∨ (4) 条件（蕴涵）“→” (5)双条件（等价）“?”或记做“?”
四.条件 (蕴涵)“→” 表示“如果… 则… ”“只要… 就…”,“若…则…”等. 例： P表示：缺少水分. Q表示：植物会死亡. P→Q：如果缺少水分，植物就会死亡. P→Q：也称之为蕴涵式，读成“P蕴涵Q”，“如果P则Q”. 也说成P是P→Q 的前件，Q是P→Q的后件.还可以说P是Q的充分条件，Q是P的必要条件.
P→Q的真值： P→Q的真值为假，当且仅当P为真，Q为假. 注意：当前件P为假时， P→Q为T.
关于充分条件和必要条件的说明： ?充分条件：就是只要条件成立，结论就成立，则该条件就是充分条件. 上例中，“缺少水分”就是“植物会死亡”的充分条件.在自然语言中表示充分条件的词有：如果…则… ，只要… 就…，若…则… . ?必要条件：就是如果该条件不成立，那么结论就不成立, 则该条件就是必要条件. 上例中，“植物死亡”就是“缺少水分”的必要条件(植物未死亡，一定不缺少水分).在自然语言中表示必要条件的词有 :只有…才… ；仅当…，… ; …, 仅当….
例1令：P：天气好. Q：我去公园. 1).如果天气好，我就去公园. 2).只要天气好，我就去公园. 3).天气好，我就去公园. 4).仅当天气好，我才去公园. 5).只有天气好，我才去公园. 6).我去公园，仅当天气好. 命题1)、2)、3)写成： P→Q . 命题4)、5)、6)写成： Q→P. 可见“→”既表示充分条件（即前件是后件的充分条件）；也表示必要条件（即后件是前件的必要条件）.这一点要 特别注意!!!它决定了哪个作为前件，哪个作为后件.
离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
名师作业练全能 第三讲逻辑联结词与四种命题充要条件班级________ 姓名___________ 考号 __________ 日期__________ 得分___________ 一、选择题：(本大题共6小题，每小题6分，共36分，将正确答案的代号填在题后的 括号内.) 1. (2010天津)命题“若f(x)是奇函数，贝U f(—x)是奇函数”的否命题是() A .若f(x)是偶函数，则f(—x)是偶函数 B ?若f(x)不是奇函数，则f( —x)不是奇函数 C.若f( —x)是奇函数，则f(x)是奇函数 D ?若f( —x)不是奇函数，则f(x)不是奇函数 解析：否命题是既否定题设又否定结论?因此否命题应为“若函数f(x)不是奇函数，则 f(—X)不是奇函数”. 答案：B 2. (2011大庆模拟)若命题p：x€ M U N,则綈p是() A . x?M? N B . x?M 或x?N C. x?M 且x?N D . x€ M n N 解析：x€ M U N, 即卩x€ M 或x€ N, ???綈p：x?M 且x?N. 答案：C 3. (2011北京东城区模拟)已知命题p, q，若p且q为真命题，则必有() A . p真q真 B . p假q假 C. p真q假 D . p假q真 答案：A 4. (2011东城区)设命题p：x>2是X2>4的充要条件，命题q：若字电，则a>b.则( ) A .“ p或q”为真 B .“ P且q”为真 C . p真q假 D . p, q均为假命题 2 2 a b 解析：依题意，由x>2? X2>4，而X2>4D?/X>2，所以命题p是假命题，又由二>二，两C C 边同时乘以c2得a>b，所以命题q正确，所以选择 A. 答案：A 5. 有下列四个命题： ①“若x+ y= 0,则x、y互为相反数”的否命题;
离散数学期末试卷 （计算机科学与技术专业）学院____________学号____________姓名___________成绩____________ 一、判断题（本题共15小题，每小题1分，满分15分） （2）对于任意正确的推理，其命题逻辑的推理形式结构一定是重言蕴涵式。 （3）设G是n个结点的m条边的简单有向连通图，那么n-1≤m≤n(n-1)/2。 （4）设R是非空集合A上的关系，R是反对称关系当且仅当R∩R-1?I A。 （5）设G为无向图，若G中恰有n个结点，n-1条边，则G必为一棵树。 （6）含n（n≥1）个命题变项的公式共有2n个不同的赋值。 （7）设R1和R2是传递的二元关系，则R1?R2也是传递的。 （8）在有限偏序集中，极小元一定存在，但最小元不一定存在。 （9）设G是n（n≥3）阶哈密顿图，则G中任意两个不相邻的顶点的度数之和均不小于n。（10）设A为n元集，R是A上的关系，则存在自然数s和t，使得R s=R t。 （11）公式?x F(x)→(?x?y G(x,y)→?x F(x))是永真式。 （12）设R是任意的关系，则srt(R)一定是等价关系。 （13）若个体域为实数集，F(x,y): x=y，G(x,y): x
9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（ ）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（ ），??x T(x)表示（ ），?x ? T(x)表示（ ），?x(S(x)→P(x))表示（ ），?x(S(x)∧G(x))表示（ ），?x(S(x)∧P(x))表示（ ），?x(S(x)→G(x))表示（ ）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。 二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={
《离散数学》双语专业词汇表 set：集合subset：子集 element, member：成员，元素well-defined：良定，完全确定brace：花括号representation：表示 sensible：有意义的rational number：有理数 empty set：空集Venn diagram：文氏图 contain(in)：包含（于）universal set：全集 finite (infinite) set：有限（无限）集cardinality：基数，势 power set：幂集operation on sets：集合运算 disjoint sets：不相交集intersection：交 union：并complement of B with respect to A：A与B的差集symmetric difference：对称差commutative：可交换的associative：可结合的distributive：可分配的idempotent：等幂的de Morgan’s laws：德摩根律 inclusion-exclusion principle：容斥原理sequence：序列 subscript：下标recursive：递归 explicit：显式的string：串，字符串 set corresponding to a sequence：对应于序列的集合 linear array(list)：线性表characteristic function：特征函数countable(uncountable)：可数（不可数）alphabet：字母表 word：词empty sequence(string)：空串 catenation：合并，拼接regular expression：正则表达式division：除法multiple：倍数prime：素（数） algorithm：算法common divisor：公因子 GCD(greatest common divisor)：最大公因子 LCM(least common multiple)：最小公倍数 Euclidian algorithm：欧几里得算法，辗转相除法 pseudocode：伪码（拟码）matrix：矩阵square matrix：方阵 row：行column：列 entry(element)：元素diagonal matrix：对角阵
《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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），（5），（6） 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。
《离散数学》双语教学第一章真值表，逻辑和证明《离散数学》双语教学第一章真值表，逻辑和证明 CHAPTER 1 TRUTH TABLES, LOGIC, AND PROOFS Glossary statement, proposition:命题 logical connective:命题联结词 compound statement:复合命题 propositional variable:命题变元 negation:否定(式) truth table:真值表 conjunction:合取 disjunction:析取 propositional function:命题公式fallacy: 谬误 syllogism:三段论 universal quantification:全称量词化 existential quantification:存在量词化 hypothesis(premise): 假设～前提～前件 conditional statement, implication:条件式～蕴涵式 consequent, conclusion:结论～后件 converse:逆命题 contrapositive:逆否命题 biconditional, equivalence:双条件式～等价 (逻辑)等价的 logically equivalent: contingency:可满足式 tautology:永真式(重言式) contradiction, absurdity:永假(矛盾)式 logically follow:是…的逻辑结论 argument:论证
axioms:公理 第 1 页共 47 页 2010-12-27 《离散数学》双语教学第一章真值表，逻辑和证明 postulate:公设 rules of reference:推理规则 modus ponens:肯定律 modus tollens:否定律 reductio ad absurdum:归谬律 proof by contradiction:反证法 counterexample:反例 minterm:极小项 disjunctive normal form:主析取范式 maxterm:极大项 conjunctive normal form:主合取范式 第 2 页共 47 页 2010-12-27 《离散数学》双语教学第一章真值表，逻辑和证明 本章内容及教学要点: 1.1 Statements and Connectives 教学内容:statements(propositions)～compound statement～ connectives:negation～conjunction～disjunction～truth tables 1.2 Conditional Statements 教学内容:implications(conditional statements)～biconditional～equivalent～and quantifications 1.3 Equivalent Statements 教学内容:logical equivalence～converse～inverse～contrapositive～tautology～contradiction(absurdity)～contingency～properties of logical connectives
第2章谓词逻辑 一、教学要求 1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。 2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。 3. 掌握谓词演算的等值式和重言蕴含式(六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词∨，∧，→的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。 4. 了解前束范式的概念，会求公式的前束范式。 5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则) 本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。 二、学习辅导 在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如 “凡人要死，张三是人，张三要死” 显然是正确推理. 用命题逻辑解释三段式. 设 P：人要死；Q张三是人；R：张三要死。 表示成复合命题有 P∧Q→R 这不是重言式，即R不是前提P，Q的有效结论. 这反映了命题逻辑的局限性，其原因是把本来有内在联系的命题P，Q，R，视为独立的命题。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。 1. 谓词与量词 学习这一部分要反复理解谓词和量词引入的意义，概念的含义。 在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。例如 (1)(1)ln5是无理数； (2)(2)高可比李木相高4cm； (3) 郑州位于北京和广州之间。 这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“……比……高4cm”，“……位于……和……之间”等都是谓词。 个体词分个体常项(用a,b,c,d,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表
常用逻辑用语与充要条件 【高考考情解读】 1.本讲在高考中主要考查集合的运算、充要条件的判定、含有一个量词的命题的真假判断与否定，常与函数、不等式、三角函数、立体几何、解析几何、数列等知识综合在一起考查.2.试题以选择题、填空题方式呈现，考查的基础知识和基本技能，题目难度中等偏下． 1．命题的定义 用语言、符号或式子表达的，可以判断真假的陈述句叫做命题．其中判断为真的语句叫真命题，判断为假的语句叫假命题． 2．四种命题及其关系 (1)原命题为“若p则q”，则它的逆命题为若q则p ；否命题为若┐p则┐q ；逆否命题为若┐q则┐p . (2)原命题与它的逆否命题等价；逆命题与它的否命题等价．四种命题中原命题与逆否命题同真同假，逆命题与否命题同真同假，遇到复杂问题正面解决困难的，采用转化为反面情况处理，即，可以转化为判断它的逆否命题的真假． 命题真假判断的方法： (1)对于一些简单命题，若判断其为真命题需推理证明．若判断其为假命题只需举出一个反例． (2)对于复合命题的真假判断应利用真值表． (3)也可以利用“互为逆否命题”的等价性，判断其逆否命题的真假． 3．充分条件与必要条件的定义 (1)若p?q且q p，则p是q的充分非必要条件． (2)若q?p且p q，则p是q的必要非充分条件． (3)若p?q且q?p，则p是q的充要条件． (4)若p q且q p，则p是q的非充分非必要条件． 设集合A＝{x|x满足条件p}，B＝{x|x满足条件q}，则有
(1)若A?B，则p是q的充分条件，若A?B，则p是q的充分不必要条件； (2)若B?A，则p是q的必要条件，若B?A，则p是q的必要不充分条件； (3)若A＝B，则p是q的充要条件； (4)若A B，且B A，则p是q的既不充分也不必要条件． 2．充分、必要条件的判定方法 (1)定义法，直接判断若p则q、若q则p的真假． (2)传递法． (3)集合法：若p以集合A的形式出现，q以集合B的形式出现，即A＝{x|p(x)}，B＝{x|q(x)}，则①若A?B，则p是q的充分条件；②若B?A，则p是q的必要条件；③若A＝B，则p是q 的充要条件． (4)等价命题法：利用A?B与┐B?┐A，B?A与┐A?┐B，A?B与┐B?┐A的等价关系，对于条件或结论是否定式的命题，一般运用等价法，利用原命题和逆否命题是等价的这个结论，有时可以准确快捷地得出结果，是反证法的理论基础． 1．简单的逻辑联结词 (1)命题中的“且”、“或”、“非”叫作逻辑联结词． (2)简单复合命题的真值表： p q ┐p ┐q p或q p且 q ┐(p或q) ┐(p且 q) ┐p或 ┐q ┐p且 ┐q 真真假假真真假假假假 真假假真真假假真真假 假真真假真假假真真假 假假真真假假真真真真 2. 全称量词与存在量词 (1)常见的全称量词有“任意一个”“一切”“每一个”“任给”“所有的”等． (2)常见的存在量词有“存在一个”“至少有一个”“有些”“有一个”“某个”“有 的”等． 3．全称命题与特称命题 (1)含有全称量词的命题叫全称命题． (2)含有存在量词的命题叫特称命题． 4．命题的否定 (1)全称命题的否定是特称命题；特称命题的否定是全称命题．
离散数学在计算机学科中的应用 离散数学是计算机学科中许多专业课程的先行课程，离散数学和后续课程的关系密切，它是计算机科学与技术应用与研究的有力工具，在计算机科学中应用非常广泛。 离散数学是计算机科学与技术专业许多课程，如《数据结构》、《数据库原理》、《数字逻辑》、《软件工程》、《计算机网络》、《信息安全》、《计算机图形学》、《计算机体系结构》、《算法设计与分析》、《人工智能》等必不可少的先行课程。其中《数据结构》、《数据库原理》、《计算机网络》是所有计算机专业的必修基础课程。（课程与计算机体系见附表） 离散数学与数据结构的关系 离散数学与数据结构的关系非常紧密，数据结构课程描述的的对象有四种，分别是线形结构、集合、树形结构和图结构，这些对象都是离散数学研究的内容。线形结构中的线形表、栈、队列等都是根据数据元素之间关系的不同而建立的对象，离散数学中的关系这一章就是研究有关元素之间的不同关系的内容；数据结构中的集合对象以及集合的各种运算都是离散数学中集合论研究的内容；离散数学中的树和图论的内容为数据结构中的树形结构对象和图结构对象的研究提供了很好的知识基础。
目前数据库原理主要研究的数据库类型是关系数据库。关系数据库中的关系演算和关系模型需要用到离散数学中的谓词逻辑的知识；关系数据库的逻辑结构是由行和列构成的二维表，表之间的连接操作需要用到离散数学中的笛卡儿积的知识，表数据的查询、插入、删除和修改等操作都需要用到离散数学中的关系代数理论和数理逻辑中的知识。 命题逻辑中的联结词广泛应用在大量信息的检索、逻辑运算和位运算中，例如目前大部分网页检索引擎都支持布尔检索，使用NOT、AND、OR等联结词进行检索有助于快速找到特定主题的网页；信息在计算机内都表示为0或1构成的位串，通过对位串的运算可以对信息进行处理，计算机字位的运算与逻辑中的联结词的运算规则是一致的，掌握了联结词的运算为计算机信息的处理提供了很好的知识基础。在计算机硬件设计中，使用了联结词完备集中的与非和或非，使用与非门和或非门设计逻辑线路，替代了之前的非门、与门和或门的组合，优化了逻辑线路。 谓词逻辑可以表示关系模型中的关系操作[4]，用谓词逻辑表示关系操作的关系演算形式是：{s[<属性表>]│R(s)}，其中R(s)指的是s用该满足的谓词，例如要查询不及格的女同学的名字，关系演算的表达式为：{s