当前位置:文档之家› 最新离散数学-第二章命题逻辑等值演算习题及答案

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

第二章作业 1 评分要求:
2 1. 每小题6分: 结果正确1分; 方法格式正确3分; 计算过程2分. 合计48
3 分
4 2. 给出每小题得分(注意: 写出扣分理由)
5 3. 总得分在采分点1处正确设置.
6 一. 证明下面等值式(真值表法, 解逻辑方程法, 等值演算法, 三种方
7 法每种方法至少使用一次):
8 说明
9 证
10 1. p ⇔(p ∧q)∨(p ∧¬q) 11
解逻辑方程法
12 设 p ↔((p ∧q)∨(p ∧¬q)) =0, 分两种情况讨论:
13
⎩⎨
⎧=⌝∧∨∧=0)()(1
)1(q p q p p 或者 14
⎩⎨
⎧=⌝∧∨∧=1
)()(0
)2(q p q p p 15
(1)(2)两种情况均无解, 从而, p ↔(p ∧q)∨(p ∧¬q)无成假赋值, 为永真式. 16
等值演算法
17 (p ∧q)∨(p ∧¬q)
18 ⇔ p ∧(q ∨¬q) ∧对∨的分配率
19
⇔ p ∧1 排中律
20
⇔ p 同一律
21
真值表法
22
即 p↔ ((p∧q)∨(p∧¬q))为永真式, 得证23
2. (p→q)∧(p→r)⇔p→(q∧r)
24
等值演算法
25
(p→q)∧(p→r)
26
⇔ (¬p∨q)∧(¬p∨r)蕴含等值式
27
⇔¬p∨(q∧r)析取对合取的分配律
28
⇔ p→(q∧r)蕴含等值式
29
3. ¬(p↔q)⇔(p∨q)∧¬(p∧q)
30
等值演算法
31
¬(p↔q)
32
⇔¬( (p→q)∧(q→p) )等价等值式
33
⇔¬( (¬p∨q)∧(¬q∨p) )蕴含等值式
34
⇔¬( (¬p∧¬q)∨(p∧q) )合取对析取分配律, 矛盾律, 同一律
35
⇔ (p∨q)∧¬(p∧q)德摩根律
36
4. (p∧¬q)∨(¬p∧q)⇔(p∨q)∧¬(p∧q)
37
等值演算法
38
(p∧¬q)∨(¬p∧q)
39
⇔ (p∨q)∧¬(p∧q)析取对合取分配律, 排中律, 同一律
40
41
说明: 用真值表法和解逻辑方程法证明相当于证明为永真式.
42
等值演算法证明时每一步后面最好注明理由以加深印象, 熟练后可以不写.
43
由于等值演算法证明具有较强的技巧性, 平时应注意总结心得.
44
45
二. 求下列公式的主析取范式与主合取范式(等值演算法与用成真赋值或成
46
假赋值求解都至少使用一次):
47
1.
48
2.
49
3.
50
4.
51
52
53
54
1. (¬p→q)→(¬q∨p)
55

56
(¬p→q)→(¬q∨p)
57
⇔ (p∨q)→(¬q∨p)蕴含等值式
58
⇔ (¬p∧¬q)∨(¬q∨p)蕴含等值式, 德摩根律59
⇔(¬p∧¬q)∨¬q ∨ p结合律
60
⇔ p∨¬q吸收律, 交换律
61
⇔ M1
62
因此, 该式的主析取范式为m
0∨m
2
∨m
3
63
64
2. (¬p→q)∧(q∧r)
65
解逻辑方程法
66
设 (¬p→q)∧(q∧r) =1, 则¬p→q=1且 q∧r=1, 67
解得q=1, r=1, p=0 或者 q=1, r=1, p=1, 从而所求主析取范式为 m
3∨m
7
, 主
68
合取范式为M
0∧M
1
∧M
2
∧M
4
∧M
5
∧M
6
69
70
等值演算法
71
(¬p→q)∧(q∧r)
72
(p q)(q r) 蕴含等值式
73
(p q r)(q r) 对分配律, 幂等律
74
(p q r) (p q r)(p q r) 同一律, 矛盾律, 对分配75

76
m
7 m
3
77
主合取范式为M
0∧M
1
∧M
2
∧M
4
∧M
5
∧M
6
78
79
3. (p↔q)→r
80
解逻辑方程法
81
设 (p↔q)→r =0, 解得 p=q=1, r=0 或者 p=q=0, r=0, 从而所求主合取范式82
为M
0∧M
6
, 主析取范式为m
1
∨m
2
∨m
3
∨m
4
∨m
5
∨m
7
83
84
等值演算法
85
(p↔q)→r
86
((p q)(q p))r 等价等值式
87
((p q)(q p))r 蕴含等值式
88
(p q)(q p)r 德摩根律, 蕴含等值式的否定(参见PPT) 89
(p q r)(q p r) 对分配律, 矛盾律, 同一律90
M
0 M
6
91
主析取范式为m
1∨m
2
∨m
3
∨m
4
∨m
5
∨m
7
92
93
4. (p→q)∧(q→r) 94

95
等值演算法
96
(p→q)∧(q→r)
97
(p q)(q r) 蕴含等值式
98
(p q)(p r)(q r) 对分配律, 矛盾律, 同一律
99
(p q r)(p q r) (p q r)(p q r) 100
(p q r)(p q r)
101
m
1 m
m
3
m
7
102
主合取范式为M
2 M
4
M
5
M
6
.
103
104
解逻辑方程法
105
设 (p q) (q r) = 1, 则p q =1 且 q r =1. 106
前者解得: p=0, q=0; 或者 p=0, q=1; 或者 p=1, q=1.
107
后者解得: q=0, r=0; 或者 q=0, r=1; 或者 q=1, r=1.
108
综上可得成真赋值为 000, 001, 011, 111, 从而主析取范式为m
0 m
1
m
3
109
m
7, 主合取范式为M
2
M
4
M
5
M
6
.
110
111
真值表法
112
公式 (p q) (q r) 真值表如下:
113
p q r(p q) (q
r) 0001 0011 0100 0111 1000 1010 1100 1111
从而主析取范式为m
0 m
1
m
3
m
7
, 主合取范式为M
2
M
4
M
5
M
6
.
114。

相关主题