第1章 离散数学习题解答(8)

第1章 习题解答

⑵(t∨s)→p ⑶p

⑷p→(q∨r) ⑸q∨r

⑵p∧q，(p?q)→(t∨s)?(t∨s) 证明:

⑴p∧q ⑵p ⑶q ⑷p→q ⑸q→p

⑹(p→q)∧(q→p) ⑺p?q

⑻(p?q)→(t∨s) ⑼t∨s

P

T⑴⑵假言推理 P

T⑶⑷假言推理

P

T⑴化简律 T⑴化简律 T⑶例1.30(2) T⑵例1.30(2) T⑷⑸合取引入 T⑹双条件等价式 P

T⑺⑻假言推理

⑶?(p→q)→?(r∨s)，(q→p)∨?r,r?p?q 证明:

⑴r P ⑵(q→p)∨?r P ⑶q→p T⑴⑵析取三段论 ⑷r∨s T⑴附加律 ⑸?(p→q)→?(r∨s) P ⑹p→q T⑷⑸拒取式 ⑺(p→q)∧(q→p) T⑶⑹合取引入 ⑻p?q T⑹双条件等价式

⑷p∧q→r，?r∨s，?s??p∨?q 证明:

⑴?s P ⑵?r∨s P ⑶?r T⑴⑵析取三段论 ⑷p∧q→r P ⑸?(p∧q) T⑶⑷拒取式 ⑹?p∨?q T⑸德·摩根律

⑸p∨?p,p→q,?p→q?q

证明:

36

第1章 习题解答

⑴?q ⑵p→q ⑶?p ⑷?p→q ⑸q

⑹?q∧q(矛盾)

⑹?p∨?s，p→q，r→s??p∨?r 证明:

⑴?(?p∨?r) ⑵p∧r ⑶p ⑷r ⑸r→s ⑹s

⑺?p∨?s ⑻?p

⑼?p∧p(矛盾)

P(附加前提) P

T⑴⑵拒取式 P

T⑶⑷假言推理 T⑴⑸合取引入

P(附加前提) T⑴条件等价式 T⑵化简律 T⑵化简律 P

T⑷⑸假言推理 P

T⑹⑺析取三段论 T⑶⑻合取引入

4.用CP规则推证下列各题的有效结论。 ⑴?p∨q,r→?q?p→?r 证明:

⑴p P(附加前提) ⑵?p∨q P ⑶q T⑴⑵析取三段论 ⑷r→?q P ⑸?r T⑶⑷拒取式 ⑹p→?r CP规则

⑵p∨q→r∧s，s∨t→u?p→u

证明:

⑴p ⑵p∨q

⑶p∨q→r∧s ⑷r∧s ⑸s ⑹s∨t ⑺s∨t→u ⑻u

P(附加前提) T⑴附加律 P

T⑵⑶假言推理 T⑷化简律 T⑸附加律 P

T⑹⑺假言推理

37

第1章 习题解答

⑼p→u

CP规则

⑶p→(q∧r)，?q∨s，(t→?u)→?s，q→(p∧?t)?q→t 证明:

⑴q P(附加前提) ⑵?q∨s P ⑶s T⑴⑵析取三段论 ⑷(t→?u)→?s P ⑸?(t→?u) T⑶⑷拒取式 ⑹?(? t∨?u) T⑸条件等价式 ⑺t∧u T⑹德·摩根律 ⑻t T⑺化简律 ⑼q→t CP规则

⑷p∨q，p→r，q→s?s∨r

证明:因为s∨r??s→r，原题可改写为：p∨q，p→r，q→s??s→r。

⑴?s P(附加前提) ⑵q→s P ⑶?q T⑴⑵拒取式 ⑷p∨q P ⑸p T⑶⑷析取三段论 ⑹p→r P ⑺r T⑸⑹假言推理 ⑻?s→r CP规则

⑸p∧q→r，?r∨s，p→?s?p→?q

证明:

⑴p

⑵p→?s ⑶?s ⑷?r∨s ⑸?r

⑹p∧q→r ⑺?(p∧q) ⑻?p∨?q ⑼?q ⑽p→?q

⑹p→r∧q，?s∨p，r?s→q

P(附加前提) P

T⑴⑵假言推理 P

T⑶⑷析取三段论 P

T⑸⑹拒取式 T⑺德·摩根律 T⑴⑻析取三段论 CP规则

38

第1章 习题解答

证明:

⑴s

⑵?s∨p ⑶p

⑷p→r∧q ⑸r∧q ⑹q ⑺s→q

5.用归谬法推证下列各题的有效结论。 ⑴p∧q，(p?q)→(t∨s)?t∨s 证明:

⑴?(t∨s)

⑵(p?q)→(t∨s) ⑶?(p?q)

⑷?((p∧q)∨(?p∧?q)) ⑸?(p∧q)∧? (?p∧?q) ⑹?(p∧q) ⑺p∧q

⑻(p∧q)∧?(p∧q)(矛盾)

⑵r→?q，r∨s，s→?q，p→q??p 证明:

⑴??p ⑵p ⑶p→q ⑷q

⑸r→?q ⑹?r ⑺r∨s ⑻s

⑼s→?q ⑽?q

⑾q∧?q（矛盾）

⑶p→q，(?q∨r)∧?r，?(?p∧s)??s 证明:

⑴??s ⑵s

P(附加前提) P

T⑴⑵析取三段论 P

T⑶⑷假言推理 T⑸化简律 CP规则

P(附加前提) P

T⑴⑵拒取式 T⑶例1.17 T⑷德·摩根律 T⑸化简律 P

T⑹⑺合取引入

P(附加前提) T⑴双重否定律 P

T⑵⑶假言推理 P

T⑷⑸拒取式 P

T⑹⑺析取三段论 P

T⑻⑼假言推理 T⑷⑽合取引入

P(附加前提) T⑴双重否定律

39

第1章 习题解答

⑶?(?p∧s) ⑷p∨?s ⑸p ⑹p→q ⑺q

⑻(?q∨r)∧?r ⑼?q∨r ⑽?r ⑾r

⑿r∧?r(矛盾)

P

T⑶德·摩根律 T⑵⑷析取三段论 P

T⑸⑹假言推理 P

T⑻化简律 T⑻化简律

T⑺⑼析取三段论 T⑽⑾合取引入

⑷(p→q)∧(r→s)，(q→t)∧(s→u)，?(t∧u)，p→r??p 证明:

⑴??p P(附加前提) ⑵p T⑴双重否定律 ⑶p→r P ⑷r T⑵⑶假言推理 ⑸(p→q)∧(r→s) P ⑹p→q T⑸化简律 ⑺r→s T⑸化简律 ⑻q T⑵⑹假言推理 ⑼s T⑷⑺假言推理 ⑽(q→t)∧(s→u) P ⑾q→t T⑽化简律 ⑿s→u T⑽化简律 ⒀t T⑻⑾假言推理 ⒁u T⑼⑿假言推理 ⒂t∧u T⒀⒁合取引入 ⒃?(t∧u) P ⒄(t∧u)∧(?(t∧u))(矛盾) T⒂⒃合取引入

⑸p→(q∨r)，(t∨s)→p，(t∨s)?q∨r

证明：

⑴?(q∨r) ⑵p→(q∨r) ⑶?p

⑷(t∨s)→p ⑸?(t∨s) ⑹(t∨s)

P(附加前提) P

T⑴⑵拒取式 P

T⑶⑷拒取式 P

40

第1章 习题解答

⑺?(t∨s)∧(t∨s)(矛盾)

T⑸⑹合取引入

⑹p→q，r→?q，r??p 证明：

⑴??p P(附加前提) ⑵p T⑴双重否定律 ⑶p→q P ⑷q T⑵⑶假言推理 ⑸r→?q P ⑹?r T⑷⑸拒取式 ⑺r P ⑻r∧?r（矛盾） T⑹⑺合取引入

6. 证明下面各命题推得的结论是有效的：如果今天是星期三，那么我有一次离散数学或数字逻辑测验。如果离散数学课老师有事，那么没有离散数学测验。今天是星期三且离散数学老师有事。所以，我有一次数字逻辑测验。

证明：设 p：今天是星期三。

q：我有一次离散数学测验。 r：我有一次数字逻辑测验。 s：离散数学课老师有事。

该推理就是要证明：p→(q∨r)，s→?q，p∧s?r

⑴p∧s P ⑵p T⑴化简律 ⑶s T⑴化简律 ⑷s→?q P ⑸?q T⑶⑷假言推理 ⑹p→(q∨r) P ⑺q∨r T⑵⑹假言推理 ⑻r T⑸⑺析取三段论

41