2.1 命题公式由命题变项、逻辑联结词和括号按照一定的正确规则组成的字符串即为命题公式proposition formula或合式公式well formed formula简称公式。单个命题变项也是命题公式。给命题公式中所有命题变项分别指定一个真值这些真值组成公式的一个指派assignment。列出命题公式所有的指派及其对应公式的真值的表格即为公式的真值表。【例】构建公式(¬P→Q)↔(P∨R)的真值表PQR¬P¬P→QP∨R(¬P→Q) ↔ (P∨R)FFFTFFTFFTTFTFFTFTTFFFTTTTTTTFFFTTTTFTFTTTTTFFTTTTTTFTTT命题公式共有三类永真式/重言式tautology在所有命题变项的真值指派下公式的取值恒为真。永假式/矛盾式contradiction在所有命题变项的真值指派下公式的取值恒为假。偶真式/可满足式contingency一部分命题变项的真值指派下公式的取值为真另一部分命题变项的真值指派下公式的取值为假。当一个命题公式是永假式该公式是不可满足的unsatisfiable否则至少能找到一种指派使该公式的真值为真该公式是可满足的satisfiable。2.2 命题公式的等价若两个命题公式在所有命题变项真值指派下其真值结果完全一致则它们是逻辑等价的logic equivalent。对于命题P、Q若P↔Q为永真式则P、Q逻辑等价记作P⇔Q或P≡Q。【提醒】区别“↔”与“⇔”P↔Q是命题公式P⇔Q不是命题公式是针对命题公式的判断。常用的逻辑等价定律逻辑等价式名称P∧T≡PP∨F≡P同一律Identity lawsP∨T≡TP∧F≡F支配律Domination lawsP∨P≡PP∧P≡P幂等律Idempotent laws¬(¬P)≡P双重否定律Double negation lawP∨Q≡Q∨PP∧Q≡Q∧P交换律Commutative laws(P∨Q)∨R≡P∨(Q∨R)(P∧Q)∧R≡P∧(Q∧R)结合律Associative lawsP∨(Q∧R)≡(P∨Q)∧(P∨R)P∧(Q∨R)≡(P∧Q)∨(P∧R)分配律Distributive laws¬(P∧Q)≡¬P∨¬Q¬(P∨Q)≡¬P∧¬Q德·摩根律De Morgans lawsP∨(P∧Q)≡PP∧(P∨Q)≡P吸收律Absorption lawsP∨¬P≡TP∧¬P≡F否定律Negation laws常用的逻辑等价式逻辑等价式P→Q≡¬P∨Q¬(P→Q)≡P∧¬Q(P→Q)∧(P→R)≡P→(Q∧R)(P→R)∧(Q→R)≡(P∨Q)→R解释“如果P则 R并且如果Q则R”⇔“只要P或Q有一个成立那么R就成立”(P→Q)∨(P→R)≡P→(Q∨R)(P→R)∨(Q→R)≡(P∧Q)→R解释“如果P则R或者如果Q则R”⇔“只有当P和Q都成立时R才必须成立”P↔Q≡¬P↔¬Q¬(P↔Q)≡P↔¬Q解释“P当且仅当Q不成立”⇔“P当且仅当非Q 成立”P↔Q≡(P∧Q)∨(¬P∧¬Q)解释“P当且仅当Q”⇔“P和Q同时为真或者同时为假”命题公式进行等价演算时常用到命题公式的替换原理rule of replacement即将命题公式A中的某个子公式B替换为和B逻辑等价的公式C所得到的新的命题公式D与原命题公式A仍然等价。【例】证明(¬A∧(¬B∧C))∨(B∧C)∨(A∧C)⇔C(¬A∧(¬B∧C))∨(B∧C)∨(A∧C)⇔((¬A∧¬B)∧C)∨(B∧C)∨(A∧C) 结合律⇔((¬A∧¬B)∨B∨A)∧C 分配律⇔(¬(A∨B)∨B∨A)∧C 德・摩根律⇔(¬(A∨B)∨(B∨A))∧C 结合律⇔(¬(A∨B)∨(A∨B))∧C 交换律⇔T∧C 否定律⇔C 同一律2.3 命题公式的范式2.3.1 命题联结词的完备集如果对于任意一个命题公式都可用S中的联结词进行等价表示则S为联结词的完备集adequate set of connectives。设T⊂S如果至少存在一个命题公式不能用T中的联结词进行等价表示则S为联结词的极小完备集minimal adequate set of connectives。联结词的极小完备集有{¬,∧}、{¬,→} 、{¬,∨}命题公式的范式使用的联结词的完备集为{¬,∧,∨}。2.3.2 范式仅由有限个命题变项或其否定通过析取构成的公式即为简单析取式simple disjunctive formula仅由有限个命题变项或其否定通过合取构成的公式即为简单合取式simple conjunctive formula。一个命题变项或其否定既是简单析取式也是简单合取式。由有限个简单合取式的析取构成的公式即为析取范式disjunctive normal form由有限个简单析取式的合取构成的公式即为合取范式conjunctive normal form。一个简单析取式或简单合取式既是析取范式或合取范式。【例】¬P∨Q∨R是简单析取式¬P∧Q∧R是简单合取式P是简单析取式是简单合取式P∨(P∧Q)∨(¬P∧¬Q∧¬R)是析取范式P∧(P∨Q)∧(¬P∨¬Q∨¬R)是合取范式P∨Q∨¬R 是析取范式是三个简单合取式的析取P∨Q∨¬R 是合取范式是一个简单析取式P∧Q∧¬R 是合取范式是三个简单析取式的合取P∧Q∧¬R 是析取范式是一个简单合取式范式的存在性定理existence theorem of normal form表明任何命题公式存在不唯一的与之等价的一个析取范式和一个合取范式。求析取范式和合取范式的基本步骤利用逻辑等价式消除“→”、“↔”利用德·摩根律与双重否定律移动“¬”至命题变项前并消除连续的“¬”利用分配律将公式化为析取范式和合取范式【例】求(P∨Q)→R的析取范式与合取范式(P∨Q)→R ⇔ ¬(P∨Q) ∨ R⇔ (¬P∧¬Q) ∨ R 析取范式⇔ (¬P∨R) ∧ (¬Q∨R) 合取范式若命题公式中共有n个命题变项…这n个命题变项的简单合取式中每个命题变项或其否定¬均出现一次且按命题变项的下标排列该简单合取式即为极小项min term或布尔合取。每个极小项只有唯一赋值使其为真其余个赋值使其为假具有一一对应关系。若极小项为真的赋值为则该极小项可记作若把视为二进制数对应十进制数为则该极小项可记作。若命题公式中共有n个命题变项…这n个命题变项的简单析取式中每个命题变项或其否定¬均出现一次且按命题变项的下标排列该简单析取式即为极大项max term或布尔析取。每个极大项只有唯一赋值使其为假其余个赋值使其为真具有一一对应关系。若极大项为假的赋值为则该极大项可记作若把视为二进制数对应十进制数为则该极大项可记作。【例】命题公式中出现P、Q、R三个命题变项P∧¬Q不是极小项R未出现P∧¬Q∧¬P不是极小项P、¬P 同时出现对于极小项¬P∧Q∧¬R只有010赋值使其为真记作或若干个不同的极小项的析取式即为主析取范式principal disjunctive normal form。任何命题公式存在唯一的与之等价的主析取范式。极小项与主析取范式的赋值存在以下关系主析取范式包含的极小项的成真赋值是主析取范式的成真赋值主析取范式未包含的极小项的成真赋值是主析取范式的成假赋值主析取范式的任何一个成真赋值是其包含的某个极小项的成真赋值用等价演算求主析取范式的基本步骤将原公式转换为析取范式的形式∨⋯∨消去重复的命题变项∧⇔消去矛盾的命题变项∨(∧¬)⇔补全缺失的命题变项⇔∧(∨¬)⇔(∧)∨(∧¬)调整命题变项的顺序使其成为标准极小项消除重复的极小项∨⇔按下标升序排列各极小项得到主析取范式∨⋯∨若干个不同的极大项的合取式即为主合取范式principal conjunctive normal form。任何命题公式存在唯一的与之等价的主合取范式。极大项与主合取范式的赋值存在以下关系主合取范式包含的极大项的成假赋值是主合取范式的成假赋值主合取范式未包含的极大项的成假赋值是主合取范式的成真赋值主合取范式的任何一个成假赋值是其包含的某个极大项的成假赋值用等价演算求主合取范式的基本步骤将原公式转换为合取范式的形式∧⋯∧消去重复的命题变项∨⇔消去矛盾的命题变项∧(∨¬)⇔补全缺失的命题变项⇔∨(∧¬)⇔(∨)∧(∨¬)调整命题变项的顺序使其成为标准极大项消除重复的极大项∨⇔按下标升序排列各极小项得到主析取范式∨⋯∨除了用等价演算法求主范式以外还可以用真值表法求主范式。【例】用等价演算法求 ((P∨Q)→R)→P 的主析取范式原公式 ⇔¬(¬(P∨Q)∨R)∨P⇔((P∨Q)∧¬R)∨P⇔(P∧¬R)∨(Q∧¬R)∨P⇔P∨(Q∧¬R) ⇔(P∧(Q∨¬Q)∧(R∨¬R))∨((Q∧¬R)∧(P∨¬P))⇔(P∧Q∧R)∨(P∧Q∧¬R)∨(P∧¬Q∧R)∨(P∧¬Q∧¬R)∨(P∧Q∧¬R)∨(¬P∧Q∧¬R)⇔(P∧Q∧R)∨(P∧Q∧¬R)∨(P∧¬Q∧R)∨(P∧¬Q∧¬R)∨(¬P∧Q∧¬R)⇔(¬P∧Q∧¬R)∨(P∧¬Q∧¬R)∨(P∧¬Q∧R)∨(P∧Q∧¬R)∨(P∧Q∧R)⇔∨∨∨​∨【例】用真值表法求¬(P∨Q)的主析取范式①列出¬(P∨Q)的真值表PQP∧Q¬(P∧Q)0001010110011110②找到使公式为真的赋值并列出极小项00 对应的极小项是 ¬P∧¬Q (​)01 对应的极小项是 ¬P∧Q ()10 对应的极小项是 P∧¬Q ()③求主析取范式¬(P∧Q)⇔(¬P∧¬Q)∨(¬P∧Q)∨(P∧¬Q)⇔​∨​∨【结论】对于含有n个命题变项的公式极小项极大项的数量为个组合而成的主析取范式主合取范式的数量为个。每个命题变项可取“原命题变项”与“原命题变项的否定”两种形式n个命题变项的形式组合数为即为极小项极大项的数量主析取范式主合取范式是若干个极小项极大项的析取合取每个极小项极大项具有“选”与“不选”两种状态个极小项极大项的状态组合数为即为主析取范式主合取范式的数量。如何从范式的角度理解命题公式的可满足性若一个公式是可满足的则它的主析取范式中至少包含一个极小项或它的主合取范式中不包含所有极大项若一个公式是不可满足的则它的主析取范式中不存在极小项或它的主合取范式中包含所有极大项。