数理逻辑

这是大学课程《离散数学》其中的一章《数理逻辑》，是我在复习过程中整理出来的其中一章，希望对大家有帮助！数理逻辑，是用数学方法研究逻辑或形式逻辑的学科，属形式逻辑形式上符号化、数学化的逻辑，本质上仍属于知性逻辑的范畴。数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。

高等数学

• 数理逻辑
  • 命题逻辑
    • 命题定义
      • 具有唯一真值的陈述句
    • 命题公式（合式公式）（公式）
      • 公式定义
        • 单个命题常项或变项或复合命题
      • 公式层数
        • 单个命题常项或变项为0层，每加一个符号层数为n+1，n为该符号左右其中层数多者
      • 赋值
        • 真值表
          • 定义：含n（n>=1）个命题变项的命题公式，共有2^n组赋值，将公式按从高到低的顺序写出各层次取值的情况列成表
          • 种类：n个命题变项只能生成2^2^n种真值表不同的命题公式
        • 类型
          • 成真赋值
          • 成假赋值
      • 公式类型
        • 按真值
          • 永真式（重言式）
          • 永假式（矛盾式）
          • 可满足式
        • 按命题数
          • 复合命题
            • 组成：联结词+简单命题
            • 联结词
              • 联结词的功能完全集
                • 独立联结词
                  • 若某一或多个联结词可将联结词集和中的其他联结词的命题公式表示，则称其为独立联结词，否则称为冗余联结词
                • 全功能集
                  • 若任一真值函数都可以用仅含某一联结词集中的联结词的命题公式表示，则称该联结词集为全功能集
                • 极小功能集
                  • 若一个联结词全功能集中不含冗余的联结词，则称他为极小功能集，如{非，合取}，{非，析取}，{与非}，{或非}等。
              • 分类
                • 否定
                  • 非p为真当且仅当p 为假
                • 合取
                  • p合取q为真当且仅当p 与q 同时为真.
                • 析取
                  • p析取q为真当且仅当p 与q 中至少有一个为真
                • 蕴含
                  • p蕴含q为假当且仅当p 为真且q 为假
                • 等价
                  • p等价q为真当且仅当p,q真值相同.
                • 排斥或（异或）
                  • p异或q为真当且仅当p,q中恰有一个为真
                • 与非
                  • p与非q为真当且仅当p,q不同时为真
                • 或非
                  • p或非q为真当且仅当p,q同时为假
          • 简单命题
      • 等值演算
        • 等值定义
          • 设A.B是命题公式，若等价式A<——>B是重言式，则称A<——>B是等值的，记为A<=>B(将AB看作一个命题则为等价，若看作两个命题则为等值)
        • 重要的等值式
        • 置换规则
          • 如果f（A）是含命题公式A的命题公式，f（B）是用命题公式B置换了f（A）中的A之后得到的命题公式。如果A<=>B，则f（A）<=>f（B）
      • 命题公式的范式
        • 简单析取式（简单合取式）
          • 定义
            • 仅有有限个命题变项或其否定构成的析取式（合取式)
          • 性质
            • 一个简单析取式是重言式，当且仅当它的形式为 p析取非p
            • 一个简单合取式是矛盾式，当且仅当它的形式为p合取非p
        • 析取（合取）范式
          • 定义
            • 仅由有限个简单合取式（析取式）构成的析取式（合取式）
          • 性质
            • 任何析取范式的对偶式为合取范式，反之亦然
              • 对偶式
                • 定义
                  • 在仅有联结词非.合取.析取的命题公式A中将合取换成析取，将析取换成合取，将0换成1，将1换成0，所得到的命题公式称为A的对偶式，记作A*。
                • 性质
                  • 对偶式是相互的，即(A*)*=A
                  • 若p1p2为A和A*的全部的命题变项，则 非A(p1p2)<=>A*(非P1非P2)， A(非p1非p2)<=>非A*(P1P2)
                  • 对偶原理：若A<=>B,A*<=>B*
            • 一个析取范式是矛盾式，当且仅当它的每一个合取式是矛盾式; 一个合取范式是重言式，当且仅当它的每一个析取式是重言式
            • 范式存在定理任意命题公式都存在者与之等值的析取（合取）范式，且任何命题公式的析取（合取）范式都不是唯一的
        • 主范式
          • 主析取范式
            • 极小项
              • 定义
                • 在含n个命题变项的简单合取式中，若每个命题变项与其否定不同时存在，而二者之一比出现且仅出现一次，且第i个命题变项或其否定出现在从左起的第i位上（命题变项无角标，则按字典顺序排列），这样的简单合取式成为极小项
              • 性质
                • 若将命题变项看成1，其否定看成0，则每个极小项对应一个二进制数，也对应一个十进制数，而二进制数正是该极小项的成真赋值，十进制数可做该极小项的抽象表示的角码，如：非p合取非q合取r 001 记作m1
                • n个命题变项共可产生2^n个极小项，分别记为m1 m2 m3……
                  • n个命题变项可产生2^2^n种真值表不同的命题公式 其中有2^n个极小项
            • 定义
              • 若命题公式A中的析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式
            • 性质
              • 任何命题公式的主析取范式都是唯一的
            • 求主析取范式
          • 主合取范式
            • 定义
              • 若命题公式A中的合取范式中的简单析取式全是极大项，则称该范式合取为A的主合取范式
            • 极大项
              • 定义
                • 在含n个命题变项的简单析取式中，若每个命题变项与其否定不同时存在，而二者之一比出现且仅出现一次，且第i个命题变项或其否定出现在从左起的第i位上（命题变项无角标，则按字典顺序排列），这样的简单析取式成为极大项
              • 性质
                • 若将命题变项看成0，其否定看成1，则每个极大项对应一个二进制数，也对应一个十进制数，而二进制数正是该极大项的成假赋值，十进制数可做该极大项的抽象表示的角码，如：p析取q析取非r 001 记作m1
                • n个命题变项共可产生2^n个极大项，分别记为m1 m2 m3……
            • 性质
              • 任何命题公式的主析取范式都是唯一的
            • 求主合取范式
              • • 与求主析取范式类似
              • 子主题
    • 推理规则和证明方法
      • 命题逻辑的推理过程
        • 推理的形式结构
          • 若(A1^A2^A3)->B为重言式，则称A1,A2,A3推理结论B正确，记为(A1^A2^A3)=>B,称B为前提A1,A2,A3的逻辑结论或有效结论
        • 构造证明
          • 推理定律（重言蕴含式）
          • 推理规则
          • 构造证明的推理技巧
            • 附加前提的证明法
              • (A1^A2^A3)->(A->B)可转化为(A1^A2^A3^A)->B
            • 归谬法
              • A1^A2^…^Ak是可满足式,则称A1,A2,…,Ak 是相容的;若A1^A2^…^Ak 是矛盾式,则称A1,A2,…,Ak是不相容的.因为A1^A2^…^Ak->B <=>非(A1^A2^…^Ak^非B),所以若A1,A2,…,Ak,非B不相容,则说明B 是公式A1,A2,…,Ak 的逻辑结论.
  • 谓词逻辑
    • 谓词逻辑定义
      • 谓词逻辑就是对简单命题做进一步分析,分析出其中的个体词、谓词、量词等,研究它们的形式结构及逻辑关系,总结出正确的推理形式和规则.命题逻辑中的联结词在谓词逻辑中均可使用.
    • 结构
      • 谓词
        • 简单命题的结构
          • 个体词
            • 定义
              • 个体词是指可以独立存在的客体,它可以是一个具体的事 物,也可以是一个抽象的概念
            • 分类
              • 个体常项
                • 表示具体的 或特定的个体的词称为个体常项,用a,b,c,…表示
              • 个体变项
                • 表示抽象的或者泛指的个体的词称为个 体变项,用x,y,z,…表示
            • 个体域（论域）
              • 个体变项的取值范围称为个体域(或论域),个体域可以是有限事物 的集合;也可以是无限事物的集合.特别地,将宇宙间的一切事物组成的个体域称为全总个体域.
          • 谓词
            • 定义
              • 谓词是用来刻画个体词的性质或个体词之间关系的词.
            • 分类
              • 谓词常项
                • 称表示具体性质或关系的谓词为谓词常项,用 F,G,H,…表示
              • 谓词变项
                • 表示抽象的或泛指的谓词为谓词变量,也用F,G,H,…表示
        • 个体词数量不同的谓词及其性质
          • 元数
            • 在谓词中所包含的个体词数量称为元数
          • 分类
            • n元谓词
              • 含n(n>=1)个个体词的谓词称为n元谓词.一元谓词是表示个体词性质的.n(n>=2)元谓词是表示个体词之间关系的
              • n个个体变项的顺序不能随意改动.
              • 一般来说,谓词 P(x1,x2,…,xn)不是命题,它的真值无法确定,要想使它成为命题,必须指定某一谓词常项代替P,同时还要用n个个体常项代替n 个个体变项
            • 0元谓词
              • 将不带个体变项的谓词称为0元谓词
              • 命题逻辑中简单命题都可以用0元谓词表 示,因而可将命题看成谓词的特殊情况.
      • 量词
        • 分类
          • 全称量词
            • ∀x表示对个体域里的所有个体,∀xF(x)表示个体域里的所有个体都有性质F.
          • 存在量词
            • ∃x表示存在个体域里的个体,∃xF(x)表示个体域中存在具有性质F的个体.
        • 使用的注意事项
          • 1、在不同个体域中,命题符号化的形式可能不一样.
          • 2、若事先没有给出个体域,都应以全总个体域为个体域.
          • 3、在引入特性谓词（限定个体词的个体域）后,使用全称量词与存在量词符号化的形式是不同的
          • 4、个体域和谓词的含义确定之后,n元谓词要转化为命题至少需要n 个量词.
          • 5、（将一阶逻辑中命题公式转化为命题逻辑中的命题公式）当个体域为有限集时,如D={a1,a2,…,an},对任意的谓词A(x)都有∀xA(x)=A(a1)∧A(a2)∧…∧A(an); ∃xA(x)=A(a1)∨A(a2)∨…∨A(an).
          • 7、多个量词同时出现时,不能随意颠倒其顺序,否则可能会改变原命题的含义
    • 谓词逻辑公式
      • 公式定义
        • 项
          • (1)个体常项和个体变项是项; (2)若f(x1,x2,…,xn)是任意n元函数,t1,t2,…,tn 是项,则f(t1,t2, …,tn)是项; (3)只有有限次地使用(1)、(2)生成的符号串才是项.
        • 原子公式
          • 设R(x1,x2,…,xn)是任意的n元谓词,t1,t2,…,tn 是项,则称R(t1,t2,…,tn)为原子公式,其中R 是元语言符号
        • 谓词公式（合式公式）（公式）
          • (1)原子公式是合式公式; (2)若A 是合式公式,则(￢A)是合式公式; (3)若A,B 是合式公式,则(A∧B),(A∨B),(A→B),(A↔B)也是合式公式; (4)若A 是合式公式,则∀xA,∃xA 也是合式公式; (5)只有有限次地应用(1)~(4)构成的符号串才是合式公式,
      • 符号
        • 名称
          • 在合式公式∃xA 和∀xA 中,x 称为指导变项,A 称为相应谓词的辖域.在辖域中,x的所有出现称为约束出现(即指导变项x受相应量词的约束),A 中不受约束出现的其他变项的出现称为自由出现.
          • 设A 为任意公式,若A 中无自由出现的个体变项,则称A 是封闭的合式公式,简称闭式.
        • 换名规则和替换规则
          • 有的个体变项既可以约束出现,又可以自由出现,容易产生混淆，为此采用下面两条规则可以避免混淆
          • 换名规则:将量词辖域中某个约束出现的个体变项及对应的指导变项,改成另一个辖域中未曾出现过的个体变项符号,公式中其余部分不变
          • 代替规则:对某自由出现的个体变项用与原公式中所有个体变项符号不同的变项符号去代替,且处处代替.
      • 解释
        • 含义
          • 一般情况下,一个谓词逻辑合式公式中含有个体常项、个体变项(自由出现或约束出现的)、函数变项、谓词变项等.对各种变项指定特殊的常项去代替,就构成了一个公式的解释
        • 定义
          • 一个解释I由下面4部分组成: (1)非空个体域D; (2)D 中一部分特定元素; (3)D 上一些特定的函数; (4)D 上一些特殊的谓词.
        • 注意
          • 对闭式来说,每个个体变项都受量词约束的,在具体的解释中总表达一个意义确定的语句,一定是一个命题,不真就假.而不是闭式的公式就不一定具有这种性质
      • 公式类型
        • 类型
          • 逻辑有效式或永真公式
          • 矛盾式或永假公式
          • 可满足式
        • 公式类型的判断
          • 代换实例
            • 定义
              • 设A0 是含命题变项p1,p2,…,pn 的命题公式,A1,A2,…,An 是n 个谓词公式,用Ai(1<=i<=n)处处代换pi,所得公式A 称为A0 的代换实例.
            • 性质
              • 命题公式中,重言式的代换实例在谓词公式中仍可称为重言式,这样的重言式都是逻辑有效式.命题公式中的矛盾式的代换实例仍为矛盾式.
          • 实例
      • 等值演算
        • 等值定义
          • 设A,B 是谓词逻辑中任意的两个公式,若 A<——>B 为逻辑有效式,则称 A 与B是等值的,记作A <=>B,称A<=>B 为等值式
        • 重要的等值式
          • 24个等值式
            • 因重言式都是逻辑有效式,故命题逻辑中的24个等值式及其代换实例都是谓词逻辑中的等值式
          • 量词否定等值式
            • 
          • 量词的辖域收缩与扩张等值式
          • 量词分配等值式
            • 
          • 量词交换等值式
            • 
      • 谓词公式的范式
        • 前束范式
          • 概念
            • 
          • 性质
            • 在谓词逻辑中,任何合式公式A 的前束范式都是存在的,并且可用换名规则及代替规则求A 的前束范式,而且前束范式是不唯一的
        • 子主题
    • 谓词演算的推理规则
      • 推理的形式结构
        • 若(A1^A2^A3)->B为逻辑有效式，则称A1,A2,A3推理结论B正确，记为(A1^A2^A3)=>B,称B为前提A1,A2,A3的逻辑结论或有效结论
      • 推理定律
        • 
        • 
      • 推理规则
        • 规则
          • 全称量词消去规则(简称 UI规则)：规则有两种形式: ∀xA(x)=>A(y); ∀xA(x)=>A(c). 在推理过程中根据需要选用,其成立的条件是: (1)x是A(x)中自由出现的个体变项; (2)y为任意的不在A(x)中约束出现的个体变项; (3)c为任意的个体变项.
          • 全称量词引入规则(简称 UG规则)： A(y)∀=>xA(x). 其成立的条件是: (1)y在A(y)中自由出现,且y取任何值时A 均为真; (2)取代y的x 不能在A(y)中约束出现,否则也会产生错误
          • 存在量词引入规则(简称 EG规则)： A(c)=>∃xA(x). 其成立的条件是: (1)c是特定的个体常项; (2)取代c的x 不能在A(c)中出现过.
          • 存在量词消去规则(简称 EI规则)： ∃xA(x)=>A(c). 其成立的条件是: (1)c是使A 为真的特定的个体常项; (2)A(x)中除x外还有其他自由出现的个体变项时,不能用此规则.
        • 注意
          • 所在前提中,若既有存在量词公式,又有全称量词公式,应先引入存在量词公式
          • 为了存在量词开始的条件或者结论可以在后续证明中使用(主要是假言推理中可以直接用到),我们不是将存在量词消去,而是从对应的假言推理的前件在合适的条件下增加存在量词,这样不用消去存在量词,但是应用时却达到了存在量词消去的效果。具体如下: A(x)->B=>∃xA(x)->B, x不在B 和已知中自由出现.