离散数学课后习题答案(左孝凌版)

1-1，1-2 （1） 指出下列哪些语句是命题，那些不是命题，如果是命题，指出它的真值。 a) 离散数学是计算机科学系的一门必修课。 是命题，真值为 T。 b) 计算机有空吗？ 不是命题。 c) 明天我去看电影。 是命题，真值要根据具体情况确定。 d) 请勿随地吐痰。 不是命题。 e) 不存在最大的质数。 是命题，真值为 T。 f) 如果我掌握了英语，法语，那么学习其他欧洲语言就容易多了。 是命题，真值为 T。 g) 9+5 ≤ 12. 是命题，真值为 F。 h) X=3. 不是命题。 i) 我们要努力学习。 不是命题。 （2） 举例说明原子命题和复合命题。 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3） 设 P 表示命题“天下雪。 ”
f) A → ( B ∨ C ) ⇔ ( A ∧ ¬B) → C 证明：A→(B∨C)⇔ ┐A∨(B∨C) ⇔ (┐A∨B)∨C ⇔┐(A∧┐B)∨C ⇔ (A∧┐B)→C g) ( A → D ) ∧ ( B → D ) ⇔ ( A ∨ B ) → D 证明：(A→D)∧(B→D)⇔(┐A∨D)∧(┐B∨D) ⇔(┐A∧┐B)∨D ⇔ ┐(A∨B)∨D ⇔ (A∨B)→D h) (( A ∧ B ) → C ) ∧ ( B → ( D ∨ C )) ⇔ ( B ∧ ( D → A)) → C 证明：((A∧B)→C)∧(B→(D∨C)) ⇔(┐(A∧B)∨C)∧(┐B∨(D∨C)) ⇔ (┐(A∧B)∧(┐B∨D))∨C ⇔(┐(A∧B) ∧┐(┐D∧B))∨C ⇔┐((A∧B)∨(┐D∧B))∨C ⇔ ((A∨┐D)∧B)→C ⇔ (B∧(D→A))→C （8）化简以下各式： A）((A→B) ↔ (┐B→┐A))∧C 解：((A→B) ↔ (┐B→┐A))∧C ⇔ ((┐A∨B) ↔ (B∨┐A))∧C ⇔ ((┐A∨B) ↔ (┐A∨B))∧C ⇔T∧C ⇔C B）A∨(┐A∨(B∧┐B)) 解：A∨(┐A∨(B∧┐B))⇔(A∨┐A)∨(B∧┐B)⇔T∨F⇔T

4
第一章 命题逻辑（Propositional Logic）1.3命题
公式与翻译
• 联结词旳优先级：┐、∧、∨、→、。
则：
P∧Q→R 是合式公式
等价于Wff ： （（P∧Q）→R ）命题公式外层旳括号能够省略
等价于Wff ： （P∧Q）→R
不等价于Wff ： P∧（Q→R）
第一章 命题逻辑（Propositional Logic）1.3命题
P Q ┐P∨Q
TT T TF F FT T
P→Q
T F T
FF T
T
第一章 命题逻辑（Propositional Logic） 1.4真值表 与等价公式
1.4.2 等价公式
同理(P∧Q)∨(┐P∧┐Q)与P↔ Q相应旳真值相同，如表1-4.6所示。
表1-4.6
P Q P↔Q TT T TF F FT F FF T
公式与翻译
• 1.3.2 复合命题旳符号化(翻译) • 自然语言旳语句用Wff 形式化：
① 要精确拟定原子命题，并将其形式化。 ② 要选用恰当旳联结词，尤其要善于辨认自然语言中旳联 结词（有时它们被省略），否定词旳位置要放精确。 ③ 必要时能够进行改述，即变化原来旳论述方式， 但要确保体现意思一致。 ④ 需要旳括号不能省略，而能够省略旳括号， 在需要提升公式可读性时亦可不省略。
例2：构造公式 (P Q) ∧R旳 真值表。
P Q R PQ (P Q) ∧R
00 0 00 1
01 0 01 1 10 0 10 1 11 0 11 1
20
第一章 命题逻辑（Propositional Logic） 1.4真值表 与等价公式
例2：构造公式 (P Q) ∧R旳 真值表。

计算机学院
5-1 代数系统的引入
定义5-1.1 [ n元运算] 对于集合A，一个从An到B的映射，称为集合
A上的一个n元运算。如果BA，则称该n元运算
是封闭的。 定义5-1.2[代数系统] 一个非空集合A连同若干个定义在该集合上的 运算f1,f2,…,fk所组成的系统就称为一个代数系统， 记作<A,f1,f2,…,fk>。
计算机学院
第三篇 代数系统（Algebraic System ）
针对某个具体问题选用适宜的数学结构去进 行较为确切的描述，这就是所谓的“数学模型”。
可见，数学结构在数学模型中占有极为重要的位
置。我们这里所要研究的是一类特殊的数学结 构—由集合上定义若干个运算而组成的系统。我 们通常称它为代数系统。它在计算机科学中有着 广泛的应用。
第 三 篇 代 数 系 统
计算机学院
第三篇 代数系统（Algebraic System ）
人们研究和考察现实世界中的各种现象或过程， 往往要借助某些数学工具。譬如，在微积分学中，
可以用导数来描述质点运动的速度，可以用定积
分来计算面积、体积等；在代数学中，可以用正 整数集合上的加法运算来描述工厂产品的累计数， 可以用集合之间的“并”、“交”运算来描述单 位与单位之间的关系等。
<P(S), ∩ >
P(S)是S的幂 集∩为集合的 “交” A∩B∈P (S) A∩B=B∩A (A∩B)∩C =A∩(B∩C)
I为整数集合 · 为普通乘法 x· y∈I x· y=y· x (x· y)· z=x· (y· z )
计算机学院
5-2 运算及其性质
定义5-2.1[运算封闭] 设*是定义在集合A上的二元运算，如果对于任意 的x,y∈A,都有x*y∈A,则称二元运算*在A上是封 闭的。

表1-6.1 P 0 0 1 1 Q 0 1 0 1 P ∨Q 0 1 1 0
不可兼析取
不可兼析取有下列的性质： ⑴ P ∨ QQ ∨ P ⑵ (P ∨ Q) ∨ RP ∨ (Q ∨ R) (交换律) (结合律)
⑶ P∧(Q ∨ R)(P∧Q) ∨ (P∧R) (合取对异或的分配律) ⑷ P∨ Q(P∧Q)∨(P∧Q) ⑸ P ∨ Q(PQ) ⑹ P ∨ P0，0 ∨ PP，1 ∨ PP 定理1-6.1 设P，Q，R为命题公式，如果P ∨ QR，则P ∨ R Q，Q ∨ RP，P ∨ Q ∨ R为一矛盾式。 (书中有证明)
不等价的命题公式的个数
两个命题变元可以构成多少个不等价的命题公式？ 由等价的概念知道，等价的命题公式有相同的真值表，所以上述问题就转化为两个 命题变元构成的命题公式有多少个不同的真值表？
两个命题变元构成的命题公式的真值表的格式如下表所示。真值表中每行 4 公式的真值都有1，0两种可能，所以命题公式的真值有2×2×2×2 = 2 = 22 = 16种可能，既有22 个不同的真值表。故有22 种不等价的公式。
表1-6.3 q 0 1 0 1 p 0 0 1 1 p↓q 1 0 0 0
1.6 全功能联结词集
至此已经学了8个联结词： ,∧,∨,→,, ∨ ,↑,↓。类似于定义命题 公式的方法，可以定义包含上述8个联结词 的命题公式。 定义1-6.4 设S是一个联结词集合，如果任何 n(n≥1)个变元组成的公式，都可以由S中的 联结词来表示，则称S是全功能联结词集。
1.6 全功能联结词集
定义1-6.1 设P和Q是两个命题，复合命题P ∨ Q称作P和Q的 不可兼析取，也叫异或。定义为：P ∨ Q为T当且仅当P 和Q的真值不相同时。联结词“ ∨ ”称为异或联结词。 联结词“ ∨ ”的真值表如表 1-6.1所示。 “ ∨ ”也可以看成逻辑运 算，它是二元逻辑运算。它在程 序设中有广泛的引用。