离散数学复习指导

发布 2021-05-18 09:57:28 阅读 5450

命题逻辑部分。

一学习要求。

1.理解命题、联结词的含义,掌握命题的符号化;

2.理解命题公式的赋值,能求出公式的真值表,判断公式的类型;

3. 理解公式等值的定义,记住一些基本等值式,能进行等值演算;

4. 体会公式的主范式与公式赋值之间的关系,能利用等值演算求出范式;

5. 理解公式的蕴涵及推理的含义及联系,记住一些基本的推理规则,能用演绎。

推理方法进给出推理证明;

二范例。例1 将下列命题符号化。

⑴小王聪明但不用功;

⑵ 说数理逻辑枯燥无味或毫无价值,那是不对的;

⑶ 你不及格就要补考。

⑷ 不经一事,不长一智;

解:⑴ 设p:小王聪明,q:小王用功,则该命题可符号化为:。

⑵ p:数理逻辑枯燥无味,q:数理逻辑毫无价值,则:。

p:你及格了;q:你要参加补考,则:。

p:经一事;q:长一智,则:。

这是简单命题,则p:李卫与李星是兄弟。

例2 求命题公式的主析取范式和主合取范式,指出公式的成真赋值和成假赋值,并判断公式的类型。

解: 主合取范式)

(主析取范式)

公式的成真赋值为:000,001,011,101,110,111 成假赋值为:010,100

公式为非重言式的可满足式。

例3 构造下面推理的证明:

前提: 结论:

证:(1p;

(2t(1)化简规则;

3t(1)化简规则

4p;5) rt(3)(4)假言推理;

(6p;7) st(3)(6)析取三段论;

(8t(5)(7)合取式。

例4. 先将下列相关命题符号化,给出推理证明。

如果4是偶数,则2不能整除5. 或者7不是素数或者2整除5. 7是素数。因此4不是偶数。

解: 设p: 4是偶数; q: 2能整除5; r: 7是素数; s: 2整除5,则。

前提: 结论:

证明: (1结论之否定;

(2t(1)等值式;

3p; 4t(2)(3)假言推理;

5p; (6t(4)(5)析取三段论;

7p;8t(6)(7)合取式。

三练习题 1. 将下列命题符号化。

小王不但聪明而且美丽。

不经历风雨,就不能见彩虹。

只有天气又冷又下雨,他才乘车上班。

天黑了,我就回家。

说学生考试不及格是因为学生不聪明或基础太差是不对的。

进入机房者,必须换拖鞋,穿工作服,否则罚款五元。

2.求下列公式的主析取范式和主合取范式,指出公式的成真赋值和成假赋值,并判断命公式的类型。

3.构造下述推理的证明。

前提:,结论:

前提: 结论:

前提: 结论:

4. 先将下列相关命题符号化,给出推理证明。

如是我好好学习,那么我就不要补考。如果我不玩电脑游戏,我就会好好学习。我要补考。所以我玩电脑游戏了。

2) 如果一班不参加篮球赛,那么二班也不参加,如果一班参加篮球赛,那么二班和三班就参加,因此如果二班参加了篮球赛,那么三班也参加了。

谓词逻辑部分。

一学习要求。

1.理解谓词逻辑的三要素,掌握命题的符号化;

2.理解谓词公式中量词的辖域、约束关系,及公式的解释,能求出在一个解释下公式的真值,能判断公式的类型;

3. 理解公式等值的定义,记住谓词公式的特殊的基本等值式,能进行等值演算;

4. 理解前束范式的定义,能利用等值演算求出公式的前束范式;

5. 理解公式的蕴涵及推理的含义及联系,特别记住谓词中的一些推理规则,能用演绎。

推理方法进给出推理证明;

二范例。例1 将下列命题符号化。

不是所以的人都要补考,但就有人要补考。

天下乌鸦一般黑。

不是所有火车都比汽车快,但有的火车比所有汽车快。

解:⑴:是人;:要补考,则:

注意特性谓词的用法)

⑵ 设d=,:是黑的,则: (本题使用了论域)

:是火车;:是汽车;:比快,则:

或:。例2 设解释i如下:

d=, a =0,b=1,,

试求出下列公式在解释i下的真值。

3.求下列公式的前束范式。

4.将下列命题符号化,并证明之。

⑴ 没有不守信用的人是可以信赖的。有些可以信赖的人是受过教育的。因此有些受过教育的人是守信用的。

⑵ 有些人喜欢所有的花。但人人都不喜欢杂草。所以花不是杂草。

⑶ 三好生都是成绩好的学生。 学生干部不一定成绩好,所以学生干部不一定是三好生。

离散数学复习指导

例4.先将下列相关命题符号化,给出推理证明。如果4是偶数,则2不能整除5.或者7不是素数或者2整除5.7是素数。因此4不是偶数。解 设p 4是偶数 q 2能整除5 r 7是素数 s 2整除5,则。前提 结论 证明 1结论之否定 2t 1 等值式 3p 4t 2 3 假言推理 5p 6t 4 5 析取...

离散数学复习

离散数学 复习资料 2014年12月。一 单项选择题 每小题3分,本题共15分 1 若集合a b 则下列表述正确的是 a a ab,且a b b ba,且a b c ab,且ab d ab,且a b 2 设有向图 a b c 与 d 如图一所示,则下列结论成立的是 d 图一。a a 是强连通的b b...

离散数学难点

联结词与复合命题。复合命题 p并且q 或 p与q 记作p q p并且q 的多种表述方式 既p又q.不仅p而且q.虽然p但qpq 的逻辑关系 q为p的必要条件,p为q的充分条件。如果p,则q 的多种表述方式 若p,就q只要p,就q p仅当q只有q 才p 除非q,才p 除非q,否则非p 假如没有q,就没...