离散数学是传统逻辑学集合论数论基础.ppt

* a)解：设P：他有理论知识；Q：他有实践经验。则命题转化为： P ∧ Q b)解：设P：明天下雨；Q：明天下雪；R：我去学校 则 i)： ?(P∧Q) →R ii)： ?P∧ ?Q →R iii)：P ∨Q → ? R iv)： P∧Q∧R∨?P∧Q∧R∨P∧?Q∧R∨? P∧?Q∧R v)： ? P∧?Q ? R * c)：说小学生编不了程序，或说小学生用不了个人计算机，那是不对的。 解：设P：小学生会编程序；Q：小学生会用个人计算机； 则? (? P ∨ ? Q) d)：若不是他生病了或出差了，我是不会同意他不参加学习 解：设P：他生病了；Q：他出差了；R：我们同意他不参加学习； 则?(P∨Q) ? ?R或?(P∨Q) ? ?R e)：如果我上街了，我就去书店看看，除非我很累 解：设P：我上街；Q：我去书店看看；R：我很累； 则：P →(?R →Q)或?R →(P →Q)或(?R ∧P) →Q * 解： (1).永真公式； (2).永真公式； (3). 可满足公式。 * 解：G(H, S) = ?(H→S)→H = ?((P ∧Q) →(P?Q))→(P∧Q) =G’(P, Q); 用真值表验证 ，先验证G(H, S)，再验证G’(P, Q)。 解：设P：开关P闭合，Q：开关Q闭合，S：开关S闭合，G：灯泡亮 则G=(P∧Q∧S)∨(P∧R∧S) =(P∧S∧Q)∨(P∧S∧R) =(P∧S) ∧(Q∨R) * 则执行X的条件为：(A∧B)∨(?A∧B) =B∧(A∨?A) =B 执行Y的条件为：(A∧?B)∨(?A∧?B) =?B∧(A∨?A) =?B 解：设P：输入端P为高电位，Q：输入端Q为高电位，R：输入端R为高电位； 则：((P∧Q)∨(P∧R))∧(Q∨R) =(P∧(Q∨R))∧(Q∨R) ∴电路简化为： ∴程序可简化为：if B then X else Y，流程图为： * 证明： (1). P∨?((P∨?Q)∧Q) = P∨?(P∨?Q)∨?Q =(P∨?Q)∨ ?(P∨?Q) =T (2). P→(Q→R) =?P∨(Q→R) =?P∨(?Q ∨R) =(?P∨?Q)∨R =? (P∧Q)∨R =(P∧Q)→R (3).(P∧(Q∨R))∨(P∧?Q∧ ?R) = P∧((Q∨R)∨(?Q∧ ?R) = P∧((Q∨R)∨? (Q∨R) = P∧T = P (4).(?P∧(?Q∧R))∨(Q∧R)∨(P∧R) = ((?P∧?Q)∧R)∨((Q∨P)∧R) = (?(P∨Q)∧R)∨((Q∨P)∧R) = (?(P∨Q) ∨(Q∨P))∧R = T∧R = R * 证明：(用归纳法证明) (1): ?Pi=?Pi；?T=F；?F=T；所以当A是由一个变元或常元构成时公式(1)成立； (2): 设A1(P1,P2, …,Pn)，A2(P1,P2, …,Pn)对公式(1)成立，即： ?A1(P1,P2, …,Pn)=A1*(?P1, ?P2, …, ?Pn) ?A2(P1,P2, …,Pn)=A2*(?P1, ?P2, …, ?Pn) 现证明：①A1∧A2，②A1∨A2，③?A1时， 公式(1)也成立。 ①记A1∧A2为A，A= A1∧A2则A*= A1*∨A2*,由定义： ?A(P1,P2, …,Pn) =?(A1(P1,P2, …,Pn)∧A2(P1,P2, …,Pn)) =?A1(P1,P2, …,Pn)∨?A2(P1,P2, …,Pn) =A1*(?P1, ?P2, …, ?Pn)∨A2*(?P1, ?P2, …, ?Pn) =A*(?P1, ?P2, …, ?Pn) ②A1∨A2，同理可证 ③?A1，记?A1为A，?A1=A则A* =?A* ?A(P1,P2, …,Pn) =?(?A1(P1,P2, …,Pn)) =?(A1*(?P1,?P2, …,?Pn)) =A*(?P1,?P2, …,?Pn) ∴公式(1)成立 * 证明： A=B，即 A(P1,P2, …,Pn)?B(P1,P2, …,Pn)永真 ∴ ? A(P1,P2, …,Pn)? ?B(P1,P2, …,Pn)永真 由定理1.4 ：A*(?P1, ?P2, …, ?Pn) ?B*(?P1, ?P2, …, ?