《离散数学》速成

《离散数学》速成-练习题答案（含题目）

课时一  命题逻辑的基本概念

• 1. 命题：能判断其真值的陈述句.
• 2. 真值：真、假.（1、0）
• 3. 真命题：真值为真的命题.
• 4. 假命题：真值为假的命题.
• 5. 原子命题（简单命题）：不能再被分解成更简单的命题.
• 6. 复合命题：由简单命题通过联结词联结而成的命题.

判定给定句子是否为命题，应该分两步：

① 首先判定它是否为陈述句.

② 其次判断它是否有唯一真值

题 1.下列语句中，下面哪一个选项是命题？（）

1. 你今天有空吗？
2. 我正在说谎.
3. 请勿随地吐痰！
4. 2是偶数

答案：4

题 1. 将下列命题符号化 .

1.4 不是素数.

2.小智和小红是学生.

3.小智和小红是同学.

4.小智是江苏人或者江西人.

5.小红喜欢唱歌或跳舞.

6.①只要 能被 4 整除，则 一定能被 2 整除.

②只有 能被 4 整除，则 才能被 2 整除.

③ 能被 4 整除，仅当 能被 2 整除.

7.2+3=5的充要条件是 是无理数.

答案

• ：自然语言中的“既……，又……”“不但……，而且……”“虽然……，但是……”“一面……，一面……”等.

• ：“只要 p ，就q ”，“因为  p，所以 q”，“ p仅当q ”，“只有q 才p”，“除非q才p ”，“除非q ，否则非 p ”等等，符号化为p q

• ：“当且仅当”，“……充要条件”等.

3. 命题公式及其赋值

命题变元 ：取值 1（真）或 0（假）的变元.

合式公式 ：将命题变元用联结词或圆括号按一定逻辑关系联结起来的符号串.

3. 设 是出现在公式 A中的全部命题变元，给 各指定一个真值，称为对A的一个 赋值 ，

若指定的一组值使A为 1，则称这组值为A的成真赋值；若使为 0，则称这组值的成假赋值.

题 1. 写出下列公式的 真值表 ，并求它们的成真赋值和成假赋值 .

设A为任一命题公式

1. 若 A在它的各种赋值下取值均为真，则称A为 重言式或永真式 .

2. 若A在它的各种赋值下取值均为假，则称A为 矛盾式或永假式 .

3. 若A不是矛盾式，则称A为 可满足式 .

课时一练习题

课时二：命题逻辑等值演算

1.

等值式

设A，B是两个命题公式，若A，B构成的等价式 为重言式，则称A与B是等值的，记作

2.

析取范式与合取范式

1. 文字：命题变元及其否定.
2. 简单析取式：仅由有限个文字构成的析取式.
3. 简单合取式：仅由有限个文字构成的合取式.
4. 析取范式：由有限个简单合取式的析取构成的命题式 ，其中 (i =1, 2,…,s)是简单合取式.
5. 合取范式：由有限个简单析取式的合取构成的命题式 ，其中 是简单析取式.

3. 主析取范式与主合取范式

在含有n个命题变元的简单合取式（简单析取式）中，若每个命题变元和它的否定式恰好

出现一个且仅出现一次，而且命题变元或它的否定式按照下标从小到大顺序排列，称这

样的简单合取式（简单析取式）为极小项（极大项）.

设 与 ,是命题变元含 的极小项和极大项，则

所有简单合取式都是极小项的析取范式称为主析取范式.

所有筒单析取式都是极大项的合取范式称为主合取范式.

4. 联结词的完备集

设S是一个联结词集合，如果一个命题公式都可以由仅含S中的联结词构成的公式表示，则称S是一个联结词完备集.

课时二练习题

课时三：命题逻辑的推理理论

1. 推理的相关公式

2. 自然推理系统

题⒉.在自然推理系统中，构造并证明下列推理．(命题逻辑推理证明)

如果小王是理科生,则他的数学成绩一定很好.

如果小王不是文科生,则他一定是理科生.

小王的数学成绩不好.所以，小王是文科生.

解:设简单命题

p:小王是理科生.q:小王的数学成绩很好.r :小王是文科生.

前提:

结论: r

证明:

题 3. 用推理的形式结构证明：

题 4.在自然推理系统P中构造下面推理的证明.

如果小张守第一垒并且小李向B队投球，则A队取胜；或者A队未取胜，或者A队成为联赛第一名；

A 队没有成为联赛的第一名；小张守第一垒.因此，小李没向B队投球.

解：设简单命题

p：小张守第一垒.

q：小李向 B队投球.

r： 队取胜.

s： 队成为联赛第一名.

前提：

结论：