离散数学课后习题答案 |
您所在的位置:网站首页 › 图书馆宣传海报背景 › 离散数学课后习题答案 |
1-1,1-2 (1) 解: a) 是命题,真值为T。 b) 不是命题。 c) 是命题,真值要根据具体情况确定。 d) 不是命题。 e) 是命题,真值为T。 f) 是命题,真值为T。 g) 是命题,真值为F。 h) 不是命题。 i) 不是命题。 (2) 解: 原子命题:我爱北京天安门。 复合命题:如果不是练健美操,我就出外旅游拉。 (3) 解: a) (┓P ∧R)→Q b) Q→R c) ┓P d) P→┓Q (4) 解: a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q« (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 (Q→R)∧(R→Q):一个数是奇数,则它不能被2整除并且一个数不能被2整除,则它是奇数。 (5) 解: a) 设P:王强身体很好。Q:王强成绩很好。P∧Q b) 设P:小李看书。Q:小李听音乐。P∧Q c) 设P:气候很好。Q:气候很热。P∨Q d) 设P: a和b是偶数。Q:a+b是偶数。P→Q e) 设P:四边形ABCD是平行四边形。Q :四边形ABCD的对边平行。P«Q f) 设P:语法错误。Q:程序错误。R:停机。(P∨ Q)→ R (6) 解: a) P:天气炎热。Q:正在下雨。 P∧Q b) P:天气炎热。R:湿度较低。 P∧R c) R:天正在下雨。S:湿度很高。 R∨S d) A:刘英上山。B:李进上山。 A∧B e) M:老王是革新者。N:小李是革新者。 M∨N f) L:你看电影。M:我看电影。 ┓L→┓M g) P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h) P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 (1)解: a) 不是合式公式,没有规定运算符次序(若规定运算符次序后亦可作为合式公式) b) 是合式公式 c) 不是合式公式(括弧不配对) d) 不是合式公式(R和S之间缺少联结词) e) 是合式公式。 (2)解: a) A是合式公式,(A∨B)是合式公式,(A→(A∨B)) 是合式公式。这个过程可以简记为: A;(A∨B);(A→(A∨B)) 同理可记 b) A;┓A ;(┓A∧B) ;((┓A∧B)∧A) c) A;┓A ;B;(┓A→B) ;(B→A) ;((┓A→B)→(B→A)) d) A;B;(A→B) ;(B→A) ;((A→B)∨(B→A)) (3)解: a) ((((A→C)→((B∧C)→A))→((B∧C)→A))→(A→C)) b) ((B→A)∨(A→B))。 (4)解: a) 是由c) 式进行代换得到,在c) 中用Q代换P, (P→P)代换Q. d) 是由a) 式进行代换得到,在a) 中用 P→(Q→P)代换Q. e) 是由b) 式进行代换得到,用R代换P, S代换Q, Q代换R, P代换S. (5)解: a) P: 你没有给我写信。 R: 信在途中丢失了。 P Q b) P: 张三不去。Q: 李四不去。R: 他就去。 (P∧Q)→R c) P: 我们能划船。 Q: 我们能跑步。 ┓(P∧Q) d) P: 你来了。Q: 他唱歌。R: 你伴奏。 P→(Q«R) (6)解: P:它占据空间。 Q:它有质量。 R:它不断变化。 S:它是物质。 这个人起初主张:(P∧Q∧R) « S 后来主张:(P∧Q«S)∧(S→R) 这个人开头主张与后来主张的不同点在于:后来认为有P∧Q必同时有R,开头时没有这样的主张。 (7)解: a) P: 上午下雨。 Q:我去看电影。 R:我在家里读书。 S:我在家里看报。(┓P→Q)∧(P→(R∨S)) b) P: 我今天进城。Q:天下雨。┓Q→P c) P: 你走了。 Q:我留下。Q→P 1-4 (4)解:a) P Q R Q∧R P∧(Q∧R) P∧Q (P∧Q)∧R T T T T T F T F T T F F F T T F T F F F T F F F T F F F T F F F T F F F F F F F T T F F F F F F T F F F F F F F 所以,P∧(Q∧R) Û (P∧Q)∧R b) P Q R Q∨R P∨(Q∨R) P∨Q (P∨Q)∨R T T T T T F T F T T F F F T T F T F F F T F F F T T T F T T T F T T T T T T T F T T T T T T F F T T T T T T T F 所以,P∨(Q∨R) Û (P∨Q)∨R c) P Q R Q∨R P∧(Q∨R) P∧Q P∧R (P∧Q)∨(P∧R) T T T T T F T F T T F F F T T F T F F F T F F F T T T F T T T F T T T F F F F F T T F F F F F F T F T F F F F F T T T F F F F F 所以,P∧(Q∨R) Û (P∧Q)∨(P∧R) d) P Q ┓P ┓Q ┓P∨┓Q ┓(P∧Q) ┓P∧┓Q ┓(P∨Q) T T T F F T F F F F T T F T F T F T T T F T T T F F F T F F F T 所以,┓(P∧Q) Û┓P∨┓Q, ┓(P∨Q) Û┓P∧┓Q (5)解:如表,对问好所填的地方,可得公式F1~F6,可表达为 P Q R F1 F2 F3 F4 F5 F6 T T T T F T T F F T T F F F T F F F T F T T F F T T F T F F F T F T T F F T T T F F T T F F T F T F F F T F F F T T F T T T F F F F F T F T T T F1:(Q→P)→R F2:(P∧┓Q∧┓R)∨(┓P∧┓Q∧┓R) F3:(P←→Q)∧(Q∨R) F4:(┓P∨┓Q∨R)∧(P∨┓Q∨R) F5:(┓P∨┓Q∨R)∧(┓P∨┓Q∨┓R) F6:┓(P∨Q∨R) (6) P Q 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 F F F T F T F T F T F T F T F T F T F T F F T T F F T T F F T T F F T T T F F F F F T T T T F F F F T T T T T T F F F F F F F F T T T T T T T T 解:由上表可得有关公式为 1.F 2.┓(P∨Q) 3.┓(Q→P) 4.┓P 5.┓(P→Q) 6.┓Q 7.┓(P«Q) 8.┓(P∧Q) 9.P∧Q 10.P«Q 11.Q 12.P→Q 13.P 14.Q→P 15.P∨Q 16.T (7) 证明: a) A→(B→A)Û ┐A∨(┐B∨A) Û A∨(┐A∨┐B) Û A∨(A→┐B) Û┐A→(A→┐B) b) ┐(A«B) Û┐((A∧B)∨(┐A∧┐B)) Û┐((A∧B)∨┐(A∨B)) Û(A∨B)∧┐(A∧B) 或 ┐(A«B) Û┐((A→B)∧(B→A)) Û┐((┐A∨B)∧(┐B∨A)) Û┐((┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)) Û┐((┐A∧┐B)∨(B∧A)) Û┐(┐(A∨B))∨(A∧B) Û(A∨B)∧┐(A∧B) c) ┐(A→B) Û ┐(┐A∨B) ÛA∧┐B d) ┐(A«B)Û┐((A→B)∧(B→A)) Û┐((┐A∨B)∧(┐B∨A)) Û(A∧┐B)∨(┐A∧B) e) (((A∧B∧C)→D)∧(C→(A∨B∨D))) Û(┐(A∧B∧C)∨D)∧(┐C∨(A∨B∨D)) Û(┐(A∧B∧C)∨D)∧(┐(┐A∧┐B∧C)∨D) Û (┐(A∧B∧C)∧┐(┐A∧┐B∧C))∨D Û((A∧B∧C)∨(┐A∧┐B∧C))→D Û (((A∧B)∨(┐A∧┐B))∧C)→D Û ((C∧(A«B))→D) f) A→(B∨C) Û ┐A∨(B∨C) Û (┐A∨B)∨C Û┐(A∧┐B)∨C Û (A∧┐B)→C g) (A→D)∧(B→D)Û(┐A∨D)∧(┐B∨D) Û(┐A∧┐B)∨D Û ┐(A∨B)∨D Û (A∨B)→D h) ((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) « (┐A∨B))∧C ÛT∧C ÛC b) A∨(┐A∨(B∧┐B)) Û (A∨┐A)∨(B∧┐B) ÛT∨F ÛT c) (A∧B∧C)∨(┐A∧B∧C) Û (A∨┐A) ∧(B∧C) ÛT∧(B∧C) ÛB∧C (9)解:1)设C为T,A为T,B为F,则满足A∨CÛB∨C,但AÛB不成立。 2)设C为F,A为T,B为F,则满足A∧CÛB∧C,但AÛB不成立。 3)由题意知┐A和┐B的真值相同,所以A和B的真值也相同。 习题 1-5 (1) 证明: a) (P∧(P→Q))→Q Û (P∧(┐P∨Q))→Q Û(P∧┐P)∨(P∧Q)→Q Û(P∧Q)→Q Û┐(P∧Q)∨Q Û┐P∨┐Q∨Q Û┐P∨T ÛT b) ┐P→(P→Q) ÛP∨(┐P∨Q) Û (P∨┐P)∨Q ÛT∨Q ÛT c) ((P→Q)∧(Q→R))→(P→R) 因为(P→Q)∧(Q→R)Þ(P→R) 所以 (P→Q)∧(Q→R)为重言式。 d) ((a∧b)∨(b∧c) ∨(c∧a))«(a∨b)∧(b∨c)∧(c∨a) 因为((a∧b)∨(b∧c)∨(c∧a)) Û((a∨c)∧b)∨(c∧a) Û((a∨c)∨(c∧a))∧(b∨(c∧a)) Û(a∨c)∧(b∨c)∧(b∨a) 所以((a∧b)∨(b∧c) ∨(c∧a))«(a∨b)∧(b∨c)∧(c∨a) 为重言式。 (2) 证明: a)(P→Q)ÞP→(P∧Q) 解法1: 设P→Q为T (1)若P为T,则Q为T,所以P∧Q为T,故P→(P∧Q)为T (2)若P为F,则Q为F,所以P∧Q为F,P→(P∧Q)为T 命题得证 解法2: 设P→(P∧Q)为F ,则P为T,(P∧Q)为F ,故必有P为T,Q为F ,所以P→Q为F。 解法3: (P→Q) →(P→(P∧Q)) Û┐(┐P∨Q)∨(┐P∨(P∧Q)) Û┐(┐P∨Q)∨((┐P∨P)∧(┐P∨Q)) ÛT 所以(P→Q)ÞP→(P∧Q) b)(P→Q)→QÞP∨Q 设P∨Q为F,则P为F,且Q为F, 故P→Q为T,(P→Q)→Q为F, 所以(P→Q)→QÞP∨Q。 c)(Q→(P∧┐P))→(R→(R→(P∧┐P)))ÞR→Q 设R→Q为F,则R为T,且Q为F,又P∧┐P为F 所以Q→(P∧┐P)为T,R→(P∧┐P)为F 所以R→(R→(P∧┐P))为F,所以(Q→(P∧┐P))→(R→(R→(P∧┐P)))为F 即(Q→(P∧┐P))→(R→(R→(P∧┐P)))ÞR→Q成立。 (3) 解: a) P→Q表示命题“如果8是偶数,那么糖果是甜的”。 b) a)的逆换式Q→P表示命题“如果糖果是甜的,那么8是偶数”。 c) a)的反换式┐P→┐Q表示命题“如果8不是偶数,那么糖果不是甜的”。 d) a)的逆反式┐Q→┐P表示命题“如果糖果不是甜的,那么8不是偶数”。 (4) 解: a) 如果天下雨,我不去。 设P:天下雨。Q:我不去。P→Q 逆换式Q→P表示命题:如果我不去,则天下雨。 逆反式┐Q→┐P表示命题:如果我去,则天不下雨 b) 仅当你走我将留下。 设S:你走了。R:我将留下。R→S 逆换式S→R表示命题:如果你走了则我将留下。 逆反式┐S→┐R表示命题:如果你不走,则我不留下。 c) 如果我不能获得更多帮助,我不能完成个任务。 设E:我不能获得更多帮助。H:我不能完成这个任务。E→H 逆换式H→E表示命题:我不能完成这个任务,则我不能获得更多帮助。 逆反式┐H→┐E表示命题:我完成这个任务,则我能获得更多帮助 (5) 试证明P«Q,Q逻辑蕴含P。 证明:解法1: 本题要求证明(P«Q) ∧QÞP, 设(P«Q) ∧Q为T,则(P«Q)为T,Q为T,故由«的定义,必有P为T。 所以(P«Q) ∧QÞP 解法2: 由体题可知,即证((P«Q)∧Q)→P是永真式。 ((P«Q)∧Q)→P Û (((P∧Q) ∨(┐P∧┐Q)) ∧Q)→P Û (┐((P∧Q) ∨(┐P∧┐Q)) ∨┐Q) ∨P Û (((┐P∨┐Q) ∧(P∨Q)) ∨┐Q) ∨P Û ((┐Q∨┐P∨┐Q) ∧(┐Q∨P∨Q)) ∨P Û ((┐Q∨┐P) ∧T) ∨P Û┐Q∨┐P∨P Û┐Q∨T ÛT (6) 解: P:我学习 Q:我数学不及格 R:我热衷于玩扑克。 如果我学习,那么我数学不会不及格: P→┐Q 如果我不热衷于玩扑克,那么我将学习: ┐R→P 但我数学不及格: Q 因此我热衷于玩扑克。 R 即本题符号化为:(P→┐Q)∧(┐R→P)∧QÞR 证: 证法1:((P→┐Q)∧(┐R→P)∧Q)→R Û ┐((┐P∨┐Q)∧(R∨P)∧Q) ∨R Û (P∧Q)∨(┐R∧┐P)∨┐Q∨R Û ((┐Q∨P)∧(┐Q∨Q))∨((R∨┐R)∧(R∨┐P)) Û ┐Q∨P∨R∨┐P Û T 所以,论证有效。 证法2:设(P→┐Q)∧(┐R→P)∧Q为T, 则因Q为T,(P→┐Q) 为T,可得P为F, 由(┐R→P)为T,得到R为T。 故本题论证有效。 (7) 解: P:6是偶数 Q:7被2除尽 R:5是素数 如果6是偶数,则7被2除不尽 P→┐Q 或5不是素数,或7被2除尽 ┐R∨Q 5是素数 R 所以6是奇数 ┐P 即本题符号化为:(P→┐Q)∧(┐R∨Q)∧R Þ┐P 证: 证法1:((P→┐Q)∧(┐R∨Q)∧R)→┐P Û ┐((┐P∨┐Q) ∧(┐R∨Q) ∧R) ∨┐P Û ((P∧Q) ∨(R∧┐Q) ∨┐R) ∨┐P Û ((┐P∨P) ∧(┐P∨Q)) ∨((┐R∨R) ∧(┐R∨┐Q)) Û (┐P∨Q) ∨(┐R∨┐Q) ÛT 所以,论证有效,但实际上他不符合实际意义。 证法2:(P→┐Q)∧(┐R∨Q)∧R为T, 则有R为T,且┐R∨Q 为T,故Q为T, 再由P→┐Q为T,得到┐P为T。 (8) 证明: a) PÞ(┐P→Q) 设P为T,则┐P为F,故┐P→Q为T b) ┐A∧B∧CÞC 假定┐A∧B∧C为T,则C为T。 c) CÞA∨B∨┐B 因为A∨B∨┐B为永真,所以CÞA∨B∨┐B成立。 d) ┐(A∧B) Þ┐A∨┐B 设┐(A∧B)为T,则A∧B为F。 若A为T,B为F,则┐A为F,┐B为T,故┐A∨┐B为T。 若A为F,B为T,则┐A为T,┐B为F,故┐A∨┐B为T。 若A为F,B为F,则┐A为T,┐B为T,故┐A∨┐B为T。 命题得证。 e) ┐A→(B∨C),D∨E,(D∨E)→┐AÞB∨C 设┐A→(B∨C),D∨E,(D∨E)→┐A为T, 则D∨E为T,(D∨E)→┐A为T,所以┐A为T 又┐A→(B∨C)为T,所以B∨C为T。命题得证。 f) (A∧B)→C,┐D,┐C∨DÞ┐A∨┐B 设(A∧B)→C,┐D,┐C∨D为T,则┐D为T,┐C∨D为T,所以C为F 又(A∧B)→C为T,所以A∧B为F,所以┐A∨┐B为T。命题得证。 (9)解: a) 如果他有勇气,他将得胜。 P:他有勇气 Q:他将得胜 原命题:P→Q 逆反式:┐Q→┐P 表示:如果他失败了,说明他没勇气。 b) 仅当他不累他将得胜。 P:他不累 Q:他得胜 原命题:Q→P 逆反式:┐P→┐Q 表示:如果他累,他将失败。 习题 1-6 (1)解: a) (P∧Q)∧┐PÛ(P∧┐P)∧QÛ┐(T∨Q) b) (P→(Q∨┐R)) ∧┐P∧Q Û (┐P∨(Q∨┐R))∧┐P∧Q Û(┐P∧┓P∧Q)∨(Q∧┓P∧Q)∨(┓R∧┓P∧Q) Û(┓P∧Q)∨(┓P∧Q)∨(┓P∧┓R∧Q) Û┓P∧Q Û┐(P∨┐Q) c) ┐P∧┐Q∧(┐R→P) Û┐P∧┐Q∧(R∨P) Û(┐P∧┐Q∧R)∨(┐P∧┐Q∧P) Û(┐P∧┐Q∧R)∨F Û┐P∧┐Q∧R Û┐(P∨Q∨┐R) (2) 解: a)┐PÛ P↓P b)P∨QÛ┐(P↓Q) Û (P↓Q)↓(P↓Q) c)P∧QÛ┐P↓┐QÛ (P↓P)↓(Q↓Q) (3)解: P→(┐P→Q) Û┐P∨(P∨Q) ÛT Û┐P∨P Û (┐P↑┐P)↑(P↑P) ÛP↑(P↑P) P→(┐P→Q) Û┐P∨(P∨Q) ÛT Û┐P∨P Û┐(┐P↓P) Û┐((P↓P)↓P) Û((P↓P)↓P)↓((P↓P)↓P) (4)解: P↑Q Û┐(┐P↓┐Q) Û┐((P↓P)↓(Q↓Q)) Û ((P↓P)↓(Q↓Q))↓((P↓P)↓(Q↓Q)) (5)证明: ┐(B↑C) Û┐(┐B∨┐C) Û ┐B↓┐C ┐(B↓C) Û┐(┐B∧┐C) Û┐B↑┐C (6)解:联结词“↑”和“↓”不满足结合律。举例如下: a)给出一组指派:P为T,Q为F,R为F,则(P↑Q)↑R为T,P↑(Q↑R)为F 故 (P↑Q)↑R P↑(Q↑R). b)给出一组指派:P为T,Q为F,R为F,则(P↓Q) ↓R为T,P↓(Q↓R)为F 故(P↓Q)↓R P↓(Q↓R). (7)证明: 设变元P,Q,用连结词«,┐作用于P,Q得到:P,Q,┐P,┐Q,P«Q,P«P,Q«Q,Q«P。 但P«QÛQ«P,P«PÛQ«Q,故实际有: P,Q,┐P,┐Q,P«Q,P«P(T) (A) 用┐作用于(A)类,得到扩大的公式类(包括原公式类): P,Q,┐P,┐Q,┐(P«Q), T,F, P«Q (B) 用«作用于(A)类,得到: P«Q,P«┐PÛF,P«┐QÛ┐(P«Q),P«(P«Q)ÛQ,P«(P«P)ÛP, Q«┐PÛ┐(P«Q),Q«┐QÛF,Q«(P«Q)ÛP,Q«TÛQ, ┐P«┐QÛP«Q,┐P«(P«Q)Û┐Q,┐P«TÛ┐P, ┐Q«(P«Q)Û┐P,┐Q«TÛ┐Q, (P«Q)«(P«Q)ÛP«Q. 因此,(A)类使用运算后,仍在(B)类中。 对(B)类使用┐运算得: ┐P,┐Q,P,Q, P«Q, F,T, ┐(P«Q), 仍在(B)类中。 对(B)类使用«运算得: P«Q,P«┐PÛF,P«┐QÛ┐(P«Q),P«┐(P«Q)Û┐Q,P«TÛP,P«FÛ┐P,P«(P«Q)ÛQ, Q«┐PÛ┐(P«Q),Q«┐QÛF,Q«┐(P«Q)Û┐P,Q«TÛQ, Q«FÛ┐Q, Q«(P«Q)ÛP, ┐P«┐QÛP«Q,┐P«┐(P«Q)ÛQ,┐P«TÛ┐P, ┐P«FÛP,┐P«(P«Q)Û┐Q, ┐Q«┐(P«Q)ÛP,┐Q«TÛ┐Q, ┐Q«TÛ┐Q,┐Q«(P«Q)Û┐P, ┐(P«Q)«TÛ┐(P«Q),┐(P«Q)«FÛP«Q,┐(P«Q)«(P«Q)ÛF T«FÛF,T«(P«Q)Û P«Q F«(P«Q)Û ┐(P«Q) (P«Q)«(P«Q)ÛP«Q. 故由(B)类使用«运算后,结果仍在(B)中。 由上证明:用«,┐两个连结词,反复作用在两个变元的公式中,结果只能产生(B)类中的公式,总共仅八个不同的公式,故{«,┐}不是功能完备的,更不能是最小联结词组。 已证{«,┐}不是最小联结词组,又因为P QÛ ┐(P«Q),故任何命题公式中的联结词,如仅用{ , ┐}表达,则必可用{«,┐}表达,其逆亦真。故{ , ┐}也必不是最小联结词组。 (8)证明{∨},{∧}和{→}不是最小联结词组。 证明:若{∨},{∧}和{→}是最小联结词,则 ┐PÛ(P∨P∨……) ┐PÛ(P∧P∧……) ┐PÛP→(P→(P→……) 对所有命题变元指派T,则等价式左边为F,右边为T,与等价表达式矛盾。 所以{∨},{∧}和{→}不是最小联结词。 (9)证明{┐,→}和{┐, }是最小联结词组。 证明:因为{┐,∨}为最小联结词组,且P∨QÛ┐P→Q 所以{┐,→}是功能完备的联结词组,又{┐},{→}都不是功能完备的联结词组。 所以{┐,→}是最小联结词组。 又因为P→QÛ┐(P Q),所以{┐, }是功能完备的联结词组,又{┐},{ }不是功能完备的联结词组, 所以{┐, }是最小联结词组。 习题 1-7 (1) 解: P∧(P→Q) ÛP∧(┐P∨Q) Û (P∧┐P)∨(P∧Q) P∧(P→Q) Û (P∨(┐Q∧Q))∧(┐P∨Q) Û (P∨┐Q)∧(P∨Q)∧(┐P∨Q) (2) 解: a) (┐P∧Q)→R Û┐(┐P∧Q)∨R Û P∨┐Q∨R Û(P∧Q)∨(P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(R∧P)∨(R∧┐P) b) P→((Q∧R)→S) Û┐P∨(┐(Q∧R)∨S) Û┐P∨┐Q∨┐R∨S Û(┐P∧Q)∨(┐P∧┐Q) ∨(┐Q∧R)∨(┐Q∧┐R)∨(┐R∧S)∨(┐R∧┐S)∨(S∧P)∨(S∧┐P) c) ┐(P∨┐Q)∧(S→T) Û(┐P∧Q)∧(┐S∨T) Û(┐P∧Q∧┐S)∨(┐P∧Q∧T) d) (P→Q)→R Û┐(┐P∨Q)∨R Û(P∧┐Q)∨R Û(P∨R)∧(┐Q∨R) e) ┐(P∧Q)∧(P∨Q) Û(┐P∨┐Q)∧(P∨Q) Û(┐P∧P)∨(┐P∧Q)∨(┐Q∧P)∨(┐Q∧Q) Û (┐P∧Q)∨(┐Q∧P) (3) 解: a) P∨(┐P∧Q∧R) Û(P∨┐P)∧(P∨Q)∧(P∨R) Û(P∨Q)∧(P∨R) b) ┐(P→Q)∨(P∨Q) Û┐(┐P∨Q)∨(P∨Q) Û(P∧┐Q)∨(P∨Q) Û(P∨P∨Q)∧(┐Q∨P∨Q) c) ┐(P→Q) Û┐(┐P∨Q) Û P∧┐Q Û(P∨Q)∧(P∨┐Q)∧(┐Q∨┐P) d) (P→Q)→R Û┐(┐P∨Q)∨R Û (P∧┐Q)∨R Û (P∨R)∧(┐Q∨R) e) (┐P∧Q)∨(P∧┐Q) Û(┐P∨P)∧(┐P∨┐Q)∧(Q∨P)∧(Q∨┐Q) Û(┐P∨┐Q)∧(Q∨P) (4) 解: a) (┐P∨┐Q)→(P«┐Q) Û┐(┐P∨┐Q) ∨(P«┐Q) Û (P∧Q) ∨(P∧┐Q)∨(┐P∧Q) Ûå1,2,3 ÛP∨Q=P0 b) Q∧(P∨┐Q) Û (P∧Q)∨(Q∧┐Q) Û P∧Q =å3 ÛP0,1,2 Û(P∨Q)∧(P∨┐Q) ∧(┐P∨Q) c) P∨(┐P→(Q∨(┐Q→R)) ÛP∨(P∨(Q∨(Q∨R)) ÛP∨Q∨R=P0 Ûå1,2,3,4,5,6,7 =(┐P∧┐Q∧R) ∨(┐P∧Q∧┐R) ∨(┐P∧Q∧R) ∨(P∧┐Q∧┐R) ∨(P∧┐Q∧R) ∨(P∧Q∧┐R) ∨(P∧Q∧R) d) (P→(Q∧R) )∧(┐P→(┐Q∧┐R)) Û (┐P∨(Q∧R)) ∧(P∨(┐Q∧┐R)) Û (P∧┐P) ∨(P∧(Q∧R)) ∨ ((┐Q∧┐R) ∧┐P) ∨((┐Q∧┐R) ∧(Q∧R)) Û (P∧Q∧R) ∨(┐P∧┐Q∧┐R) =å0,7 ÛP1,2,3,4,5,6 Û (P∨Q∨┐R) ∧(P∨┐Q∨R) ∧(P∨┐Q∨┐R) ∧(┐P∨Q∨R) ∧(┐P∨Q∨┐R) ∧(┐P∨┐Q∨R) e) P→(P∧(Q→P) Û┐P∨(P∧(┐Q∨P) Û(┐P∨P)∧(┐P∨┐Q∨P) ÛT∨(T∧┐Q) ÛT Ûå0,1,2,3= (┐P∧┐Q) ∨(┐P∧Q) ∨(P∧┐Q) ∨(P∧Q) f) (Q→P) ∧(┐P∧Q) Û (┐Q∨P) ∧┐P∧Q Û (┐Q∨P) ∧┐(P∨┐Q) ÛF ÛP0,1,2,3= (P∨Q) ∧(P∨┐Q) ∧(┐P∨Q) ∧(┐P∨┐Q) (5) 证明: a) (A→B) ∧(A→C) Û (┐A∨B) ∧(┐A∨C) A→(B∧C) Û┐A∨(B∧C) Û (┐A∨B) ∧(┐A∨C) b) (A→B) →(A∧B) Û┐(┐A∨B) ∨(A∧B) Û (A∧┐B) ∨(A∧B) ÛA∧(B∨┐B) ÛA∧T ÛA (┐A→B) ∧(B→A) Û (A∨B) ∧(┐B∨A) ÛA∨(B∧┐B) ÛA∨F ÛA c) A∧B∧(┐A∨┐B) Û ((A∧┐A)∨(A∧┐B))∧B ÛA∧B∧┐B ÛF ┐A∧┐B∧(A∨B) Û ((┐A∧A)∨(┐A∧B))∧┐B Û┐A∧┐B∧B ÛF d) A∨(A→(A∧B) ÛA∨┐A∨(A∧B) ÛT ┐A∨┐B∨(A∧B) Û┐(A∧B) ∨(A∧B) ÛT (6)解:AÛR↑(Q∧┐(R↓P)),则A*Û R↓(Q∨┐(R↑P)) AÛR↑(Q∧┐(R↓P)) Û┐(R∧(Q∧(R∨P))) Û┐R∨┐Q∨┐(R∨P) Û┐(R∧Q) ∨┐(R∨P) A*ÛR↓(Q∨┐(R↑P)) Û┐(R∨(Q∨(R∧P)) Û┐R∧┐Q∧┐(R∧P) Û┐(R∨Q) ∧┐(R∧P) (7) 解:设A:A去出差。B:B去出差。C:C去出差。D:D去出差。 若A去则C和D中要去一个。 A→(C D) B和C不能都去。 ┐(B∧C) C去则D要留下。 C→┐D 按题意应有:A→(C D),┐(B∧C),C→┐D必须同时成立。 因为C D Û (C∧┐D) ∨(D∧┐C) 故(A→(C D))∧┐(B∧C) ∧(C→┐D) Û (┐A∨(C∧┐D) ∨(D∧┐C)) ∧┐(B∧C) ∧(┐C∨┐D) Û (┐A∨(C∧┐D) ∨(D∧┐C)) ∧(┐B∨┐C) ∧(┐C∨┐D) Û (┐A∨(C∧┐D) ∨(D∧┐C)) ∧((┐B∧┐C) ∨(┐B∧┐D) ∨(┐C∧┐D) ∨┐C) Û (┐A∧┐B∧┐C) ∨(┐A∧┐B∧┐D) ∨(┐A∧┐C∧┐D) ∨(┐A∧┐C) ∨(┐B∧┐C∧D) ∨(┐C∧D∧┐B∧┐D) ∨(┐C∧D∧┐C∧┐D) ∨(┐C∧D∧┐C) ∨(┐D∧C∧┐B∧┐C) ∨(┐D∧C∧┐B∧┐D) ∨(┐D∧C∧┐C∧┐D) ∨(┐D∧C∧┐C) 在上述的析取范式中,有些(画线的)不符合题意,舍弃,得 (┐A∧┐C) ∨(┐B∧┐C∧D) ∨(┐C∧D)∨(┐D∧C∧┐B) 故分派的方法为:B∧D ,或 D∧A,或 C∧A。 (8) 解:设P:A是第一。Q:B是第二。R:C是第二。S:D是第四。E:A是第二。 由题意得 (P Q) ∧(R S) ∧(E S) Û ((P∧┐Q) ∨(┐P∧Q)) ∧((R∧┐S) ∨(┐R∧S)) ∧((E∧┐S) ∨(┐E∧S)) Û ((P∧┐Q∧R∧┐S) ∨(P∧┐Q∧┐R∧S) ∨(┐P∧Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S)∨(┐E∧S)) 因为 (P∧┐Q∧┐R∧S)与(┐P∧Q∧R∧┐S)不合题意,所以原式可化为 ((P∧┐Q∧R∧┐S) ∨(┐P∧Q∧┐R∧S))∧((E∧┐S) ∨(┐E∧S)) Û (P∧┐Q∧R∧┐S∧E∧┐S) ∨(P∧┐Q∧R∧┐S∧┐E∧S) ∨(┐P∧Q∧┐R∧S∧E∧┐S)∨(┐P∧Q∧┐R∧S∧┐E∧S) Û (P∧┐Q∧R∧┐S∧E) ∨(┐P∧Q∧┐R∧S∧┐E) 因R与E矛盾,故┐P∧Q∧┐R∧S∧┐E为真, 即A不是第一,B是第二,C不是第二,D为第四,A不是第二。 于是得: A是第三 B是第二 C是第一 D是第四。 习题1-8 (1)证明: a)┐(P∧┐Q),┐Q∨R,┐RÞ┐P (1) ┐R P (2) ┐Q∨R P (3) ┐Q (1)(2)T,I (4) ┐(P∧┐Q) P (5) ┐P∨Q (4)T,E (6) ┐P (3)(5)T,I b)J→(M∨N),(H∨G)→J,H∨GÞM∨N (1) (H∨G) →J P (2) (H∨G) P (3) J (1)(2)T,I (4) J→(M∨N) P (5) M∨N (3)(4)T,I c)B∧C,(B«C)→(H∨G) ÞG∨H (1) B∧C P (2) B (1)T,I (3) C (1)T,I (4) B∨┐C (2)T,I (5) C∨┐B (3)T,I (6) C→B (4)T,E (7) B→C (5)T,E (8) B«C (6)(7)T,E (9) (B«C) →(H∨G) P (10) H∨G (8)(9)T,I d)P→Q,(┐Q∨R)∧┐R,┐(┐P∧S) Þ┐S (1) (┐Q∨R) ∧┐R (2) ┐Q∨R (1)T,I (3) ┐R (1)T,I (4) ┐Q (2)(3)T,I (5) P→Q P (6) ┐P (4)(5)T,I (7) ┐(┐P∧┐S) P (8) P∨┐S (7)T,E (9) ┐S (6)(8)T,I (2) 证明: a)┐A∨B,C→┐BÞA→┐C (1) ┐(A→┐C) P (2) A (1)T,I (3) C (1)T,I (4) ┐A∨B P (5) B (2)(4)T,I (6) C→┐B P (7) ┐B (3)(6)T,I (8) B∧┐B 矛盾。(5),(7) b)A→(B→C),(C∧D)→E,┐F→(D∧┐E) ÞA→(B→F) (1) ┐(A→(B→F)) P (2) A (1)T,I (3) ┐(B→F) (1)T,I (4) B (3)T,I (5) ┐F (3)T, (6) A→(B→C) P (7) B→C (2)(6)T,I (8) C (4)(7)T,I (9) ┐F→(D∧┐E) P (10) D∧┐E (5)(9)T,I (11) D (10)T,I (12) C∧D (8)(11)T,I (13) (C∧D) →E P (14) E (12)(13)T,I (15) ┐E (10)T,I (16) E∧┐E 矛盾。(14),(15) c)A∨B→C∧D,D∨E→FÞA→F (1) ┐(A→F) P (2) A (1)T,I (3) ┐F (1)T,I (4) A∨B (2)T,I (5) (A∨B) →C∧D P (6) C∧D (4)(5)T,I (7) C (6)T,I (8) D (6)T,I (9) D∨E (8)T,I (10) D∨E→F P (11) F (9)(10)T,I (12) F∧┐F 矛盾。(3),(11) d)A→(B∧C),┐B∨D,(E→┐F)→┐D,B→(A∧┐E) ÞB→E (1) ┐(B→E) P (2) B (1)T,I (3) ┐E (1)T,I (4) ┐B∨D P (5) D (2)(4)T,I (6) (E→┐F) →┐D P (7) ┐(E→┐F) (5)(6)T,I (8) E (7)T,I (9) E∧┐E 矛盾 e)(A→B)∧(C→D),(B→E)∧(D→F),┐(E∧F),A→CÞ┐A (1) (A→B) ∧(C→D) P (2) A→B (1)T,I (3) (B→E) ∧(D→F) P (4) B→E (3)T,I (5) A→E (2)(4)T,I (6) ┐(E∧F) P (7) ┐E∨┐F (6)T,E (8) E→┐F (7)T,E (9) A→┐F (5)(8)T,I (10) C→D (1)T,I (11) D→F (3)T,I (12) C→F (10)(10)T,I (13) A→C P (14) A→F (13)(12)T,I (15) ┐F→┐A (14)T,E (16) A→┐A (9)(15)T,I (17) ┐A∨┐A (16)T,E (18) ┐A (17) T,E (3) 证明: a)┐A∨B,C→┐BÞA→┐C (1) A P (2) ┐A∨B P (3) B (1)(2)T,I (4) C→┐B P (5) ┐C (3)(4)T,I (6) A→┐C CP b)A→(B→C),(C∧D)→E,┐F→(D∧┐E) ÞA→(B→F) (1) A P (2) A→(B→C) P (3) B→C (1)(2)T,I (4) B P (5) C (3)(4)T,I (6) (C∧D) →E P (7) C→(D→E) (6)T,E (8) D→E (5)(7)T,I (9) ┐D∨E (8)T,E (10) ┐(D∧┐E) (9)T,E (11) ┐F→(D∧┐E) P (12) F (10)(11)T,I (13) B→F CP (14) A→(B→F) CP c)A∨B→C∧D,D∨E→FÞA→F (1) A P (2) A∨B (1)T,I (3) A∨B→C∨D P (4) C∧D (2)(3)T,I (5) D (4)T,I (6) D∨E (5)T,I (7) D∨E→F P (8) F (6)(7)T,I (9) A→F CP d)A→(B∧C),┐B∨D,(E→┐F)→┐D,B→(A∧┐E) ÞB→E (1) B P(附加前提) (2) ┐B∨D P (3) D (1)(2)T,I (4) (E→┐F)→┐D P (5) ┐(E→┐F) (3)(4)T,I (6) E (5)T,I (7) B→E CP (4)证明: a) R→┐Q,R∨S,S→┐Q,P→QÞ┐P (1) R→┐Q P (2) R∨S P (3) S→┐Q P (4) ┐Q (1)(2)(3)T,I (5) P→Q P (6) ┐P (4)(5)T,I b) S→┐Q,S∨R,┐R,┐P«QÞP 证法一: (1) S∨R P (2) ┐R P (3) S (1)(2)T,I (4) S→┐Q P (5) ┐Q (3)(4)T,I (6) ┐P«Q P (7)(┐P→Q)∧(Q→┐P) (6)T,E (8) ┐P→Q (7)T,I (9) P (5)(8)T,I 证法二:(反证法) (1) ┐P P(附加前提) (2) ┐P«Q P (3)(┐P→Q)∧( Q→┐P) (2)T,E (4) ┐P→Q (3)T,I (5) Q (1)(4)T,I (6) S→┐Q P (7) ┐S (5)(6)T,I (8) S∨R P (9) R (7)(8)T,I (10) ┐R P (11) ┐R∧R 矛盾(9)(10)T,I c)┐(P→Q)→┐(R∨S),((Q→P)∨┐R),RÞP«Q (1) R P (2) (Q→P) ∨┐R P (3) Q→P (1)(2)T,I (4)┐(P→Q) →┐(R∨S) P (5) (R∨S) →(P→Q) (4)T,E (6) R∨S (1)T,I (7) P→Q (5)(6) (8) (P→Q) ∧(Q→P) (3)(7)T,I (9) P«Q (8)T,E (5) 解: a) 设P:我跑步。Q:我很疲劳。 前提为:P→Q,┐Q (1) P→Q P (2) ┐Q P (3) ┐P (1)(2)T,I 结论为:┐P,我没有跑步。 b) 设S:他犯了错误。 R:他神色慌张。 前提为:S→R,R 因为(S→R)∧RÛ(┐S∨R)∧RÛR。故本题没有确定的结论。 实际上,若S →R为真,R为真,则S可为真,S也可为假,故无有效结论。 c) 设P:我的程序通过。 Q:我很快乐。 R:阳光很好。 S:天很暖和。(把晚上十一点理解为阳光不好) 前提为:P→Q,Q→R,┐R∧S (1) P→Q P (2) Q→R P (3) P→R (1)(2)T,I (4) ┐R∨S P (5) ┐R (4)T,I (6) ┐P (3)(5)T,I 结论为: ┐P,我的程序没有通过 习题2-1,2-2 (1) 解: a) 设W(x):x是工人。c:小张。 则有 ¬W(c) b) 设S(x):x是田径运动员。B(x):x是球类运动员。h:他 则有 S(h)ÚB(h) c) 设C(x):x是聪明的。B(x):x是美丽的。l:小莉。 则有 C(l)Ù B(l) d)设O(x):x是奇数。 则有 O(m)®¬ O(2m)。 e)设R(x):x是实数。Q(x):x是有理数。 则有 ("x)(Q(x)®R(x)) f) 设R(x):x是实数。Q(x):x是有理数。 则有 ($x)(R(x)ÙQ(x)) g) 设R(x):x是实数。Q(x):x是有理数。 则有 ¬("x)(R(x)®Q(x)) h)设P(x,y):直线x平行于直线y G(x,y):直线x相交于直线y。 则有 P(A,B)D¬G(A,B) (2) 解: a) 设J(x):x是教练员。L(x):x是运动员。 则有 ("x)(J(x)®L(x)) b) 设S(x):x是大学生。L(x):x是运动员。 则有 ($x)(L(x)ÙS(x)) c) 设J(x):x是教练员。O(x):x是年老的。V(x):x是健壮的。 则有 ($x)(J(x)ÙO(x)ÙV(x)) d) 设O(x):x是年老的。V(x):x是健壮的。j:金教练 则有 ¬ O(j)Ù¬V(j) e) 设L(x):x是运动员。J(x):x是教练员。 则 ¬("x)(L(x)®J(x)) 本题亦可理解为:某些运动员不是教练。 故 ($x)(L(x)Ù¬J(x)) f) 设S(x):x是大学生。L(x):x是运动员。C(x):x是国家选手。 则有 ($x)(S(x)ÙL(x)ÙC(x)) g) 设C(x):x是国家选手。V(x):x是健壮的。 则有 ("x)(C(x)®V(x))或¬($x)(C(x)Ù¬V(x)) h) 设C(x):x是国家选手。O(x):x是老的。L(x):x 是运动员。 则有 ("x)(O(x)ÙC(x)®L(x)) i) 设W(x):x是女同志。H(x):x是家庭妇女。C(x):x是国家选手。 则有 ¬($x)(W(x)ÙC(x)ÙH(x)) j) W(x):x是女同志。J(x):x是教练。C(x):x是国家选手。 则有($x)(W(x)ÙJ(x)ÙC(x)) k) L(x):x 是运动员。J(y):y是教练。A(x,y):x钦佩y。 则有 ("x)(L(x)® ($y)(J(y)ÙA(x,y))) l) 设S(x):x是大学生。L(x):x 是运动员。A(x,y):x钦佩y。 则($x)(S(x)Ù("y)(L(y)®¬ A(x,y))) 习题2-3 (1)解: a)5是质数。 b)2是偶数且2是质数。 c)对所有的x,若x能被2除尽,则x是偶数。 d)存在x,x是偶数,且x能除尽6。(即某些偶数能除尽6) e)对所有的x,若x不是偶数,则x不能被2除尽。 f)对所有的x,若x是偶数,则对所有的y,若x能除尽y,则y也是偶数。 g)对所有的x,若x是质数,则存在y,y是偶数且x能除尽y(即所有质数能除尽某些偶数)。 h)对所有的x,若x是奇数,则对所有y,y是质数,则x不能除尽y(即任何奇数不能除尽任何质数)。 (2)解:("x)("y)((P(x)∧P(y)∧┐E(x,y)→($!z)(L(z)∧R(x,y,z))) 或 ("x)("y)((P(x)∧P(y)∧┐E(x,y)→($z)(L(z)∧R(x,y,z) ∧┐($u)(┐E(z,u) ∧L(u)∧R(x,y,u)))) (3)解: a) 设N(x):x是有限个数的乘积。 z(y):y为0。 P(x):x的乘积为零。 F(y):y是乘积中的一个因子。 则有 ("x)((N(x)∧P(x)→($y)(F(y)∧z(y))) b) 设R(x):x是实数。Q(x,y):y大于x。 故 ("x)(R(x)→($y)(Q(x,y)∧R(y))) c) R(x):x是实数。G(x,y):x大于y。 则 ($x)($y)($z)(R(x)∧R(y)∧R(z)∧G(x+y,x·z) (4)解:设G(x,y):x大于y。则有 ("x)("y)("z)(G(y,x) ∧G(0,z)→G(x·z,y·z)) (5)解:设N(x):x是一个数。 S(x,y):y是x的后继数。E(x,y):x=y.则 a) ("x)(N(x)→($!y)(N(y)∧S(x,y))) 或("x)(N(x)→($y)(N(y)∧S(x,y) ∧┐($z)(┐E(y,z) ∧N(z)∧S(x,z)))) b) ┐($x)(N(x)∧S(x,1)) c) ("x)(N(x)∧┐S(x,2)→($!y)(N(y) ∧S(y,x))) 或("x)(N(x)∧┐S(x,2)→($y)(N(y) ∧S(y,x) ∧┐($z)(┐E(y,z) ∧N(z)∧S(z,x)))) (6)解:设S(x):x是大学生。 E(x):x是戴眼睛的。 F(x):x是用功的。 R(x,y):x在看y。 G(y):y是大的。 K(y):y是厚的。 J(y):y是巨著。 a:这本。 b:那位。 则有 E(b)∧F(b)∧S(b)∧R(b,a)∧G(a)∧K(a)∧J(a) (7)解:设P(x,y):x在y连续。 Q(x,y):x>y。则 P(f,a)D(("ε)($δ)("x)(Q(ε,0)→(Q(δ,0)∧Q(δ,|x-a|)→Q(ε,|f(x)-f(a)|)))) 习题2-4 (1) 解:a) x是约束变元,y是自由变元。 b) x是约束变元,P(x)∧Q(x)中的x受全称量词"的约束,S(x)中的x受存在量词$的约束。 c) x,y都是约束变元,P(x)中的x受$的约束,R(x)中的x受"的约束。 d) x,y是约束变元,z是自由变元。 (2) 解:a) P(a)∧P(b)∧P(c) b) R(a)∧R(b)∧R(c)∧S(a)∧S(b)∧S(c) c) (P(a)→Q(a))∧(P(b)→Q(b))∧(P(c)→Q(c) d) (┐P(a)∧┐P(b)∧┐P(c))∨(P(z)∧P(b)∧P(c)) e) (R(a)∧R(b)∧R(c))∧(S(a)∨S(b)∨S(c)) (3) 解: a) ("x)(P(x)∨Q(x))Û(P(1)∨Q(1))∧(P(2)∨Q(2)), 但P(1)为T,Q(1)为F,P(2)为F,Q(2)为T,所以 ("x)(P(x)∨Q(x))Û(T∨F)∧(F∨T) ÛT。 b) ("x)(P→Q(x))∨R(a)Û ((P→Q(-2))∧(P→Q(3))∧(P→Q(6)))∨R(a) 因为P 为T,Q(-2)为T,Q(3)为T,Q(6)为F,R(5)为F,所以 ("x)(P→Q(x))∨R(a)Û ((T→T)∧(T→T)∧(T→F))∨FÛ F (4) 解:a) ("u)($v)(P(u,z)→Q(v))DS(x,y) b) ("u)(P(u)→ (R(u)∨Q(u))∧($v)R(v))→($z)S(x,z) (5) 解:a) (($y)A(u,y)→("x)B(x,v))∧($x)("z)C(x,t,z) b) (("y)P(u,y)∧($z)Q(u,z))∨("x)R(x,t) 习题2-5 (1)解: a) P(a,f(a))∧P(b,f(b))ÛP(1,f(1))∧P(2,f(2))ÛP(1,2)∧P(2,1) ÛT∧FÛF b) ("x)($y)P(y,x)Û ("x) (P(1,x)∨P(2,x))Û (P(1,1)∨P(2,1))∧(P(1,2)∨P(2,2)) Û (T∨F)∧(T∨F) Û T c) ("x)( "y)(P(x,y)→P(f(x),f(y))) Û ("x) ((P(x,1)→P(f(x),f(1)))∧(P(x,2) →P(f(x)f(2)))) Û (P(1,1)→P(f(1),f(1)))∧(P(1,2)→P(f(1),f(2))) ∧(P(2,1)→P(f(2),f(1)))∧(P(2,2) →P(f(2),f(2))) Û (P(1,1)→P(2,2))∧(P(1,2)→P(2,1))∧(P(2,1)→P(1,2))∧(P(2,2)→P(1,1)) Û (T→F∧(T→F)∧(F→T)∧(F→T)ÛF∧F∧T∧TÛF (2)解:a) ("x)(P(x)→Q(f(x),a)) Û(P(1)→Q(f(1),1))∧(P(2)→Q(f(2),1)) Û (F→Q(2,1))∧(T→Q(1,1)) Û (F→F)∧(T→T) ÛT b) ($x)(P(f(x))∧Q(x,f(a)) Û (P(f(1))∧Q(1,f(1)))∨(P(f(2))∧Q(2,f(1)) Û (T∧T)∨(F∧F) ÛT c) ($x)(P(x)∧Q(x,a)) Û (P(1)∧Q(1,a))∨(P(2)∧Q(2,a)) Û (P(1)∧Q(1,1))∨(P(2)∧Q(2,1)) Û (F∧T)∨(T∧F) ÛF d) ("x)( $y)(P(x)∧Q(x,y)) Û ("x) (P(x)∧($y)Q(x,y)) Û ("x) (P(x)∧(Q(x,1)∨Q(x,2))) Û (P(1)∧(Q(1,1)∨Q(1,2)))∧(P(2)∧(Q(2,1)∨Q(2,2))) Û (F∧(T∨T))∧(T∧(F∨F)) ÛF (3) 举例说明下列各蕴含式。 a) ù(($x)(P(x)∧Q(a))Þ ($x)P(x)®ùQ(a) b) ("x) (ù P(x) ®Q(x)), ("x) ùQ(x)ÞP(a) c) ("x) (P(x) ®Q(x)), ("x) (Q(x) ®R(x))Þ ("x) (P(x) ®R(x)) d) ("x) (P(x) ÚQ(x)), ("x) ùP(x)Þ ($x)Q (x) e) ("x) (P(x) ÚQ(x)), ("x) ùP(x)Þ ("x)Q (x) 解:a)因为ù(($x)(P(x)∧Q(a)) Ûù($x)P(x)∨ùQ(a) 故原式为ù($x)P(x)∨ùQ(a) Þ ($x)P(x)®ùQ(a) 设P(x):x是大学生。Q(x):x是运动员 前提 或者不存在x,x是大学生,或者a是运动员 结论 如果存在x是大学生,则必有a是运动员。 b)设P(x):x是研究生。Q(x):x是大学生。a:论域中的某人。 前提:对论域中所有x,如果x不是研究生则x是大学生。 对论域中所有x, x不是大学生。 结论:对论域中所有x都是研究生。 故,对论域中某个a,必有结论a是研究生,即P(a)成立。 c)设P(x):x是研究生。Q(x):x曾读过大学。R(x):x曾读过中学。 前提 对所有x,如果x是研究生,则x曾读过大学。 对所有x,如果x曾读过大学,则x曾读过中学。 结论:对所有x,如果x是研究生,则x曾读过中学。 d)设P(x):x是研究生。Q(x):x是运动员。 前提 对所有x,或者x是研究生,或者x是运动员。 对所有x,x不是研究生 结论 必存在x,x是运动员。 e)设P(x):x是研究生。Q(x):x是运动员。 前提 对所有x,或者x是研究生,或者x是运动员。 对所有x,x不是研究生 结论 对所有x,x是运动员。 (4)证明:($x)(A(x)→B(x))Û ($x) (┐A(x)∨B(x)) Û ($x)┐A(x)∨ ($x) B(x) Û ┐("x)A(x)∨($x) B(x) Û ("x)A(x)→($x) B(x) (5) 设论域D={a,b,c},求证("x)A(x)∨("x)B(x)Þ( "x)(A(x)∨B(x)) 证明:因为论域D={a,b,c},所以 ("x)A(x)∨("x)B(x) Û(A(a) ∧A(b) ∧A(c)) ∨(B(a) ∧B(b) ∧B(c)) Û(A(a) ∨B(a)) ∧(A(a) ∨B(b)) ∧(A(a) ∨B(c)) ∧(A(b) ∨B(a)) ∧(A(b) ∨B(b)) ∧(A(b)∨B(c)) ∧(A(c) ∨B(a)) ∧(A(c) ∨B(b)) ∧(A(c) ∨B(c)) Þ(A(a) ∨B(a)) ∧(A(b) ∨B(b))∧(A(c) ∨B(c)) Û( "x)(A(x)∨B(x)) 所以("x)A(x)∨("x)B(x)Þ( "x)(A(x)∨B(x)) (6)解:推证不正确,因为 ┐($x)(A(x)∧┐B(x))Û┐(($x)A(x)∧($x)┐B(x)) (7)求证("x)( "y)(P(x)→Q(y)) Û ( $x)P(x)→("y)Q(y) 证明:("x)( "y)(P(x)→Q(y)) Û("x)( "y)( ┐P(x) ∨Q(y)) Û("x) ┐P(x) ∨( "y)Q(y) Û┐($x)P(x) ∨( "y)Q(y) Û ( $x)P(x)→("y)Q(y) 习题2-6 (1)解:a) ("x)(P(x)→($y)Q(x,y)) Û("x)( ┐P(x) ∨($y)Q(x,y)) Û("x) ($y) (┐P(x) ∨Q(x,y)) b) ($x)(┐(($y)P(x,y))→(($z)Q(z)→R(x))) Û($x)(($y)P(x,y)∨(($z)Q(z)→R(x))) Û($x)(($y)P(x,y) ∨(┐($z)Q(z) ∨R(x))) Û($x)(($y)P(x,y) ∨(("z)┐Q(z) ∨R(x))) Û($x) ($y) ("z) ( P(x,y) ∨┐Q(z) ∨R(x)) c)("x)( "y)((($zP(x,y,z)∧($u)Q(x,u))→($v)Q(y,v)) Û("x)( "y)( ┐(($z)P(x,y,z)∧($u)Q(x,u))∨($v)Q(y,v)) Û("x)( "y)( ("z)┐P(x,y,z) ∨("u)┐Q(x,u)∨($v)Q(y,v)) Û("x)( "y)( ("z)┐P(x,y,z) ∨("u)┐Q(x,u)∨($v)Q(y,v)) Û("x)( "y) ("z) ("u) ($v) (┐P(x,y,z) ∨┐Q(x,u)∨Q(y,v)) (2)解:a) (($x)P(x)∨($x)Q(x))→($x)(P(x)∨Q(x)) Û┐(($x)P(x)∨($x)Q(x)) ∨($x)(P(x)∨Q(x)) Û┐($x) (P(x)∨Q(x)) ∨($x)(P(x)∨Q(x)) ÛT b) ("x)(P(x)→("y)(("z)Q(x,y)→┐("z)R(y,x))) Û("x)( ┐P(x) ∨("y)( Q(x,y)→┐R(y,x))) Û("x) ("y) ( ┐P(x) ∨┐Q(x,y) ∨┐R(y,x)) 前束合取范式 Û("x) ("y)( (P(x) ∧Q(x,y) ∧R(y,x)) ∨(P(x) ∧Q(x,y) ∧┐R(y,x)) ∨ (P(x) ∧┐Q(x,y) ∧R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧R(y,x)) ∨(┐P(x) ∧┐Q(x,y) ∧R(y,x)) ∨( (P(x) ∧┐Q(x,y) ∧┐R(y,x)) ∨(┐P(x) ∧Q(x,y) ∧┐R(y,x))) 前束析取范式 c) ("x)P(x)→($x)(("z)Q(x,z)∨("z)R(x,y,z)) Û┐("x)P(x) ∨($x)(("z)Q(x,z)∨("z)R(x,y,z)) Û($x)┐P(x) ∨($x)(("z)Q(x,z)∨("u)R(x,y,u)) Û($x)(┐P(x) ∨("z)Q(x,z)∨("u)R(x,y,u)) Û($x) ("z) ("u)(┐P(x) ∨Q(x,z)∨R(x,y,u)) 前束合取范式 Û($x) ("z) ("u)(( P(x) ∧Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(P(x) ∧┐Q(x,z) ∧┐R(x,y,u)) ∨(┐P(x) ∧Q(x,z) ∧┐R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧R(x,y,u)) ∨(┐P(x) ∧┐Q(x,z) ∧┐R(x,y,u))) 前束析取范式 d)("x)(P(x)→Q(x,y))→(($y)P(y)∧($z)Q(y,z)) Û┐("x)( ┐P(x) ∨Q(x,y)) ∨(($y)P(y)∧($z)Q(y,z)) Û($x)( P(x) ∧┐Q(x,y)) ∨(($u)P(u)∧($z)Q(y,z)) Û($x) ($u) ($z) (( P(x) ∧┐Q(x,y)) ∨(P(u)∧Q(y,z))) 前束析取范式 Û($x) ($u) ($z) (( P(x)∨P(u)) ∧ (P(x)∨Q(y,z)) ∧(┐Q(x,y)∨P(u)) ∧ (┐Q(x,y)∨Q(y,z))) 前束合取范式 习题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)与其他前提不矛盾,故本题的推证仍是有效的。 证明 设A上定义的二元关系R为: <<x,y>, <u,v>>∈RÛy(x)=v(u) ① 对任意<x,y>∈A,因为y(x)=y(x),所以 <<x,y>, <x,y>>∈R 即R是自反的。 ② 设<x,y>∈A,<u,v>∈A,若 <<x,y>, <u,v>>∈RÞy(x)=v(u)Þv(u)=y(x)Þ<<u,v>,<x,y>>∈R 即R是对称的。 ③ 设任意<x,y>∈A,<u,v>∈A,<w,s>∈A,对 <<x,y>, <u,v>>∈R∧<<u,v>, <w,s>>∈R Þ(y(x)=v(u))∧(v(u)=s(w))Þy(x)=s(w) Þ<<x,y>, <w,s>>∈R 故R是传递的,于是R是A上的等价关系。 3-10.6 设R是集合A 上的对称和传递关系,证明如果对于A中的每一个元素a,在A中同时也存在b,使在R之中,则R是一个等价关系。 证明 对任意a∈A,必存在一个b∈A,使得<a,b>∈R. 因为R是传递的和对称的,故有: <a,b>∈R∧<b, c>∈RÞ<a, c>∈RÞ<c,a>∈R 由<a,c>∈R∧<c, a>∈RÞ<a,a>∈R 所以R在A上是自反的,即R是A上的等价关系。 3-10.7 设R1和R2是非空集合A上的等价关系,试确定下述各式,哪些是A上的等价关系,对不是的式子,提供反例证明。 a)(A×A)-R1; b)R1-R2; c)R12; d) r(R1-R2)(即R1-R2的自反闭包)。 解 a)(A×A)-R1不是A上等价关系。例如: A={a,b},R1={<a,a>,<b,b>} A×A={<a,a>,<a,b>,<b,a>,<b,b>} (A×A)-R1={<a,b>,<b,a>} 所以(A×A)-R1不是A上等价关系。 b)设 A={a,b,c} R1={<a,b>,<b,a>,<b,c>,<c,b>,<a,c>,<c,a>,<a,a>,<b,b>,<c,c>} R2={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>} R1-R2={<a,b>,<b,a>,<a,c>,<c,a>} 所以R1和R2是A上等价关系,但R1-R2不是A上等价关系。 c)若R1是A上等价关系,则 <a,a>∈R1Þ<a,a>∈R1○R1 所以R12是A上自反的。 若<a,b>∈R12则存在c,使得<a, c>∈R1∧<c,b>∈R1。因R1对称,故有 <b, c>∈R1∧<c,a>∈R1Þ<b, a>∈R12 即R12是对称的。 若<a,b>∈R12∧<b, c>∈R12,则有 <a,b>∈R1○R1∧<b, c>∈R1○R1 Þ($e1)(<a, e1>∈R1∧<e1, b>∈R1) ∧($e2)(<b, e2>∈R1∧<e2, c>∈R1) Þ<a,b>∈R1∧<b, c>∈R1(∵R1传递) Þ<a,c>∈R12 即R12是传递的。 故R12是A上的等价关系。 d)如b)所设,R1和R2是A上的等价关系,但 r(R1-R2)=(R1-R2)∪IA ={<a,b>, <b,a>, <a,c>,<c,a>,<a,a>,<b,b>, <c,c>} 不是A上的等价关系。 3-10.8 设C*是实数部分非零的全体复数组成的集合,C*上的关系R定义为:(a+bi)R(c+di)Ûac>0,证明R是等价关系,并给出关系R的等价类的几何说明。 证明:(1)对任意非零实数a,有a2>0Û(a+bi)R(a+bi) 故R在C*上是自反的。 (2) 对任意(a+bi)R(c+di)Ûac>0, 因ca=ac>0Û(c+di)R(a+bi), 所以R在C*上是对称的。 (3)设(a+bi)R(c+di) ,(c+di)R(u+vi),则有ac>0Ùcu>0 若c>0,则a>0Ùu>0Þ au>0 若c |
CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |