大二课件-离散第6次课2013年3月15日

例10.30R→S前P→(Q→S)，R∨P的有效结论证明：(1) 规则 (1),置换规 P附加前提 (23),假言推 (45),假言推 (67),假言推 CP例前提pq,pr,st,sr,t 结论证明：st②③s④⑤⑥p⑦⑧p⑨例

r,

p证明：①p

q ③ ④r

例：一 一 案，已知事实如下A或 了 若 了x，则作案时间不可能发生在午夜前若 正确，则在午夜时屋里灯光未灭若 不正确，则作案时间发生在午夜之前A不富裕问：谁 犯，写出推导过程解：设 了 了

例：一 A或 了 r：作案时间发生在

若 若 t：午夜时灯光未灭u：A不富裕

A 再将各前提写出p∨q,p→r,s→t,s→r,t,① ② ①②拒取④ ③④假言推⑥ ⑤⑥拒取⑧ ⑨q 了x。前提u在推理过程中没有

t,不是p，就是基本蕴涵例前提:如 飞或羊吃草,则母鸡就会是飞鸟;如果鸡是飞鸟,那么烤结论:羊不吃草。符号化上述语句

鸭子还会跑;飞Q羊吃草

鸭子不会跑R:母鸡是飞鸟S:烤 鸭子还会跑,S:烤

鸭子不会跑Q前提集合{P∨QR,RS,S},结论Q (1(2),拒取 (3(4),拒取 (5), (6),I例如 解设P: PQ,QR,R∧S公 依 结论: 考试没通过6是偶数，则2不能整除7；因此，6q：2证明P②r③rP④q⑤pP⑥例如果乙不参加篮球赛，那么甲就不参加；qr

p

r)

p

证明：①②q③p

⑤q qrqqr qqrq

qr定义10.25设H1，H2，…，Hm都是命题公式，P1，P2，…，Pn是其中的全部命题变元，在P1，P2，…，Pn的全部真值指派中，如果存在一组真值指派，使得H1∧H2∧Hm为T，则称公式H1，H2，…，Hm是相容的(一致的)；如果对于P1，P2，…，PnH1∧H2∧∧Hm的真值均为则称公H1，H2，…，Hm是不相容的设有一组前提H1，H2，…，Hm，要推出结论即要证明H1∧H2∧∧HmC记作SC即S→C为永真亦S∨C永故S∧C为永假，因此，要证明H1∧H2∧∧HmC只要证H1∧H2∧HmC相容即可例若A若A若AA证明P:A因病缺了许多课,Q:A中学考试失败,R:A有知识,SA读了许多书。PQQR,SR,P∧SPP(1)化简S(1)化简PQ(2),(4)假言推PR(3),(6)假言推P(5),(8)假言推

例：证明A是A→B，(B∨C)的有效结论。证明：(1)A→B 规则P P附加前提 (3)，置换规 (1)，(2)，假言推 (5)，(6)，p33结论有效例：证明D→C是A→(B→C)，D∨A，B的有效结论。证明：(1)D 规则P(附加前提) (2’ (2)置换规 (1)，(2’ (3)，(4 (5)，(6 结论有效 基本蕴涵能判定真陈述句称作命题。要将自然语言表达的问题符号化为命题,使推理过程简捷、正确。命题联结词作用于命题时,和数算符号相当，所以又称逻辑运算符。联结词反映了复合命题和部分命题之间的真假关系,这种关系是命题联结词的逻辑内如果一个联结词可以由集合中其它的联结词来定义,则该联结词称为冗余的联结词,否则,称为独立的联结命题公式是由命题、命题变元，命题联结词和圆 题演算方法,当公式很复杂所含命题变元很多时,真值表法的工作量太大。利用等价式进行命题演算和推理是切实可行的,但技巧性用对偶原理可成对 公式并推导新公式一、命题与联结词1 2

判断命题(简单或复合)二、命题公式及分类12 三、等值演算12五、对偶与范式2 六、推理理论12

例判断下列各语句中，命题，简单命题，2x30，2若22

明年5月1解：命题有例下列语句哪些是命题，哪些不是命题？若是命题，2020年会出 电灯不亮是灯泡或线路有毛病，或者是停电所致。 7）我正在说谎。Paradox (p

p

(

q)

pq例求命题公式(pq)(q q)(qpq)q

q)(pp)q

q)(

q)(

(0,2,故主合取范式为

(q A

(p

r)

解A

r)

qr)(p

r)

(p

r)(

r)(

qr)

(0,1,2,3,5,A(pqr)(pqr)M4M6(4,例pp解：可用多种方法(如真值表法，等值演算法主范式法)p

(p

q)

pq 写出对应下面推理的证明证明：

p：红队第三，qr

前提：p

r),s

p,

前提：p

r),s

p,①②s①②s③p④p⑤q⑥q⑦8rs规则因此 都在说谎。问谁说真话,谁说假话？解设A: 说真话;B: 说真话;C: 依题意有AB,BC,CA∧B。(AB)∧(BC)∧(C(AB)∧(BA)∧(BC)∧(C即 说真话 说假话“童画报》”。问:什么情况下,这位父亲食言？(2(3)父亲没去书店,却给儿子买了《儿童画报》。(4)父亲没去书店,也没给儿子买《儿童画报》。显然(1),(4)(3只有情况(2),命题逻辑例 ,需满足若AC若BC解记p:派A去,q:派Br:派C(1) (2) (3)命题命题逻辑例结论:方案1派A与C去 方案2派B命题命题逻辑例 如果B愉快，那么A不努力工作；命题逻辑例证明：设A：A、、分别表示、C、愉快。则前提公式为：(∨)，，C结论为：AD P（附加前提② T①、④ ⑤ T

T①、 T③、⑧ ⑨ T T⑦、⑾ 命题逻辑例

解设P：它占据空间 后来认 命题逻辑例解:P:今天下雨,Q:今天我进城PQPQ:一个数能被1整除,命题逻辑例 命题逻辑例

解：设3个表决者的按钮分别与命题变元P1，P2，P3对应 根据题意，电铃与按钮之间的关系如下表所示命题逻辑例B00000010B00000010010001111000101111011111P1P2P3， P1P2P3P1P2P3，P1P2P3B(P1P2P3)(P1P2P3)(P1P2P3)(P1P2P3）命题逻辑例证明｛↑｝是极小全证：(1)P∧QP∨Q PP→Q PQ 命题逻辑例

P：矿样为铁；Q：矿样为铜；R命题逻辑例甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁P：矿样为铁；Q：矿样为铜；RF1F2(甲全对)∧(乙全错)∧(丙对一半)F3(甲对一半)∧(乙全对)∧(丙全错)F4(甲对一半)∧(乙全错)∧(丙全对)F5(甲全错)∧(乙对一半)∧(丙全对)F6命题逻辑例甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁P：矿样为铁；Q：矿样为铜；R：矿样为锡F1(甲全对)∧(乙对一半)∧(丙全错)(P∧Q)∧((P∧R)∨(P∧R))∧(P∧Q∧R)∧((P∧R)∨(P∧R)(P∧Q∧R∧P∧R)∨F2(P∧Q)∧(P∧R)∧((P∧R)∨(P∧R)命题逻辑例甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁P：矿样为铁；Q：矿样为铜；RF1(甲全对)∧(乙对一半)∧(丙全错)F2(甲全对)∧(乙全错)∧(丙对一半)F3(甲对一半)∧(乙全对)∧(丙全错)F4(甲对一半)∧(乙全错)∧(丙全对)F5(甲全错)∧(乙对一半)∧(丙全对)F6

设XXF1∨F2∨F3∨F4∨F5∨(P∧Q∧R)∨(P∧Q∧R)命题逻辑例甲说：这不是铁，也不是铜；乙说：这不是铁，是锡；丙说：这不是锡，是铁P：矿样为铁；Q：矿样为铜；R设XXF1∨F2∨F3∨F4∨F5∨(P∧Q∧R)∨(P∧Q∧R)于是Q,R中必有假命题,P∧Q∧RP∧Q∧R命题逻辑例

16.有一逻辑学家误入某部落，被拘于劳狱，酋长意欲放行，他对逻辑学家说：“今有两门，一为自由,一为死亡,你可任意开启一门。现你从两战士中选择一人负责Sol逻辑学家手指一门问其中一战士说;“门他(指另一名战士)将答‘是’对吗当被问战士回答“对”