24
六、等值演算
例:证明 (P∨Q)→R ⇔(P→R)∧(Q→R) 证明 证： 可以从左边开始演算，也可以从右边 开始演算。现在从左边开始演算。 (P∨Q)→R ⇔┐(P∨Q)∨R (蕴含等值式） ⇔(┐P∧┐Q)∨R （德摩根律） ⇔(┐P∨R)∧(┐Q∨R)（分配律） ⇔(P→R)∧(Q→R) （蕴含等值式） 练习：从右边开始演算？
18
六、等值演算
1. 双重否律(对合律） P ⇔ ┐┐P 2. 幂等律 P∨P ⇔P P∧P⇔ P 3. 结合律 (P∨Q)∨R ⇔P∨(Q∨R) (P∧Q)∧R ⇔P∧(Q∧R) 4. 交换律 P∨Q ⇔ Q∨P P∧Q ⇔ Q∧P
19
六、等值演算
5.分配律 P∨(Q∧R) ⇔(P∨Q)∧(P∨R) （∨对∧的分配律） 的分配律） P∧(Q∨R) ⇔(P∧Q)∨(P∧R) （∧对∨的分配律） 的分配律） 6.吸收律 P∨(P∧Q) ⇔ P P∧(P∨Q) ⇔ P 7.德.摩根律 ┐(P∨Q) ⇔ ┐P∧┐Q ┐(P∧Q) ⇔ ┐P∨┐Q 8. 同一律 A∨0 ⇔ A A∧1 ⇔ A 20
二、命题公式分量指派
公式就代表命题，但代表的命题是真还是假呢？ 在命题公式中，由于有命题符号的出现，因而 真值是不确定的。当将公式中出现的全部命题符 号都解释成具体的命题之后，公式就成了真值确 定的命题了。 例如，在公式(P∨Q)→R中: (P Q) R 若将P解释成：2是素数， Q解释成：3是偶数， R解释成：是无理数，则P与R被解释成真命 题，Q被解释成假命题了，此时公式(P∨Q)→R被 解释成：若2是素数或3是偶数，则 是无理数。 这是一个真命题。
六、等值演算
9.零律 P∨1 ⇔ 1 P∧0 ⇔ 0 10.否定律 P∨┐P ⇔ 1 （排中律） P∧┐P ⇔ 0 （矛盾律） 11.蕴涵等值式（补充） P→Q⇔┐P∨Q 12. 等价等值式（补充） (P ↔ Q) ⇔(P→Q)∧(Q→P)
21
六、等值演算
13.假言易位 （补充） P→Q ⇔ ┐Q→┐P 14.等价否定等值式（补充） P ↔ Q ⇔ ┐P ↔ ┐Q 15.归谬论（补充） (P→Q)∧(P→┐Q) ⇔ ┐P
28
22
六、等值演算
在最基本的15组命题公式的等价关系的基础上， 利用等价置换就可以推证一些更为复杂的命题等 价公式。 例：命题公式(P→Q)→R中 ，可用┐P∨Q置换其中 的P→Q，由蕴涵等值式可知， P→Q P Q ⇔ ┐P∨Q， P Q 所以有 (P→Q)→R ⇔ (┐P∨Q) → R 在这里，使用了等价置换规则。如果再一次地用 蕴涵等值式及等价置换规则，又会得到 (┐P∨Q)→R ⇔ ┐(┐P∨Q)∨R
5
二、命题公式分量指派
不难看出，含n(n≥1)个命题变元的公式共 有2n个不同的指派（赋值）。 下面的问题是，指定P，Q，R的真值为何值 时，(P∨Q)→R的真值为1；指定P，Q，R的 真值为何值时，(P∨Q)→R的真值为0。 为看清命题公式在各种指派下的取值情况， 通常构造下面的“真值表”。
6
三、真值表
4
二、命题公式分量指派
2．若A中出现的命题符号为P，Q，R...,给定A的指 派（赋值）α1,α2,…,αn是指P＝α1，Q＝α2,…， 最后一个字母赋值αn。 上述αi取值为0或1，i＝1,2,…,n。 例如，在公式(┐P1∧┐P2∧┐P3)∨(P1∧P2)中
000(P1＝0，P2＝0，P3＝0)， 110(P1＝1，P2＝1，P3＝0)都是成真赋值 而001(P1＝0，P2＝0，P3＝1) 011(P1＝0，P2＝1，P3＝1)都是成假赋值。 在(P∧┐Q)→R中，011(P＝0，Q＝1，R＝1)为成真赋 值，100(P＝1，Q＝0，R＝0)为成假赋值。
第一章 命题逻辑
1-4 真值表与等价公式
1
一、公式的层次
公式的层次（补充）定义： 公式的层次 (1)若公式A是单个的命题变元，则称A为0层公式 0层公式。 (2)称A是n+1(n≥0)层公式是指下面情况之一： (a)A＝┐B，B是n层公式； (b)A＝B∧C，其中B，C分别为i层和j层公式，且n＝ max(i，j)； (c)A＝B∨C，其中B，C的层次及n同(b)； (d)A＝B→C，其中B，C的层次及n同(b)； (e)A＝B↔C，其中B，C的层次及n同(b)； (3)若公式A的层次为k，则称A是k层公式 k层公式。 易知， (┐P∧Q)→R，(┐(P→┐Q))∧((R∨S)↔┐P)分 别为3层和4层公式。 2
如表1所示。
(┐P∧Q)→┐R P∧Q)→┐R的真值表 表1 (┐P∧Q)→┐R的真值表
从表1可知，公式(1)的成假赋值为011，其余7个赋值都是 成真赋值。
9
三、真值表
公式(2)是含2个命题变项的3层合式公式，它的真值表如表2 所示。
表2 (P∧┐P)↔(Q∧┐Q)的真值表 (P∧┐P) (Q∧┐Q)的真值表
23
六、等值演算
如果再用德摩根律及置换规则，又会得到 ┐(┐P∨Q)∨R ⇔(P∧┐Q)∨R 再用分配律及置换规则，又会得到 (P∧┐Q)∨R ⇔(P∨R)∧(┐Q∨R) 将以上过程连在一起，可得到 (P→Q)→R ⇔(┐P∨Q) → R ⇔ ┐(┐P∨Q)∨R ⇔(P∧┐Q)∨R ⇔(P∨R)∧(┐Q∨R) 上述演算中得到的5个公式彼此之间都是等值的 个公式彼此之间都是等值的， *上述演算中得到的 个公式彼此之间都是等值的， 在演算的每一步都用到了等价置换规则 在演算的每一步都用到了等价置换规则 上述用等值式及等价置换规则进行推演的过程称 等值演算，这是数理逻辑的主要内容。 为等值演算，这是数理逻辑的主要内容。 数理逻辑的主要内容
11
三、真值表
注意：表1～表3都是按构造真值表的步骤一步一 步地构造出来的，这样构造真值表不易出错。如 果构造的思路比较清楚，有些层次可以省略。 有一类公式，不论其命题变元做何种指派，其真 值永为真（假），就把这类公式记为T（F）。 关于n个命题变元P1,P2,…,Pn,可以构造多少个真 值表呢? n个命题变元共产生2n个不同指派,在每个指派下,公 式的值只有0和1两个值。于是n个命题变元的真值 表共有 种不同情况。
从表2可以看出，该公式的4个赋值全是成真赋值，即无成 假赋值。
10
三、真值表
公式(3)是含3个命题变项的4层合式公式。它的真值表如表3 所示。
表3 ┐(P→Q)∧Q∧R的真值表 ┐(P→Q)∧Q∧R的真值表 P→Q)∧Q∧R
它的真值表如表3所示。不难看出，该公式的8个赋值全是 成假赋值，它无成真赋值。
17
六、等值演算
虽然用真值法可以判断任何两个命题公式 是否等值，但当命题变元较多时，工作量 是很大的。可以先用真值表验证一组基本 的又是重要的等价公式，以它们为基础进 行公式之间的演算，来判断公式之间的是 否等值。下面给出15组（共24个）重要的 等值式，希望同学们牢牢记住它们。在下 面公式中出现的P,Q,R仍然是元语言符号， 它们代表任意的命题公式。P15 表1-4.8
15
五、公式置换
在一命题公式中，如果用公式置换命题的 某个部分，一般地会产生某种新的公式， 例如Q→（P∨（P∧Q））中以（ ┐P →Q）取 代（P∧Q），则Q→（P∨ （ ┐P →Q））就与 原式不同。为了保证取代后的公式与原式 等价（即真值相同），需要对置换作出一 些规定。
16
五、公式置换
定义 1-4.3 如果X是合式公式A的一部分， 且X本身也是一个合式公式，则称X为公式A 的子公式。 定理 1-4.1 设X是合式公式A的子公式，若 X ⇔Y，如果将A中的X用Y来置换，所得到 公式B与公式A等价，即A ⇔B。 证明 书P16 *满足定理1-4.1条件的置换称为等价置换（等 价代换）
3
二、命题公式分量指派
若P，Q的解释不变，R被解释为：是有理数，则 (P∨Q)→R被解释成：若2是素数或3是偶数，则 是有理数。这是个假命题。 其实，将命题符号P解释成真命题，相当于指定P 的真值为1，解释成假命题，相当于指定P的真值 为0。 在本课中，对含n个命题变项的公式A的指派（赋 值）情况做如下规定： 1．若A中出现的命题符号为P1,P2,…,Pn，给定A的 指派（赋值）α1,α2,…,αn 是指P1＝α1，P2＝ α2,…，Pn＝αn。
26
本节小结
公式层次 命题公式分量指派 真值表 公式等价 公式置换 等值演算
27
课后作业
复习课本例题 P18 （7）a)、c)、e)、f)、h) (使用等值 演算方法证明） 补充:（使用等值演算方法或真值表证明） (1) ┐(P ∨ Q ) ∨ (┐ P ∧Q) ⇔ ┐P (2) (P∧Q) →R⇔(P→R)∨(Q →R) (3) P→(Q→R)⇔(P∧┐R) → ┐Q
12
四、公式等价
根据真值表，有些命题公式在分量的不同 指派下，其对应的真值与另一命题公式对 应的真值完全相同，如表（P14 1-4.5)：
P 0 0 1 1 Q 0 1 0 1 P→Q 1 1 0 1
P 0 0 1 1 Q 0 1 0 1 ┐P 1 1 0 0 ┐P∨ Q 1 1 0 1
P→Q
┐P∨Q
定义1-4.1 在命题公式中，对于各分量指派真值的 各种可能组合，就确定了这个命题公式的各种真 种情况，把它汇列成表，就是命题公式的真值表 命题公式的真值表。 命题公式的真值表 真值表的构造步骤： (1) 找出公式中所含的全体命题变项P1,P2,…,Pn (若 无下角标就按字典顺序排列)，列出2n个赋值。本 课规定，赋值从00…0开始，然后按二进制加法 依次写出各赋值，直到11…1为止。
25
六、等值演算
证明： 例2.4 证明：(P→Q)→R P→(Q→R) 证 方法一 方法一：真值表法，可自己证明。 方法二 ：设A=(P→Q)→R,B=P→(Q→R)
先将A,B通过等值演算化成容易观察真值的情况，再进行判断。