范文一:离散数学(左孝凌)课后习题解答(详细)
离散数学 ~
习题 1.1
1. 下列句子中,哪些是命题?哪些不是命题?如果是命题,指出它的真值。
⑴ 中国有四大发明。
⑵ 计算机有空吗 ?
⑶ 不存在最大素数。
⑷ 21+3<>
⑸ 老王是山东人或河北人。
⑹ 2与 3都是偶数。
⑺ 小李在宿舍里。
⑻ 这朵玫瑰花多美丽呀 !
⑼ 请勿随地吐痰 !
⑽ 圆的面积等于半径的平方乘以 。
⑾ 只有 6是偶数, 3才能是 2的倍数。
⑿ 雪是黑色的当且仅当太阳从东方升起。
⒀如果天下大雨,他就乘班车上班。
解:⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题,其中⑴⑶⑽⑾是真命题,⑷⑹⑿是假命题,⑸⑺ ⒀的真值目前无法确定;⑵⑻⑼不是命题。
2. 将下列复合命题分成若干原子命题。
⑴ 李辛与李末是兄弟。
⑵ 因为天气冷,所以我穿了羽绒服。
⑶ 天正在下雨或湿度很高。
⑷ 刘英与李进上山。
⑸ 王强与刘威都学过法语。
⑹ 如果你不看电影,那么我也不看电影。
⑺我既不看电视也不外出,我在睡觉。
⑻ 除非天下大雨,否则他不乘班车上班。
解:⑴本命题为原子命题;
⑵ p :天气冷; q :我穿羽绒服;
⑶ p :天在下雨; q :湿度很高;
⑷ p :刘英上山; q :李进上山 ;
⑸ p :王强学过法语; q :刘威学过法语;
⑹ p :你看电影; q :我看电影;
⑺ p :我看电视; q :我外出; r :我睡觉;
⑻ p :天下大雨; q :他乘班车上班。
3. 将下列命题符号化。
⑴ 他一面吃饭,一面听音乐。
⑵ 3是素数或 2是素数。
⑶ 若地球上没有树木,则人类不能生存。
⑷ 8是偶数的充分必要条件是 8能被 3整除。
⑸ 停机的原因在于语法错误或程序错误。
⑹ 四边形 ABCD 是平行四边形当且仅当 它的对边平行。
⑺ 如果 a 和 b 是偶数,则 a +b 是偶数。
解:⑴ p :他吃饭; q :他听音乐;原命题符号化为:p ∧ q
⑵ p :3是素数; q :2是素数;原命题符号化为:p ∨ q
⑶ p :地球上有树木; q :人类能生存;原命题符号化为:?p → ?q
⑷ p :8是偶数; q :8能被 3整除;原命题符号化为:p ? q
⑸ p :停机; q :语法错误; r :程序错误;原命题符号化为:q ∨ r → p
⑹ p :四边形 ABCD 是平行四边形; q :四边形 ABCD 的对边平行;原命题符号化 为:p ? q 。
⑺ p :a 是偶数; q :b 是偶数; r :a+b是偶数;原命题符号化为:p ∧ q → r
4. 将下列命题符号化,并指出各复合命题的真值。
⑴ 如果 3+3=6,则雪是白的。
⑵ 如果 3+3≠ 6,则雪是白的。
⑶ 如果 3+3=6,则雪不是白的。
⑷ 如果 3+3≠ 6,则雪不是白的。
⑸ 是无理数当且仅当加拿大位于亚洲。
⑹ 2+3=5的充要条件是 是无理数。 (假定是 10进制 )
⑺ 若两圆 O 1, O 2的面积相等,则它们的半径相等,反之亦然。
⑻ 当王小红心情愉快时,她就唱歌,反之,当她唱歌时,一定心情愉快。
解:设 p :3+3=6。 q :雪是白的。
⑴ 原命题符号化为:p → q ;该命题是真命题。
⑵ 原命题符号化为:?p → q ;该命题是真命题。
⑶ 原命题符号化为:p → ?q ;该命题是假命题。
⑷ 原命题符号化为:?p → ?q ;该命题是真命题。
⑸ p :是无理数; q :加拿大位于亚洲;原命题符号化为:p ? q ; 该命题是假命 题。
⑹ p :2+3=5; q :是无理数;原命题符号化为:p ? q ; 该命题是真命题。 ⑺ p :两圆 O 1,O 2的面积相等; q :两圆 O 1,O 2的半径相等;原命题符号化为:p ? q ; 该命题是真命题。
⑻ p :王小红心情愉快; q :王小红唱歌;原命题符号化为:p ? q ; 该命题是真命题。
习题 1.2
1. 判断下列公式哪些是合式公式,哪些不是合式公式。
⑴ (p ∧ q → r )
⑵ (p ∧ (q → r )
⑶ ((?p → q ) ? (r ∨ s ))
⑷ (p ∧ q → rs )
⑸ ((p → (q → r )) → ((q → p ) ? q ∨ r )) 。
解:⑴⑶⑸是合式公式;⑵⑷不是合式公式。
2. 设 p :天下雪。
q :我将进城。
r :我有时间。
将下列命题符号化。
⑴ 天没有下雪,我也没有进城。
⑵ 如果我有时间,我将进城。
⑶ 如果天不下雪而我又有时间的话,我将进城。
解:⑴ ?p ∧ ?q
⑵ r → q
⑶ ?p ∧ r → q
3. 设 p 、 q 、 r 所表示的命题与上题相同,试把下列公式译成自然语言。
⑴ r ∧ q
⑵ ? (r ∨ q )
⑶ q ? (r ∧? p)
⑷ (q → r ) ∧ (r → q )
解:⑴ 我有时间并且我将进城。
⑵ 我没有时间并且我也没有进城。
⑶ 我进城,当且仅当我有时间并且天不下雪。
⑷ 如果我有时间,那么我将进城,反之亦然。
4. 试把原子命题表示为 p 、 q 、 r 等,将下列命题符号化。
⑴ 或者你没有给我写信,或者它在途中丢失了。
⑵ 如果张三和李四都不去,他就去。
⑶ 我们不能既划船又跑步。
⑷ 如果你来了,那末他唱不唱歌将看你是否伴奏而定。
解:⑴ p :你给我写信; q :信在途中丢失;原命题符号化为:(?p ∧ ? q) ∨ (p ∧ q ) 。 ⑵ p :张三去; q :李四去; r :他去;原命题符号化为:?p ∧ ?q → r 。
⑶ p :我们划船; q :我们跑步;原命题符号化为:?(p ∧ q ) 。
⑷ p :你来了; q :他唱歌; r :你伴奏;原命题符号化为:p →(q ? r ) 。
5. 用符号形式写出下列命题。
⑴假如上午不下雨,我去看电影,否则就在家里读书或看报。
⑵我今天进城,除非下雨。
⑶仅当你走,我将留下。
解:⑴ p :上午下雨; q :我去看电影; r :我在家读书; s :我在家看报;原命题符 号化为:(?p → q )∧(p → r ∨ s ) 。
⑵ p :我今天进城; q :天下雨;原命题符号化为:?q → p 。
⑶ p :你走; q :我留下;原命题符号化为:q → p 。
习题 1.3
1. 设 A 、 B 、 C 是任意命题公式,证明:
⑴ A ?A
⑵若 A ?B ,则 B ?A
⑶若 A ?B , B ?C ,则 A ?C
证明:⑴由双条件的定义可知 A ? A 是一个永真式,由等价式的定义可知 A ?A 成立。 ⑵因为 A ?B ,由等价的定义可知 A ? B 是一个永真式,再由双条件的定义可知 B ? A 也是一个永真式,所以, B ?A 成立。
⑶对 A 、 B 、 C 的任一赋值,因为 A ?B ,则 A ? B 是永真式, 即 A 与 B 具有相同的真 值,又因为 B ?C ,则 B ? C 是永真式, 即 B 与 C 也具有相同的真值,所以 A 与 C 也具有 相同的真值;即 A ?C 成立。
2. 设 A 、 B 、 C 是任意命题公式,
⑴若 A ∨ C ?B ∨ C , A ?B 一定成立吗?
⑵若 A ∧ C ?B ∧ C , A ?B 一定成立吗?
⑶若?A ??B , A ?B 一定成立吗?
解:⑴不一定有 A ?B 。若 A 为真, B 为假, C 为真,则 A ∨ C ?B ∨ C 成立,但 A ?B 不成立。
⑵不一定有 A ?B 。若 A 为真, B 为假, C 为假,则 A ∧ C ?B ∧ C 成立,但 A ?B 不 成立。
⑶一定有 A ?B 。
3. 构造下列命题公式的真值表,并求成真赋值和成假赋值。
⑴ q ∧ (p → q ) → p
⑵ p → (q ∨ r )
⑶ (p ∨ q )?(q ∨ p )
⑷ (p ∧ ?q ) ∨ (r ∧ q ) → r
⑸ ((?p → (p ∧?q )) → r ) ∨ (q ∧?r )
解:⑴ q ∧ (p → q ) → p 的真值表如表 1.24所示。
表 1.24
使得公式 q ∧ (p → q ) → p 成真的赋值是:00, 10, 11,使得公式 q ∧ (p → q ) → p 成假的赋 值是:01。
⑵ p → (q ∨ r ) 的真值表如表 1.25所示。
表 1.25
使得公式 p → (q ∨ r ) 成真的赋值是:000, 001, 010, 011, 101, 110, 111,使得公式 p → (q ∨ r ) 成假的赋值是:100。
⑶ (p ∨ q ) ? (q ∨ p ) 的真值表如表 1.26所示。
表 1.26
所有的赋值均使得公式 (p ∨ q ) ? (q ∨ p ) 成真,即 (p ∨ q ) ? (q ∨ p ) 是一个永真式。
⑷ (p ∧ ?q ) ∨ (r ∧ q ) → r 的真值表如表 1.27所示。
表 1.27
使得公式 (p ∧ ?q ) ∨ (r ∧ q ) → r 成假的赋值是:100。
⑸ ((?p → (p ∧ ?q )) → r ) ∨ (q ∧ ?r ) 的真值表如表 1.28所示。
表 1.28
使得公式 ((?p → (p ∧ ?q )) → r ) ∨ (q ∧ ?r ) 成真的赋值是:000, 001, 010, 011, 101, 110, 111,使得公式 ((?p → (p ∧ ?q )) → r ) ∨ (q ∧ ?r ) 成假的赋值是:100。
4. 用真值表证明下列等价式:
⑴ ?(p → q ) ?p ∧ ?q
证明:证明 ?(p → q ) ?p ∧ ?q 的真值表如表 1.29所示。
表 1.29
由上表可见:?(p → q ) 和 p ∧ ?q 的真值表完全相同,所以 ?(p → q ) ?p ∧ ?q 。
⑵ p → q ??q → ?p
证明:证明 p → q ??q → ?p 的真值表如表 1.30所示。
表 1.30
⑶ ?(p ? q ) ?p ? ?q
证明:证明 ?(p ? q ) 和 p ? ?q 的真值表如表 1.31所示。
表 1.31
由上表可见:?(p ? q ) 和 p ? ?q 的真值表完全相同,所以 ?(p ? q ) ?p ? ?q 。
⑷ p → (q → r ) ?(p ∧ q ) → r
证明:证明 p → (q → r ) 和 (p ∧ q ) → r 的真值表如表 1.32所示。
表 1.32
由上表可见:p → (q → r ) ?(p ∧ q ) → r 。 ⑸ p → (q → p ) ? ?p → (p → ?q )
证明:证明 p → (q → p ) 和 ?p → (p → ?q ) 的真值表如表 1.33所示。
表 1.33
由上表可见:p → (q → p ) 和 ?p → (p → ?q ) 的真值表完全相同, 且都是永真式, 所以 p → (q → p ) ??p → (p → ?q ) 。
⑹ ?(p ? q ) ?(p ∨ q ) ∧ ?(p ∧ q ) 证明:证明 ?(p ? q ) 和 (p ∨ q ) ∧ ?(p ∧ q ) 的真值表如表 1.34所示。
表 1.34
由上表可见:?(p ? q ) 和 (p ∨ q ) ∧ ?(p ∧ q ) 的真值表完全相同, 所以 ?(p ? q ) ?(p ∨ q ) ∧ ?(p ∧ q )
⑺ ?(p ? q ) ?(p ∧ ?q ) ∨ (?p ∧ q ) 证明:证明 ?
(p ? q ) 和 (p ∧ ?q ) ∨ (?p ∧ q ) 的真值表如表 1.35所示。
表 1.35
由上表可见:?(p ? q ) 和 (p ∧ ?q ) ∨ (?p ∧ q ) 的真值表完全相同,所以 ?(p ? q ) ?(p ∧ ?q ) ∨ (?p ∧ q ) 。
⑻ p → (q ∨ r ) ?(p ∧ ?q ) → r
证明:证明 p → (q ∨ r ) 和 (p ∧ ?q ) → r 的真值表如表 1.36所示。
表 1.36
由上表可见:p → (q ∨ r ) 和 (p ∧ ?q ) → r 的真值表完全相同, 所以 p → (q ∨ r ) ?(p ∧ ?q ) → r 。 5. 用等价演算证明习题 4中的等价式。
⑴ ?(p → q )
??(?p ∨ q ) (条件等价式 )
?p ∧ ?q (德·摩根律 )
⑵ ?q → ?p
???q ∨ ?p (条件等价式 )
?q ∨ ?p (双重否定律 )
??p ∨ q (交换律 )
? p→ q (条件等价式 )
⑶ ?(p ? q )
??((p → q ) ∧ (q → p )) (双条件等价式 )
??((?p ∨ q ) ∧ (?q ∨ p )) (条件等价式 )
?(p ∧ ?q ) ∨ (q ∧ ?p ) (德·摩根律 )
?((p ∧ ?q ) ∨ q ) ∧ ((p ∧ ?q ) ∨ ?p ) (分配律 )
?(p ∨ q ) ∧ (?q ∨ ?p ) (分配律 )
?(?p ∨ ?q ) ∧ (q ∨ p ) (交换律 )
?(p → ?q ) ∧ (?q → p ) (条件等价式 )
?p ? ?q (双条件等价式 )
⑷ p → (q → r )
??p ∨ (?q ∨ r ) (条件等价式 )
?(?p ∨ ?q ) ∨ r (结合律 )
??(p ∧ q ) ∨ r (德·摩根律 )
?(p ∧ q ) → r (条件等价式 )
⑸ p → (q → p )
??p ∨ (?q ∨ p ) (条件等价式 )
?T
?p → (p → ?q )
?p ∨ (?p ∨ ?q ) (条件等价式 )
?T
所以 p → (q → p ) ? ?p → (p → ?q )
⑹ ?(p ? q )
??((p ∧ q ) ∨ (?p ∧ ?q )) (例 1.17)
?(p ∨ q ) ∧ (?p ∨ ?q ) (德·摩根律 )
?(p ∨ q ) ∧ ?(p ∧ q ) (德·摩根律 )
所以 ?(p ? q ) ?(p ∨ q ) ∧ ?(p ∧ q )
⑺ ?(p ? q )
范文二:左孝凌离散数学课后题答案最新版
1 则有 ?(,x)(R(x),Q(x))
a) 设S:他犯了错误。 R:他神色慌张。 h)设P(x,y):直线x平行于直线y
前提为:S?R,R G(x,y):直线x相交于直线y。
因为(S?R)?R,(?S?R)?R,R。故本题没有确定的结论。 则有 P(A,B),?G(A,B)
实际上,若S ?R为真,R为真,则S可为真,S也可为假,故无(2) 解:
有效结论。 a) 设J(x):x是教练员。L(x):x是运动员。
b) 设P:我的程序通过。 Q:我很快乐。 则有 (,x)(J(x),L(x))
R:阳光很好。 S:天很暖和。(把晚上十一点理解为阳光不b) 设S(x):x是大学生。L(x):x是运动员。
好) 则有 (,x)(L(x),S(x))
前提为:P?Q,Q?R,?R?S c) 设J(x):x是教练员。O(x):x是年老的。V(x):x是健壮的。
(1) P?Q P 则有 (,x)(J(x),O(x),V(x))
(2) Q?R P d) 设O(x):x是年老的。V(x):x是健壮的。j:金教练
(3) P?R (1)(2)T,I 则有 ? O(j),?V(j)
(4) ?R?S P e) 设L(x):x是运动员。J(x):x是教练员。
(5) ?R (4)T,I 则 ?(,x)(L(x),J(x))
(6) ?P (3)(5)T,I 本题亦可理解为:某些运动员不是教练。
结论为: ?P,我的程序没有通过 故 (,x)(L(x),?J(x))
f) 设S(x):x是大学生。L(x):x是运动员。C(x):x是国家选习题2-1,2-2 手。
(1) 解: 则有 (,x)(S(x),L(x),C(x))
a) 设W(x):x是工人。c:小张。 g) 设C(x):x是国家选手。V(x):x是健壮的。
则有 ?W(c) 则有 (,x)(C(x),V(x))或?(,x)(C(x),?V(x))
b) 设S(x):x是田径运动员。B(x):x是球类运动员。h:他 h) 设C(x):x是国家选手。O(x):x是老的。L(x):x 是运动员。
则有 S(h),B(h) 则有 (,x)(O(x),C(x),L(x))
c) 设C(x):x是聪明的。B(x):x是美丽的。l:小莉。 i) 设W(x):x是女同志。H(x):x是家庭妇女。C(x):x是国家
则有 C(l), B(l) 选手。
d)设O(x):x是奇数。 则有 ?(,x)(W(x),C(x),H(x))
则有 O(m),? O(2m)。 j)W(x):x是女同志。J(x):x是教练。C(x):x是国家选手。
e)设R(x):x是实数。Q(x):x是有理数。 则有(,x)(W(x),J(x),C(x))
则有 (,x)(Q(x),R(x)) k)L(x):x 是运动员。J(y):y是教练。A(x,y):x钦佩y。
f) 设R(x):x是实数。Q(x):x是有理数。 则有 (,x)(L(x), (,y)(J(y),A(x,y)))
则有 (,x)(R(x),Q(x)) l)设S(x):x是大学生。L(x):x 是运动员。A(x,y):x钦佩y。
g) 设R(x):x是实数。Q(x):x是有理数。 则(,x)(S(x),(,y)(L(y),? A(x,y)))
或(,x)(N(x)??S(x,2)?(,y)(N(y) ?S(y,x) ??(,z)(?E(y,z) ?习题2-3 N(z)?S(z,x))))
(1)解: (6)解:设S(x):x是大学生。 E(x):x是戴眼睛的。
a)5是质数。 F(x):x是用功的。 R(x,y):x在看y。
b)2是偶数且2是质数。 G(y):y是大的。 K(y):y是厚的。 J(y):y是巨著。 a:这
c)对所有的x,若x能被2除尽,则x是偶数。 本。 b:那位。
d)存在x,x是偶数,且x能除尽6。(即某些偶数能除尽6) 则有 E(b)?F(b)?S(b)?R(b,a)?G(a)?K(a)?J(a)
e)对所有的x,若x不是偶数,则x不能被2除尽。 (7)解:设P(x,y):x在y连续。 Q(x,y):x>y。则
f)对所有的x,若x是偶数,则对所有的y,若x能除尽y,则y也 P(f,a),((,ε)(,δ)(,x)(Q(ε,0)?(Q(δ,0)?Q(δ,|x-a|)?Q(ε,|f(x)-f(a)|)))) 是偶数。
g)对所有的x,若x是质数,则存在y,y是偶数且x能除尽y(即习题2-4
所有质数能除尽某些偶数)。 (1) 解:a) x是约束变元,y是自由变元。
h)对所有的x,若x是奇数,则对所有y,y是质数,则x不能除尽 b) x是约束变元,P(x)?Q(x)中的x受全称量词,的约束,S(x)中的xy(即任何奇数不能除尽任何质数)。 受存在量词,的约束。
(2)解:(,x)(,y)((P(x)?P(y)??E(x,y)?(,!z)(L(z)?R(x,y,z))) c) x,y都是约束变元,P(x)中的x受,的约束,R(x)中的x受,的约束。 或 (,x)(,y)((P(x)?P(y)??E(x,y)?(,z)(L(z)?R(x,y,z) ??(,u)(? d) x,y是约束变元,z是自由变元。
E(z,u) ?L(u)?R(x,y,u)))) (2) 解:a) P(a)?P(b)?P(c)
(3)解: b) R(a)?R(b)?R(c)?S(a)?S(b)?S(c)
a) 设N(x):x是有限个数的乘积。 z(y):y为0。 c) (P(a)?Q(a))?(P(b)?Q(b))?(P(c)?Q(c)
P(x):x的乘积为零。 F(y):y是乘积中的一个因子。 d) (?P(a)??P(b)??P(c))?(P(z)?P(b)?P(c))
则有 (,x)((N(x)?P(x)?(,y)(F(y)?z(y))) e) (R(a)?R(b)?R(c))?(S(a)?S(b)?S(c))
b) 设R(x):x是实数。Q(x,y):y大于x。 故 (,x)(R(x)?(,y)(Q(x,y)(3) 解:
?R(y))) a) (,x)(P(x)?Q(x)),(P(1)?Q(1))?(P(2)?Q(2)),
c) R(x):x是实数。G(x,y):x大于y。 则 但P(1)为T,Q(1)为F,P(2)为F,Q(2)为T,所以
(,x)(,y)(,z)(R(x)?R(y)?R(z)?G(x+y,x?z) (,x)(P(x)?Q(x)),(T?F)?(F?T) ,T。 (4)解:设G(x,y):x大于y。则有 (,x)(,y)(,z)(G(y,x) ?G(0,z)?b) (,x)(P?Q(x))?R(a), ((P?Q(,2))?(P?Q(3))?(P?Q(6)))?R(a)
G(x?z,y?z)) 因为P 为T,Q(,2)为T,Q(3)为T,Q(6)为F,R(5)为F,所以 (5)解:设N(x):x是一个数。 S(x,y):y是x的后继数。E(x,y):x=y.则 (,x)(P?Q(x))?R(a), ((T?T)?(T?T)?(T?F))?F, F
a) (,x)(N(x)?(,!y)(N(y)?S(x,y))) (4) 解:a) (,u)(,v)(P(u,z)?Q(v)),S(x,y)
或(,x)(N(x)?(,y)(N(y)?S(x,y) ??(,z)(?E(y,z) ?N(z)? b) (,u)(P(u)? (R(u)?Q(u))?(,v)R(v))?(,z)S(x,z)
S(x,z)))) (5) 解:a) ((,y)A(u,y)?(,x)B(x,v))?(,x)(,z)C(x,t,z)
b) ?(,x)(N(x)?S(x,1)) b) ((,y)P(u,y)?(,z)Q(u,z))?(,x)R(x,t)
c) (,x)(N(x)??S(x,2)?(,!y)(N(y) ?S(y,x)))
习题2-5 d) (,x) (P(x) ,Q(x)), (,x) ,P(x), (,x)Q (x)
(1)解: e) (,x) (P(x) ,Q(x)), (,x) ,P(x), (,x)Q (x)
解:a)因为,((,x)(P(x)?Q(a)) ,,(,x)P(x)?,Q(a) 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)?故原式为,(,x)P(x)?,Q(a) , (,x)P(x),,Q(a) P(2,1))?(P(1,2)?P(2,2)) 设P(x):x是大学生。Q(x):x是运动员
, (T?F)?(T?F) , T 前提 或者不存在x,x是大学生,或者a是运动员
c) (,x)( ,y)(P(x,y)?P(f(x),f(y))) 结论 如果存在x是大学生,则必有a是运动员。
b)设P(x):x是研究生。Q(x):x是大学生。a:论域中的某人。 , (,x) ((P(x,1)?P(f(x),f(1)))?(P(x,2) ?P(f(x)f(2))))
前提:对论域中所有x,如果x不是研究生则x是大学生。 , (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))) 对论域中所有x, x不是大学生。
结论:对论域中所有x都是研究生。 ,
(P(1,1)?P(2,2))?(P(1,2)?P(2,1))?(P(2,1)?P(1,2))?(P(2,2)?P(1,1)) 故,对论域中某个a,必有结论a是研究生,即P(a)成立。
c)设P(x):x是研究生。Q(x):x曾读过大学。R(x):x曾读过中 , (T?F?(T?F)?(F?T)?(F?T),F?F?T?T,F
(2)解:a) (,x)(P(x)?Q(f(x),a)) 学。
前提 对所有x,如果x是研究生,则x曾读过大学。 ,(P(1)?Q(f(1),1))?(P(2)?Q(f(2),1))
对所有x,如果x曾读过大学,则x曾读过中学。 , (F?Q(2,1))?(T?Q(1,1))
结论:对所有x,如果x是研究生,则x曾读过中学。 , (F?F)?(T?T) ,T
b) (,x)(P(f(x))?Q(x,f(a)) d)设P(x):x是研究生。Q(x):x是运动员。
, (P(f(1))?Q(1,f(1)))?(P(f(2))?Q(2,f(1)) , (T?T)?前提 对所有x,或者x是研究生,或者x是运动员。
对所有x,x不是研究生 (F?F) ,T
c) (,x)(P(x)?Q(x,a)) 结论 必存在x,x是运动员。
, (P(1)?Q(1,a))?(P(2)?Q(2,a)) e)设P(x):x是研究生。Q(x):x是运动员。
, (P(1)?Q(1,1))?(P(2)?Q(2,1)) 前提 对所有x,或者x是研究生,或者x是运动员。
, (F?T)?(T?F) ,F 对所有x,x不是研究生
d) (,x)( ,y)(P(x)?Q(x,y)) 结论 对所有x,x是运动员。
(4)证明:(,x)(A(x)?B(x)), (,x) (?A(x)?B(x)) , (,x)?A(x)? (,x) , (,x) (P(x)?(,y)Q(x,y))
, (,x) (P(x)?(Q(x,1)?Q(x,2))) B(x)
, (P(1)?(Q(1,1)?Q(1,2)))?(P(2)?(Q(2,1)?Q(2,2))) , ?(,x)A(x)?(,x) B(x) , (,x)A(x)?(,x) B(x)
, (F?(T?T))?(T?(F?F)) ,F (5) 设论域D={a,b,c},求证(,x)A(x)?(,x)B(x),( ,x)(A(x)?B(x))
(3) 举例说明下列各蕴含式。 证明:因为论域D={a,b,c},所以 a) ,((,x)(P(x)?Q(a)), (,x)P(x),,Q(a) (,x)A(x)?(,x)B(x) ,(A(a) ?A(b) ?A(c)) ?(B(a) ?B(b) ?B(c)) 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))
,(A(a) ?B(a)) ?(A(a) ?B(b)) ?(A(a) ?B(c)) ?(A(b) ?B(a)) ?,(,x)( ?P(x) ?(,y)( Q(x,y)??R(y,x)))
(A(b) ?B(b)) ?(A(b)?B(c)) ?(A(c) ?B(a)) ?(A(c) ?B(b)) ,(,x) (,y) ( ?P(x) ??Q(x,y) ??R(y,x))
?(A(c) ?B(c)) 前束合取范式
,(A(a) ?B(a)) ?(A(b) ?B(b))?(A(c) ?B(c)) ,(,x) (,y)( (P(x) ?Q(x,y) ?R(y,x)) ,( ,x)(A(x)?B(x)) ?(P(x) ?Q(x,y) ??R(y,x)) 所以(,x)A(x)?(,x)B(x),( ,x)(A(x)?B(x)) ? (P(x) ??Q(x,y) ?R(y,x)) (6)解:推证不正确,因为 ?(?P(x) ?Q(x,y) ?R(y,x))
?(,x)(A(x)??B(x)),?((,x)A(x)?(,x)?B(x)) ?(?P(x) ??Q(x,y) ?R(y,x)) (7)求证(,x)( ,y)(P(x)?Q(y)) , ( ,x)P(x)?(,y)Q(y) ?( (P(x) ??Q(x,y) ??R(y,x)) 证明:(,x)( ,y)(P(x)?Q(y)) ?(?P(x) ?Q(x,y) ??R(y,x))) ,(,x)( ,y)( ?P(x) ?Q(y)) 前束析取范式
,(,x) ?P(x) ?( ,y)Q(y) c) (,x)P(x)?(,x)((,z)Q(x,z)?(,z)R(x,y,z)) ,?(,x)P(x) ?( ,y)Q(y) ,?(,x)P(x) ?(,x)((,z)Q(x,z)?(,z)R(x,y,z)) , ( ,x)P(x)?(,y)Q(y) ,(,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))
习题2-6 ,(,x) (,z) (,u)(?P(x) ?Q(x,z)?R(x,y,u)) (1)解:a) (,x)(P(x)?(,y)Q(x,y)) 前束合取范式
,(,x)( ?P(x) ?(,y)Q(x,y)) ,(,x) (,z) (,u)(( P(x) ?Q(x,z) ?R(x,y,u))
,(,x) (,y) (?P(x) ?Q(x,y)) ?(P(x) ?Q(x,z) ??R(x,y,u))
b) (,x)(?((,y)P(x,y))?((,z)Q(z)?R(x))) ?(P(x) ??Q(x,z) ?R(x,y,u))
,(,x)((,y)P(x,y)?((,z)Q(z)?R(x))) ?(P(x) ??Q(x,z) ??R(x,y,u))
,(,x)((,y)P(x,y) ?(?(,z)Q(z) ?R(x))) ?(?P(x) ?Q(x,z) ??R(x,y,u))
,(,x)((,y)P(x,y) ?((,z)?Q(z) ?R(x))) ?(?P(x) ??Q(x,z) ?R(x,y,u))
,(,x) (,y) (,z) ( P(x,y) ??Q(z) ?R(x)) ?(?P(x) ??Q(x,z) ??R(x,y,u)))
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)) d)(,x)(P(x)?Q(x,y))?((,y)P(y)?(,z)Q(y,z))
,(,x)( ,y)( (,z)?P(x,y,z) ?(,u)?Q(x,u)?(,v)Q(y,v)) ,?(,x)( ?P(x) ?Q(x,y)) ?((,y)P(y)?(,z)Q(y,z))
,(,x)( ,y)( (,z)?P(x,y,z) ?(,u)?Q(x,u)?(,v)Q(y,v)) ,(,x)( P(x) ??Q(x,y)) ?((,u)P(u)?(,z)Q(y,z))
,(,x)( ,y) (,z) (,u) (,v) (?P(x,y,z) ??Q(x,u)?Q(y,v)) ,(,x) (,u) (,z) (( P(x) ??Q(x,y)) ?(P(u)?Q(y,z))) (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) (,u) (,z) (( P(x)?P(u)) ? (P(x)?Q(y,z)) ?(?Q(x,y)?P(u))
,?(,x) (P(x)?Q(x)) ?(,x)(P(x)?Q(x)) ,T ? (?Q(x,y)?Q(y,z)))
b) (,x)(P(x)?(,y)((,z)Q(x,y)??(,z)R(y,x))) 前束合取范式
? (,x)(A(x)?B(x)) P
习题2-7 ?A(u)?B(u) US
(1) 证明: ?A(u) T??I (2) a) ?(,x)(?A(x)?B(x)) P ?(,x)A(x) UG? ??A(u)?B(u) US? (2) 证明:
?( ,x)?B(x) P a)?( ,x)P(x) P(附加前提) ??B(u) US? ?P(u) US? ?A(u)?B(u) T?E ?(,x)(P(x)?Q(x)) P ?A(u) T??I ?P(u)?Q(u) US? ? ( ,x)A(x) EG? ?Q(u) T??I b) ??( ,x)(A(x)?B(x)) P(附加前提) ?(,x)Q(x) UG? ?( ,x)?(A(x)?B(x)) T?E ?( ,x)P(x)?(,x)Q(x) CP ??(A(c)?B(c)) ES? b)因为(,x)P(x)?(,x)Q(x),?(,x)P(x) ?(,x)Q(x) ?A(c) T?I 故本题就是推证(,x)(P(x)?Q(x)) , ?(,x)P(x) ?(,x)Q(x) ??B(c) T?I ??(,x)P(x) P(附加前提) ?( ,x)A(x) EG? ?( ,x)?P(x) T?E ? (,x)A(x)?(,x)B(x) P ??P(c) ES? ?(,x)B(x) T??I ?(,x)(P(x)?Q(x)) P ?B(c) US? ?P(c)?Q(c) ES? ?B(c)? ?B(c) T??矛盾 ?Q(c) T??I c)?(,x)(A(x)?B(x)) P ?( ,x) Q(x) EG? ?A(u)?B(u) US? ??(,x)P(x) ?(,x)Q(x) CP ?( ,x)(C(x)??B(x)) P (3)
?C(u)??B(u) US? 解:a)设R(x):x是实数。Q(x):x是有理数。I(x):x是整数。 ??B(u) ??A(u) T?E 本题符号化为:
?C(u)??A(u) T??I (,x)(Q(x) ?R(x)) ?(,x)(Q(x) ?I(x)) , (,x)(R(x) ?I(x)) ?(,x)(C(x)??A(x)) UG? ?(,x)(Q(x) ?I(x)) P d) (,x)(A(x)?B(x)),( ,x)(B(x)??C(x)),( ,x)C(x), (,x)A(x) ?Q(c) ?I(c) ES? ?( ,x)(B(x)??C(x)) P ?(,x)(Q(x) ?R(x)) P ?B(u)??C(u) US? ?Q(c) ?R(c) US? ?( ,x)C(x) P ?Q(c) T?I ?C(u) US? ? R(c) T??I ??B(u) T??I ?I(c) T?I
?R(c)?I(c) T??I 证明 设A上定义的二元关系R为: ?(,x)(R(x) ?I(x)) EG? xub)设P(x):x喜欢步行。Q(x):x喜欢乘汽车。R(x):x喜欢骑自行,,x,y,, ,u,v,,?R, = yv车
本题符号化为: xx (,x)(P(x) ??Q(x)), (,x)(Q(x) ?R(x)) , (,x) ?R(x) , (,x) ?P(x) ? 对任意,x,y,?A,因为 = ,所以 yy?(,x) ?R(x) P
??R (c) ES? ,,x,y,, ,x,y,,?R ?(,x)(Q(x) ?R(x)) P 即R是自反的。
?Q(c) ?R(c) US? ? 设,x,y,?A,,u,v,?A,若 ?Q(c) T??I xuux? (,x)(P(x) ??Q(x)) P ,,x,y,, ,u,v,,?R, = , = ,,,u,v,,,yvvy?P(c) ??Q(c) US?
??P (c) T??I x,y,,?R
?(,x) ?P(x) EG? 即R是对称的。
c) 每个大学生不是文科学生就是理工科学生,有的大学生是优等生,小? 设任意,x,y,?A,,u,v,?A,,w,s,?A,对 张不是理工科学生,但他是优等生,因而如果小张是大学生,他就是文,,x,y,, ,u,v,,?R?,,u,v,, ,w,s,,?R 科学生。 xuuwxw设G(x):x是大学生。L(x):x是文科学生。P(x):x是理工科学生。 ,( = )?( = ), = yvvsysS(x):x是优秀生。c:小张。
本题符号化为: ,,,x,y,, ,w,s,,?R
(,x)(G(x) ?L(x)?P(x)), (,x)(G(x) ? S(x)), ?P (c) , S(c) , G(c) ?故R是传递的,于是R是A上的等价关系。 L(c)
?G(c) P(附加前提) 3-10.6 设R是集合A 上的对称和传递关系,证明如果对于A中的每一?(,x)(G(x) ?L(x)?P(x)) P 个元素a,在A中同时也存在b,使在R之中,则R是一个等价关系。 ?G(c) ?L(c)?P(c) US? 证明 对任意a?A,必存在一个b?A,使得,a,b,?R. ?L(c)?P(c) T??I 因为R是传递的和对称的,故有: ??P (c) P ,a,b,?R?,b, c,?R,,a, c,?R,,c,a,?R ? L(c) T??I 由,a,c,?R?,c, a,?R,,a,a,?R ?G(c) ?L(c) CP 所以R在A上是自反的,即R是A上的等价关系。 注意:本题推证过程中未用到前提(,x)(G(x) ? S(x))以及S(c)。主要是S
(x):x是优秀生,这个条件与其他前提的联系对证明结论没有影响,3-10.7 设R和R是非空集合A上的等价关系,试确定下述各式,哪些12
因S(x)与其他前提不矛盾,故本题的推证仍是有效的。 是A上的等价关系,对不是的式子,提供反例证明。
a)(A×A)-R; ,b,b,, ,c,c,} 1
b)R-R; 不是A上的等价关系。 122c)R; 1**d) r(R-R)(即R-R的自反闭包)。 3-10.8 设C是实数部分非零的全体复数组成的集合,C上的关系R定义1212
解 a)(A×A)-R不是A上等价关系。例如: 为:(a+bi)R(c+di),ac>0,证明R是等价关系,并给出关系R的等价类1
A={a,b},R={,a,a,,,b,b,} 的几何说明。 1
A×A={,a,a,,,a,b,,,b,a,,,b,b,} 2(A×A)-R={,a,b,,,b,a,} 证明:(1)对任意非零实数a,有a>0,(a+bi)R(a+bi) 1*所以(A×A)-R不是A上等价关系。 故R在C上是自反的。 1
b)设 A={a,b,c} (2) 对任意(a+bi)R(c+di),ac>0,
R={,a,b,,,b,a,,,b,c,,,c,b,,,a,c,,,c,a,,因ca=ac>0,(c+di)R(a+bi), 1*,a,a,,,b,b,,,c,c,} 所以R在C上是对称的。
R={,a,a,,,b,b,,,c,c,,,b,c,,,c,b,} (3)设(a+bi)R(c+di) ,(c+di)R(u+vi),则有ac>0,cu>0 2
R-R={,a,b,,,b,a,,,a,c,,,c,a,} 若c>0,则a>0,u>0, au>0 12
所以R和R是A上等价关系,但R-R不是A上等价关系。 若c<><><0, au="">0 1212* c)若R是A上等价关系,则 所以(a+bi)R(u+vi),即R在C上是传递的。 1
,a,a,?R,,a,a,?R?R 关系R的等价类,就是复数平面上第一、四象限上的点,或第二、三象1112所以R是A上自反的。 限上的点,因为在这两种情况下,任意两个点(a,b),(c,d),其横坐标12若,a,b,?R则存在c,使得,a, c,?R?,c,b,?R。因R乘积ac>0。 1111
对称,故有 2,b, c,?R?,c,a,?R,,b, a,?R 3-10.9 设Π和Π,是非空集合A上的划分,并设R和R,分别为由Π和Π,1112即R是对称的。 诱导的等价关系,那么Π,细分Π的充要条件是R,, R。 1 22若,a,b,?R?,b, c,?R,则有 证明:若Π,细分Π。由假设aR,b,则在Π,中有某个块S,,使得a,b?S,,11
,a,b,?R?R?,b, c,?R?R 因Π,细分Π,故在Π中,必有某个块S,使S,, S,即a,b?S,于是有1111
,(,e)(,a, e,?R?,e, b,?R) ?(,e)(,b, e,?aRb,即R,, R。 1111122
R?,e, c,?R) 反之,若R,, R,令S,为H,的一个分块,且a?S,,则S,=[a]={x|xR,a} 121 R,
,,a,b,?R?,b, c,?R(?R传递) 但对每一个x,若xR,a,因R,, R,故xRa,因此{x|xR,a},{x|xRa}即[a]111 R ,2,,a,c,?R ,[a]1R 2即R是传递的。 设S=[a],则S,, S 1R2故R是A上的等价关系。 这就证明了Π,细分Π。 1
d)如b)所设,R和R是A上的等价关系,但 12
r(R-R)=(R-R)?I3-10.10 设R是表示I上的模j等价关系,R是表示I上的模k等价关1212A jk
={,a,b,, ,b,a,, ,a,c,,,c,a,,,a,a,,系,证明I/R细分I/R当且仅当k是j的整数倍。 kj
证明:由题设R={ R={ 故 a)假设I/R细分I/R,则R, Rkjk j 因此 故k-0=1,k=c,j (对某个c?I) 于是k是j的整数倍。 b)若对于某个r?I,有k=rj则: , x-y=crj (对某个c,r?I) , 因此,R, R,于是I/R细分I/R k jkj 导读:就爱阅读网友为您分享以下“离散数学教学方法探讨”资讯,希望对您有所帮助,感谢您对92to.com的支持! 离散数学教学方法探讨 【摘要】离散数学是计算机科学与技术专业一门重要的专业基础课。本文对离散数学的教学内容、教学手段及教学方法进行了探讨。首先根据学校技术应用型大学的办学方略,精选教学内容,注重知识应用能力;其次探讨了教学手段和方法,通过课程引入激发学习兴趣,注重课堂讨论分析,加强实验教学,注重类比归纳,进行多媒体辅助教学,从而提高离散数学的教学效果。 【关键词】离散数学;教学内容;教学方法;教学手段 1.引言 1 离散数学是现代数学的重要分支,是计算机科学与技术专业的重要基础课,主要研究离散结构和离散数量的关系。随着计算机科学技术的迅猛发展,离散数学越来越重要,其基本理论在计算机理论研究以及计算机软件、硬件开发的各个领域都有广泛的应用[1]。 离散数学的授课内容主要分为“数理逻辑”,“集合论”,“代数结构”、“图论”,“组合分析”以及“形式语言与自动机”等几大分支,课程概念较多,定义及定理比较抽象,理论性较强[2]。在教学过程中,如果只从数学方面讲授定义定理,学生理解起来比较困难,容易对本课程的学习失去兴趣。因此,设计精彩的教学内容,改进教学方法,探讨教学手段,以提高学生学习的主动性和积极性,具有重要的意义 。 2.精选教学内容 改变教学观念 2.1 精选教学内容 离散数学是计算机科学与技术本科专业的一门基础课,众多本科高校均开设此课程,其教材也非常丰富。因此,需要教师在符合学校自身办学方略和培养目标的基础上,精选教学内容。笔者工作单位上海电机学院是一所具有技术应用型 2 本科内涵实质和行业大学属性特征的全日制普通本科院校,办学方略注重“技术立校,应用为本”,因此从学校学生培养方案和学校特色出发,对本课程的教学不能照搬研究型大学的授课方式和教学内容。应该从学生的自身素质以及课程应用性的角度出发精选授课内容,培养学生对课程内容的实际应用能力,让学生从枯燥的数学概念中走出来,达到学以致用的目的。 2.2 改变教学观念 在离散数学课程的教学过程中,如果采取传统的教师讲授,学生课堂听课的方式,学生普遍觉得内容枯燥,提不起学习兴趣。因此教师应在传统课堂教学方法的基础上,注重学生的发展和参与,应“以教师为主导,以学生为主体”,在授课过程中从教师为主体变为以学生为主体,在教学过程中设置问题情境,启发学 百度搜索“就爱阅读”,专业资料,生活学习,尽在就爱阅读网92to.com,您的在线图书馆 3 4 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:我在看电视边吃苹果。 ) 设Q:一个数是奇数。R:一个数不能被2除。 c (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)) ) A;B;(A?B) ;(B?A) ;((A?B)?(B?A)) d (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 T T T T F F F T F T F T F F F F T F F F F F F F T T T F F F F T F F F F F F F T F F F F 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 , , , , 所以,P?(Q?R) , (P?Q)?R ;) , , , ,?, ,?(,?,) ,?, ,?, (,?,)?(,?,) , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , , 所以,P?(Q?R) , (P?Q)?(P?R) ,) P Q ?P ?Q ?P??Q ?(P?Q) ?P??Q ?(P?Q) T T F F F F F F T F F T T T F F F T T F T T F F F F T T T T T T 所以,?(P?Q) ,?P??Q, ?(P?Q) ,?P??Q (5)解:如表,对问好所填的地方,可得公式F,F,可表达为 16 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 ?Q为F,则P为F,且Q为F, 设P 故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 ?R?Q 或5不是素数,或7被2除尽 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成立。 ?(A?B) ,?A??B d) 设?(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。命题得证。 (A?B)?C,?D,?C?D,?A??B f) 设(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 ?C) ?(B ,?(?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。 ,Q,Q,P,P,P,Q,Q,故实际有: 但P 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 ,(P,Q), ?(P,Q) F (P,Q),(P,Q),P,Q. 故由(B)类使用,运算后,结果仍在(B)中。 由上证明:用,,?两个连结词,反复作用在两个变元的公式中,结果只能产生(B)类中的公式,总共仅八个不同的公式,故{,,?}不是功能完备的,更不能是最小联结词组。 已证{,,?}不是最小联结词组,又因为P Q, ?(P,Q),故任何命题公式中的联结词,如仅用{ , ?}表达,则必可用{,,?}表达,其逆亦真。故{ , ?}也必不是最小联结词组。 (8)证明{?},{?}和{?}不是最小联结词组。 ? ? ? 证明:若{?},{?}和{?}是最小联结词,则 ?P,(P?P???) ?P,(P?P???) ?P,P?(P?(P???) ,则等价式左边为F,右边为T,与等价表达式矛盾。 对所有命题变元指派T 所以{?},{?}和{?}不是最小联结词。 c (9)证明{?,?}和{?, }是最小联结词组。 ? 证明:因为{?,?}为最小联结词组,且P?Q,?P?Q 所以{?,?}是功能完备的联结词组,又{?},{?}都不是功能完备的联结词组。 所以{?,?}是最小联结词组。 c c c 又因为P?Q,?(P Q),所以{?, }是功能完备的联结词组,又{?},{ }不是功能完备的联结词组, ? ? ? 所以{?, }是最小联结词组。 c ? 习题 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=,0 b) Q?(P??Q) , (P?Q)?(Q??Q) P?Q =,, 3 ,, 0,1,2 ,(P?Q)?(P??Q) ?(?P?Q) c) P?(?P?(Q?(?Q?R)) ,P?(P?(Q?(Q?R)) ,P?Q?R=, 0 ,, 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 ,, 1,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 ,,= (?P??Q) ?(?P?Q) ?(P??Q) ?(P?Q) 0,1,2,3 f) (Q?P) ?(?P?Q) , (?Q?P) ??P?Q , (?Q?P) ??(P??Q) ,F ,,= (P?Q) ?(P??Q) ?(?P?Q) ?(?P??Q) 0,1,2,3 (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去出差。 V若A去则C和D中要去一个。 A?(CD) B和C不能都去。 ?(B?C) C去则D要留下。 C??D 按题意应有:A?(CD),?(B?C),C??D必须同时成立。 V 因为CD , (C??D) ?(D??C) V 故(A?(CD))??(B?C) ?(C??D) V , (?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) 在上述的析取范式中,有些(画线的)不符合题意,舍弃,得 ?C?D)?(?D?C??B) (?A??C) ?(?B??C?D) ?( 故分派的方法为:B?D ,或 D?A,或 C?A。 (8) 解:设P:A是第一。Q:B是第二。R:C是第二。S:D是第四。E:A是第二。 VVV 由题意得 (PQ) ?(RS) ?(ES) , ((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 (1)T,I (2) B (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 Q?R) ??R (1) (? (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 (B?F) (1)T,I (3) ? (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 D) ?E P (13) (C? (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 (2)(4)T,I (5) D (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 E (2)(4)T,I (5) A? (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?C),(C?D)?E,?F?(D??E),,A?(B?F) b)A? (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 (D??E) (9)T,E (10) ? (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 证法二:(反证法) P P(附加前提) (1) ? (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 ?(P?Q)??(R?S),((Q?P)??R),R,P,Q c) (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,我的程序没有通过 实验一 油管铺设 实验准备 最小生成树问题,求最小生成树的Prim 算法 实验目的 运用最小生成树思想和求最小生成树程序解决实际问题 实验过程 八口海上油井相互间距离如下表,其中1号井离海岸最近,为5km 。问从海岸经1号井铺设油管把各井连接起来,怎样连油管长度最短(为便于检修,油管只准在油井处分叉)? 实验二 最短路问题 实验准备 图的邻接矩阵,求最短路的 Dijkstra 算法 实验目的 运用最短路思想和求最短路程序解决实际问题 实验过程 某建筑公司签订了一项合同,要为一家制造公司建造一座新的加工厂。合同规定工厂的完工 期限为12个月。要是工厂不能在一年内完工,就要赔款,因此建筑公司认真分析,找出建筑工厂必须完成的各道工序和这些工序之间的先后关系,并估计出它们延续的时间,如下表所示。为建筑公司制定工程完工计划提供理论依据。 实验三 中国邮递员问题 实验准备 欧拉图,中国邮递员问题(G 是欧拉图;G 不是欧拉图:G 正好有两个奇次顶点,G 有2n 个奇次顶点n ≥2) 实验目的 通过程序实现中国邮递员问题,强化其基本思想和实际应用 实验过程 针对下图所示加权图G ,给出中国邮递员问题的解决方案。 实验四 旅行推销商问题 实验准备 哈密顿图,旅行推销商问题 实验目的 通过程序实现旅行推销商问题,强化其基本思想和实际应用,并初步了解NP -难题。 实验过程 自拟一加权连通图,求出具有充分小权的哈密顿回路。 转载请注明出处范文大全网 » 离散数学(左孝凌)课后习题解范文三:离散数学 教学视频 离散数学教学方法探讨
范文四:离散数学 左孝凌 李为鉴 刘永才编著课后习题答案
范文五:离散数学实验