高斯课堂离散数学

1.1 命题及其表示法

1.下列陈述句中，（ ）不是命题。

A.2013年国庆节是星期天。 B.火星上有生物。 C.月球距离地球近。 D.上海是大城市。 2.下列命题中，（ ）是复合命题。

A.江山代有人才出。 B.我花开时百花杀。 C.春江水暖鸭先知。 D.万紫千红总是春。 3.下列命题中，（ ）是原子命题。

A.燕子飞回南方，春天来了。 B.天才是炼成的，而不是天生的。 C.暮春三月，江南草长。 D.哥白尼指出地球绕太阳转。 4.下列命题中，（ ）是原子命题。

A.王芳与王菲是姐妹。 B.王芳与王菲是三好学生。 C.王芳与王菲持有驾照。 D.王芳与王菲喜欢早睡早起。 5.下列命题中，（ ）是原子命题。

A.数学是科学的皇后，而数论是数学的皇后。 B.数学使人精细，逻辑使人善辩。 C.较大的偶数都可表示为两个素数的和。 D.数学是一种语言，也是一种工具。 6.判断一个语句是否为命题，首先看它是否为 陈述句 ，然后再看它是否具有唯一的 真值

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

离散数学标准化作业纸 专业班级 学号 姓名 第一章 命题逻辑的基本概念

一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （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）

第一讲 引言

一、课程内容

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

二、数理逻辑发展史

1. 目的

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

2. 数理

《离散数学》练习

福建农林大学东方学院

2009 ——2010 学年第一学期

第一篇 数理逻辑

一、填空题及单项选择题：

1、设解释I为：客体城D?{2,3}，

a2b,3f(2)3f(3),2P(2,2)1P(2,3)1P(3,2)0P(3,3) 0则P(a,f(a))?P(b,f(b))? ，?x?yP(x,y) 。

2、公式G?(P?(?Q?R))?Q的主析取范式为 。 3、下列命题等值式正确的是 【 】 （A）P?Q?(P?Q)?(Q?P)；

P?Q?(P?Q)?(P??Q)；（B）

（C）P?Q??Q??P； （D）P?Q?P??Q.

4、设命题公式G?(Q?P)?(?P?Q)，则G是 【 】 （A）可满足的； （B）永真的； （C）永假的； （D）析取范式

5、前提?xP(x)与?x(P(x)?Q(x))的有效结论是 【 】

命题演算

? 命题（真值确定但不一定要知道真假，比如“存在外星人”是一个命题，它的真值确定，即使我们不知道真值）

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

原始命题/原子命题 复合命题 逻辑连接词 否定/┐ 合取/∧ 析取/∨

条件/→（┐P∨Q）

双条件（不好意思，双向箭头字符未找到，(P∧Q)∨(┐P∧┐Q)） 真值表 命题公式/公式 命题变元 命题演算

等价（自反性、对称性、传递性，等价变换法俗称“少林派”） 结合律 交换律 分配律

德·摩根律/反演律 双重否定率 代换

蕴含（自反性、反对称性、传递性，蕴含推理法俗称“武当派”，传递法俗称“隔山打牛”） 对偶法则 对偶

不可兼析取（析取符上加一横，异或） 逆条件（条件符上加字母c） 与非/↑ 或非/↓

? ? ? ? ? ? ? ? ? ?

结合力（ ⑴┐⑵∧⑶∨、不可兼析取、↑、↓⑷→、逆条件⑸双条件 ） 析取范式 合取范式

主析取范式（∑=m∨…） 主合取范式（∏=M∧…） 直接推演 P规则 T规则

CP规则（俗称“北冥神功”） 间接推演/间接证明/反

第六章 图论基础

图是建立和处理离散数学模型的一种重要工具。图论是一门应用性很强的学科。许多学科，诸如运筹学、网络理论、控制论、化学、生物学、物理学、社会科学、计算机科学等，凡是研究事物之间关系的实际问题或理论问题，都可以建立图论模型来解决。随着计算机科学的发展，图论的应用也越来越广泛，同时图论也得到了充分的发展。这里将主要介绍与计算机科学关系密切的图论的内容。

6.1 图的基本概念

我们已知集合的笛卡尔积的概念，为了定义无向图，还需要给出集合的无序积的概念。 任意两个元素a,b构成的无序对（Unordered pair）记作(a,b)，这里总有(a,b)?(b,a)。 设A,B为两个集合，无序对的集合{(a,b)a?A?b?B}称为集合A与B的无序积（Unordered Product），记作A&B。无序积与有序积的不同在于A&B?B&A。

例如，设A??a,b?，B??0,1,2?，则A&B?{(a,0),(a,1),(a,2),(b,0),(b,1),(b,2)} ?B&A,A&A?{(a,a),(a,b),(b,b)}。 为了引出图的定义，我们先介绍如下的例子。

B start s=0,i =1 i=1 S i=11? Y N s

离散数学试题(A卷及答案)

一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？(写过程) 1)P?(P∨Q∨R) 2)?(P?Q)∧Q 3)(P?Q)∧?R

解：1)重言式；2)矛盾式；3)可满足式

二、（10分）求命题公式(?P?Q)?(?Q∨P)的主析取范式，并求成真赋值。

解：(?P?Q)?(?Q∨P)?(P∨Q)?(?Q∨P)??(P∨Q)∨(?Q∨P)

?(?P∧?Q)∨?Q∨P??Q∨P?((P∨?P)∧?Q)∨(P∧?Q)∨(P∧Q) ?(?P∧?Q)∨(P∧?Q)∨(P∧?Q)∨(P∧Q)? m0∨m2∨m3

成真赋值为：00、10、11。

三、（10分）证明下列命题的等值关系：(P∨Q)∧?(P∧Q)??(P?Q）

证明：(P∨Q)∧?(P∧Q)?(P∨Q)∧(?P∨?Q)?(P∧?Q)∨(Q∧?P)

??((?P∨Q)∧(?Q∨P))??((P?Q)∧(Q?P))??(P?Q）

四、（10分）叙述并证明苏格拉底三段论

解：所有人都是要死的，苏格拉底是人，所以苏格拉底是要死的。 符号化：F（x）：x是一个人。G（x）：x要死的。A：苏格拉底。 命题符号化为?x（F（x）?G（x）），F（a）?G（a

《离散数学》复习资料 2014年12月

一、单项选择题（每小题3分，本题共15分）

1．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( A )．

A． A?B，且A?B B．B?A，且A?B C．A?B，且A?B D．A?B，且A?B 2．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是 ( D )．

图一 A．（a）是强连通的 B．（b）是强连通的

C．（c）是强连通的 D．（d）是强连通的 3．设图G的邻接矩阵为

?01100??10011???

?10000???01001????01010??则G的边数为( B )．

A．6 B．5 C．4 D．3

4．无向简单图G是棵树，当且仅当( A )．

A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 C．G的边数比结点数少1 D．G中没有回路． 5．下列公式 ( C

-离散数学 专业班级 学号 姓名 第一章 命题逻辑的基本概念

一、单项选择题

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. 设命题公式?p( )

?(q?r),则使公式取真值为1的p，q，r赋值分别是

(B)0,0,1(C)0,1,0(D)1,0,0

(A)0,0,04. 命题公式(p?q)?q为 ( )

(A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q：我有时间．

命题“我将去市里，仅当我有时间时”符号化为为( )

(A)q?p(B)p?q(C)p?q(D)?p??q 6．设P：我听课,Q：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. P??Q ； B. ?P?Q； C. ?Q