数理逻辑（讲义）(3)

（逻辑）语义等价：若A,B构成的等价式A?B为重言式，则称A与B是等值的，或语义等价。记作A?B。

用真值表判断公式的等值（在所有赋值下验证） 例： ?(p?q)?(?p??q)

（逻辑）语义蕴含：若公式A?B为重言式，则称A蕴含B。记作A?B。表示：若A为真命题，则B为真命题。

逻辑的主要任务是研究逻辑推理。 命题公式的规范表示：

合取范式： CNF公式。 析取范式： DNF公式。

文字：变元或变元的否定统称为文字。x,?x 子句：文字的析取称为子句。C?L1?L2?......?Ln。 子句C中所含文字的个数n 称为子句长度。

CNF公式：子句的合取称为CNF公式。F?C1?C2?......?Cm。 公式F的(大小)规模定义为。|F|?|C1|?|C2?......?|Cm|。 k-CNF公式: 公式F中每个子句的长度?k。

Horn子句：出现在C?L1?L2?......?Ln中的正文字个数至多为1。

DNF公式：

(1) 项：文字的合取称为项。C?L1?L2?......?Ln。 (2) DNF公式：项的析取称为DNF公式。

10

定理.设F为一个命题公式，则存在公式F1和F2， 使得F?F1， F?F2. 其中，F1为CNF公式，F2为DNF公式。

范式的唯一性——主范式 p,q形成的极小项与极大项

p,q,r形成的极小项与极大项

联结词的完备集: 能表示任意布尔函数的联结词集合。

设S是一个联结词集合，如果任何n(n≥1)元真值函数都可以由仅含S中的联结词构成的公式表示，则称S是联结词完备集。 定理. S={┐,∧,∨}是联结词完备集。 例：{?,?,?},

11

{?,?},{?,?}。

所有2元真值函数

逻辑推理：?|?A

设A?Form(LP)，??Form(LP)。若对于任一赋值v, 如果?v?1，则Av?1， 称由?逻辑可推A。记为： ?|?A。

若A|?B且B|?A，称A与B逻辑等价。记为：A|?|B。 注意：若?不可满足，则对任意的A，均有?|?A。 证明方法：证?|?A。

v证明：假定任意赋值v, 使得??1，验证A?1。

v反证法： 假定?|?A，由存在一个赋值v, 使得?v?1，但A?0。然后导出矛盾。

定理1.(1) A1,......,Anv|?A?(A1?A2?......?An)|?A

(2) A1,......,An|?A?|?(A1?(A2?(......(An?A)......)

定理2. (等值替换定理)

设F为一个命题公式，A是出现在F中的一个子公式，A|?|B。F'是将B替换F中的部份A得到的公式，则 F|?|F'。

12

语义证明方法

一、王浩算法

原理：将A1,......,An|?B的证明转换为证明(A1?......?An)?B为重言式。 子句格式：

(a?b?c??d??e)(a?b?c)??(d?e)(d?e)?(a?b?c)

串格式：d,e?sa,b,c

重言子句的串格式：d,a?sa,b,c，对应a?b?c??d??a 公理格式：A,??A,?。 前项规则：

??: 若?,?A??，则??A,? ??: 若?,A?B??，则?,A,B?? ??: 若?,A?B??，则?,A??或?,B?? ??: 若?,A?B??，则??A,?或?,B?? ??: 若?,A?B??，则?,A,B??或??A,B,?

后项规则：

??: 若???,?A，则A,??? ??: 若???,A?B，则???,A或???,B ??: 若???,A?B，则???,A,B ??: 若???,A?B，则?,A?B,? ??: 若???,A?B，则?,A?B,? 或B,??A,?

13

证明形式：

以一个起始串为树根，按规则消去联结词。当串为公理形式时，不再往下做。如果证明树的每个叶结点均为公理形式，则原公式为重言式（或矛盾式）。 证F为重言式：起始串为 ?F 要证： A1,......,An|?B。

即证： F:?(A1?......?An)?B为重言式。 证明起始串取为： A1,......,An?B。 例：证明A?(B?C),A?B|?A?C （1）A?(B?C),A?B?A?C （2）（1-1）A?(B?C),A?B,A?C （3）（2-1）A?(B?C),A?C,A (公理) （4）（2-2）A?(B?C),A,B?C（待分解） （5）（4-1）A,B?C,A (公理)

（6）（4-2）A,B,(B?C)?C(待分解) （7）（6-1）A,B?C,B(公理) （8）（6-2）A,B,C?C(公理)

14