数理逻辑与集合论：2-2 命题逻辑的等值和推理演算

1、请交作业1等值式应用举例n A、B、C、D 四人做百米竞赛，观众甲、乙、丙预测比赛结果如下：甲：甲：C第一，第一，B第二；第二；乙：乙：C第二，第二，D第三；第三；丙：丙：A第二，第二，D第四；第四；比赛结束后发现他们每人都说对一半，试问实际名次如何(假设无并列者)？n 解：首先，将命题符号化: 设用设用Ai “A第第i名名”、 Bi “B第第i名名”、 Ci “C第第i名名”、 Di “D第第i名名” (i=1,2,3,4) Ai、Bi、Ci、Di中均各有一个真命中均各有一个真命题，按题意要寻找使下列题，按题意要寻找使下列3式成式成立的真命题立的真命题 (C1 B2) ( C1 B2) 1

2、(C2 D3) ( C2 D3) 1 (A2 D4) ( A2 D4) 1等值式应用举例 (C1 B2) ( C1 B2) 1 (C2 D3) ( C2 D3) 1 (A2 D4) ( A2 D4) 1n 因为真命题的合取式仍为真命题（因为真命题的合取式仍为真命题（1 1 1），故得），故得 1 (C1B2) ( C1 B2) (C2D3) ( C2 D3) (C1B2) (C2D3) (C1B2) ( C2 D3) ( C1 B2) (C2D3) ( C1 B2) ( C2 D3)等值式应用举例 (C1 B2) ( C1 B2) 1 (C2 D3) ( C2 D3) 1 (A2 D4) (

3、A2 D4) 1n 1 (C1B2 C2 D3) ( C1 B2 C2 D3) 1 (C1B2 C2 D3 A2 D4) (C1B2 C2 D3 A2 D4) ( C1 B2 C2 D3 A2 D4) ( C1 B2 C2 D3 A2 D4)等值式应用举例 (C1 B2) ( C1 B2) 1 (C2 D3) ( C2 D3) 1 (A2 D4) ( A2 D4) 1n 1 C1B2 C2 D3 A2 D4 A2 B2 (C1 C2) (D3 D4 )A第二第二C第一第一D第三第三B第四第四第2章 命题逻辑的等值和推理演算 2.1 等值定理2.2 等值公式2.3 命题公式与真值表的关系2.4

4、联结词的完备集2.5 对偶式2.6 范式2.7 推理形式2.8 基本的推理公式2.9 推理演算2.10 归结推理法讨论讨论等值演算等值演算讨论讨论推理演算推理演算 真值表中每个公式的真值都有真值表中每个公式的真值都有T、F两种可能，所两种可能，所以命题公式的真值有以命题公式的真值有24= =16种可能，即有种可能，即有 个个不同的真值表。故有不同的真值表。故有 种不等价的公式。种不等价的公式。 222222222真值函数问题：两个命题变项可构成多少个不等价的合式公式？n即两个命题变项构成的合式公式有多少个不同的真值表？即两个命题变项构成的合式公式有多少个不同的真值表？结论：结论： 含含n个命题

5、变项的所有公个命题变项的所有公式共产生式共产生 个互不相同的个互不相同的真值表真值表n22 P Q 公公 式式 F FF TT FT TT或或FT或或FT或或FT或或FP QF FF TT FT T F F F F F F F F F F F F T T T T F F T T F F T T F T F T F T F T )2(7)2(6)2(5)2(4)2(3)2(2)2(1)2(0FFFFFFFFP QF FF TT FT T T T T T T T T T F F F F T T T T F F T T F F T T F T F T F T F T )2(15)2(14)2(13)

6、2(12)2(11)2(10)2(9)2(8FFFFFFFF2元真值函数对应的真值表联结词的完备集n 定义 n在一个联结词的集合中，如果一个联结词可由集合中的在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为其他联结词定义，则称此联结词为冗余的联结词冗余的联结词，否则，否则称为称为独立的联结词独立的联结词。n 如：如： P Q = P Q P Q = (P Q) ( P Q )n在在 ， ， ，中中、是冗余的。是冗余的。n 在，中， P Q = （ P Q ）n所以所以 是冗余的。是冗余的。n在在 ， 中无冗余的联结词。中无冗余的联结词。n 同理，同理，在在 ， 中

7、无冗余的联结词。中无冗余的联结词。联结词的完备集n定义 n设设C是联结词的集合，若对任一命题公式都由是联结词的集合，若对任一命题公式都由C中的联中的联结词表示出来的公式与之等值，就说结词表示出来的公式与之等值，就说C是是完备的联结词集合。n 显然，全体联结词的无限集合是完备的。显然，全体联结词的无限集合是完备的。n ， ， ，n ， ， ， n ， ， n ， ， ， ， ， 等是完备且无冗余的。是完备的是完备的2.5 对偶式n 定义定义n 在仅含联结词在仅含联结词，的命题公式的命题公式A中，将中，将联结词联结词，F，T分别换成分别换成，T，F所得的公式称为公式所得的公式称为公式A的的对偶式对

8、偶式，记为，记为A*n 如：如：P Q与与P Q 是对偶式是对偶式n (P Q) R与与 (P Q) R是对偶式是对偶式n 推广n 在仅含有联结词在仅含有联结词，的命题公式的命题公式中，将联结词中，将联结词，F，T分别换成分别换成 ，T，F，就得到了它的对偶式。，就得到了它的对偶式。与对偶式有关的定理n设设A和和A*互为对偶式，互为对偶式，P1, P2, Pn是出现在是出现在A和和A*中的全部命题变项，中的全部命题变项，令 A=A (P1, P2, , Pn), A=A ( P1, P2, Pn)n 定理定理2.5.1： (A*)=( A)*, (A)=( A)n 如：A= P Q ，则，则

9、n A*= P Q ，A= P Q ， A= P Q n 所以： ( A)*= P Q (A *)= P Q n 所以： ( A)= P Q (A)= P Q (A*)=( A)* (A)=( A)与对偶式有关的定理n 定理定理2.5.2： (A*)*= A, (A)= An 定理定理2.5.3： A = A*n 如：A= P ( Q R) n 则则： A= P (Q R) A*= P ( Q R) 所以：A*= P (Q R) = A此定理为摩根律：此定理为摩根律： (A B) = AB (A B) = AB的另一种形式的另一种形式，与对偶式有关的定理n 定理定理2.5.4 若若A=B，必有

10、，必有A*=B*n 证：A=B AB 永真 AB 永真 A*B* 永真 A*B* 永真 A*=B*n 定理2.5.5 若AB永真，必有B * A *永真(作业)n 定理2.5.6 A 与A 同永真，同可满足 A与A* 同永真，同可满足n 对偶性是逻辑规律，给证明公式的等值和求否定带来方便对偶性是逻辑规律，给证明公式的等值和求否定带来方便依定理依定理2.5.3有，有， A=A* B=B*2.6 范 式 n范式提出的背景n与与 P Q 等值的公式有等值的公式有 P Q (P Q) (Q P) P Q (P Q) ( P Q) P Q (P Q) ( P Q )n与与 P Q 等值的公式有等值的公式

11、有P Q ( P Q) ( P Q) (P Q)P Q P Q n 可见同一公式可以有多种表示形式，能否有统一的可见同一公式可以有多种表示形式，能否有统一的规范等值式，使真值表相等的公式形式相同？规范等值式，使真值表相等的公式形式相同？范式范式范 式n 简单析取式 n它是仅由有限个命题变项或其否定构成的析取式。它是仅由有限个命题变项或其否定构成的析取式。n如如: P，Q， P， Q， P Q， P Q， P Q n 它是它是重言式重言式当且仅当它同时含一个命题变项及其否定；当且仅当它同时含一个命题变项及其否定；n如：如： P Q P 是重言式是重言式n 简单合取式n它是仅由有限个命题变项或其否

12、定构成的合取式。它是仅由有限个命题变项或其否定构成的合取式。n如如: P，Q， P， Q， P Q， P Qn 它是它是矛盾式矛盾式当且仅当它同时含一个命题变项及其否定。当且仅当它同时含一个命题变项及其否定。n如：如： P P Q 是矛盾式是矛盾式 析取范式n 析取范式n由有限个简单合取式组成的析取式。由有限个简单合取式组成的析取式。 A1 A2 . An（n 1，Ai 都是都是简单合取式简单合取式） n如：如：(P Q R) ( P Q) Qn一个析取范式是一个析取范式是矛盾式矛盾式，当且仅当其每个简单合取式，当且仅当其每个简单合取式都是都是矛盾式矛盾式n 合取范式n由有限个简单析取式组成的

13、合取式。由有限个简单析取式组成的合取式。 A1 A2 . An（n 1, Ai都都是是简单析取式简单析取式）n如：如：(P Q R) ( P Q) Qn一个合取范式是一个合取范式是重言式重言式，当且仅当其每个简单析取式，当且仅当其每个简单析取式都是都是重言式重言式n 范式范式析取范式与合取范式的总称析取范式与合取范式的总称 。范式存在定理任何命题公式都存在着与之任何命题公式都存在着与之等值的析取范式与合取范式等值的析取范式与合取范式命题公式的范式 n求公式A的范式的步骤： (1) 消去消去A中的中的, （若存在）（若存在） A B = A B A B = (A B)( A B) (求析取范式时

14、求析取范式时) = (A B)( A B) (求合取范式时求合取范式时) (2) 否定联结词否定联结词 的内移或消去（摩根定律）的内移或消去（摩根定律） (3) 使用分配律使用分配律 对对 分配（析取范式）分配（析取范式） 对对 分配（合取范式）分配（合取范式）n注意：n公式的范式存在，但公式的范式存在，但不惟一不惟一，这是它的局限性，这是它的局限性 求公式的范式举例 例: 求下列公式的析取范式与合取范式(1) A=(PQ)R解解 (PQ)R = ( PQ)R （消去（消去） = PQR （结合律）（结合律） 这既是这既是A的的析取范式析取范式（由（由3个简单合取式组成的个简单合取式组成的析取

15、式）析取式） 又是又是A的的合取范式合取范式（由一个简单析取式组成的（由一个简单析取式组成的合取式）合取式）求公式的范式举例(2) B=(PQ)R解解 (PQ)R = ( PQ)R （消去第一个（消去第一个） = ( PQ) R （消去第二个（消去第二个） = (P Q) R （否定号内移（否定号内移摩根律）摩根律）这已为这已为析取范式析取范式（两个简单合取式构成）（两个简单合取式构成）继续：继续： (P Q) R = (P R) (Q R) （ 对对 分配律）分配律）这一步得到这一步得到合取范式合取范式（由两个简单析取式构成（由两个简单析取式构成） 极小项n 定义 n n个命题变项的个命题变

16、项的简单合取式简单合取式，其中每个命题变项与其否，其中每个命题变项与其否定不同时出现，定不同时出现，而二者之一必出现且仅出现一次而二者之一必出现且仅出现一次，这样，这样的简单合取式称为的简单合取式称为极小项极小项。n如：两个命题变元如：两个命题变元P和和Q，其极小项为：，其极小项为： P Q， P Q ， P Q ， P Qn 说明nn个命题变项产生个命题变项产生2n个极小项，它们互不等值个极小项，它们互不等值n用用mi表示第表示第i个极小项，每个小项的个极小项，每个小项的n个变元排序相同。个变元排序相同。（按下标或字典顺序），分别记为（按下标或字典顺序），分别记为n其中其中i是该极小项是该极

17、小项成真赋值成真赋值的十进制表示的十进制表示. m11 m10 m01 m00 1210, nmmm极小项n由由P, Q, R三个命题变项形成的极小项三个命题变项形成的极小项极小项极小项成真赋值成真赋值名称名称PQR000m0PQR001m1PQR010m2PQR011m3PQR100m4PQR101m5PQR110m6PQR111m7主析取范式n主析取范式n设命题公式设命题公式 A 中含中含n个命题变项，如果个命题变项，如果 A 的析的析取范式中的简单合取式全是取范式中的简单合取式全是极小项极小项，则称该析，则称该析取范式为取范式为 A 的的主析取范式主析取范式n如：如：n=3, 命题变项为

18、命题变项为P, Q, R 时，主析取范式时，主析取范式： ( PQ R) ( P Q R) = m1 m3 n定理定理n任何命题公式都任何命题公式都惟一惟一存在与之等值的主析取范式存在与之等值的主析取范式. . n求主析取范式的方法求主析取范式的方法n等值演算法和真值表法等值演算法和真值表法用等值演算法求主析取范式的步骤1. 求求 A 的析取范式的析取范式 A ； 2. 若若 A 的某简单合取式的某简单合取式 B 中不含某命题变项或其中不含某命题变项或其否定，则将否定，则将 B 展成如下形式：展成如下形式： B = B T = B (Pi Pi ) = (B Pi) (B Pi)3. 将重复出

19、现的命题变项、矛盾式及重复出现的极将重复出现的命题变项、矛盾式及重复出现的极小项都小项都“消去消去”。 4. 将极小项按由小到大的顺序排列，并用将极小项按由小到大的顺序排列，并用 表示之，表示之，如如 m1 m2 m6 用用 (1,2,6) 表示表示。求公式 A=(PQ)R 的主析取范式解法1： (PQ)R = ( P Q) R = (P Q) R （析取范式）（析取范式） P Q = (P Q) ( R R) = (P QR) (P Q R) = m6 m7 R =( P P) ( Q Q) R =( PQ R) ( P Q R) (PQ R) (P Q R) = m1 m3 m5 m7 ,

20、 代入并合并相同式，得主析取范式：代入并合并相同式，得主析取范式： (PQ)R = m1 m3 m5 m6 m7= (1,3,5,6,7) 解法2： (PQ)R = ( P Q) R = (P Q) R （析取范式）（析取范式） = m11x mxx1 = (m110 m111) ( m001 m011 m101 m111) = (1,3,5,6,7)求公式 A=(PQ)R 的主析取范式主析取范式的用途(1) 求公式的成真赋值和成假赋值求公式的成真赋值和成假赋值n 如前面例子中得到如前面例子中得到 (PQ)R = m1 m3 m5 m6 m7n其成真赋值为：其成真赋值为： 001, 011, 101, 110, 111(P=F, Q=F, R=T )n则其余的赋值为成假赋值则其余的赋值为成假赋值000, 010, 100 主析取范式的用途 (2) 判断公式的类型判断公式的类型 设设A含含n个命题变项，则个命题变项，则 n A为重言式为重言式A的主析取范式含的主析取范