数理逻辑13.ppt

1、1.3.1 基本概念,定义1设 , 是两个命题公式。如果对于 与 的合成变元组(即这两个公式所有不同命题变元合在一起)的任意指派 ，均有 () = ()则称 与 逻辑等价，也称永真等价或同真假。记为 。 判断两个命题公式逻辑等价的第一种方法是使用真值表。先将与的合成变元组的各种指派和与在各种指派下的真假值写在同一张表上，然后检验与的相应位置上的真值是否相同。 例如，利用真值表即可验证命题公式PQ与命题公式P(PQ)逻辑等价。,基 本 逻 辑 等 价 式,请用真值表验证各个逻辑等价公式,研究两个命题公式之间逻辑等价关系的方法之二是利用命题公式的永真性。定理1设, 为命题公式， 当且仅当 为永真公

2、式。命题公式间的逻辑等价关系具有： 1) 自反性： ； 2) 对称性：若 ，则 ； 3) 传递性：若 且 ，则 。 应当指出的是，两个命题公式逻辑等价与两个命题公式相等是有所区别的。前者是指结果相同，后者是指形式相同(当然结果必相同)。因此相等比逻辑等价的要求更高。以后仍用“”表示相等。,1.3.2替换定理,定义2设命题公式，是命题公式的一部分且是命题公式，则称是的子命题公式。定义3设是命题公式，若将的子命题公式用另一命题公式替换，则称替换后产生的命题公式是关于替换为的结果。利用替换，可以将原有的命题公式改造成新的命题公式。例如，命题公式P(P(PQ)关于P(PQ)替换为PQ的结果为P(PQ)

3、 。替换定理设是关于替换为的结果。如果 ，则 。,引理 设1, 2, 1, 2均为命题公式。若1 1 , 2 2 , 则 1) 1 1 2) 1 2 1 2 3) 1 2 1 2 4) 1 2 1 2 5) 1 2 1 2 证：3） 设1, 2, 1, 2的合成变元组为(P1 , P2, , Pn) 。 对于该合成变元组的任一指派，由条件1 1 , 2 2 有 1() = 1() 2() = 2() 于是有 1() 2() = 1() 2() 由于 (1 2)() = 1() 2() (1 2)() = 1() 2() 于是有 (1 2)() = (1 2)() 由指派的任意性和逻辑等价的定义

4、知有1 2 1 2 。,替换定理设是关于替换为的结果。如果 ，则 。 证：对中除之外的联结词个数k 进行归纳证明。 当k = 0 时， 为下述两种形式之一。 1) = P (P是命题变元)，2) = 对于1) 根据的定义可知，此时 = P。于是有 = = P ，当然有 。 对于2) 有 = = 。 设当 kn 时，结论成立。下证当k = n 时，结论也成立。 事实上，按照命题公式的定义可知， 必呈下述形式之一。1, 1 2 , 1 2 , 1 2 , 1 2 仅以1 2 为例进行证明。 由于是关于替换为 的结果，而且只是对中以外的联结词进行归纳，即12中的不是中的联结词。因此，必呈12的形式，

5、其中1,2分别是1, 2关于替换为的结果。又由于1, 2中除之外的联结词的个数必然小于n。于是按照归纳假设可知，有1 1 2 2 再由引理知，有1 2 1 2 , 即 。,1.3.3代入定理,代入是通过已有的永真公式推出更多的永真公式的一种有效途径。例如，是否可由 PP 是永真公式而直接推断出 PQ PQ 是永真公式。这就是代入定理所要回答的问题。 定义4设为命题公式，P是中的命题变元，是任一命题公式。如果将中P的所有出现均用命题公式代替，则称代替后所得到的命题公式为关于P代入为的结果，简称的代入实例，记为/P。 例 = (P(PQ)Q， = PQ，代入P后则有 /P = (PQ)(PQ)Q)

6、Q,代入定理设为命题公式，P是中的命题变元。如果是永真公式，那么对任意命题公式 ，有/P为永真公式。 证令 = /P。设 的变元组为 (P1, P2, , Pn)， 的变元组为(Q1,Q2, , Qm)。于是 的变元组应为(Q1,Q2,Qm,P1,P2,Pn)于是 的变元组的任何指派 = (Q10,Q20,Qm0,P10,P20,Pn0)必确定了 的一个指派1 = (Q10,Q20,Qm0)令 P 0 = (1) ，于是得到 的一个完全指派2 = (P 0, P10, P20, , Pn0)注意到 是将 中 P 的所有出现均用 代替，于是有() = (2)而 是永真公式，于是有 (2) = T

7、 ，即有() = T 。由指派的任意性和永真公式的定义知 为永真公式。,由于代入定理的引入，获得永真公式的手段就更加丰富了。由代入定理知，每一个永真公式都是一族永真公式的代表。例如，由 (P(PQ)Q 是永真公式可推知所有形如 () 的命题公式均为永真公式。因此，每个永真公式中的命题变元都可以理解为子命题公式的形式。 将代入定理运用于命题公式之间的逻辑等价，可以得到如下结论。 推论设 , 是命题公式。若 ，则 /P /P 。 证由条件知 ，由定理1知 是永真公式。根据代入定理有 /P/P 是永真公式。再由定理1知/P /P 。 利用这个推论，可将上节给出的基本逻辑等价式中的命题变元理解为命题公

8、式。 例如，PQ QP 可理解为 等等。,1.3.4逻辑等价变换,利用代入定理、替换定理和基本逻辑等价式，可以十分方便地进行命题公式间的逻辑等价变换。 例 证明 P Q (PQ)(PQ),1.3.5联结词归约和范式,1) 异或联结词 异或联结词将成分命题P,Q组成新的命题“P或者Q之一成立”，即前面曾经提到的“不可兼或”。记为PQ，其中称为异或词。 它们的真假值关系由表3确定。 表3异或联结词之真值表 从异或词的定义知 PQ (PQ)(PQ),2) 与非联结词 与非联结词 将成分命题P,Q组成新的命题“P且Q不成立”，记为 P Q，其中 称为与非词。 它们的真假值关系由表4确定。 表4 与非联

9、结词之真值表 由与非词的定义知 P Q (PQ),3) 或非联结词 或非联结词 将成分命题P,Q组成新的命题“P或者Q不成立”，记为 P Q，其中 称为或非词。 它们的真假值关系由表5确定。 表5 或非联结词之真值表 由或非词的定义知 P Q (PQ),定义5设 P1, P2, , Pn 是 n 个命题变元，f 是从T, Fn 到T, F的对应关系。如果对于 n 个命题变元的任一指派，通过 f 均有唯一的真假值与之对应，则称 f 是 n 元真值函数。 例 三元真值函数W的真值表 定义6若A是真值函数集合的子集，则称A是联结词集合。,定义7设A是联结词集合。若任一真值函数都可以用A中的联结词表示

10、，则称A是全功能(功能完备)的。 定理2联接词集合 , , 是全功能的。 证对于任一n元真值函数 f (P1,P2,Pn)，其所有的成真指派为 | f () = T = 1, 2, m其中i = (P1i, P2i, , Pni), i = 1, 2, 3, m. 对于每个 i，通过下述方法给出相应的i其中 于是对于每个 i 有 , i() = T 当且仅当 = i 。 令 = 1 2 m， 于是有() = T 当且仅当存在一个 i，使得 = i 。 于是有 f () = T当且仅当() = T。即 f (P1, P2, , Pn) (P1, P2, , Pn)而是仅含有, , 的命题公式，故

11、, , 是全功能的。,定义8设A是全功能联结词集合。若A中的任一联结词不能用其它联结词来表示，则称A是极小全功能的。 定理3下面的联结词集合都是极小全功能的。 , , , , , 定理4下述联结词集合是极小全功能的。 , 证只证是全功能的。只要证明全功能联结词集,中的每个联结词可分别由 表示。由于P P PP Q (P Q) (P Q)故是全功能的。 由于中只有一个联结词，故是极小全功能的。 由定理4可知，所有真值函数均可由一个联结词 或 来表示。这正是在数字逻辑电路中选择“与非门”或“或非门”作为基本逻辑器件的理论根据。 但从另一个角度来看，单由 或 组成的命题公式不满足结合律。这给人们直接

12、用 或 进行研究带来不便。,定义9设 是命题公式。如果 具有下述形式 = 1 2 n 其中诸 i 为命题变元或命题变元的否定或命题变元和命题变元的否定构成的合取式，则称 为析取范式。 例(PQR) R Q 是析取范式。 定义10设 是命题公式。如果 具有下述形式 = 1 2 n其中诸 i 为命题变元或命题变元的否定或命题变元和命题变元的否定构成的析取式，则称 为合取范式。 例 P (PQR) (QR) 是合取范式。 任何一个命题公式都可以通过下述步骤化为析取范式或合取范式。 1) 联结词归约：将命题公式中的所有联结词化归成仅含,的命题公式。 2) 否定词深入：利用de Morgan律将否定词移

13、到每个命题变元之前。 3) 调整 与 ：利用与 的分配律、结合律等性质将命题公式化归成析取范式或合取范式。,定义11设 是 n 元命题公式。如果 具有下述形式 = 1 2 n 并且诸 i 具有形式其中 为Pi 或Pi ，称为小项范式(主析取范式)，称i 为小项。 定义12设 是 n 元命题公式。如果 具有下述形式 = 1 2 n 并且诸 i 具有形式 其中 为Pi 或Pi ，称为大项范式(主合取范式)，称i为大项。 例 (PQR)(PQR)(PQR) 是主析取范式。 (PQR)(PQR)(PQR) 是主合取范式。,下面给出求一个命题公式的主析取范式的步骤(求主合取范式的步骤类似)。 1) 联结

14、词归约：同前。 2) 否定词深入：同前。 3) 调整与 ：同前。 4) 消除永假项：若某个i中同时含有同一命题变元及其否定，则将此i去掉。 5) 变元合并：若某个i中含有两个以上同名的命题变元，则只保留一个。 6) 补足变元：若某个命题变元P在i中没有出现，则用i (PP) 替换i ，然后用分配律展开。 7) 合并相同项：若i与j相同，则只保留i 。例 求 (PQ)(PR) 的主析取范式。,引理设是含有n个命题变元 P1, P2, , Pn 的小项，即 = (P10,P20,Pn0)是的任一指派。则() = T当且仅当 定理5 主析取范式或主合取范式是唯一的。 证只证主析取范式的唯一性。 设是n元命题公式， 的成真指派分别为1, 2, m 根据引理，由这些成真指派可分别确定出相应的小项1 , 2 , , m 由它们之间的一一对应关系可知， 的主析取范式为1 2 m 当然，这里的唯一性并不保证各小项及各命题变元的位置的唯一性。而命题变元的位置可以事先约定。 根据上面的讨论，不难得出这样的结论：两个命题公式逻辑等价必须且只须它们相应的主范式相同。当然，如果两个命题公式的主范式相同时，这两个命题公式必然逻辑等价。,