离散数学-第二章命题逻辑等值演算习题及答案

第二章作业

评分要求:

1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分

2. 给出每小题得分(注意: 写出扣分理由)

3. 总得分在采分点1处正确设置.

一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):

说明

1. p⇔(p∧q) ∨(p∧¬q)

解逻辑方程法

设 p ((p∧q) ∨(p∧¬q)) =0,

分两种情况讨论:

⎧p =1 或者 (1) ⎨⎩(p ∧q ) ∨(p ∧⌝q ) =0

⎧p =0 (2) ⎨(p ∧q ) ∨(p ∧⌝q ) =1⎩

(1)(2)两种情况均无解, 从而, p(p∧q) ∨(p∧¬q) 无成假赋值, 为永真式.

等值演算法

(p∧q) ∨(p∧¬q)

⇔ p ∧(q∨¬q)

⇔ p ∧1 排中律 ⇔ p 同一律 ∧对∨的分配率 真值表法

2. (p→q) ∧(p→r) ⇔p →(q∧r)

等值演算法

(p→q) ∧(p→r)

⇔ (¬p ∨q) ∧(¬p ∨r) 蕴含等值式

⇔ ¬p ∨(q∧r) 析取对合取的分配律

⇔ p →(q∧r) 蕴含等值式

3. ¬(pq) ⇔(p∨q) ∧¬(p∧q)

等值演算法

¬(pq)

⇔ ¬( (p→q) ∧(q→p) )等价等值式

⇔ ¬( (¬p ∨q) ∧(¬q ∨p) )蕴含等值式

⇔ ¬( (¬p ∧¬q) ∨(p∧q) )合取对析取分配律, 矛盾律, 同一律

⇔ (p∨q) ∧¬(p∧q) 德摩根律

4. (p∧¬q) ∨(¬p ∧q) ⇔(p∨q) ∧¬(p∧q)

等值演算法

(p∧¬q) ∨(¬p ∧q)

⇔ (p∨q) ∧¬(p∧q) 析取对合取分配律, 排中律, 同一律

说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.

等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.

二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):

1.

2.

3.

4.

1. (¬p →q) →(¬q ∨p)

(¬p →q) →(¬q ∨p)

⇔ (p∨q) →(¬q ∨p) 蕴含等值式

⇔ (¬p ∧¬q) ∨(¬q ∨p) 蕴含等值式, 德摩根律

⇔ (¬p ∧¬q) ∨¬q ∨ p 结合律

⇔ p ∨¬q 吸收律, 交换律

⇔ M 1

因此, 该式的主析取范式为m 0∨m 2∨m 3

2. (¬p →q) ∧(q∧r)

解逻辑方程法

设 (¬p →q) ∧(q∧r) =1, 则 ¬p →q=1且 q ∧r=1,

解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m 3∨m 7, 主合取范式为 M 0∧M 1∧M 2∧M 4∧M 5∧M 6

等值演算法

(¬p →q) ∧(q∧r)

⇔ (p∨q) ∧(q∧r) 蕴含等值式

⇔ (p∧q ∧r) ∨(q∧r) ∧对∨分配律, 幂等律

⇔ (p∧q ∧r) ∨ (p∧q ∧r) ∨(⌝p ∧q ∧r) 同一律, 矛盾律, ∧对∨分配律

⇔ m 7 ∨ m3

主合取范式为M 0∧M 1∧M 2∧M 4∧M 5∧M 6

3. (pq) →r

解逻辑方程法

设 (pq) →r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M 0∧M 6, 主析取范式为m 1∨m 2∨m 3∨m 4∨m 5∨m 7

等值演算法

(pq) →r

⇔ ((p→q) ∧(q→p)) →r 等价等值式

⇔ ⌝((p→q) ∧(q→p)) ∨r 蕴含等值式

⇔ (p∧⌝q) ∨(q∧⌝p) ∨r 德摩根律, 蕴含等值式的否定(参见PPT)

⇔ (p∨q ∨r) ∧(⌝q ∨⌝p ∨r) ∨对∧分配律, 矛盾律, 同一律

⇔ M 0 ∧ M6

主析取范式为 m 1∨m 2∨m 3∨m 4∨m 5∨m 7

4. (p→q) ∧(q→r)

等值演算法

(p→q) ∧(q→r)

⇔ (⌝p ∨q) ∧(⌝q ∨r) 蕴含等值式

⇔ (⌝p ∧⌝q) ∨(⌝p ∧r) ∨(q∧r) ∧对∨分配律, 矛盾律, 同一律

⇔ (⌝p ∧⌝q ∧r) ∨(⌝p ∧⌝q ∧⌝r) ∨ (⌝p ∧q ∧r) ∨(⌝p ∧⌝q ∧r) ∨ (p∧q ∧r) ∨(⌝p ∧q ∧r) ⇔ m 1 ∨ m0 ∨ m3 ∨ m7

主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.

解逻辑方程法

设 (p → q) ∧ (q → r) = 1, 则p → q =1 且 q → r =1. 前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1. 后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.

综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m 0 ∨ m1 ∨ m3 ∨ m7, 主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.

真值表法

公式 (p → q) ∧ (q

从而主析取范式为m 0 ∨ m1 ∨ m3 ∨ m7, 主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.

第二章作业

评分要求:

1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48分

2. 给出每小题得分(注意: 写出扣分理由)

3. 总得分在采分点1处正确设置.

一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方法每种方法至少使用一次):

说明

1. p⇔(p∧q) ∨(p∧¬q)

解逻辑方程法

设 p ((p∧q) ∨(p∧¬q)) =0,

分两种情况讨论:

⎧p =1 或者 (1) ⎨⎩(p ∧q ) ∨(p ∧⌝q ) =0

⎧p =0 (2) ⎨(p ∧q ) ∨(p ∧⌝q ) =1⎩

(1)(2)两种情况均无解, 从而, p(p∧q) ∨(p∧¬q) 无成假赋值, 为永真式.

等值演算法

(p∧q) ∨(p∧¬q)

⇔ p ∧(q∨¬q)

⇔ p ∧1 排中律 ⇔ p 同一律 ∧对∨的分配率 真值表法

2. (p→q) ∧(p→r) ⇔p →(q∧r)

等值演算法

(p→q) ∧(p→r)

⇔ (¬p ∨q) ∧(¬p ∨r) 蕴含等值式

⇔ ¬p ∨(q∧r) 析取对合取的分配律

⇔ p →(q∧r) 蕴含等值式

3. ¬(pq) ⇔(p∨q) ∧¬(p∧q)

等值演算法

¬(pq)

⇔ ¬( (p→q) ∧(q→p) )等价等值式

⇔ ¬( (¬p ∨q) ∧(¬q ∨p) )蕴含等值式

⇔ ¬( (¬p ∧¬q) ∨(p∧q) )合取对析取分配律, 矛盾律, 同一律

⇔ (p∨q) ∧¬(p∧q) 德摩根律

4. (p∧¬q) ∨(¬p ∧q) ⇔(p∨q) ∧¬(p∧q)

等值演算法

(p∧¬q) ∨(¬p ∧q)

⇔ (p∨q) ∧¬(p∧q) 析取对合取分配律, 排中律, 同一律

说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.

等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写. 由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.

二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成假赋值求解都至少使用一次):

1.

2.

3.

4.

1. (¬p →q) →(¬q ∨p)

(¬p →q) →(¬q ∨p)

⇔ (p∨q) →(¬q ∨p) 蕴含等值式

⇔ (¬p ∧¬q) ∨(¬q ∨p) 蕴含等值式, 德摩根律

⇔ (¬p ∧¬q) ∨¬q ∨ p 结合律

⇔ p ∨¬q 吸收律, 交换律

⇔ M 1

因此, 该式的主析取范式为m 0∨m 2∨m 3

2. (¬p →q) ∧(q∧r)

解逻辑方程法

设 (¬p →q) ∧(q∧r) =1, 则 ¬p →q=1且 q ∧r=1,

解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m 3∨m 7, 主合取范式为 M 0∧M 1∧M 2∧M 4∧M 5∧M 6

等值演算法

(¬p →q) ∧(q∧r)

⇔ (p∨q) ∧(q∧r) 蕴含等值式

⇔ (p∧q ∧r) ∨(q∧r) ∧对∨分配律, 幂等律

⇔ (p∧q ∧r) ∨ (p∧q ∧r) ∨(⌝p ∧q ∧r) 同一律, 矛盾律, ∧对∨分配律

⇔ m 7 ∨ m3

主合取范式为M 0∧M 1∧M 2∧M 4∧M 5∧M 6

3. (pq) →r

解逻辑方程法

设 (pq) →r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式为M 0∧M 6, 主析取范式为m 1∨m 2∨m 3∨m 4∨m 5∨m 7

等值演算法

(pq) →r

⇔ ((p→q) ∧(q→p)) →r 等价等值式

⇔ ⌝((p→q) ∧(q→p)) ∨r 蕴含等值式

⇔ (p∧⌝q) ∨(q∧⌝p) ∨r 德摩根律, 蕴含等值式的否定(参见PPT)

⇔ (p∨q ∨r) ∧(⌝q ∨⌝p ∨r) ∨对∧分配律, 矛盾律, 同一律

⇔ M 0 ∧ M6

主析取范式为 m 1∨m 2∨m 3∨m 4∨m 5∨m 7

4. (p→q) ∧(q→r)

等值演算法

(p→q) ∧(q→r)

⇔ (⌝p ∨q) ∧(⌝q ∨r) 蕴含等值式

⇔ (⌝p ∧⌝q) ∨(⌝p ∧r) ∨(q∧r) ∧对∨分配律, 矛盾律, 同一律

⇔ (⌝p ∧⌝q ∧r) ∨(⌝p ∧⌝q ∧⌝r) ∨ (⌝p ∧q ∧r) ∨(⌝p ∧⌝q ∧r) ∨ (p∧q ∧r) ∨(⌝p ∧q ∧r) ⇔ m 1 ∨ m0 ∨ m3 ∨ m7

主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.

解逻辑方程法

设 (p → q) ∧ (q → r) = 1, 则p → q =1 且 q → r =1. 前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1. 后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.

综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m 0 ∨ m1 ∨ m3 ∨ m7, 主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.

真值表法

公式 (p → q) ∧ (q

从而主析取范式为m 0 ∨ m1 ∨ m3 ∨ m7, 主合取范式为M 2 ∧ M4 ∧ M5 ∧ M6.


相关文章

  • 离散数学答案
  • 2015春课件作业 第一部分 集合论 第一章 集合的基本概念和运算 1-1 设集合 A ={{2,3,4},5,1},下面命题为真是 A (选择题) [ A ] A .1 ∈A : B.2 ∈ A: C.3 ∈A : D.{3,2,1} ⊆ ...查看


  • 离散数学 第二章练习题答案
  • 一. 选择题 1.下列四个公式正确的是 ①∀x (A (x ) ∧B (x )) ⇒∀xA (x ) ∧∀xB (x ) ②∀x (A (x ) ∨B (x )) ⇒∀xA (x ) ∨∀xB (x ) ③∃x (A (x ) ∨B (x ...查看


  • 离散数学课后习题答案第一章
  • 第一章部分课后习题参考答案 16 设p .q 的真值为0:r .s 的真值为1,求下列各命题公式的真值. (1)p ∨(q∧r) ⇔ 0∨(0∧1) ⇔0 (2)(p r )∧(﹁q ∨s) ⇔(01)∧(1∨1) ⇔0∧1⇔0. (3)( ...查看


  • 离散数学第二章
  • 2.1 等值式 一.等值式的概念 两公式什么时候代表了同一个命题呢?抽象地看,它们的真假取值完全相同时即代表了相同的命题. 设公式A,B 共同含有n 个命题变项,可能A 或B 若A 与B 则说明在2n 个赋值的每个赋值下,A 与B 的真值都 ...查看


  • 离散数学(屈婉玲)答案
  • 第一章部分课后习题参考答案 16 设p .q 的真值为0:r .s 的真值为1,求下列各命题公式的真值. (1)p ∨(q∧r) ⇔ 0∨(0∧1) ⇔0 (2)(p r )∧(﹁q ∨s) ⇔(01)∧(1∨1) ⇔0∧1⇔0. (3)( ...查看


  • [离散数学]同步练习答案
  • 华南理工大学网络教育学院 <离散数学>练习题参考答案 第一章命题逻辑 一填空题 (1)设:p :派小王去开会.q :派小李去开会.则命题: "派小王或小李中的一人去开会" 可符号化 为: (p ∨⌝q ) ∧ ...查看


  • 命题逻辑在数学解题中的应用
  • 命题逻辑在数学解题中的应用 学生姓名: 指导老师: 一.引言 在一些数学竞赛和考试中我们经常会遇到一些很难推断推理的题,它们一般是 用自然语言表述的,容易引起歧义,这时如果用一般的推断推理方法时,需要进行 多个假设,即使通过很复杂的假设能够 ...查看


  • fg习题四重言式与蕴含式
  • 习题四:重言式与蕴含式 1.试证下列各式为重言式. (1) (2) (3) (4) (P ∧(P →Q )) →Q ⌝P →(P →Q ) ((P →Q ) ∧(Q →R )) →(P →R ) ((a ∧b ) ∨(b ∧c ) ∨(c ...查看


  • 第1章 离散数学习题解答
  • 习题1.1 1. 下列句子中,哪些是命题?哪些不是命题?如果是命题,指出它的真值. ⑴ 中国有四大发明. ⑵ 计算机有空吗? ⑶ 不存在最大素数. ⑷ 21+3<5. ⑸ 老王是山东人或河北人. ⑹ 2与3都是偶数. ⑺ 小李在宿舍里 ...查看


热门内容