离散数学
计算机专业通知：计算机资料就是同学们网上学习的阶段测试和简答练习等资料，请同学们打印下来复习，如有新的资料更新会通知大家！（以下资料只是网上一部分）
离散数学
一、单项选择题
1、（p∨(q∧r)）→(p∧q∧r)的主析取范式是：（B ）
A. ∑(0,1)
B. ∑(0,1,7)
C. ∑(0,7)
D. ∑(1,7)
2、下列是真命题的是（A ）
A. 2是素数
B. 2+3=6
C. 雪是黑色的
D. 3能被2整除
3、设P：我们划船，Q：我们跳舞，命题“我们不能既划船又跳舞”符号化为（B ）
A. P Q
B. ┐（P∧Q）
C. ┐P∧┐Q
D. ┐P∧Q
4、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式 x(P(x)Q(x))在哪个个体域中为真
(A)
A. 自然数
B. 实数
C. 复数
D. 前面三者均成立
5、当P的真值是1,Q的真值是1 R的真值是0，下列复合命题中真值为0的是（D ）
A. （PvQ）→R
B. R→(P ? Q)
C. (PvR) →Q
D. (P ?R)??Q
6、设A=｛1，2，3｝，则下列说法正确的是（C ）
A. R={<1,1>，<2，2>，<3，3>，<1,2>}在A上是反自反的
B. R=｛<2，3>，<3，2>｝在A上是自反的
C. R=｛<1，2>，<2，1>，<3，3>在A上是对称的
D. R={<1，2>，<1，3>}在A上是对称的
7、下面关于集合的表示中，正确的是(B )．
A. φ＝0
B. φ∈{φ}
C. φ∈φ
D. φ∈{a，b}
8、设A={?}，B=P（P（A）），以下不正确的式子是（）（分数：1分）
A. ．{{? }，{{? }}，{?，{? }}}包含于B
B. {{{? }}}包含于B
C. {{?，{? }}}包括于B
D. {{? }，{{?，{? }}}}包含于B
标准答案是：D。您的答案是：
9、六阶群的子群的阶数可以是（）。（分数：1分）
A. 1，2，5
B. 2，4
C. 3，6，7
D. 2，3
标准答案是：D。您的答案是：
10、设G是n个结点、m条边和r个面的连通平面图，则m等于（）。（分数：1分）
A. n+r-2
B. n-r+2
C. n-r-2
D. n+r+2
标准答案是：A。您的答案是：
11、若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ). （分数：1分）
A. (1,2,2,3,4,5)
B. (1,2,3,4,5,5)
C. (1,1,1,2,3)
D. (2,3,3,4,5,6)
标准答案是：C。您的答案是：
12、有向图G是单向连通图，当且仅当( ) （分数：1分）
A. 图G中至少有一条通路
B. 图G中有通过每个顶点至少一次的通路
C. 图G的连通分枝数为一
D. 图G中有通过每个顶点至少一次的回路
标准答案是：B。您的答案是：
13、下面给出的符号串集合中，哪一个是前缀码？（）（分数：1分）
A. {1, 01, 001, 000}
B. {1, 11, 101, 001, 0011}
C. {b, c, aa, bc, aba}
D. {b, c, a, aa, ac, abb}
标准答案是：A。您的答案是：
14、无向图G是欧拉图，当且仅当（）（分数：1分）
A. G的所有结点的度数全为偶数。
B. G中所有结点的度数全为奇数。
C. G连通且所有结点度数全为奇数
D. G连通且所有结点度数全为偶数
标准答案是：D。您的答案是：
15、设Ｇ是具有n个结点的无向简单图，若在Ｇ中存在一条汉密尔顿路，则Ｇ中每一对结点的度数之和与n-1的关系为（）（分数：1分）
A. 大于
B. 大于等于
C. 等于
D. 小于
标准答案是：B。您的答案是
一、单项选择题
1、下列公式中不属于逻辑有效式的是（）。（分数：1分）
A. ?x F(x)→?x F(x)
B. ?x F(x)→(?x?y G(x,y)→?x F(x))
C. ?x F(x)→(?x F(x)∨?y G(y))
D. ?(F(x,y)→R(x,y))∧R(x,y)
标准答案是：D。您的答案是：B
2、命题公式（P∧Q）的成真指派是（）（分数：1分）
A. 000，001，110
B. 001，011，101，110，111
C. 全体指派
D. 无
标准答案是：D。您的答案是：
3、下面哪一个命题是假命题（）（分数：1分）
A. 如果2是偶数，那么一个公式的析取范式唯一
B. 如果2是偶数，那么一个公式的析取范式不唯一
C. 如果2是奇数，那么一个公式的析取范式唯一
D. 如果2是奇数，那么一个公式的析取范式不唯一
标准答案是：A。您的答案是：
4、谓词公式( x)(P(x,y))→( z)Q(x,z)∧( y)R(x,y)中变元x( ) （分数：1分）
A. 是自由变元但不是约束变元
B. 既不是自由变元又不是约束变元
C. 既是自由变元又是约束变元
D. 是约束变元但不是自由变元
标准答案是：C。您的答案是：
5、集合A={1,2,…,10}上的关系R={|x+y=10,x,y A}，则R 的性质为（）。（分数：1分）
A. 自反的
B. 对称的
C. 传递的，对称的
D. 传递的
标准答案是：B。您的答案是：
6、设 A ={1，2，3，4}，A 上的二元关系 R ={〈x，y〉︱（x-y）能被3整除}，则自然映射 g：A→A/R使 g(1) = ( ) （分数：1分）
A. ｛1,2｝
B. ｛1,3｝
C. ｛1,4｝
D. ｛1｝
标准答案是：C。您的答案是：
7、在实数集合R上，下列定义的运算中不可结合的是（）（分数：1分）
A. a*b=a+b+2ab
B. a*b=a+b
C. a*b=a+b+ab
D. a*b=a-b
标准答案是：D。您的答案是：
8、设集合A={a,b,c},B={β,ε,θ},则从A到B最多可以定义多少个双射函数( ) （分数：1分）
A. 27
B. 9
C. 8
D. 6
标准答案是：D。您的答案是：
9、设A={a,b,c}，A上二元关系R={〈a,a〉，〈b,b〉,〈a,c〉}，则关系R的对称闭包S(R)是( ) （分数：1分）
A. R∪IA
B. R
C. R∪{〈c,a〉}
D. R∩IA
标准答案是：C。您的答案是：
10、下面给出的集合中，哪一个不是前缀码( )。（分数：1分）
A. {a，ab，110，a1b11}
B. {01，001，000，1}
C. {1，2，00，01，0210}
D. {12，11，101，002，0011}
标准答案是：A。您的答案是：
11、设D=为有向图，V={a,，b，c，d，e，f},E={,,,,}是（）（分数：1分）
A. 强连通图
B. 单向连通图
C. 弱连通图
D. 不连通图
标准答案是：D。您的答案是：
12、设G是一棵树,则G 的生成树有( )棵. （分数：1分）
A. 0
B. 1
C. 2
D. 不能确定
标准答案是：B。您的答案是：
13、设i是虚数，?是复数乘法运算，则G=<{1,-1,i,-i},?>是群，下列是G的子群是( ) （分数：1分）
A. <{1},?>
B. 〈{-1},?〉
C. 〈{i},?〉
D. 〈{-i},?〉
标准答案是：A。您的答案是：14、设X={a,b,c},Ix是X上恒等关系，要使Ix∪{〈a,b〉，〈b,c〉，〈c,a〉，〈b,a〉}
∪R为X上的等价关系，R应取( ) （分数：1分）
A. ｛〈c,a〉，〈a,c〉｝
B. {〈c,b〉，〈b,a〉}
C. {〈c,a〉，〈b,a〉}
D. {〈a,c〉，〈c,b〉}
标准答案是：D。您的答案是：
15、下列集合对所给的运算是封闭的只有（）（分数：1分）
A. 非零整数集合Z*上的除法运算
B. 全体n×n实可逆矩阵集合Mn（R）上的矩阵加法和乘法运算
C. 全体n×n实矩阵集合Mn（R）上的矩阵加法和乘法运算
D. A={1，2，…，10}，x*y=LCM（x，y），即x，y最小公倍数
标准答案是：C。您的答案是：
一、单项选择题
1、下列语句中是真命题的是（）（分数：1分）
A. 我正在说谎
B. 严禁吸烟
C. 如果1+2=3，那么雪是黑的
D. 如果1+2=5，那么雪是黑的
标准答案是：D。您的答案是：B
2、下列公式类型属于重言式的是（）。（分数：1分）
A. q∨?((?p∨q)∧p)
B. (p∨?p)→((q∧?q)∧r)
C. (p→q)∧?p
D. ?(p→q)∧q
标准答案是：A。您的答案是：
3、设个体域A={a、b}，公式在A上消去量词应为（）（分数：1分）
A. P(x)∧S(x)
B. P(a)∧P(b)∧S(a)∨S(b)
C. P(a)∧S(b)
D. P(a)∧P(b)∧(S(a)∨S(b))
标准答案是：D。您的答案是：
4、若A-B=Ф，则下列哪个结论不可能正确？( ) （分数：1分）
A. A=Ф
B. B=Ф
C. A＝B
D. A B
标准答案是：D。您的答案是：5、设A={?}，B=P(P(A))，以下正确的式子是（）（分数：1分）
A. {?,{?}}∈B
B. {{?,?}}∈B
C. {{?},{{?}}}∈B
D. {?,{{?}}}∈B
标准答案是：A。您的答案是：
6、下列定律正确的是（）（分数：1分）
A. A的补集的补集=A
B. A∪φ=φ
C. A∩φ=A
D. A∪(A的补集)=φ
标准答案是：A。您的答案是：
7、S={0，1}，*为普通乘法，则< S , * >是（）。（分数：1分）
A. 半群，但不是独异点
B. 只是独异点，但不是群
C. 群
D. 环，但不是群
标准答案是：B。您的答案是：
8、下列关系中哪一个是集合A={a,b,c,d,e,f}上偏序关系？（）（分数：1分）
A. {,,}∪IA
B. {,,}∪IA
C. {,,}∪IA
D. {,,,}∪IA
标准答案是：B。您的答案是：
9、在实数集合R上，下列定义的运算中不可结合的是（）（分数：1分）
A. a*b=a+b+2ab
B. a*b=a+b
C. a*b=a+b+ab
D. a*b=a-b
标准答案是：D。您的答案是：
10、设有代数系统G=〈A，*〉，其中A是所有命题公式的集合，*为命题公式的合取运算，则G的幺元是（）（分数：1分）
A. 矛盾式
B. 重言式
C. 可满足
D. 公式p∧q
标准答案是：B。您的答案是：
11、 2 类型单选题目给定下列各序列：①（2，2，2，2，2）②（1，1，2，2，3）
③（1，1，2，2，2）④（0，1，3，3，3）⑤（1，3，4，4，5）以上5组数中，可以构成无向简单图的度数序列的是（）（分数：1分）
A. ①③④
B. ①③
C. ①②
D. ③④⑤
标准答案是：B。您的答案是：
12、图G和G’的结点和边分别存在——对应关系是（同构）的（）（分数：1分）
A. 充分条件
B. 充分必要条件
C. 必要条件
D. 既不充分也不必要条件
标准答案是：B。您的答案是：
13、下面哪一种图不一定是树。（）（分数：1分）
A. 有n个顶点n—1条边的连通图
B. 无回路的连通图
C. 连通但删去一条边则不连通的图
D. 每对结点间都有路的图
标准答案是：D。您的答案是：
14、有向图G是强连通图，当且仅当( ) （分数：1分）
A. 图G中至少有一条通路
B. 图G中有通过每个顶点至少一次的通路
C. 图G中至少有一条回路
D. 图G中有通过每个顶点至少一次的回路
标准答案是：D。您的答案是：
15、设连通平面图Ｇ，共有n个结点，e条边，r个面，则欧拉证明成立的公式是（）（分数：1分）
A. e-n+r=2
B. n+r-e=2
C. n-r+e=2
D. n-e-r=2
标准答案是：B。您的答案是：
一、单项选择题
1、令p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）（分数：1分）
A. p∧┐q
B. p∨┐q
C. p∧q
D. p→┐q
标准答案是：A。您的答案是：A 2、下列句子是命题的是（）（分数：1分）
A. 6是奇数
B. 请小心！
C. 试题难吗？
D. 我在讲假话
标准答案是：A。您的答案是：
3、设S(x): x是三好学生, a:张三, b: 李四, 命题“张三是三好学生而李四不是”符号化为（）（分数：1分）
A. S（a），?S（b）
B. S（a）∨?S（b）
C. S（a）∨?S（b）
D. S（a）∧?S（b）
标准答案是：D。您的答案是：
4、设R，S是集合A上的关系，则下列说法正确的是（）（分数：1分）
A. 若R，S 是自反的，则是自反的；
B. 若R，S 是反自反的，则是反自反的；
C. 若R，S 是对称的，则是对称的；
D. 若R，S 是传递的，则是传递的。
标准答案是：A。您的答案是：
5、集合A＝{1,2,3，4，5，6，7，8，9，10}，A上的整除关系是一个偏序关系，则元素10是集合的（）．（分数：1分）
A. 最大元
B. 最小元
C. 极大元
D. 极小元
标准答案是：C。您的答案是：
6、设S={1，2，…，10 }，则下面定义的运算*关于S非封闭的有（）（分数：1分）
A. x*y=max(x ,y)
B. x*y=min(x ,y)
C. x*y=取其最大公约数
D. x*y= 取其最小公倍数
标准答案是：D。您的答案是：
7、6阶群的任何非平凡子群一定不是（）。（分数：1分）
A. 2阶
B. 4阶
C. 3阶
D. 6阶
标准答案是：B。您的答案是：
8、给定下列各序列：①（2，2，2，2，2）②（1，1，2，2，3）③ (1,1,2,2,2) ④(0,1,3,3,3) 哪些可以构成无向简单图的度数序列：( ) （分数：1分）
A. ①②
B. ②④
C. ①③
D. ③④
标准答案是：C。您的答案是：
9、G=是简单有向图，可达矩阵P（G）刻划下列哪种关系（）（分数：1分）
A. 点与点
B. 点与边
C. 边与点
D. 边与边
标准答案是：A。您的答案是：
10、设G=为（n, m）连通图，则要确定G的一棵生成树必删去G中边数为（）（分数：1分）
A. n－m+1
B. n－m－1
C. m－n+1
D. m－n－1
标准答案是：C。您的答案是：
11、有3条边的互不同构的4阶无向简单图的个数为（）（分数：1分）
A. 2
B. 3
C. 4
D. 5
标准答案是：A。您的答案是：
12、下列语句中不是命题的只有（）（分数：1分）
A. 鸡毛也能飞上天？
B. 或重于泰山，或轻于鸿毛。
C. 不经一事，不长一智
D. 牙好，胃口就好
标准答案是：A。您的答案是：
13、下列集合对所给的二元运算封闭的是（）（分数：1分）
A. 正整数集上的减法运算
B. 在正实数的集R+上规定*为a*b=ab-a-b a,b∈R+
C. 正整数集Z+上的二元运算*为x*y=min(x,y) x,y∈Z+
D. 全体n×n实可逆矩阵集合Rn×n上的矩阵加法
标准答案是：C。您的答案是：
14、设集合A={1，2，3}，下列关系R中不是等价关系的是（）（分数：1分）
A. R={<1,1>,<2,2>,<3,3>}
B. R={<1,1>,<2,2>,<3,3>,<3,2>,<2,3>}
C. R={<1,1>,<2,2>,<3,3>,<1,2>}
D. R={<1,1>,<2,2>,<3,3>,<1,2>,<2,1>,<1,3>,<3,1>,<2,3>,<3,2>}
15、设D的结点数大于1，D=是强连通图，当且仅当（）（分数：1分）
A. D中至少有一条通路
B. D中至少有一条回路
C. D中有通过每个结点至少一次的通路
D. D中有通过每个结点至少一次的回路
标准答案是：D。您的答案是：
一、单项选择题
1、下列语句中是命题的只有（）（分数：1分）
A. 1+1=10
B. x+y=10
C. sinx+siny<0
D. x mod 3=2
标准答案是：A。您的答案是：B
2、使命题公式p→(p∧q)为假的赋值是 ( ) （分数：1分）
A. 10
B. 01
C. 00
D. 11
标准答案是：A。您的答案是：
3、设A={{1,2,3}, {4,5}, {6,7,8}}，下列哪个式子为真（）（分数：1分）
A. 1∈A
B. {1,2,3}?A
C. {{4,5}}?A
D. A
标准答案是：C。您的答案是：
4、设集合A = {1,2,3,4}, A上的关系R＝{(1,1),(2,3),(2,4),(3,4)}, 则R具有( )。（分数：1分）
A. 自反性
B. 传递性
C. 对称性
D. 以上答案都不对
标准答案是：B。您的答案是：
5、下列定义错误的是（）（分数：1分）
A. A∪B={x|x∈A∨x∈B}
B. A∩B={x|x∈A∨x∈B}
C. A-B={x|x∈A∧x不属于B}
D. A的补集={x|x不属于A}
6、设S=Q×Q,其中Q为有理数的集合，定义S上的二元运算*，〈a,b〉*〈x,y〉=〈ax,ay+b〉,则〈S,*〉是:( ) （分数：1分）
A. 可交换的
B. 可结合的
C. 不是可交换的，也不是可结合的
D. 可结合，也可交换
标准答案是：B。您的答案是：
7、集合A上的关系R是偏序关系的必要条件是（）（分数：1分）
A. 自反的，反对称的和传递的
B. 自反的和对称的
C. 传递和和对称的
D. 传递的和反对称的
标准答案是：A。您的答案是：
8、下列集合关于所给定的运算成为群的是（）（分数：1分）
A. 已给实数a的正整数次幂的全体，且a属于 {0，1，-1}，关于数的乘法
B. 所有非负整数的集合，关于数的加法
C. 所有正有理数的集合，关于数的乘法
D. 实数集，关于数的除法
标准答案是：C。您的答案是：
9、在自然数集合上，下列那种运算是可结合的( ) （分数：1分）
A. x*y = max(x,y)
B. x*y = 2x+y
C. x*y = x2+y2
D. x*y =︱x-y︱
标准答案是：A。您的答案是：
10、若供选择答案中的数值表示一个简单图中各个顶点的度，能画出图的是( ). （分数：1分）
A. (1,2,2,3,4,5)
B. (1,2,3,4,5,5)
C. (1,1,1,2,3)
D. (2,3,3,4,5,6).
标准答案是：C。您的答案是：
11、设图G是有6个顶点的连通图，总度数为20，则从G中删去多少条边使之变成树？（）（分数：1分）
A. 10
B. 5
C. 3
D. 2
12、设G是连通平面图，G中有6个顶点8条边，则G的面的数目是（）（分数：1分）
A. 2个面
B. 3个面
C. 4个面
D. 5个面
标准答案是：C。您的答案是：
13、设A（G）是有向图G=（V，E）的邻接矩接，其中第i行中值为1的元素数目为（）（分数：1分）
A. 结点Vi的入度
B. 结点Vi的出度
C. 结点Vi的度数
D. 结点Vj的度数
标准答案是：B。您的答案是：
14、下列命题为假命题的是（）（分数：1分）
A. 如果2是偶数，那么一个公式的析取范式惟一
B. 如果2是偶数，那么一个公式的析取范式不惟一
C. 如果2是奇数，那么一个公式的析取范式惟一
D. 如果2是奇数，那么一个公式的析取范式不惟一
标准答案是：A。您的答案是：
15、下列不一定是树的是（）（分数：1分）
A. 无回路的连通图
B. 有n个结点，n-1条边的连通图
C. 每对结点之间都有通路的图
D. 连通但删去一条边则不连通的图
标准答案是：C。您的答案是：简答：
证明题：
离散数学论文
浅论离散数学的实际应用 摘要： 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用：数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。 关键字：离散数学、电路设计、软件技术、应用 1.什么是离散数学 1.1简介 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。1.2离散数学的内容 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。 2.离散数学在门电路设计中的应用 2.1 逻辑门的概念 逻辑门是集成电路中的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假”
《离散数学》-教案.doc
《离散数学》教案 第一章集合与关系 集合是数学中最基本的概念，又是数学各分支、自然科学及社会科学各领域的最普 遍采用的描述工具。集合论是离散数学的重要组成部分，是现代数学中占有独特地位的 一个分支。 G. Cantor( 康脱 ) 是作为数学分支的集合论的奠基人。1870 年前后，他关于无穷序列的研究导致集合论的系统发展。 1874 年他发表了关于实数集合不能与自然数集合建立 一一对应的有名的证明。 1878 年，他引进了两个集合具有相等的“势”的概念。然 而，朴素集合论中包含着悖论。第一个悖论是布拉利 - 福尔蒂的最大序数悖论。 1901 年罗素发现了有名的罗素悖论。 1932 年康脱也发表了关于最大基数的悖论。集合论的现代公理化开始于1908 年策梅罗所发表的一组公理，经过弗兰克尔的加工，这个系统称 为策梅罗 - 弗兰克尔集合论（ ZF），其中包括 1904 年策梅罗引入的选择公理。另外一种系 统是冯·诺伊曼 - 伯奈斯 - 哥德尔集合论。公理集合论中一个有名的猜想是连续统假设（CH）。哥德尔证明了连续统假设与策梅罗 - 弗兰克尔集合论的相容性，科恩证明了连续统假设与策梅罗 - 弗兰克尔集合论的独立性。现在把策梅罗 - 弗兰克尔集合论与选择公理一起称为 ZFC系统。 一、学习目的与要求 本章目的是介绍集合的基本概念，讲授集合运算的基本理论，关系的定义与运算。 通过本章的学习，使学生了解集合是数学的基本语言，掌握主要的集合运算方法和关系运 算方法，为学习后续章节打下良好基础。 二、知识点 1．集合的基本概念与表示方法； 2．集合的运算； 3．序偶与笛卡尔积； 4．关系及其表示、关系矩阵、关系图； 5．关系的性质，符合关系、逆关系； 6．关系的闭包运算； 7．集合的划分与覆盖、等价关系与等价类；相容关系； 8．序关系、偏序集、哈斯图。
离散数学作业
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学期末试题
离散数学考试试题（A 卷及答案） 一、（10分）求(P ↓Q )→(P ∧?(Q ∨?R ))的主析取范式 解：(P ↓Q )→(P ∧?(Q ∨?R ))??(?( P ∨Q ))∨(P ∧?Q ∧R )) ?(P ∨Q )∨(P ∧?Q ∧R )) ?(P ∨Q ∨P )∧(P ∨Q ∨?Q )∧(P ∨Q ∨R ) ?(P ∨Q )∧(P ∨Q ∨R ) ?(P ∨Q ∨(R ∧?R ))∧(P ∨Q ∨R ) ?(P ∨Q ∨R )∧(P ∨Q ∨?R )∧(P ∨Q ∨R ) ?0M ∧1M ?2m ∨3m ∨4m ∨5m ∨6m ∨7m 二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断： 甲说：王教授不是苏州人，是上海人。 乙说：王教授不是上海人，是苏州人。 丙说：王教授既不是上海人，也不是杭州人。 王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？ 解 设设P ：王教授是苏州人；Q ：王教授是上海人；R ：王教授是杭州人。则根据题意应有： 甲：?P ∧Q 乙：?Q ∧P 丙：?Q ∧?R 王教授只可能是其中一个城市的人或者3个城市都不是。所以，丙至少说对了一半。因此，可得甲或乙必有一人全错了。又因为，若甲全错了，则有?Q ∧P ，因此，乙全对。同理，乙全错则甲全对。所以丙必是一对一错。故王教授的话符号化为： ((?P ∧Q )∧((Q ∧?R )∨(?Q ∧R )))∨((?Q ∧P )∧(?Q ∧R )) ?(?P ∧Q ∧Q ∧?R )∨(?P ∧Q ∧?Q ∧R )∨(?Q ∧P ∧?Q ∧R ) ?(?P ∧Q ∧?R )∨(P ∧?Q ∧R ) ??P ∧Q ∧?R ?T 因此，王教授是上海人。 三、（10分）证明tsr (R )是包含R 的且具有自反性、对称性和传递性的最小关系。 证明 设R 是非空集合A 上的二元关系，则tsr (R )是包含R 的且具有自反性、对称性和传递性的关系。 若'R 是包含R 的且具有自反性、对称性和传递性的任意关系，则由闭包的定义知r (R )?' R 。则sr (R )?s ('R )＝'R ，进而有tsr (R )?t ('R )＝'R 。
离散数学(大作业)与答案
一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>}
{<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(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。
离散数学作业(2)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
离散数学期末试题及答案完整版
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
离散数学教案
学习目标： 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 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
离散数学期末试卷A卷及答案
《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???.
2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？
离散数学作业
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
离散数学期末试卷及答案
一．判断题（共10小题，每题1分，共10分） 在各题末尾的括号内画 表示正确，画 表示错误： 1．设p、q为任意命题公式，则(p∧q)∨p ? p ( ) 2．?x(F(y)→G(x)) ? F(y)→?xG(x)。( ) 3．初级回路一定是简单回路。( ) 4．自然映射是双射。( ) 5．对于给定的集合及其上的二元运算，可逆元素的逆元是唯一的。( ) 6．群的运算是可交换的。( ) 7．自然数集关于数的加法和乘法
列为。 19．n阶无向简单连通图G的生成树有条边。 20．7阶圈的点色数是。 三、运算题（共5小题，每小题8分，共40分） 21．求?xF(x)→?yG(x,y)的前束范式。 22．已知无向图G有11条边，2度和3度顶点各两个，其余为4度顶点，求G 的顶点数。 23．设A={a,b,c,d,e,f}，R=I A?{
离散数学期末考试试题及答案
离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ
（2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={
离散数学教案范本
《离散数学》教案 课目：第一章命题逻辑 教师：熊建英 学时： 12课时
Ⅰ教学提要 一、教学对象（人数） 学生：信息安全专业本科二年级学生50人 二、教学目标（任务） 各小结中知识点掌握程度(* 理解；** 基本掌握；***熟练掌握) 三、教学要求 （一）学生：着重知识点的学习，积极思考，参与提问。 （二）教官：严格纪律，严密组织、保持良好教学秩序，确保教学效果。 四、教官分工 主讲教师1名：负责教案编写，课堂的组织教学，教学总结编写。
五、本章重点 1、利用联接词构造复合命题公式 2、真值表的构建 3、等值演算 4、复合命题公式转化为主析取范式、主合取范式的方法 5、推理证明 六、本章难点 1、利用命题公式演算、真值表进行等值判断和公式类型判断 2、利用命题公式演算、真值表转化主析取范式、主合取范式 3、将现实背景下的条件约束构造为命题公式 七、教学方法 采用课堂教授，主要使用多媒体课件，部分内容及例题用黑板解释。 八、课时分配 1.1 命题及联接词2课时； 1.2 命题公式及其赋值2课时； 1.3 等值式2课时； 1.4 析取范式与合取范式2课时； 1.5 推理理论与消解法2课时； 1.6 命题逻辑应用案例2课时； 九、场地器材 多媒体教室 十、参考书目 1、杨圣洪、张英杰、陈义明：《离散数学》，科学出版社，2011年。 2、屈婉玲、耿素云、张立昂：《离散数学》，高等教育出版社，2008年。 3、屈婉玲、耿素云、张立昂：《离散数学学习指导与习题解析》，高等教育出版社，2008年。
Ⅱ教学进程 1.1 命题及联接词（2课时） 一、教学内容 1、命题的概念表示与分类 2、五种基本的联接词的逻辑关系 3、复合命题的符号化 4、复合命题的真值判断 二、课程时间安排 1、首先介绍本课程的性质，任务和教学安排，对学生明确提出教学上的要求（10分钟） 2、介绍离散数学学科的发展历史（20分钟） 3、命题与真值、命题的分类、简单命题符号化（15分钟） 4、联结词与复合命题（35分钟） 5、本次课小结（10分钟） 三、教学实施 （一）创设意境、导入课程（10分钟） 目的 体会离散数学理论在现实生活中的应用、是计算机专业多门核心课程的基础，让学生明白“离散数学”课程作用和意义。 1、从生活应用中理解逻辑推理作用，及离散数学学习意义； 如：犯罪推理、电路设计、人事安排的最优方案、网络中最优路径等； (1)逻辑推理问题范例（PPT展示一个犯罪推理案例） (2)离散数学是一门可以对逻辑推理规律建立相应的符号运算系统，解决此类问题的科学。 2、离散数学与其他专业课程的联系； (1) 涉及多门计算机专业中很多专业课程，如：编程语言、数据结构、操作系统、数据数据加密。
华南理工离散数学作业题2017版
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解：（1）真值表如下： P Q ?Q P →Q ?Q∧（P→Q）?P ?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??(?Q∧(?P∨ Q)) ∨? P ?( Q∨? (?P∨ Q)) ∨? P ?? ( ?P∨ Q) ∨ (Q∨?P) ?1（析取范式） ?(?P∧? Q) ∨ (?P∧ Q) ∨ (P∧? Q) ∨（P∧ Q）（主析取范式） （3）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解：前题：?x (F (x) →?G(x)), ?x (G (x) ∨H (x)) ? x ?H (x) 结论:? x ?F (x) 证：（1）? x ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(c)US(3) (5)G(c) T(2,4)I (6)?x (F (x) →?G(x)), p (7)F (c) →?G(c) US(6) (8) ?F (c) T(5,7)I (9)( ? x) ?F (x) EG(8) 4．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证： （1）（?x）（C（x）∧Q（x））P (2) C (c) ∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P
《离散数学》期末考试试题
《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ； B 、)()())()((x xQ x xP x Q x P x ?∨??∨?； C 、)()())()((x xQ x xP x Q x P x ?∧??∧?； D 、Q x xP Q x P x ∧??∧?)())((。
离散数学作业答案一
离散数学作业7 离散数学数理逻辑部分形成性考核书 面作业 本课程形成性考核书面作业共3次,内容主要分别就是集合论部分、图论部分、数理逻辑部分的综合练习,基本上就是按照考试的题型(除单项选择题外)安排练习题目,目的就是通过综合性书面作业,使同学自己检验学习成果,找出掌握的薄弱知识点,重点复习,争取尽快掌握。本次形考书面作业就是第三次作业,大家要认真及时地完成数理逻辑部分的综合练习作业。 要求:将此作业用A4纸打印出来,手工书写答题,字迹工整,解答题要有解答过程,要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”与“交卷”按钮,以便教师评分。 一、填空题 1.命题公式()P Q P →∨的真值就是 T 或1 . 2.设P :她生病了,Q :她出差了.R :我同意她不参加学习、 则命题“如果她生病或出差了,我就同意她不参加学习”符号化的结果为 (P ∨Q)→R . 3.含有三个命题变项P ,Q ,R 的命题公式P ∧Q 的主析取范式就是 )()(R Q P R Q P ?∧∧∨∧∧ . 4.设P (x ):x 就是人,Q (x ):x 去上课,则命题“有人去上课.” 可符号化为 ))()((x Q x P x ∧? . 5.设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 ))()(())()((b B a B b A a A ∧∨∨ . 6.设个体域D ＝{1, 2, 3},A (x )为“x 大于3”,则谓词公式(?x )A (x ) 的真值为 F 或0 . 7.谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y . 8.谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ,y ))中的约束变元为 x . 三、公式翻译题 1.请将语句“今天就是天晴”翻译成命题公式. P 。，P 则今天是天晴设答:: 2.请将语句“小王去旅游,小李也去旅游.”翻译成命题公式. Q 。P ；，Q P ∧则小李去旅游小王去旅游设答::: 3.请将语句“如果明天天下雪,那么我就去滑雪”翻译成命题公式. Q 。P ；，Q P →则我去滑雪明天下雪设答;:: 4.请将语句“她去旅游,仅当她有时间.”翻译成命题公式.
- 离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
- 离散数学第二版 屈婉玲 1-5章(答案)
- 离散数学答案屈婉玲版第二版课后答案
- 离散数学答案屈婉玲版第二版 高等教育出版社课后答案
- 离散数学答案屈婉玲版第二版 高等教育出版社课后答案
- 离散数学第二版邓辉文编著第一章第五节习题答案
- 离散数学(第二版)最全课后习题答案详解
- 离散数学(第二版)最全课后习题答案详解
- 离散数学答案解析屈婉玲版第二版高等教育出版社课后答案解析
- 离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
- 离散数学 第二版 课后习题答案详解
- 离散数学第二版邓辉文编著第一章第二节习题答案
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 离散数学第二版+++
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 最新 离散数学(第二版)最全课后习题答案详解
- 离散数学第二版屈婉玲第九章第十章答案
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案