数理逻辑

关于数理逻辑的思维导图，分享了 命题逻辑的基本概念、命题逻辑等值演算、命题逻辑的推理理论、一阶逻辑基本概念、一阶逻辑等值演算与推理，欢迎学习。

数理逻辑

• 命题逻辑的基本概念
  • 命题：具有确切真值的陈述句称为命题。真值：作为命题的陈述句所表达的判断结果原子（简单）命题：不能再分解为更简单命题的命题。复合命题：可以分解的命题悖论：既不能为真也不能为假的陈述句称作悖论
  • 联结词¬ ：否定、非∧ 合取、且∨ ：析取、或⊕ ⊕:异或→ ：条件语句、蕴含↔ ：等价联结词
  • 真值表：在命题公式中，对于分量指派真值的各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。n个原子命题，真值表有2 n 2^n2 n 行，每个原子命题都有T or F 两种指派。
  • 命题变量：一个表示确定命题的命题标识符命题变元：表示任一命题的命题标识符。（命题变元不是命题）原子变元：命题变元是原子命题子公式：如果X是合式公式A的一部分，且X本身也是一个合式公式，则称X为公式A的子公式。
    • 命题公式：由命题变量、命题变元、联结词和括号等组成的复合命题形式，这些符号不能任意组合，必须按下列定义： 命题变元本身是一个公式 若P是公式，┐P也是公式 如PQ是公式，则P∧ Q、P∨ Q,P→ Q,P↔ Q也是公式 仅由有限步骤使用规则1-3后产生的结果。
• 命题逻辑等值演算
  • 等值公式
    • 双重否定律幂等律交换律结合律分配律德摩根律吸收律零律同一律排中律矛盾律蕴含等值式等价等值式假言易位等价否定等值式归谬论
  • 文字：命题变项及其否定简单析取式：仅由有限个文字构成的析取式简单合取式：仅由有限个文字构成的合取式析取范式：由有限个简单析取式的合取构成的命题公式合取范式：由有限个简单合取式的析取构成的命题公式小项：n个命题变元的合取式，称为布尔合取或小项，但是每个变元和和他的否定不能同时存在，但两者必须出现且仅出现一次。每个小项当其真值指派与编码相同时，其真值为T，其余情况都是F 两个不同小项的合取永假 全体小项的析取式永真主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价公式称作原式的主析取范式。在真值表中，是真值为1的指派所对应小项的析取。大项：n个命题变元的析取式，称作布尔析取或大项，其中每个变元和她的否定不能同时存在，但两者必须出现且仅出现一次。每个大项当其真值指派与编码相同时，其真值是F，其余均为T任何两个不同大项的析取式永真全体大项的合取式永假主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取组成，则该等价式称为原式的主合取范式。在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。
• 命题逻辑的推理理论
  • 推理定律
    • 附加律化简律假言推理拒取式析取三段论假言三段论等价三段论构造性二难破坏性二难
  • 自然推理系统P
    • 附加前提证明法归谬法（反证法）
• 一阶逻辑基本概念
  • 基本等值式
    • 量词否定等值式量词辖域收缩与扩张等值式量词分配等值式
  • 置换规则
  • 换名规则
  • 前束范式：一个公式，如果量词全在公式开头，它们的作用域延伸到公式末尾，则该公式叫做前束范式。
  • 化为前束范式的方法 消去条件，双条件联结词 ┐内移 变元换名 量词提前
  • 自然推理系统N推理规则全称特指规则（US）：( ∀ x ) P ( x ) → P ( c ) x是P（x）中自由出现的个体变量c是任意的个体变量存在特指规则（ES）：( ∃ x ) P ( x ) → P ( c ) x是P（x）中自由出现的个体变量在P（x）中变元x的每一次自由出现都用相同的个体变量c代入c是使P(x)为真的特定个体变量此c是在推导之前从未使用过的全称推广规则（UG）：P ( y ) → ( ∀ x ) P ( x ) y是P(y)中自由出现的个体变量。且y取遍整个个体域时都有P（y）为真对P(y)中不满足假设前提（使P(y)为真）的自由变元y不能使用该规则添加的量词中的x和取代y的x不能在P(y)中以约束身份出现对于曾经由使用规则ES所得公式中原来的约束变元不能使用该规则存在推广规则（EG）：P ( c ) → ( ∃ x ) P ( x ) c是使P©为真的特定个体变量取代c的x和添加的量词中的x不能在P©中以任何约束出现
• 一阶逻辑等值演算与推理
  • 在句子中可以独立存在的客体称为个体词，而用以刻画客体的属性或者客体之间关系的是谓词。 表示具体或者特定的个体词称为个体常量 表示抽象或者泛指的个体词称为个体变量个体词的取值范围叫做个体域或论域，常用D表示。而宇宙间所有个体域聚集在一起所构成的个体域称为全总个体域简单命题函数：由一个谓词、一些客体变元组成的表达式复合命题函数：由一个或者n个简单命题函数以及逻辑连接词组合而成的表达式命题函数：简单命题函数和复合命题函数的统称命题函数不是命题，只有客体变元取特定的名称时才能成为一个命题。量词：表示个体常项或变项之间数量关系的词。全称量词：∀ ,存在量词：∃
  • 项：任意的常量符号或者任意的变量符号是项。若f(x1,x2,…xn)是n元函数符号，t1,t2…tn是项，则f（t1,…tn）是项原子公式：若P(x1,…xn)是n元谓词，t1…tn是项，则称P(t1…tn)为原子公式合式公式： 原子公式 原子公式的非，析取，合取，条件，双条件 原子公式前加量词以上三种的有限次组合 谓词公式： 原子谓词公式是谓词公式 若A是谓词公式，非A也是谓词公式 若AB是谓词公式，则他们的合取，析取，条件，双条件都是谓词公式 若A是谓词公式，X是A中出现的变元，则（∀ \forall∀x）A与(∃ \exist∃x)A也是谓词公式有限次上述过程得到的 (∀ )F(x)或(∃ )F(x)中，x称为作用变量，F(x)称为量词的辖域 作用域：P（x）叫做相应量词的作用域或辖域 约束变元：在作用域中变元x的出现称为约束出现，此时的变元x称为约束变元 自由变元：若x的出现不是约束出现，则称它为自由出现，此时的变元称为自由变元。 闭式：无自由变元的公式赋值/解释：在谓词公式中客体变元由确定的客体取代，命题变元由确定的命题取代。