命題邏輯備選

命題邏輯備選第1頁，課件共39頁，創(chuàng)作于2023年2月§1命題命令句，感嘆句，疑問句均不是命題。（1）把門關(guān)上?。?）你到哪里去？語句既為真，同時又包含假的不是命題，這樣的句子稱為“悖論”。（3）他正在說謊。（在命題邏輯中不討論這類問題）第2頁，課件共39頁，創(chuàng)作于2023年2月§2命題聯(lián)結(jié)詞例.將下列命題符號化：（1）李明是計算機系的學生，他住在312室或313室。（2）張三和李四是朋友。（3）雖然交通堵塞，但是老王還是準時到達了車站。（4）只有一個角是直角的三角形才是直角三角形。（5）老王或小李中有一個去上海出差。第3頁，課件共39頁，創(chuàng)作于2023年2月§2命題聯(lián)結(jié)詞解：（1）首先用字母表示簡單命題。P：李明是計算機系的學生。Q：李明住在312室。R：李明住在313室。該命題符號化為：P（Q▽R）（2）張三和李四是朋友。是一個簡單句該命題符號化為：P第4頁，課件共39頁，創(chuàng)作于2023年2月§2命題聯(lián)結(jié)詞（3）首先用字母表示簡單命題。P：交通堵塞。Q：老王準時到達了車站。該命題符號化為：PQ（4）首先用字母表示簡單命題。P：三角形的一個角是直角。Q：三角形是直角三角形。該命題符號化為：PQ第5頁，課件共39頁，創(chuàng)作于2023年2月§2命題聯(lián)結(jié)詞（5）首先用字母表示簡單命題。P：老王去上海出差。Q：小李去上海出差。該命題符號化為：P▽Q也可符號化為：（PQ）（PQ）或者（PQ）（PQ）第6頁，課件共39頁，創(chuàng)作于2023年2月§３命題公式PQP∨Q（Ｐ∨Ｑ）ΛＰ?（（Ｐ∨Ｑ）ΛＰ）FFFFTFTTFTTFTTFTTTTF例１．構(gòu)造命題公式?（（Ｐ∨Ｑ）ΛＰ）的真值表：第7頁，課件共39頁，創(chuàng)作于2023年2月§３命題公式例２．寫出命題公式Ｐ∨（ＱΛＲ）的真值表PQRＰ∨（ＱΛＲ)FFF

FFFFT

FFFTF

FFFTT

TTTFF

TFTFT

TFTTF

TFTTT

TT第8頁，課件共39頁，創(chuàng)作于2023年2月例：證明：Ｐ→（Ｑ→Ｒ）Ｐ→（?Ｑ∨Ｒ）?Ｐ∨?Ｑ∨?Ｒ?（ＰΛＱ）∨Ｒ（ＰΛＱ）→Ｒ例：證明：（（Ｐ∨Ｑ）Λ?（?ＰΛ（?Ｑ∨?Ｒ）））∨（?ＰΛ?Ｑ）∨（?ＰΛ?Ｒ）為一永真式第9頁，課件共39頁，創(chuàng)作于2023年2月§4等價式證明：原式：（（Ｐ∨Ｑ）Λ?（?ＰΛ（?Ｑ∨?Ｒ）））∨（?ＰΛ?Ｑ）∨（?ＰΛ?Ｒ）（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）））∨?（Ｐ∨Ｑ）∨?（Ｐ∨Ｒ）

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））Ｔ∵它是ＰΛ?Ｐ（永真式）的代換實例，永真式的代換實例仍為永真式！第10頁，課件共39頁，創(chuàng)作于2023年2月§4等價式證明：原式：（（Ｐ∨Ｑ）Λ?（?ＰΛ（?Ｑ∨?Ｒ）））∨（?ＰΛ?Ｑ）∨（?ＰΛ?Ｒ）（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）））∨?（Ｐ∨Ｑ）∨?（Ｐ∨Ｒ）

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨?（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））Ｔ∵它是ＰΛ?Ｐ（永真式）的代換實例，永真式的代換實例仍為永真式！第11頁，課件共39頁，創(chuàng)作于2023年2月§4等價式例：證明：（１）?（ＰΛＱ）→（?Ｐ∨（?Ｐ∨Ｑ））（?Ｐ∨Ｑ）（２）（Ｐ∨Ｑ）Λ（?ＰΛ（?ＰΛＱ））（?ＰΛＱ）證明：（１）左邊

??（ＰΛＱ）∨（?Ｐ∨（?Ｐ∨Ｑ））

（ＰΛＱ）∨（?Ｐ∨Ｑ）（Ｐ∨?Ｐ∨Ｑ）Λ（Ｑ∨?Ｐ∨Ｑ）（?Ｐ∨Ｑ）第12頁，課件共39頁，創(chuàng)作于2023年2月§4等價式（２）左邊（Ｐ∨Ｑ）Λ（?ＰΛＱ）（ＰΛ?ＰΛＱ）∨（ＱΛ?ＰΛＱ）（?ＰΛＱ）結(jié)論：（１）和（２）是互為對偶的。第13頁，課件共39頁，創(chuàng)作于2023年2月§7范式和判定例：證明Ｐ∨（?Ｐ∧Ｑ）Ｐ∨Ｑ證明方法是寫出二個命題公式的主析范式，看其是否相同：（Ｑ∨?Ｑ）∧Ｐ∨（?Ｐ∧Ｑ）

（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ）而Ｐ∨Ｑ

（Ｐ∧（Ｑ∨?Ｑ））∨（Ｑ∧（Ｐ∨?Ｐ））

（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（Ｐ∧Ｑ）∨（?Ｐ∧Ｑ）

（Ｐ∧Ｑ）∨（Ｐ∧?Ｑ）∨（?Ｐ∧Ｑ）主析范式相同，∴有Ｐ∨（?Ｐ∧Ｑ）Ｐ∨Ｑ第14頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論例1：P(QS),

?R∨P,QRS證:(1)R附加前提

(2)

?R∨PP(3)RPT(2)E(4)PT(1)(3)I(5)P(QS)P(6)QST(4)(5)I第15頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論

(7)QP(8)ST(6)(7)I(9)RSCP例2:PQP(P∧Q)(1)P附加前提

(2)PQP(3)QT(1)(2)I(4)P∧QT(1)(3)(5)P(P∧Q)CP第16頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論例：證明?P

?Q

?(PQ)

證:(1)?(?(PQ))假設(shè)前提

(2)PQT(1)(3)PT(2)(4)?P

?QP(5)?PT(4)(6)P?PT(3)(5)(7)F第17頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論例2:證明:R?Q,R∨S,S?Q,PQ?P(1)?(?P) 假設(shè)前提

(2)P T(1)(3)PQ P(4)Q T(2)(3)(5)S?Q P (6)Q?S T(5) (7)?S T(4)(6) (8)R∨S P (9)R T(7)(8)

第18頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論

(10)R?Q P (11)?Q T(9)(10) (12)Q∧?Q T(4)(11)討論：由上例可見，間接證明法在結(jié)論較為簡單的條件下，使用是比較方便的，實際上間接證明法也可以用CP規(guī)則代替它。

第19頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論例：一位計算機工作者協(xié)助公安人員審查一起謀殺案，經(jīng)調(diào)查，他認為下列情況均是真的。

（1）會計張某或鄰居王某謀害了廠長。

（2）如果會計張某謀害了廠長，則謀害不可能發(fā)生在半夜。

（3）如果鄰居王某的證詞不正確，則在半夜時房里燈光未滅。（4）如果鄰居王某的證詞是正確的，則謀害發(fā)生在半夜。

（5）在半夜房子里的燈光滅了，且會計張某曾貪污過。

第20頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論解：設(shè)P：會計張某謀害了廠長

Q：鄰居王某謀害了廠長

N：謀害發(fā)生在半夜

O：鄰居王某的證詞是正確的

R：半夜時房子的燈光滅了

A：會計張某曾貪污過

列出條件公式：

第21頁，課件共39頁，創(chuàng)作于2023年2月§8推理理論

(1)P∨Q(4)QN(2)P?N(5)RA (3)?O?R推導(dǎo)過程為：(1)RA P(6)NT(2)RT (7)P?N P(3)?O?RP (8)?PT(4)OT(9)P∨QP(5)ORP (10)QT結(jié)論：鄰居王某謀害了廠長；

第22頁，課件共39頁，創(chuàng)作于2023年2月例題選講例1.符號化下列命題：（1）辱罵和恐嚇決不是戰(zhàn)斗；（2）除非天氣好，否則我是不會去公園的；（3）如果晚上做完作業(yè)且沒有其它的事，他就會去看電視或聽音樂。解：（1）設(shè)P：辱罵不是戰(zhàn)斗。

Q：恐嚇不是戰(zhàn)斗。

PQ

（2）設(shè)P：今天天氣好。

Q：我去公園。

QP第23頁，課件共39頁，創(chuàng)作于2023年2月例題選講（3）設(shè)P：他晚上做完了作業(yè)。

Q：他晚上沒有其它事情。

R：他看電視。

S：他聽音樂。（PQ）（RS）例2.證明P（QR）（PQ）（PR）給出本題的各種證明：（1）列真值表：設(shè)MP（QR）

K（PQ）（PR）

SP（QR）（PQ）（PR）第24頁，課件共39頁，創(chuàng)作于2023年2月例題選講PQRQRMPQPRKSTTTTTTTTTTTFFFTFFTTFTTTFTTTTFFTTFFTTFTTTTTTTTFTFFTTTTTFFTTTTTTTFFFTTTTTT第25頁，課件共39頁，創(chuàng)作于2023年2月例題選講a)直接證法：P（QR）的真值為T，其對應(yīng)指派下（PQ）（PR）的真值均為T。b)反證法：（PQ）（PR）的真值為F，其對應(yīng)指派下P（QR）的真值為F。c)條件永真式：（P（QR））（（PQ）（PR））的真值都為T，及為永真式。（2）邏輯推證a)直接證法：設(shè)P（QR）為T，則①

P為T，QR為T，有三種情況：

P為T，Q為T，R為T，則（PQ）（PR）為T。第26頁，課件共39頁，創(chuàng)作于2023年2月例題選講

P為T，Q為F，R為T，則（PQ）（PR）為T。

P為T，Q為F，R為F，則（PQ）（PR）為T。②P為F，QR為F，則：

P為F，Q為T，R為F，所以PQ為T，PR為T，得（PQ）（PR）為T。③P為F，QR為T，則：

P為F，Q為T，R為T，則（PQ）（PR）為T。

P為F，Q為F，R為F，則（PQ）（PR）為T。

P為F，Q為F，R為T，則（PQ）（PR）為T。綜上各點：當P（QR）為T時，必有（PQ）（PR）為T。第27頁，課件共39頁，創(chuàng)作于2023年2月例題選講b)間接證法：設(shè)（PQ）（PR）為F，則必有PQ為T，PR為F，故得P為T，Q為T，R為F。所以P（QR）為F。（3）等價變換S(P(QR))((PQ)(PR))(P(QR))((PQ)(PR))(PQR)((PQ)(PR))(PQR)((PQ)(PR))(PQR)((PRP)(QPR))(PQR)(PQR)(PQR)(PQR)T第28頁，課件共39頁，創(chuàng)作于2023年2月例題選講例3.證明｛，｝不是最小聯(lián)結(jié)詞組。證明：設(shè)變元P，Q，用聯(lián)結(jié)詞，作用于P，Q得到：P，Q，P，Q，PQ，PP，QQ，QP。但(PQ)(QP)，(PP)(QQ)，故實際有：P，Q，P，Q，PQ，PP(T)(A)用作用于(A)類,得到擴大的公式類(包括原公式類):P，Q，P，Q，PQ，(PQ)，T，F(xiàn)(B)用作用于(A)類得到：PQ，PP(F)，PQ(PQ)，P(PQ)Q，P(PP)P,QP(PQ)，QQ(F)，Q(PQ)P,

QTQ，第29頁，課件共39頁，創(chuàng)作于2023年2月例題選講

PQ(PQ)，P(PQ)Q，PTP，Q(PQ)P，QTQ，(PQ)(PP)PQ。因此(A)類使用運算后，仍在(B)類中。同樣，對(B)類使用，運算后，結(jié)果仍在(B)中。由上證明：用，兩個聯(lián)結(jié)詞，反復(fù)作用在兩個變元的公式中，結(jié)果只能產(chǎn)生(B)類中的公式，總共僅八個不同公式，而兩個變元所形成的公式共有222=16個彼此不等價的公式，因此｛，｝不是功能完備的，更不可能是最小聯(lián)結(jié)詞組。

第30頁，課件共39頁，創(chuàng)作于2023年2月例題選講例4.求(ABC)(A(BC))的主析取范式與主合取范式。解：(1)列表法：設(shè)S(ABC)(A(BC))，

RABC，

MA(BC)，根據(jù)真值表中S真值為T的指派，所對應(yīng)的小項析取即為S的主析取范式，S真值為F的指派，所對應(yīng)的大項合取即為主合取范式。S的真值表如下：第31頁，課件共39頁，創(chuàng)作于2023年2月例題選講ABCBCRABCMSTTTTTFFTTTTFFFFFTFTFTFFFFTFTFFFFFTFFFTTTTTFFFFTFFTTFFFFFTFTTFFFFFFFTTTTT第32頁，課件共39頁，創(chuàng)作于2023年2月例題選講S(ABC)(ABC)－－主析取范式

S(ABC)(ABC)(ABC)(ABC)(ABC)(ABC) －－主合取范式(2)公式推導(dǎo)法：

S(ABC)(A(BC))

(A(BC))(A(BC))((BC)A)(A(BC))(A(BC))((BC)A)((ABC)(ABC))(BCA)

(ABC)(ABC)m000m1110,7第33頁，課件共39頁，創(chuàng)作于2023年2月例題選講當求出主析取范式的編碼表達式后可直接利用編碼關(guān)系，解出主合取范式。即：S(ABC)(A(BC))(ABC)(ABC)m000m1110,71,2,3,4,5,6M001M010M011M100M100M101M110(ABC)(ABC)(ABC)(ABC)(ABC)(ABC)第34頁，課件共39頁，創(chuàng)作于2023年2月例題選講例5.用推理規(guī)則論證下述問題：或者是天晴，或者是下雨。如果是天晴，我去看電影。如果我去看電影，我就不看書。所以，如果我在看書，則天在下雨。解：設(shè)S：今天天晴。R：今天下雨。E：我去看電影。B：我去看書。本題符號化為：SR，SE，EBBR因為SR(SR)故本題為(SR)，SE，EBBR第35頁，課件共39頁，創(chuàng)作于2023年2月例題選講①直接證法：

(1)(SR)P

(2)SRT(1),E(3)(SR)(RS)T(2),E(4)RS T(3),I(5)SE P(6)RE T(4)(5),I(7)EB P(8)RBT(6)(7),I(9)BR