（逻辑）语义等价：若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