逻辑学

学逻辑学，用逻辑思维思考问题。主要内容有命题逻辑的推理理论、谓词、谓词公式、谓词逻辑的演绎与推理、规律命题、命题联结词、命题公式、析取范式和合取范式。

逻辑学

• 命题逻辑的推理理论
  • 在推理中，前提是指已知的命题公式，结论是从前提出发应用推理规则推出的命题公式。这一过程称为有效推理或形式证明，所得的结论称为有效结论。这里我们最关心的不是结论的真实性，而是推理的有效性，前提的实际真值不作为确定推理有效性的依据。但是，如果前提全为真，则有效结论也应该为真。
  • 有效的推理不一定产生真实的结论；而产生真实结论的推理过程未必是有效的。有效的推理中可能包含为“假”的前提，而无效的推理却可能得到为“真”的结论 。 所谓推理有效，指的是它的结论是它前提的合乎逻辑的结果，即结论是从前提出发应用推理规则推出的。亦即，如果它的前提都为真，那么所得的结论也必然为真，而并不是要求前提或结论一定为真或为假，如果推理是有效的话，那么不可能它的前提都为真时，而它的结论为假。
  • 判定定理公式H是前提集合Г={G1, G2, …,Gn}的逻辑结果当且仅当G1∧G2∧…∧Gn→H为永真公式
  • 演绎法是从前提(假设)出发，依据公认的推理规则和推理定律，推导出一个结论来。
• 谓词
  • 设D为非空的个体域，定义在Dn(表示n个个体都在个体域D上取值)上取值于{0, 1}上的n元函数，称为n元命题函数或n元谓词(Propositional Function)，记为P(x1, x2, …, xn)。此时，个体变量x1, x2, …, xn的定义域都为D，P(x1, x2, …, xn)的值域为{0, 1｝。
  • 具体命题的谓词表示形式和n元命题函数(n元谓词)是不同的，前者是有真值的，而后者不是命题，它的真值是不确定的。如上例中S(a)是有真值的，但S(x)却没有真值； 一个n元谓词不是一个命题，但将n元谓词中的个体变元都用个体域中具体的个体取代后，就成为一个命题。而且，个体变元在不同的个体域中取不同的值对是否成为命题及命题的真值有很大的影响。
  • 确定量词辖域的方法： （1）若量词后有括号，则括号内的子公式就是该量词的辖域； （2）若量词后无括号，则与该量词紧邻的最短子公式为该量词的辖域。
  • 为了使得我们的研究更方便，而不致引起混淆，同时为了使其式子给大家以一目了然的结果，对于表示不同意思的个体变元，我们总是以不同的变元符号来表示之。
  • 定义5.3.5 设G是任意一个公式，若G中无自由变元，则称G为封闭的合适公式，简称闭式。
  • 定义5.3.8 如果公式GH是有效公式，则公式G，H称为等价的(Equivalent)，记为G = H。 定义5.3.9 设G(P1,P2,…,Pn)是命题演算中的命题公式，P1,P2,…,Pn是G中的命题变元，当用任意的谓词公式Gi (1≤i≤n) 分别代入Pi后，得到的新谓词公式Ｇ(G1,G2,…,Gn)称为原公式的代入实例。
  • 在命题逻辑里，每一公式都有与之等值的范式，范式是一种统一的表达形式，当研究一个公式的特点(如永真、永假)时，范式起着重要作用。 对谓词逻辑的公式来说，也有范式，其中前束范式与原公式是等值的，而其它范式与原公式只有较弱的关系。
  • 定义5.4.1 称公式G是一个前束范式，如果G中的一切量词都位于该公式的最前端(不含否定词)且这些量词的辖域都延伸到公式的末端。 其标准形式如下： (Q1x1)(Q2x2)…(Qnxn)M(x1, x2, …, xn) 其中Qi为量词或 (i=1, 2,…, n)，M称作公式G的母式(基式)，M中不含有量词。
  • 定义5.4.1 称公式G是一个前束范式，如果G中的一切量词都位于该公式的最前端(不含否定词)且这些量词的辖域都延伸到公式的末端。
• 谓词公式
  • 满足下列条件的表达式，称为合式公式(Well-Formed Formulae/Wff)，简称公式(Formulae)。 (1) 原子公式是合式公式； (2) 若G, H是合式公式，则(┐G)、(┐H)、(G∨H)、(G∧H)、(G→H)、(G∨H)也是合式公式； (3) 若G是合式公式，x是个体变量，则(┐x)G、(┐x)G 也是合式公式； (4) 仅仅由(1)-(3)产生的表达式才是合式公式。
  • 在命题逻辑里，每一公式都有与之等值的范式，范式是一种统一的表达形式，当研究一个公式的特点(如永真、永假)时，范式起着重要作用。 对谓词逻辑的公式来说，也有范式，其中前束范式与原公式是等值的，而其它范式与原公式只有较弱的关系。
• 谓词逻辑的演绎与推理规律
  • ES（存在特指规则， Existential SPecify ）(彐x)G(x) ⇒ G(c) 其中c为使G(c)为真的特定个体常量；若G(x)中还有除x以外的自由变量时，则必须用这些变量的函数符号来取代。
  • 推导过程中可以引用命题演算中的规则P 和规则T 如果结论是以蕴涵形式(或析取形式)给出，还可以使用规则CP 若需消去量词，可以引用规则US和规则ES 当所要求的结论可能被定量时，此时可引用规则UG和规则EG将其量词加入
• 命题
  • 命题逻辑也称命题演算，或语句逻辑。
  • 特征：把一个命题只分析到其中所含的命题成份为止，不再分析下去。 不把一个简单命题再分析为非命题的集合，不把谓词和量词等非命题成份分析出来。
  • 命题 定义 具有确切真值的陈述句称为命题,该命题可以取一个“值”，称为真值。 注意：一切没有判断内容的句子，如命令句、感叹句、疑问句、祈使句、二义性的陈述句等都不能作为命题。
• 命题联结词
  • 设P是任一命题，复合命题“非P”(或“P的否定”)称为P的否定式(Negation)，记作P，┐称为否定联结词。
  • 合取连接词
    • 定义 设P、Q是任两个命题，复合命题“P并且Q”(或“P和Q”)称为P与Q的合取式(Conjunction)，记作P∧Q，“∧”为合取联结词。
  • 析取连接词
    • 定义 设P、Q是任两个命题，复合命题“P或者Q”称为P与Q的析取式(Disjunction)，记作P∨Q，“∨”为析取联结词。
  • 蕴含连接词
    • 定义 设P、Q是任两个命题，复合命题“如果P，则Q”称为P与Q的蕴涵式(Implication)，记作P→Q，“→”称为蕴涵联结词，P称为蕴涵式的前件，Q称为蕴涵式的后件。
  • 等价连接词
    • 定义 设P、Q是任两个命题，复合命题“P当且仅当Q”称为P与Q的等价式(Enuivalence)，记作P↔Q，“↔”称为等价联结词
• 命题公式
  • 定义4.3.1 一个特定的命题是一个常值命题，它的真值不是“真”（“1”），就是“假”（“0”）。 一个任意的、没有赋予具体内容的原子命题是一个变量命题，常称它为命题变量(或命题变元)，该命题变量无具体的真值，它的变域是集合{T, F}（或{0, 1}）。 原子命题在不确定时称为命题变元，即命题变元可以表示任意命题，因此不能确定它的真值。
  • 注意：这仅仅是一种为了书写简单的约定，把程序输入计算机时，括号是不可随意省略的
  • 公式G称为永真公式(重言式)，如果在它的所有解释之下都为“真”。 公式G称为永假公式(矛盾式),如果在它的所有解释之下都为“假”。 公式G称为可满足的，如果它不是永假的。
  • 结论：永真公式G的否定G是矛盾式；矛盾式G的否定G是永真公式。 永真公式一定是可满足公式,可满足公式不一定是永真公式 可满足公式的否定不一定为不可满足公式(即为矛盾式)
  • 定义4.3.6 设G、H是公式，如果在任意解释I下，G与H的真值相同，则称公式G、H是等价的，记作G＝H。
  • 定理4.3.1 公式G、H等价的充分必要条件是公式GH是永真公式。
  • “=”的性质： 由于“=”不是一个联结词，而是一种关系，为此，这种关系具有如下三个性质：（1）自反性 G = G； （2）对称性 若G = H，则H = G； （3）传递性 若G = H，H = S，则G = S。 这三条性质体现了“=”的实质含义。
  • 替换定理： 设G1是公式G的子公式（即G1是公式G的一部分且为公式），H1是任意的公式，在G中凡出现G1处都以H1替换后得到新的公式H，若G1＝H1，则G＝H。
  • 当原子命题是命题变元时，此复合命题也即为命题变元的“函数”，且该“函数”的值仍为“真”或“假”值，这样的函数可形象地称为“真值函数”,或称为命题公式，此命题公式没有确切真值。
• 析取范式和合取范式
  • 范式的求解方法
    • 定理3.5.1 对于任意命题公式，都存在与其等价的析取范式和合取范式。
  • 定理： （1）公式G为永真式当且仅当G的合取范式中每个子句至少包含一个命题变元及其否定； （2）公式G为永假式当且仅当G的析取范式中每个短语至少包含一个命题变元及其否定；
  • 定义3.5.4 在给定的析取范式中，每一个短语都是极小项，则称该范式为主析取范式。 在给定的合取范式中，每一个子句都是极大项，则称该范式为主合取范式。 如果一个主析取范式不包含任何极小项，则称该主析取范式为“空”；如果一个主合取范式不包含任何极大项，则称主合取范式为“空”。
  • 命题公式是永真公式当且仅当它的主析取范式包含所有的极小项，此时主合取范式为“空”。 命题公式是永假公式当且仅当它的主合取范式包含所有的极大项，此时主析取范式为“空”。 两个命题公式是相等的当且仅当它们对应的主析取范式之间相等，或者(可兼或)它们对应的主合取范式之间相等。
  • 真值表技术
    • 列出公式对应的真值表，选出公式的真值结果为真的所有的行，在这样的每一行中，找到其每一个解释所对应的极小项，将这些极小项进行析取即可得到相应的主析取范式。 列出公式对应的真值表，选出公式的真值结果为假的所有的行，在这样的每一行中，找到其每一个解释所对应的极大项，将这些极大项进行合取即可得到相应的主合取范式。