离散数学复习资料习题与解答

《离散数学复习资料习题与解答》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《离散数学》习题与解答第一篇数理逻辑第一章命题逻辑1-1(1)指出下列语句哪些是命题，哪些不是命题，如果是命题指出他的真值a)离散数学是计算机科学系的一门必修棵b)口裁吗？c)明天我去看电影d)请勿随地吐痰e)不存在最大质数f)如果我掌握了英语，法语，那么学习其他欧洲的语言就容易多了g)9+5<12h)x<3i)月球上有水j)我正在说假话［解］a)不是命题b)是命题，真值视具体情况而定c)不是命题d)是命题，真值为te)是命题，真值为tf)是命题，真值为fg)不是命题h)是命题，真值视具体情况而定i)不是命题1-2(1)用P表示命题“天下雪”，(又表示命题“我将去镇上”川表示

2、命题“我有时间”.以符号形式写出下列命题：(a)如果天不下雪和我有时间，那么我将去镇上.(b)我将去镇上，仅当我有时间.(c)天不下雪(d)天下雪，那么我不去镇上［解］a)(-］PAR)-Qb)Q->Rc)qPd)P->nQ1-2(2)将下而这段陈述屮所出现的原子命题符号化，并指出他们的真值，然后将这段陈述屮的每一命题符号化、吃是有理数是不对的.2是偶素数.2或4是素数.如杲2是素数则3也是素数.2是素数当且仅当3也是素数.［解］:陈述屮出现5个原子命题，将他们符号化为：P:、血是有理数Q：2是素数R：2是偶数S:3是素数U:4是素数其真值为F其真值为T其真值为T其真值为T其

3、真值为F陈述中各命题符号化为：-1P;QAR;QVU;Q->S;Q<=>S1-2(3)将下列命题符号化a)如果3+3=6,则雪是白色的.b)如果3+3H6,则雪是白色的c)如果3+3=6,则雪不是白色的.d)如果3+3H6,则雪不是白色的e)王强身体很好，成绩也很好.f)四边形ABCD是平行四边形，仅当其对边平行［解］:设P:3+3二6Q:雪是白色的R:王强成绩很好S:王强身体很好U:四边形ABCD是平行四边形V:四边形ABCD的对边是平行的于是：a)可表示为:P—Qb)可表示为：P~*Qc)可表示为：P—-］Qd)可表示为：1P-*-

4、Qe)可表不为：SARf)可表示为:U

5、<=>V1-3(1)判别下列公式中哪些是合式公式，那些不是合式公式a)(Q-RAS)b)(p<=>(R->s))c)(GP-Q)f(Q-P)))d)(RS-T)e)((P-(Q->R))-((PfQ)-*(P~R)))［解］:a)不是合式公式(若规定运算符优先级后也可以作为合式公式)b)是合式公式c)不是合式公式(括号不配对)d)不是合式公式e)是合式公式1-3(2)对下列各式用指定的公式进行代换：a)(((A->B)->B)->A),用(A-C)代换A,用((B/C)-A代换B。b)((A-B)V(B-A),用B代换A,A代换B.［解］:a)((((A-*C)-((BAC

6、)-A))-((BAC)->A))->(A-C))b)((B->A)V(A->B))1-3(3)用符号形式写出下列命题a)假如上午不下雨,我去看电影;否则就在家里读书或看报.b)我今天进城，除非下雨.c)仅当你走，我将留下.［解b)设P:上午天下雨.Q:我去看电影R：我在家读书S:我在家看报原命题可译为：(-1P-Q)A(P-(RVS))b)设:P:我今天进城Q:天下雨原命题可译为：iQfPc)设:P:你走Q：我留下原命题可译为:Q-*P1—3(4)称「Pf~iQ为条件命题P-*Q的反换式QfP为条件命题Q的逆换式-1Q-1P为条件命题P-Q的逆反式试写出如下条件命题的反换式

7、，逆换式，逆反式。(a)如果他有勇气，则他将得胜。(b)如果天下雨，我不去。［解］(a)设P：他有勇气，Q：他将得胜原条件命题可译为：P-Q反换式：「Q,表示：如果他没有勇气，则他将不能获胜。逆换式：Q-P,表示：如果他将得胜，则他有勇气。逆反式：「P,表示：如果他不获胜，则他没有勇气。(b)设P：天下雨，Q：我去原条件命题可译为：P—Q反换式：-1P-Q,表示：如果如果天不下雨，则我去。逆换式：Q-P,表示：如果我不去，则天下雨。逆反式：nQ-*nP,表示：如果我去，则天不下雨。1-4(1)试求下列各命题公式的真值表并解释其结果(a)(P-Q)A(Q-P)；(b)(PAQ)

8、7；(c)Q->(PVQ)；(d)(P-Q)<=>(-1PVQ)；(e)(nPVQ)A(n(1PAnQ))；(f)-i(P-Q)AQARo［解］(a)从真值表1-1中可看出：(P-Q)A(Q-P)<=>(PV=>Q)(b)从真值表1-2中可看出：(PAQ)-P是永真式(c)从真值表1-3中可看出：Q-*(PVQ)是永真式(d)从真值表1-4中可看出：(P-Q)<=>(-］PVQ)是永真式(e)从真值表1-5屮可看出：(-1PVQ)A(-1(-1PA-iQ))<=>1PVQ<=>P->Q<=>-1(PA-