左孝凌离散数学13命题公式与翻译-14真值表与等价课件

1(DiscreteMathematics)1.3.1命题公式1.3.2复合命题的符号化(翻译)2第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译1.3.1合式公式(Well-formedformula)(wff)定义1.3.1:原子公式

单个命题变元和命题常量称为原子公式。3第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译定义1.3.2：合式公式

(1)原子公式是合式公式(wff)。（2）若A，B是合式公式，则（A），(A∧B)，(A∨B)，(AB)，(AB)也是合式公式。（3）当且仅当有限次地应用(1)(2)所得到的包含原子公式、联结词和括号的符号串是合式公式。联结词的优先级：┐、∧、∨、→、。

则：P∧Q→R是合式公式等价于Wff

：（（P∧Q）→R）命题公式外层的括号可以省略等价于Wff

：（P∧Q）→R不等价于Wff

：P∧（Q→R）第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译6第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译1.3.2复合命题的符号化(翻译)自然语言的语句用Wff

形式化：

①

要准确确定原子命题，并将其形式化。

②

要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略），否定词的位置要放准确。

③

必要时可以进行改述，即改变原来的叙述方式，但要保证表达意思一致。④

需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。

⑤要注意语句的形式化未必是唯一的。可以把本命题表达为：┐(P↔Q）。

解P：上海到北京的14次列车是下午五点半开。

Q：上海到北京的14次列车是下午六点开。在本例中，汉语的“或”是不可兼或，而逻辑联结词∨是“可兼或”，因此不能直接对两命题析取。构造如表1-3.1所示。PQ原命题P↔Q┐(P↔Q)TTFTFTFTFTFTTFTFFFTF表1-3.1例题2上海到北京的14次列车是下午五点半或六点开。

解这个命题的意义是：

可兼或若设

P：张三可以做这事。Q：李四可以做这事。本例可表示为：

P∨Q例题6张三或李四都可以做这件事。10第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译1)我今天进城，除非下雨。[1-3.(7)]2)仅当你走我将留下。[1-3.(7)]3)假如上午不下雨，我去看电影，否则就在家里读书或看报。[1-3.(7)]4)一个人起初说：“占据空间的、有质量的而且不断变化的叫做物质”；后来他改说，“占据空间的有质量的叫做物质，而物质是不断变化的。”问他前后主张的差异在什么地方，试以命题形式进行分析。[1-3.(6)]练习111第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译我今天进城，除非下雨。[1-3.(7)]P：我今天进城。Q:天下雨。┓Q→P2)仅当你走我将留下。[1-3.(7)]P:你走。Q:我留下。Q→P3)假如上午不下雨，我去看电影，否则就在家里读书或看报。[1-3.(7)]P:上午下雨。Q:我去看电影。R:我在家里读或看报。┓(┓P→Q)↔(P→R)）（要么看电影要么留在家里，排斥或）解答练习2

（小李不在图书馆），（他要么找老师去了），（要么就是因为身体不适，回宿舍去了）。命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。解设P：小李在图书馆。Q：小李找老师。

R：小李身体不适。S：小李回宿舍。则命题符号化为：（┐P）∧（┐(Q(R→S)）（小李不是……而是……∧）（要么……要么……排斥或）14第一章命题逻辑（PropositionalLogic）1.3命题公式与翻译小结：本节介绍了命题公式的概念及复合命题的符号化.重点是理解命题公式的递归定义,掌握复合命题的符号化方法.作业：p12(5)15离散数学(DiscreteMathematics)1.4.1真值表(TruthTable)1.4.2等价公式(PropositionalEquivalences)17第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式对公式A构造真值表的具体步骤为：（1）找出公式中所有命题变元P1,P2,…,Pn（2）按从小到大的顺序列出对命题变元P1,P2,…,Pn,的全部2n组赋值。（3）对应各组赋值计算出公式A的真值，并将其列在对应赋值的后面。18第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例1.给出┐(PQ)(┐P┐Q)的真值表：PQPQ ┐(PQ)┐P┐Q┐(PQ)(┐P┐Q)0001101119第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例1.给出┐(PQ)(┐P┐Q)的真值表：PQPQ ┐(PQ)┐P┐Q┐(PQ)(┐P┐Q)00011011000111101110111121第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例2：构造公式(PQ)∧R的真值表。PQRPQ(PQ)∧R000100011101010011111000010100110101111122第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式练习1：构造公式(PQ)(QP）真值表。PQ

P

QP

Q

QP(P

Q)(

Q

P)0001101123第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式练习1：构造公式(PQ)(QP）真值表。PQ

P

QP

Q

QP(P

Q)(

Q

P)001111101101111001001110011125第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式PQ(P

Q)(P

Q)(P

Q)∧Q00100011001001011100练习2：构造公式

(PQ）∧Q真值表。永真公式永假公式：无论对其分量作怎样的真值指派，其真值永为T，称为永真公式，记为T。如例1无论对其分量作怎样的真值指派，其真值永为F，称为永假公式，记为F。如例2

第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式29第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式定义1.4.3:给定两个命题公式A和B,设P1,P2,…,Pn为出现于A和B中的所有原子变元,若给P1,P2,…,Pn任一组真值指派,A和B的真值都相同,则称A和B是等价.

记作AB。1.4.2等价公式30第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式1.真值表法2.等值演算法1.真值表法

例1.┐(PQ)(┐P┐Q)见真值表例题1.例2.证明:PQ(P→Q)(Q→P)PQPQQ→PP→Q(P→Q)(Q→P)00011011证明公式等价的方法：31第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式1.真值表法2.等值演算法1.真值表法

例1.┐(PQ)(┐P┐Q)见真值表例题1.例2.证明:PQ(P→Q)(Q→P)PQPQQ→PP→Q(P→Q)(Q→P)001111010010100100111111所以：PQ(P→Q)(Q→P)(P∧Q)∨(┐P∧┐Q)试用等值演算方法证明另外，PQ(┐P∨Q)∧(┐Q∨P)32第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式2.等值演算法(EquivalentCaculation)（利用P15表1-4.8)重要的等价式(补充):11.蕴涵等值式:PQ┐PQQ┐P┐Q┐P（假言易位）12.等价等值式:PQ(P→Q)(Q→P)

(┐P∨Q)∧(┐Q∨P)(P∧Q)∨(┐P∧┐Q)

13.假言易位:PQ┐Q┐P

14.等价否定等值式:PQ┐P┐Q

15.归谬论:(PQ)(

P┐Q)┐P对合律┐┐PP1幂等律P∨PP，P∧PP2结合律(P∨Q）∨RP∨（Q∨R）(P∧Q）∧RP∧（Q∧R）3交换律P∨QQ∨PP∧QQ∧P4分配律P∨（Q∧R）（P∨Q）∧（P∨R）P∧（Q∨R）（P∧Q）∨（P∧R）5吸收律P∨（P∧Q）

PP∧（P∨Q）

P6德摩根律┐(P∨Q)┐P∧┐Q┐(P∧Q)┐P∨┐Q7同一律P∨F

P，P∧T

P8零律P∨TT，P∧FF9否定律P∨┐P

T，P∧┐P

F10表1-4.8命题定律任何数与0相或还是任何数任何数与1相与为1任何数与1相与还是任何数与0相与为0例题6验证吸收律P∨（P∧Q）

PP∧（P∨Q）

P证明列出真值表表1-4.9PQP∧QP∨（P∧Q）P∨QP∧（P∨Q）TTTTTTTFFTTTFTFFTFFFFFFF由表1-4.9可知吸收律成立。练习18页（4）35第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式等值演算中使用的一条重要规则：置换规则。定义1.4.4子公式：如果X是wffA的一部分,且X本身也是wff，则称X是A的子公式。

例如,P(PQ)为Q(P(PQ))的子公式。定理1.4.1

置换定理：设X是wffA的子公式，若XY，则若将A中的X用Y来置换，所得公式B与A等价，即AB。定义1.4.5

等值演算：根据已知的等价公式,推演出另外一些等价公式的过程称为等值演算.36第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例1：证明Q→（P（PQ））Q→P

证:Q→（P（PQ））Q→P

P(吸收律)例2：证明（P┐Q）Q

PQ

证：(P┐Q)Q(PQ)(┐QQ)(PQ)TPQ例3：证明（P→Q）→（QR）

PQR证：（P→Q）→（QR）（┐PQ）→（QR）┐(┐PQ)（QR）（P┐Q）（QR）

（PQR）（┐QQR）

(PQR)

((┐QQ)R)

(PQR)

(TR)

(PQR)

T

(PQR)

37第一章命题逻辑（PropositionalLogic）

1.4真值表与等价公式例4：验证P(QR)(P

∧

Q)R证:右

(P

∧

Q)∨R（蕴含等值）