1、習(xí)題課習(xí)題課1 1 - - 命題邏輯命題邏輯2014 2014 秋季秋季第一章第一章 命題邏輯命題邏輯 總總 結(jié)結(jié)一、基本概念一、基本概念n命題命題 命題的真值命題的真值 原子命題、復(fù)合命題原子命題、復(fù)合命題邏輯聯(lián)結(jié)詞（、邏輯聯(lián)結(jié)詞（、 、）n命題公式命題公式 公式的解釋公式的解釋永真式永真式( (重言式重言式) )永假式永假式( (矛盾式，不可滿(mǎn)足公式矛盾式，不可滿(mǎn)足公式) )可滿(mǎn)足式可滿(mǎn)足式n命題公式的等價(jià)命題公式的等價(jià) 基本等價(jià)式基本等價(jià)式命題定律命題定律替換規(guī)則（定理）替換規(guī)則（定理） 對(duì)偶式對(duì)偶式 對(duì)偶原理對(duì)偶原理 n范式范式 句節(jié)、子句、短語(yǔ)、析取范式、合取范式句節(jié)、子句、短語(yǔ)、析

2、取范式、合取范式極小項(xiàng)極小項(xiàng)-主析取范式主析取范式 極大項(xiàng)極大項(xiàng)-主合取范式主合取范式 n命題公式的蘊(yùn)涵命題公式的蘊(yùn)涵基本蘊(yùn)含（關(guān)系）式基本蘊(yùn)含（關(guān)系）式 n推理規(guī)則推理規(guī)則 P P規(guī)則（稱(chēng)為前提引用規(guī)則）規(guī)則（稱(chēng)為前提引用規(guī)則） 規(guī)則（邏輯結(jié)果引用規(guī)則）規(guī)則（邏輯結(jié)果引用規(guī)則） 規(guī)則（附加前提規(guī)則）規(guī)則（附加前提規(guī)則） 二、基本方法二、基本方法1、應(yīng)用基本等價(jià)式及置換規(guī)則進(jìn)行等價(jià)演算應(yīng)用基本等價(jià)式及置換規(guī)則進(jìn)行等價(jià)演算2 2、求主析?。ㄖ骱先。┓妒降姆椒ㄇ笾魑鋈。ㄖ骱先。┓妒降姆椒? 1）公式轉(zhuǎn)換法）公式轉(zhuǎn)換法2 2）真值表技術(shù)法）真值表技術(shù)法 主合取范式主合取范式-在命題公式的真值表中，使

3、公式取值在命題公式的真值表中，使公式取值 0 0時(shí)的解釋所對(duì)應(yīng)的時(shí)的解釋所對(duì)應(yīng)的全部極大項(xiàng)的合取式全部極大項(xiàng)的合取式。 主析取范式主析取范式-在命題公式的真值表中，使公式取值在命題公式的真值表中，使公式取值 1 1時(shí)的解釋所對(duì)應(yīng)的時(shí)的解釋所對(duì)應(yīng)的全部極小項(xiàng)的析取式全部極小項(xiàng)的析取式。 3 3、推理的各種方法、推理的各種方法n（1 1）直接法）直接法n（2 2）利用）利用CPCP規(guī)則規(guī)則n（3 3）反證法）反證法 4 4、消解法、消解法1.1.命題邏輯表達(dá)式的翻譯：命題邏輯表達(dá)式的翻譯：n除非你已滿(mǎn)除非你已滿(mǎn)1616周歲，否則只要你的身高不足周歲，否則只要你的身高不足1.21.2米就米就不能乘公

4、園滑行鐵道游樂(lè)車(chē)。不能乘公園滑行鐵道游樂(lè)車(chē)。解：令解：令P P：你能乘坐公園滑行鐵道游樂(lè)車(chē)。：你能乘坐公園滑行鐵道游樂(lè)車(chē)。 Q Q：你身高不足：你身高不足1.21.2米。米。 R R：你已滿(mǎn)：你已滿(mǎn)1616周歲。周歲。n翻譯成：翻譯成：(R R Q) PQ) P三、典型例題三、典型例題2 2、試證明、試證明 (P(QR)(P (P(QR)(P Q Q R)R) P P證明：證明： (P(QR)(P (P(QR)(P Q Q R) R) P(QR)(P(QR)(Q Q R)R)（分配律）（分配律） P(QR)P(QR)(QR)(QR) ) (De Morgan(De Morgan定律定律) )

5、PTPT（矛盾律）（矛盾律） P P ( (同一律同一律) )3 3、證明、證明 (P(PQ) Q) (P(PQ) Q) (P(PQ)Q)證：證： (P(PQ)Q)(P(PQ) Q) (P(PQ)Q)(P PQ) Q) (De Morgan(De Morgan定律定律) ) (P(PQ)Q)P)P) (P(PQ)Q)Q) Q) （分配律）（分配律） (P(PP)P)(Q(QP)P)(P(PQ)Q)(Q(QQ)Q) (Q(QP)P)(P(PQ) Q) （矛盾律）（矛盾律） ( (QQP)P)( (P PQ) Q) (De Morgan(De Morgan定律定律) ) ( (Q(QP)P)(P(

6、PQ) Q) （蘊(yùn)涵式）（蘊(yùn)涵式）(P(PQ) Q) （等價(jià)式）（等價(jià)式）4 4、 G=G=( ()，求公式，求公式G G的主析取范式和主合取范式。的主析取范式和主合取范式。解：首先列出其真值表如下：P Q R P Q R PQPQ（PQPQ）( (PQ)RPQ)R0 0 00 0 01 10 00 00 0 10 0 11 10 01 10 1 00 1 01 10 00 00 1 10 1 11 10 01 11 0 01 0 00 01 11 11 0 11 0 10 01 11 11 1 01 1 01 10 00 01 1 11 1 11 10 01 1極大項(xiàng)極大項(xiàng)極小項(xiàng)極小項(xiàng)PQR

7、PQRPPQRQRPPQRQRP PQ QR RP PQ QR RP PQ QR RP PQ QR RP PQ QR R主析取范式主析取范式= =（P PQ QR R）（P PQ QR R）（P PQ QR R）（P PQ QR R）（P PQ QR R）=m=m1 1 m m3 3 m m4 4 m m5 5 m m7 7主合取范式主合取范式= =（ PQRPQR ）（ PPQRQR ）（PPQRQR）=M=M0 0 M M2 2 M M6 6 5 5、用公式轉(zhuǎn)換法求上題中的主析取和主合取范式、用公式轉(zhuǎn)換法求上題中的主析取和主合取范式( ()（P PQQ）R R （P PQ Q）R R(P(

8、PQQ(R(RR R) )( )( (P(PP)P)(Q(QQ)Q)RR) )(P(PQR)QR)(P(PQQR R)（(P(PP) P) (QR)(QR)(QR)QR)）(P(PQR)QR)(P(PQQR R) (P (PP) (QR) (PP) (QR) (PP) (P) (QR)QR)（P PQRQR）（P PQQR R）（P PQQRR） （P PQQRR）（P PQ QRR）（P PQ QRR ）（主析取范式）（主析取范式）( () （P PQQ）R R （P PQ Q）R R（P PRR）（QRQR）（P P（QQQQ）R R ）（PPPP）QRQR）（P PQRQR）（P PQR

9、 QR ）（ PPQRQR）（P PQRQR）（PPQRQR）（PQR PQR ）（ PPQRQR）（主合取范式）主合取范式）6、將下面一段程序簡(jiǎn)化將下面一段程序簡(jiǎn)化If AB thenIf AB then If BC then If BC then X X Else Else Y Y End EndElseElse If AC then If AC then Y Y Else Else X X End EndEndEnd 執(zhí)行程序段執(zhí)行程序段X X 的條件為的條件為(AB)(BC)(AB)(BC)( (AB)AB) (AC)(AC) (AA BC)BC)If AIf A BC thenBC

10、then Y YElseElse X XEndEnd執(zhí)行程序段執(zhí)行程序段Y Y的條件為的條件為(AB)(AB) (BC)(BC)( (AB) AB) (AC)(AC) AA BCBC7 7、習(xí)題一、習(xí)題一 1414題題解：解：由題設(shè)由題設(shè) A A：A A去，去，B B：B B去，去，C C：C C去，去，D D：D D去去則滿(mǎn)足條件的選派應(yīng)則滿(mǎn)足條件的選派應(yīng)滿(mǎn)足滿(mǎn)足如下范式：如下范式：（AA（C C D D）（BCBC）（CDCD）構(gòu)造和以上范式等價(jià)的主析取范式構(gòu)造和以上范式等價(jià)的主析取范式（為什么？）（為什么？）（AA（C C D D）（BCBC）（CDCD）（AAB B C D C D ）

11、（AAB BC CD D）（AABCBCD D）（ABABC CD D） （AAB BC CD D）（AABBCDCD） （ABABC CD D）（ABABC CDD） 共有共有四四個(gè)極小項(xiàng)，但根據(jù)題意，需派兩人出差，所以，只有個(gè)極小項(xiàng)，但根據(jù)題意，需派兩人出差，所以，只有其中三項(xiàng)滿(mǎn)足要求：其中三項(xiàng)滿(mǎn)足要求： （AAB BC CD D），（），（AABBCDCD），）， （ABABC CD D） 即有即有三種方案：三種方案：A A和和C C去去，或者或者A A和和D D去去，或者或者B B和和D D去。去。8 8、如果今天是星期一，則要進(jìn)行離散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)兩門(mén)課、如果今天是星期一，則要進(jìn)行離

12、散數(shù)學(xué)或數(shù)據(jù)結(jié)構(gòu)兩門(mén)課程中的一門(mén)課的考試；如果數(shù)據(jù)結(jié)構(gòu)課的老師生病，則不程中的一門(mén)課的考試；如果數(shù)據(jù)結(jié)構(gòu)課的老師生病，則不考數(shù)據(jù)結(jié)構(gòu)；今天是星期一，并且數(shù)據(jù)結(jié)構(gòu)的老師生病?？紨?shù)據(jù)結(jié)構(gòu)；今天是星期一，并且數(shù)據(jù)結(jié)構(gòu)的老師生病。所以今天進(jìn)行離散數(shù)學(xué)的考試。所以今天進(jìn)行離散數(shù)學(xué)的考試。 解：解：設(shè)設(shè) P P：今天是星期一；：今天是星期一； Q Q：要進(jìn)行離散數(shù)學(xué)考試；：要進(jìn)行離散數(shù)學(xué)考試； R R：要進(jìn)行數(shù)據(jù)結(jié)構(gòu)考試；：要進(jìn)行數(shù)據(jù)結(jié)構(gòu)考試； S S：數(shù)據(jù)結(jié)構(gòu)課的老師生?。唬簲?shù)據(jù)結(jié)構(gòu)課的老師生?。?則則PQPQ R R，SSR R，PS PS Q Q。 證證: : PS PS S S , ,I,I1 1

13、 S SR R R R , , ,I,I5 5 P P , ,I,I1 1 PQ PQ R R Q Q R R , , ,I,I5 5 Q Q , , ,I,I5 5 9 9、一位計(jì)算機(jī)工作者協(xié)助公安員審查一件謀殺案，他認(rèn)為下、一位計(jì)算機(jī)工作者協(xié)助公安員審查一件謀殺案，他認(rèn)為下列情況是真的；列情況是真的；（1 1）會(huì)計(jì)張某或鄰居王某謀害了廠長(zhǎng)。）會(huì)計(jì)張某或鄰居王某謀害了廠長(zhǎng)。（2 2）如果會(huì)計(jì)張某謀害了廠長(zhǎng)，則謀害不能發(fā)生在半夜。）如果會(huì)計(jì)張某謀害了廠長(zhǎng)，則謀害不能發(fā)生在半夜。（3 3）如果鄰居王某的證詞是正確的，則謀害發(fā)生在半夜。）如果鄰居王某的證詞是正確的，則謀害發(fā)生在半夜。 （4 4）如

14、果鄰居王某的證詞不正確，則半夜時(shí)屋里燈光未滅。）如果鄰居王某的證詞不正確，則半夜時(shí)屋里燈光未滅。（5 5）半夜時(shí)屋里燈光滅了，且會(huì)計(jì)張某曾貪污過(guò)。）半夜時(shí)屋里燈光滅了，且會(huì)計(jì)張某曾貪污過(guò)。 計(jì)算機(jī)工作者用他的數(shù)理邏輯知識(shí)，很快推斷出謀害者計(jì)算機(jī)工作者用他的數(shù)理邏輯知識(shí)，很快推斷出謀害者是誰(shuí)？請(qǐng)問(wèn)是誰(shuí)？請(qǐng)問(wèn): :誰(shuí)是謀害者？怎樣推理發(fā)現(xiàn)他？誰(shuí)是謀害者？怎樣推理發(fā)現(xiàn)他？解：解：設(shè)設(shè)P P：會(huì)計(jì)張某謀害了廠長(zhǎng)：會(huì)計(jì)張某謀害了廠長(zhǎng) Q Q：鄰居王某謀害了廠長(zhǎng)：鄰居王某謀害了廠長(zhǎng) N N：謀害發(fā)生在半夜。：謀害發(fā)生在半夜。 O O：鄰居王某的證詞是正確的。：鄰居王某的證詞是正確的。 R R：半夜時(shí)屋里燈

15、光滅了。：半夜時(shí)屋里燈光滅了。 A A：會(huì)計(jì)張某曾貪污過(guò)。：會(huì)計(jì)張某曾貪污過(guò)。上述案情有如下命題公式：上述案情有如下命題公式： （1 1）PQ PQ （2 2）PPN N （3 3）ON ON （4 4）OOR R （5 5）RARA 問(wèn)題是需求證：?jiǎn)栴}是需求證： PQPQ，PPN N，ONON，OOR R，RA RA ？ 證：證： RA PRA P R T R T，I I1 1 OOR PR P O T O T，E E2323，I I5 5 ON P ON P N T N T，I I5 5 P PN PN P P TP T， E E2323，I I5 5 PQ P PQ P Q T Q T，

16、I I7 7 PQ PQ，PPN N，ONON，OOR R，RA RA Q Q結(jié)論是：鄰居王某謀害了廠長(zhǎng)。結(jié)論是：鄰居王某謀害了廠長(zhǎng)。1010、證明下面論述的有效性。、證明下面論述的有效性。 在意甲比賽中，假如有四只球隊(duì)，其比賽情況如下：在意甲比賽中，假如有四只球隊(duì)，其比賽情況如下： 如果國(guó)際米蘭隊(duì)獲得冠軍，則如果國(guó)際米蘭隊(duì)獲得冠軍，則ACAC米蘭隊(duì)或尤文圖斯隊(duì)獲得米蘭隊(duì)或尤文圖斯隊(duì)獲得亞軍；若尤文圖斯隊(duì)獲得亞軍，國(guó)際米蘭隊(duì)不能獲得冠軍；亞軍；若尤文圖斯隊(duì)獲得亞軍，國(guó)際米蘭隊(duì)不能獲得冠軍；若拉齊奧隊(duì)獲得亞軍，則若拉齊奧隊(duì)獲得亞軍，則ACAC米蘭隊(duì)不能獲得亞軍；最后，米蘭隊(duì)不能獲得亞軍；最后，國(guó)

17、際米蘭隊(duì)獲得冠軍。所以，拉齊奧隊(duì)不能獲得亞軍。國(guó)際米蘭隊(duì)獲得冠軍。所以，拉齊奧隊(duì)不能獲得亞軍。解：設(shè)解：設(shè)P P：國(guó)際米蘭隊(duì)獲得冠軍；：國(guó)際米蘭隊(duì)獲得冠軍； Q Q：ACAC米蘭隊(duì)獲得亞軍；米蘭隊(duì)獲得亞軍； R R：尤文圖斯隊(duì)獲得亞軍；：尤文圖斯隊(duì)獲得亞軍； S S：拉齊奧隊(duì)獲得亞軍；：拉齊奧隊(duì)獲得亞軍； 則原命題可符號(hào)化為：則原命題可符號(hào)化為： PQPQ R R，RRP P，SSQ Q，P PS S （S S） P P（附加前提）（附加前提） S T,S T,E,E1 1 S SQ PQ P Q T,Q T, ,I,I5 5 PQ PQ R PR P P P P P Q Q R T,R T,

18、 ,I,I5 5 R T, R T, ,I,I7 7 R RP PP P P T,P T, ,I,I5 5 P PP(P( F)F) T, T, ,E,E1919 所以，拉齊奧隊(duì)不能獲得亞軍所以，拉齊奧隊(duì)不能獲得亞軍1111、P P2525 習(xí)題一習(xí)題一 1818解：根據(jù)給定的條件有下述命題：解：根據(jù)給定的條件有下述命題：P P：珍寶藏在東廂房：珍寶藏在東廂房Q Q：藏寶的房子靠近池塘：藏寶的房子靠近池塘R R：房子的前院栽有大柏樹(shù)：房子的前院栽有大柏樹(shù)S S：珍寶藏在花園正中地下：珍寶藏在花園正中地下T T：后院栽有香樟樹(shù)：后院栽有香樟樹(shù)M M：珍寶藏在附近：珍寶藏在附近根據(jù)題意，得出：根據(jù)

19、題意，得出：（QQP P）（RPRP）QQ（RSRS）（TMTM） ？（Q QP P）（R RP P）QQ（R RS S）（T TM M） PP（R RP P）（R RS S）（T TM M） 假言推理假言推理RR（R RS S）（T TM M） 拒取式拒取式SS（T TM M）析取三段論析取三段論S S 即珍寶藏在花園正中地下即珍寶藏在花園正中地下12 P26 習(xí)題一習(xí)題一 21（2）n設(shè)：P：被盜現(xiàn)場(chǎng)沒(méi)有留下任何痕跡nQ：失竊時(shí)，小花正在卡拉OK廳nR：失竊時(shí)，小英正在卡拉OK廳nS：失竊時(shí)，小胖正在附近nT：金剛是最大的嫌疑者nM:瘦子是最大的嫌疑者則根據(jù)案情有如下命題公式：則根據(jù)案情有如下命題公式：PP，QRQR，S S P P，Q TQ T， S S R R，R MR M1212、P P2626 21 21（2 2）解：根據(jù)給定的條件有下述命題：解：根據(jù)給定的條件有下述命題：P P：現(xiàn)場(chǎng)無(wú)任何痕跡