发布时间 : 星期日 文章离散数学课后习题答案(左孝凌版)更新完毕开始阅读
前束合取范式
习题2-7 (1) 证明:
(2) a) ①(?x)(┐A(x)→B(x)) P ②┐A(u)→B(u) US① ③( ?x)┐B(x) P ④┐B(u) US③ ⑤A(u)∨B(u) T②E ⑥A(u) T④⑤I ⑦ ( ?x)A(x) EG⑥
b) ①┐( ?x)(A(x)→B(x)) P(附加前提)②( ?x)┐(A(x)→B(x)) T①E ③┐(A(c)→B(c)) ES② ④A(c) T③I ⑤┐B(c) T③I ⑥( ?x)A(x) EG④ ⑦ (?x)A(x)→(?x)B(x) P ⑧(?x)B(x) T⑥⑦I ⑨B(c) US⑧ ⑩B(c)∧ ┐B(c) T⑤⑨矛盾 c)①(?x)(A(x)→B(x)) P ②A(u)→B(u) US① ③( ?x)(C(x)→┐B(x)) P ④C(u)→┐B(u) US③ ⑤┐B(u) →┐A(u) T②E ⑥C(u)→┐A(u) T④⑤I ⑦(?x)(C(x)→┐A(x)) UG⑥ d) (?x)(A(x)∨B(x)),( ?x)(B(x)→┐C(x)),( ?x)C(x)? (?x)A(x) ①( ?x)(B(x)→┐C(x)) P ②B(u)→┐C(u) US① ③( ?x)C(x) P ④C(u) US③
⑤┐B(u) T②④I ⑥ (?x)(A(x)∨B(x)) P ⑦A(u)∨B(u) US ⑧A(u) T⑤⑦I ⑨(?x)A(x) UG⑧ (2) 证明:
a)①( ?x)P(x) P(附加前提) ②P(u) US① ③(?x)(P(x)→Q(x)) P ④P(u)→Q(u) US③ ⑤Q(u) T②④I ⑥(?x)Q(x) UG⑤ ⑦( ?x)P(x)→(?x)Q(x) CP b)因为(?x)P(x)∨(?x)Q(x)?┐(?x)P(x) →(?x)Q(x)
故本题就是推证(?x)(P(x)∨Q(x))?? ┐(?x)P(x) →(?x)Q(x) ①┐(?x)P(x) P(附加前提) ②( ?x)┐P(x) T①E ③┐P(c) ES② ④(?x)(P(x)∨Q(x)) P ⑤P(c)∨Q(c) ES④ ⑥Q(c) T③⑤I ⑦( ?x) Q(x) EG⑥ ⑧┐(?x)P(x) →(?x)Q(x) CP (3)
解:a)设R(x):x是实数。Q(x):x是有理数。I(x):x是整数。
本题符号化为:
(?x)(Q(x) →R(x)) ∧(?x)(Q(x) ∧I(x))?? (?x)(R(x) ∧I(x)) ①(?x)(Q(x) ∧I(x)) P ②Q(c) ∧I(c) ES① ③(?x)(Q(x) →R(x)) P ④Q(c) →R(c) US③ ⑤Q(c) T②I ⑥ R(c) T④⑤I
⑦I(c) T②I ⑧R(c)∧I(c) T⑥⑦I ⑨(?x)(R(x) ∧I(x)) EG⑧
b)设P(x):x喜欢步行。Q(x):x喜欢乘汽车。R(x):x喜欢骑自行车 本题符号化为:
(?x)(P(x) →┐Q(x)), (?x)(Q(x) ∨R(x)) , (?x) ┐R(x)?? (?x) ┐P(x) ①(?x) ┐R(x) P ②┐R (c) ES① ③(?x)(Q(x) ∨R(x)) P ④Q(c) ∨R(c) US③ ⑤Q(c) T②④I ⑥ (?x)(P(x) →┐Q(x)) P ⑦P(c) →┐Q(c) US⑥ ⑧┐P (c) T⑤⑦I ⑨(?x) ┐P(x) EG⑧
c) 每个大学生不是文科学生就是理工科学生,有的大学生是优等生,小张不是理工科学生,但他是优等生,因而如果小张是大学生,他就是文科学生。
设G(x):x是大学生。L(x):x是文科学生。P(x):x是理工科学生。 S(x):x是优秀生。c:小张。 本题符号化为:
(?x)(G(x) →L(x)∨P(x)), (?x)(G(x) ∧ S(x)), ┐P (c) , S(c) ? G(c) →L(c) ①G(c) P(附加前提) ②(?x)(G(x) →L(x)∨P(x)) P ③G(c) →L(c)∨P(c) US② ④L(c)∨P(c) T①③I ⑤┐P (c) P ⑥ L(c) T④⑤I ⑦G(c) →L(c) CP
注意:本题推证过程中未用到前提(?x)(G(x) ∧ S(x))以及S(c)。主要是S(x):x是优秀
生,这个条件与其他前提的联系对证明结论没有影响,因S(x)与其他前提不矛盾,故本题的推证仍是有效的。
3-5.1 列出所有从X={a,b,c}到Y={s}的关系。 解:Z1={} Z2={} Z3={