离散数学基础及实验教程pdf

第一讲 引言

一、课程内容

·数理逻辑：是计算机科学的基础，应熟练掌握将现实生活中的条件化成逻辑公式，并能做适当的推理，这对程序设计等课程是极有用处的。 ·集合论：数学的基础，对于学习程序设计、数据结构、编译原理等几乎所有计算机专业课程和数学课程都很有用处。熟练掌握有关集合、函数、关系等基本概念。 ·代数结构：对于抽象数据类型、形式语义的研究很有用处。培养数学思维，将以前学过的知识系统化、形式化和抽象化。熟练掌握有关代数系统的基本概念，以及群、环、域等代数结构的基本知识。 ·图论：对于解决许多实际问题很有用处，对于学习数据结构、编译原理课程也很有帮助。要求掌握有关图、树的基本概念，以及如何将图论用于实际问题的解决，并培养其使用数学工具建立模型的思维方式。 ·讲课时间为两个学期，第一学期讲授数理逻辑与集合论，第二学期讲授代数结构和图论。考试内容限于书中的内容和难度，但讲课内容不限于书中的内容和难度。

二、数理逻辑发展史

1. 目的

·了解有关的背景，加深对计算机学科的全面了解，特别是理论方面的了解，而不限于将计算机看成是一门技术或工程性的学科。 ·通过重要的历史事件，了解计算机科学中的一些基本思维方式和一些基本问题。

2. 数理

理 学

院

《离散数学基础》实验教学大纲

课程名称：离散数学基础实验 课程编号：080J21A 课程总学时：51 实验学时数：17 课程总学分：2.5 实验学分：0.5 开设实验项目数：5

一、实验教学目的

面向离散数学在计算机中的应用，通过实验操作，使学生掌握研究计算机科学的基础理论，进一步提高学生的抽象思维与逻辑推理能力，增强实际应用能力。 二、实验项目内容、基本要求与学时分配 序号 1 2 3 4 5 实验项目名称 逻辑运算 递推与递归 最短路问题 树与排序 排列组合 实验类型 操作 操作 设计 操作 设计 实验要求 必做 必做 必做 必做 必做 应达到的基本实验内容简介 逻辑运算、逻辑推理 递推与递归定义、推理与应用 最短路算法及应用 树的性质、冒泡排序 排列组合、二项式系数 要求 逻辑推理 推理应用 算法程序 排序 算法程序 学时分配 4 4 4 2 3 注：1、实验类型：演示、验证、操作、综合、设计、研究。2、实验要求：指必做、选做。 三、实验考核方式与标准

实验考核以学生的实验态度、掌握的实验理论、实际操作技能和实验报告等为主，各单项考核内容所占分数比例为：实

大连民族学院

计算机科学与工程学院实验报告

实验题目： 关系部分实验 课程名称： 离散数学 实验类型：□演示性 □验证性 □操作性 □设计性 ■综合性 专业： 网络工程 班级： 102 班 学生姓名：隋玉兴 学号：2010083220

实验日期：2011 年 12 月 25 日 实验地点：五机房 实验学时： 实验成绩：

指导教师签字： 年 月 日

一．实验目的

本实验课程是信息专业学生的一门专业基础课程，通过实验，帮助学生更好地掌握计算机科学技术常用的离散数学中的概念、性质和运算；通过实验提高学生编写实验报告、总结实验结果的能力；使学生具备程序设计的思想，能够独立完成简单的算法设计和分析。

熟悉掌握命题逻辑

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; (B)＝ __________________________ .

2. 设有限集合A, |A| = n, 则 | (A×A)| = __________________________.

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________.

4. 已知命题公式G＝ (P Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________.

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A B＝_________________________; A B＝_________________________;A－B＝ _____________________

《离散数学》试题及答案

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝ {3} ; {3},{1,3},{2,3},{1,2,3}} .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = 2 .

3. 设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是?1= {(a,1), (b,1)}, ?2= {(a,2), (b,2)},?3= {(a,1), (b,2)}, ?4= {(a,2), (b,1)}, 其中双射的是 ?3, ?4 .

4. 已知命题公式G＝?(P?Q)∧R，则G的主析取范式是 (P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为 12 ，分枝点数为 3 .

6 设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝ {4} ; A?B＝{1,2,3,4}; A－B＝ {1,2} .

7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是 自反性 , 对

一、填空题

1 设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝__{3}__________________;

?(A) - ?(B)＝ ___________________{3},{1,3},{2,3},{123}______ .

2. 设有限集合A, |A| = n, 则 |?(A×A)| = _____2^(n^2)_____________________.

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}

《离散数学》题库与答案 一、选择或填空

（数理逻辑部分）

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）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式

4、公式?x((A(x)?B(y，x))? ?z C(y，z))?D(x)中，自由变元是( )，约束变元是( )。

答：x,y, x,z（考察定义在公式?x

《离散数学》题库答案

一、选择或填空 （数理逻辑部分）

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、判断下列语句是不是命题。若是，给出命题的真值。( (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。

1

)，约束)

(3) 你喜欢唱歌吗？ (4) 若7+

离散数学实验报告

姓名： 学号： 专业：

实验一、真值运算

一、实验内容

从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值，并输出。 二、实验步骤

编写程序，将P,Q以不同真值带入，观察程序运行结果，调式程序。 三、实验代码

#include int main() {

int p,q; char t; while(t) {

printf(\是否运算程序(y/n):\\n\scanf(\if('y'==t) {

printf(\输入p,q的真值(0或1):\scanf(\if((p!=1)&&(p!=0)) {

printf(\请重新输入p值\

}

scanf(\

if((q!=1)&&(q!=0)) { }

if(q==0&&p==0) { }

else if(p==0&&q==1) {

printf(\﹁p=1\\n\printf(\﹁q=0\\n\printf(\∧q=0\\n\printf(\∨q=1\\n\printf(\→q=1\\n\printf(\﹁p=1\\n\printf(\﹁q=1\\n\printf(\∧q=0\\n\p

离散数学实验报告

姓名： 学号： 专业：

实验一、真值运算

一、实验内容

从键盘输入两个命题P和Q的真值，求它们的合取、析取、条件和双条件的真值，并输出。 二、实验步骤

编写程序，将P,Q以不同真值带入，观察程序运行结果，调式程序。 三、实验代码

#include int main() {

int p,q; char t; while(t) {

printf(\是否运算程序(y/n):\\n\scanf(\if('y'==t) {

printf(\输入p,q的真值(0或1):\scanf(\if((p!=1)&&(p!=0)) {

printf(\请重新输入p值\

}

scanf(\

if((q!=1)&&(q!=0)) { }

if(q==0&&p==0) { }

else if(p==0&&q==1) {

printf(\﹁p=1\\n\printf(\﹁q=0\\n\printf(\∧q=0\\n\printf(\∨q=1\\n\printf(\→q=1\\n\printf(\﹁p=1\\n\printf(\﹁q=1\\n\printf(\∧q=0\\n\p