命题逻辑备选

命题逻辑备选第1页，课件共39页，创作于2023年2月§1命题命令句，感叹句，疑问句均不是命题。（1）把门关上！（2）你到哪里去？语句既为真，同时又包含假的不是命题，这样的句子称为“悖论”。（3）他正在说谎。（在命题逻辑中不讨论这类问题）第2页，课件共39页，创作于2023年2月§2命题联结词例.将下列命题符号化：（1）李明是计算机系的学生，他住在312室或313室。（2）张三和李四是朋友。（3）虽然交通堵塞，但是老王还是准时到达了车站。（4）只有一个角是直角的三角形才是直角三角形。（5）老王或小李中有一个去上海出差。第3页，课件共39页，创作于2023年2月§2命题联结词解：（1）首先用字母表示简单命题。P：李明是计算机系的学生。Q：李明住在312室。R：李明住在313室。该命题符号化为：P（Q▽R）（2）张三和李四是朋友。是一个简单句该命题符号化为：P第4页，课件共39页，创作于2023年2月§2命题联结词（3）首先用字母表示简单命题。P：交通堵塞。Q：老王准时到达了车站。该命题符号化为：PQ（4）首先用字母表示简单命题。P：三角形的一个角是直角。Q：三角形是直角三角形。该命题符号化为：PQ第5页，课件共39页，创作于2023年2月§2命题联结词（5）首先用字母表示简单命题。P：老王去上海出差。Q：小李去上海出差。该命题符号化为：P▽Q也可符号化为：（PQ）（PQ）或者（PQ）（PQ）第6页，课件共39页，创作于2023年2月§３命题公式PQP∨Q（Ｐ∨Ｑ）ΛＰ¬（（Ｐ∨Ｑ）ΛＰ）FFFFTFTTFTTFTTFTTTTF例１．构造命题公式¬（（Ｐ∨Ｑ）ΛＰ）的真值表：第7页，课件共39页，创作于2023年2月§３命题公式例２．写出命题公式Ｐ∨（ＱΛＲ）的真值表PQRＰ∨（ＱΛＲ)FFF

FFFFT

FFFTF

FFFTT

TTTFF

TFTFT

TFTTF

TFTTT

TT第8页，课件共39页，创作于2023年2月例：证明：Ｐ→（Ｑ→Ｒ）Ｐ→（¬Ｑ∨Ｒ）¬Ｐ∨¬Ｑ∨¬Ｒ¬（ＰΛＱ）∨Ｒ（ＰΛＱ）→Ｒ例：证明：（（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ）∨（¬ＰΛ¬Ｒ）为一永真式第9页，课件共39页，创作于2023年2月§4等价式证明：原式：（（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ）∨（¬ＰΛ¬Ｒ）（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）））∨¬（Ｐ∨Ｑ）∨¬（Ｐ∨Ｒ）

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））Ｔ∵它是ＰΛ¬Ｐ（永真式）的代换实例，永真式的代换实例仍为永真式！第10页，课件共39页，创作于2023年2月§4等价式证明：原式：（（Ｐ∨Ｑ）Λ¬（¬ＰΛ（¬Ｑ∨¬Ｒ）））∨（¬ＰΛ¬Ｑ）∨（¬ＰΛ¬Ｒ）（（Ｐ∨Ｑ）Λ（Ｐ∨（ＱΛＲ）））∨¬（Ｐ∨Ｑ）∨¬（Ｐ∨Ｒ）

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））

（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））∨¬（（Ｐ∨Ｑ）Λ（Ｐ∨Ｒ））Ｔ∵它是ＰΛ¬Ｐ（永真式）的代换实例，永真式的代换实例仍为永真式！第11页，课件共39页，创作于2023年2月§4等价式例：证明：（１）¬（ＰΛＱ）→（¬Ｐ∨（¬Ｐ∨Ｑ））（¬Ｐ∨Ｑ）（２）（Ｐ∨Ｑ）Λ（¬ＰΛ（¬ＰΛＱ））（¬ＰΛＱ）证明：（１）左边

¬¬（ＰΛＱ）∨（¬Ｐ∨（¬Ｐ∨Ｑ））

（ＰΛＱ）∨（¬Ｐ∨Ｑ）（Ｐ∨¬Ｐ∨Ｑ）Λ（Ｑ∨¬Ｐ∨Ｑ）（¬Ｐ∨Ｑ）第12页，课件共39页，创作于2023年2月§4等价式（２）左边（Ｐ∨Ｑ）Λ（¬ＰΛＱ）（ＰΛ¬ＰΛＱ）∨（ＱΛ¬ＰΛＱ）（¬ＰΛＱ）结论：（１）和（２）是互为对偶的。第13页，课件共39页，创作于2023年2月§7范式和判定例：证明Ｐ∨（¬Ｐ∧Ｑ）Ｐ∨Ｑ证明方法是写出二个命题公式的主析范式，看其是否相同：（Ｑ∨¬Ｑ）∧Ｐ∨（¬Ｐ∧Ｑ）

（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）而Ｐ∨Ｑ

（Ｐ∧（Ｑ∨¬Ｑ））∨（Ｑ∧（Ｐ∨¬Ｐ））

（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）∨（Ｐ∧Ｑ）∨（¬Ｐ∧Ｑ）

（Ｐ∧Ｑ）∨（Ｐ∧¬Ｑ）∨（¬Ｐ∧Ｑ）主析范式相同，∴有Ｐ∨（¬Ｐ∧Ｑ）Ｐ∨Ｑ第14页，课件共39页，创作于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页，创作于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页，创作于2023年2月§8推理理论例：证明¬P

¬Q

¬(PQ)

证:(1)¬(¬(PQ))假设前提

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

¬QP(5)¬PT(4)(6)P¬PT(3)(5)(7)F第17页，课件共39页，创作于2023年2月§8推理理论例2:证明:R¬Q,R∨S,S¬Q,PQ¬P(1)¬(¬P) 假设前提

(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页，创作于2023年2月§8推理理论

(10)R¬Q P (11)¬Q T(9)(10) (12)Q∧¬Q T(4)(11)讨论：由上例可见，间接证明法在结论较为简单的条件下，使用是比较方便的，实际上间接证明法也可以用CP规则代替它。

第19页，课件共39页，创作于2023年2月§8推理理论例：一位计算机工作者协助公安人员审查一起谋杀案，经调查，他认为下列情况均是真的。

（1）会计张某或邻居王某谋害了厂长。

（2）如果会计张某谋害了厂长，则谋害不可能发生在半夜。

（3）如果邻居王某的证词不正确，则在半夜时房里灯光未灭。（4）如果邻居王某的证词是正确的，则谋害发生在半夜。

（5）在半夜房子里的灯光灭了，且会计张某曾贪污过。

第20页，课件共39页，创作于2023年2月§8推理理论解：设P：会计张某谋害了厂长

Q：邻居王某谋害了厂长

N：谋害发生在半夜

O：邻居王某的证词是正确的

R：半夜时房子的灯光灭了

A：会计张某曾贪污过

列出条件公式：

第21页，课件共39页，创作于2023年2月§8推理理论

(1)P∨Q(4)QN(2)P¬N(5)RA (3)¬O¬R推导过程为：(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结论：邻居王某谋害了厂长；

第22页，课件共39页，创作于2023年2月例题选讲例1.符号化下列命题：（1）辱骂和恐吓决不是战斗；（2）除非天气好，否则我是不会去公园的；（3）如果晚上做完作业且没有其它的事，他就会去看电视或听音乐。解：（1）设P：辱骂不是战斗。

Q：恐吓不是战斗。

PQ

（2）设P：今天天气好。

Q：我去公园。

QP第23页，课件共39页，创作于2023年2月例题选讲（3）设P：他晚上做完了作业。

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

R：他看电视。

S：他听音乐。（PQ）（RS）例2.证明P（QR）（PQ）（PR）给出本题的各种证明：（1）列真值表：设MP（QR）

K（PQ）（PR）

SP（QR）（PQ）（PR）第24页，课件共39页，创作于2023年2月例题选讲PQRQRMPQPRKSTTTTTTTTTTTFFFTFFTTFTTTFTTTTFFTTFFTTFTTTTTTTTFTFFTTTTTFFTTTTTTTFFFTTTTTT第25页，课件共39页，创作于2023年2月例题选讲a)直接证法：P（QR）的真值为T，其对应指派下（PQ）（PR）的真值均为T。b)反证法：（PQ）（PR）的真值为F，其对应指派下P（QR）的真值为F。c)条件永真式：（P（QR））（（PQ）（PR））的真值都为T，及为永真式。（2）逻辑推证a)直接证法：设P（QR）为T，则①

P为T，QR为T，有三种情况：

P为T，Q为T，R为T，则（PQ）（PR）为T。第26页，课件共39页，创作于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页，创作于2023年2月例题选讲b)间接证法：设（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页，创作于2023年2月例题选讲例3.证明｛，｝不是最小联结词组。证明：设变元P，Q，用联结词，作用于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(B)用作用于(A)类得到：PQ，PP(F)，PQ(PQ)，P(PQ)Q，P(PP)P,QP(PQ)，QQ(F)，Q(PQ)P,

QTQ，第29页，课件共39页，创作于2023年2月例题选讲

PQ(PQ)，P(PQ)Q，PTP，Q(PQ)P，QTQ，(PQ)(PP)PQ。因此(A)类使用运算后，仍在(B)类中。同样，对(B)类使用，运算后，结果仍在(B)中。由上证明：用，两个联结词，反复作用在两个变元的公式中，结果只能产生(B)类中的公式，总共仅八个不同公式，而两个变元所形成的公式共有222=16个彼此不等价的公式，因此｛，｝不是功能完备的，更不可能是最小联结词组。

第30页，课件共39页，创作于2023年2月例题选讲例4.求(ABC)(A(BC))的主析取范式与主合取范式。解：(1)列表法：设S(ABC)(A(BC))，

RABC，

MA(BC)，根据真值表中S真值为T的指派，所对应的小项析取即为S的主析取范式，S真值为F的指派，所对应的大项合取即为主合取范式。S的真值表如下：第31页，课件共39页，创作于2023年2月例题选讲ABCBCRABCMSTTTTTFFTTTTFFFFFTFTFTFFFFTFTFFFFFTFFFTTTTTFFFFTFFTTFFFFFTFTTFFFFFFFTTTTT第32页，课件共39页，创作于2023年2月例题选讲S(ABC)(ABC)－－主析取范式

S(ABC)(ABC)(ABC)(ABC)(ABC)(ABC) －－主合取范式(2)公式推导法：

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页，创作于2023年2月例题选讲当求出主析取范式的编码表达式后可直接利用编码关系，解出主合取范式。即：S(ABC)(A(BC))(ABC)(ABC)m000m1110,71,2,3,4,5,6M001M010M011M100M100M101M110(ABC)(ABC)(ABC)(ABC)(ABC)(ABC)第34页，课件共39页，创作于2023年2月例题选讲例5.用推理规则论证下述问题：或者是天晴，或者是下雨。如果是天晴，我去看电影。如果我去看电影，我就不看书。所以，如果我在看书，则天在下雨。解：设S：今天天晴。R：今天下雨。E：我去看电影。B：我去看书。本题符号化为：SR，SE，EBBR因为SR(SR)故本题为(SR)，SE，EBBR第35页，课件共39页，创作于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