《离散数学作业》由会员分享，可在线阅读，更多相关《离散数学作业（20页珍藏版）》请在金锄头文库上搜索。
1、 离散数学作业布置第1次作业（P15）1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p(qr)=0(01)=0 （2）（pr）(qs)=（01）(11)=01 =0 （3）（pqr）(pqr)=（111） (000)=0(4)（ rs）(p q)=（01）(10)=00=11.17 判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则 也是无理数。另外只有6能被2整除，6才能被4整除。”解： p: 是无理数 1 q: 3是无理数 0 r: 是无理数 1 s:6能被2整除 1t: 6能被4整除 0 命题符号化为： p(qr)(ts)的真值为1，所以
2、这一段的论述为真。1.19 用真值表判断下列公式的类型：（4）(pq) (qp)（5）(pr) (p q)（6）(pq) (qr) (pr)解： （4） p q pq q p q p (pq)( q p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式 ，最后一列全为1（5）公式类型为可满足式（方法如上例），最后一列至少有一个1（6）公式类型为永真式（方法如上例，最后一列全为1）。第2次作业（P38）2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.(1) (pqq)(
3、2)(p(pq)(pr)(3)(pq)(pr)解：(1) (pqq)(pq) q)(pq) qp(q q) p0 0所以公式类型为矛盾式(2)（p(pq)）(pr) (p(pq)( pr)ppqr1 所以公式类型为永真式(3) (pq) (pr) (pq) (pr) (pq) (pr)易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111P q r pq pr (pq) (pr)0 0 0 10 10 0 1 1 0 10 1 0 0 0 00 1 1 00 01 0 0 0 0 01 0 1 0 1 11 1 0 00 01 1 1 0 1 1 所以公式类型为
4、可满足式2.4 用等值演算法证明下面等值式：(2) ( (pq)(pr) ) (p(qr)(4)(pq)(pq) (pq)(pq)证明（2）(pq)(pr)( pq)(pr)p(qr)p(qr)（4）(pq)(pq) (p(pq) (q(pq) ) (pp)(pq)(qp) (qq)1(pq) (pq)1 (pq)(pq)第3次作业（P38）2.5 求下列公式的主析取X式, 并求成真赋值:(1)( pq) (qp)(2) (pq) qr(3)(p (qr) (pqr)(4) (pq) qr解：(1)(pq) (qp)(pq) (qp)pq q pq p(吸收律)(pp)q p(qq)pqpq
5、pq pqm0m2m2m3m0m2m3成真赋值为 00, 10, 11.(2) (pq) qr (pq) qr (pqr) qr (pqr) (p p) qrpqrp qrpqrm3m7成真赋值为011，111.(3) (p(qr) (pqr)(p(qr) (pqr)p(qr) (pqr)p(qr)(pqr)pqprpqrpq(rr)p(qq)rp(qq) (rr) (pp) q(rr)(pp) (qq) rm0m1m2m3m4m5m6m7, 为重言式.(4) (pq) qr(pq) qr (pq) qr p(q q)r0主析取X式为0, 无成真赋值, 为矛盾式.第4次作业（P38）2.6 求
6、下列公式的主合取X式, 并求成假赋值:(1) (qp) p(2)(pq) (pr)(3)(p(pq) r解：(1) (qp) p(qp) pqp pq00M0M1M2M3这是矛盾式. 成假赋值为 00, 01, 10, 11.(2)(pq) (pr)(pq) pr(pp)(p q)r (p q)rp qrM4, 成假赋值为100.(3)(p(pq) r(p(pq) r(pp)q r1主合取X式为1, 为重言式.第5次作业（P41）2.32 用消解原理证明下述公式是矛盾式:(1) (pq) (pr) (qr) (pr) r(2)(pq) pq)解：(1) (pq) (pr) (qr) (pr)
7、r第一次循环 S0=, S1=pq,pr,qr,pr,r, S2=由pr, pr消解得到输出“no”，计算结束(2)(pq) pq)(pq) p) q)(pq) p) q (pq) p q第一次循环 S0=, S1=pq,p, q, S2=由pq,p消解得到q,由q, q消解得到,输出“no”，计算结束2.33 用消解法判断下述公式是否可满足的:(1) p (pq) q(2) (pq) (pq) (p r)解：(1) p (pq) q第一次循环 S0=, S1=p, pq, q, S2=由p, pq消解得到q,由q, q消解得到,输出“no”，计算结束(2) (pq) (pq) (p r)第一
8、次循环 S0=, S1=pq, pq, p r, S2=由pq, pq消解得到p,由pq, p r消解得到q r,由pq, p r消解得到q r,由p, p r消解得到r,S2=p, q r, q r, r第二次循环 S0=pq, pq, p r, S1=p, q r, q r, r, S2=由pq, q r消解得到pr,由pq, q r消解得到pr,由pq, q r消解得到pr,由p r, p 消解得到r,S2=pr第三次循环 S0=p, q r,q r, r, S1=pr, S2=S2=输出“yes”，计算结束第6次作业（P52）3.6 判断下面推理是否正确. 先将简单命题符号化, 再写出
9、前提, 结论, 推理的形式结构(以蕴涵式的形式给出)和判断过程(至少给出两种判断方法):(1)若今天是星期一, 则明天是星期三；今天是星期一. 所以明天是星期三.(2)若今天是星期一, 则明天是星期二；明天是星期二. 所以今天是星期一.(3)若今天是星期一, 则明天是星期三；明天不是星期三. 所以今天不是星期一.(4)若今天是星期一, 则明天是星期二；今天不是星期一. 所以明天不是星期二.(5)若今天是星期一, 则明天是星期二或星期三. 今天是星期一. 所以明天是星期二.(6)今天是星期一当且仅当明天是星期三；今天不是星期一. 所以明天不是星期三.设p: 今天是星期一, q: 明天是星期二,
10、r: 明天是星期三.(1)推理的形式结构为(pr) pr此形式结构为重言式, 即(pr) pr所以推理正确.(2)推理的形式结构为(pq) qp此形式结构不是重言式, 故推理不正确.(3)推理形式结构为(pr) rp此形式结构为重言式, 即(pr) rp故推理正确.(4)推理形式结构为(pq) pq此形式结构不是重言式, 故推理不正确.(5)推理形式结构为(p(qr) )p q它不是重言式, 故推理不正确.(6)推理形式结构为(pr) pr此形式结构为重言式, 即(pr) pr故推理正确.推理是否正确, 可用多种方法证明. 证明的方法有真值表法, 等值演算法. 证明推理正确还可用构造证明法.下面用等值演算法和构造证明法证明(6)推理正确.1. 等值演算法(pr) pr(pr) (rp)pr(pr) (rp)p) r (pr) (rp) p r(pr)(rp)p r (rp)p r吸收律 (rp)（p r）德摩根律1即(pr) pr故推理正确2.构造证明法前提: (pr), p结论: r证明:
