• 数理逻辑基础

    数理逻辑基础第一章 命题演算1.1 命题与命题联结词1.1.1 命题1.1.2 命题联结词1.2 公式的解释与真值表1.2.1 命题公式1.2.2 公式的解释与真值表1.2.3 一些特殊的公式1. 重言式2. 恒等式3. 永真蕴涵式4. 恒等式和永真蕴涵式的两个性质1.2.4 代入规则和替换规则1.2.5 对偶原理1.3 联结词的完备集1.3.1 联结词的扩充1.3.2 与非、或非、异或的性质1.3.3 全功能联结词1.4 范式1.4.1 范式1.4.2 主析取范式和主合取范式1. 极小项和极大项的性质2. 主析取范式和主合取范式的存在性和唯一性3. 主析取范式和主合取范式之间的转换4. 主析取范式和主合取范式的性质5. 主范式的应用1.5 命题演算的推理理论1.5.1 推理的基本概念和推理形式1.5.2 判断结论有效的方法1. 真值表法2. 等值演算法3.主析取范式法1.5.3 构造证明法1. 推理规则2. 推理定理3. 附加前提证明法(CP 规则)4. 反证法(归谬法)1.6 命题演算的形式系统1.6.1 形式系统的基本概念1.6.2 命题演算公式集1.6.3 命题演算公式的唯一读法及命题演算公式集的代数结构命题演算公式的唯一读法命题演算公式集的代数结构1.6.4 命题演算 1.6.5 演绎定理、反证律与归谬律演绎定理反证律与归谬律1.6.6 命题演算的语义、赋值与语义推论命题演算的语义赋值与语义推论1.6.7 命题演算 的可靠性和完备性1.6.8 析取、合取与等值第二章 谓词演算2.1 谓词演算的基本概念与表示2.1.1 谓词2.1.2 量词2.2 谓词演算公式2.2.1 项与原子公式2.2.2 谓词演算公式集2.3 谓词演算 2.4 谓词演算的语义2.4.1 谓词的语言翻译2.4.2 谓词演算 的解释域与项解释2.4.3 公式的赋值函数2.4.4 闭式的语义特征2.5 谓词公式的判定2.5.1 一些特殊的公式2.5.2 等值式2.6 范式2.6.1 前束范式2.6.2 SKolem 标准形2.7 语义推论与有效式2.8 谓词演算的语义推论(扩展)2.8.1 推理规则2.8.2 推理规则的应用2.9 谓词演算 的可靠性和完全性可靠性完全性2.10 谓词逻辑在计算机科学中的应用2.10.1 谓词逻辑与数据库语言2.10.2 谓词逻辑与逻辑程序设计语言

    第一章 命题演算

    命题演算是最简单、最基本的形式系统,主要用来表示较为简单的逻辑推理的一种数学模型. 其简单性表现为:当它把复合命题分解成简单命题后,就把简单命题视为最小考察对象,不再继续对简单命题进行分解.

    1.1 命题与命题联结词

    1.1.1 命题

    定义1.1 命题

    具有确切真值的陈述句(或断言)称为命题(proposition).

    命题的取值称为真值. 真值只有“真”和“假”两种,分别用 T1)和 F0)表示.

    命题的真值非真即假,只有两种取值,这样的系统称为二值逻辑系统.

    注意:

    • 命题一定是通过陈述句来表达;反之,并非一切的陈述句都是命题.

    • 命题的真值有时可明确给出,有时还需要依靠环境条件、实际情况、时间等才能确定其真值,但其真值一定是唯一确定的.

    命题的类型:

    • 若一个命题已不能分解成更简单的命题,则该命题叫原子命题或本原命题或简单命题(simple proposition);

    • 若一个命题可以分解为简单命题,而且这些简单命题之间是通过关联词和标点符号复合而构成的,则该命题叫复合命题(compound proposition).

    命题通常用大写英文字母(可带下标)来表示.

    1.1.2 命题联结词

    命题通常可以通过一些联结词复合而构成新的命题,这些联结词被称为逻辑联结词. 在命题演算中,这些联结词可以看作运算符,因此也叫作逻辑运算符.

    定义1.2 否定联结词

    P 是任一命题,复合命题”非 P “(或”P 的否定“)称为 P 的否定式(negation),记作 ¬P,”¬“ 称为否定联结词.

    ¬P 为真当且仅当 P 为假.

    定义1.3 合取联结词

    PQ 是任意两个命题,复合命题 ”P 并且 Q “(或“ PQ ”)称为 PQ 的合取式(conjunction),记作 PQ,“” 称为合取联结词.

    PQ 为真当且仅当 PQ 同为真;PQ 为假当且仅当 PQ 二者至少有一为假.

    定义1.4 析取联结词

    PQ 是任意两个命题,复合命题“ PQ ” 称为 PQ 的析取式(disjunction),记作 PQ,“” 称为析取联结词.

    PQ 为真当且仅当 PQ 至少一个为真.

     

    这里的“或”是“相容或”(“可兼或”).

    定义1.5 蕴涵联结词

    PQ 是任意两个命题,复合命题“如果 P 那么 Q ” 称为 PQ 的蕴涵式(implication),记作 PQ,“” 称为蕴涵联结词,P 称为蕴涵式的前提、假设或前件,Q 称为结论或后件.

    PQ 为真当且仅当 P 为真 Q 为假.

     

    蕴涵式 PQ 可以用多种方式陈述:

    • “若 P,则 Q ”;

    • PQ 的充分条件”;

    • QP 的必要条件”;

    • Q 每当 P ”;

    • P 仅当 Q ”.

    给定命题 PQ

    • QP 是其逆命题;

    • ¬P¬Q 是其反命题;

    • ¬Q¬P 是其逆反命题.

    定义1.6 等价联结词

    PQ 是任意两个命题,复合命题“ P 当且仅当 Q ” 称为 PQ 的等价式(equivalence),记作 PQ,“” 称为等价联结词.

    PQ 为真当且仅当 PQ 同为真假.

    image-20230320224229145

    一般约定:

    1.2 公式的解释与真值表

    1.2.1 命题公式

    定义1.7

    一个特定的命题是一个常值命题(constant proposition),它不是具有值“ T ”(“0”)就是具有值“ F ”(“0”);

    一个任意的没有赋予具体内容的原子命题是一个变量命题,常称它为命题变量(命题变元、命题变项)(proposition variable),命题变量无具体的真值,它的值域是集合 {T,F} (或 {1, 0}).

    原子命题在不指派真值时称为命题变元,而复合命题由原子命题和联结词构成,可以看作是命题变元的函数,且该函数的值仍为“真”或“假”,可以称为真值函数(true value function)或命题公式(propositional formula).

    不是原子命题和联结词的任意组合都可以为命题公式. 我们用递归的方法来定义命题公式.

    定义1.8 命题公式(合式公式、形式命题)

    1. 命题变元本身是一个公式;

    2. 如果 P 是公式,则 ¬P 也是公式;

    3. 如果 PQ 是公式,则 PQPQPQPQ 也是公式;

    4. 命题公式是仅由有限步使用规则 1 ~ 3 后产生的结果,公式常用符号 H 等表示.

    注意:

    1.2.2 公式的解释与真值表

    公式本身没有真值,只有在对其所有命题变元指定真值后才变成一个具有真值的命题.

    定义1.9 公式的解释

    P1, P2,, Pn 是出现在公式 中的所有命题变元,指定 P1, P2,, Pn 一组真值,则这组真值称为 的一个解释(explanation)或真值指派,记作 I.

    一般来说,若有 n 个命题变元,则应有 2n 个不同的解释.

    定义1.10 公式的真值表

    公式 在其所有可能的解释下所取真值的表,称作 的真值表(truth).

    1.2.3 一些特殊的公式

    1. 重言式

    定义1.11

    • 公式 称为永真公式(重言式),如果在它的所有解释下都为“真”,记作 G

    • 公式 称为可满足的,如果它不是永假的;

    • 公式 称为永假公式(矛盾式),如果在它的所有解释下都为“假”,有时也称为不可满足公式.

    注意:

    2. 恒等式

    定义1.12

    公式 H,如果在其任意解释下,其真值相同,则称 H 的等价式(equivalent)或称 恒等于 H,记作 GHGH.

    定理1.1

    对于公式 HGH 的充分必要条件是公式 GH 是重言式.

    常用逻辑恒等式:

    3. 永真蕴涵式

    定义1.13

    AB 是一永真式,那么称其为永真蕴涵式,记为 AB,读作“A 永真蕴涵 B”.

    常用永真蕴涵式:

    4. 恒等式和永真蕴涵式的两个性质

    1.2.4 代入规则和替换规则

    定理1.2 代入定理

    G(P1,,Pn) 是一个命题公式,其中 P1,,Pn 是命题变元,G1(P1,,Pn)Gn(P1,,Pn) 为任意的命题公式,此时若 是永真公式或永假公式,则用 G1 取代 P1Gn 取代 Pn 后得到的新命题公式

    G(G1,,Gn)G(P1,,Pn)

    也是一个永真公式或永假公式.

    定理1.3 替换定理

    G1 的子公式,H1 是任意的命题公式,在 中凡出现 G1 处都以 H1 替换后得到新的命题公式 H. 若 G1H1,则 GH.

    1.2.5 对偶原理

    定义1.4 对偶公式

    设公式 A 中仅有联结词 ¬. 在 A 中将 TF 分别换以 FT 得到公式 A,则 A 称为 A 的对偶公式,AA 互为对偶.

    定理1.4

    AA 是对偶式,P1,P2,,Pn 是出现于 AA 中所有命题变元,于是

    (1)¬A(P1,P2,,Pn)=A(¬P1,¬P2,,¬Pn).

    定理1.5 对偶原理

    AB,且 AB 为命题变元 P1,P2,,Pn 及联结词 ,,¬ 构成的公式,则 AB.

    定理1.6

    AB,且 AB 为命题变元 P1,P2,,Pn 及联结词 ,,¬ 构成的公式,则 BA.

    1.3 联结词的完备集

    1.3.1 联结词的扩充

    首先考虑一元运算.

    image-20230322100517025

    最多只能定义 4 种运算,但除了否定之外,永假、永真、恒等作为运算意义不大,所以一般不再定义其它一元运算.


    考虑两变元在一个二元运算作用下可能的真值表.

    image-20230322100803009

    image-20230322101230871

    为了叙述方便,引进下面四个联结词.

    image-20230322101311681

    PQ¬(PQ)PQ¬(PQ)PQ¬(PQ)PQ¬(PQ)

    这九个联结词(否定、合取、析取、蕴涵、等价、异或、蕴含否定、与非、或非)构成命题演算中的所有联结词.

    1.3.2 与非、或非、异或的性质

    与非的性质:


    或非的性质:


    异或的性质:

    1.3.3 全功能联结词

    定义1.15

    S 的联结词的集合.

    1. S 中的联结词表示的公式可以等价地表示任何命题公式,则称 S 是一个联结词完备集(或全功能集合)(adequate set of connectives);

    2. S 是一个联结词的完备集,且 S 中无冗余的联结词(即集合中不存在可以被其中的其它联结词所定义的联结词),则称 S 为极小联结词完备集.

    1.4 范式

    1.4.1 范式

    同一个命题有不同的表达形式,这样给命题演算带来了一定的困难. 为了使命题公式规范化,引入范式的概念.

    定义1.16

    • 命题变元或命题变元的否定称为文字;

    • 有限个文字的析取式称为简单析取式(基本和),有限个文字的合取式称为简单合取式(基本积);

    • 由有限个简单合取式构成的析取式称为析取范式(disjunctive normal form),由有限个简单析取式构成的合取式称为合取范式(conjunctive normal form).

    性质:

    定理1.7

    任一命题公式都存在着与之等值的析取范式和合取范式.


    证明:对于任一公式,可用下面的方法构造出与之等值的范式:

    1. 利用等价公式

      AB(AB)(BA), AB¬AB

      使公式中仅含联结词 ¬

    2. 利用德·摩根定律

      ¬(AB)¬A¬B, ¬(AB)¬A¬B

      和双重否定律

      ¬¬A=A

      将否定符 ¬ 移到命题变元前,并去掉多余的否定符;

    3. 利用分配律

      A(BC)(AB)(AC), A(BC)(AB)(AC)

      将公式化成析取范式或合取范式,所得即与原公式等价.

    1.4.2 主析取范式和主合取范式

    范式虽然为命题公式提供了一种统一的表达形式,但这种表达形式却不是唯一的,这种不唯一的表达形式给研究问题带来了不便,因此有必要引进更为标准的范式.

    定义1.17

    • 包含 A 中所有命题变元或其否定一次仅一次的简单合取式称为极小项;

    • 包含 A 中所有命题变元或其否定一次仅一次的简单析取式称为极大项;

    • 由有限个极小项组成的析取范式称为主析取范式;

    • 由有限个极大项组成的合取范式称为主合取范式.

    1. 极小项和极大项的性质

    一般来说,对于 n 个命题变元,应有 2n 个不同的极小项和 2n 个不同的极大项.

    性质:

    2. 主析取范式和主合取范式的存在性和唯一性

    定理1.8

    任何命题公式的主析取范式和主合取范式存在且唯一,即任何命题公式有且仅有一个与之等价的主析取范式和主合取范式.


    image-20230322141502126

    求主析取范式和主合取范式的方法:

    3. 主析取范式和主合取范式之间的转换

    (1) 已知公式 的主析取范式,求公式 的主合取范式:

    即,若

    G=ikmji

    的主析取范式,则

    ¬G=i=12nkmji

    ¬G 的主析取范式,其中 mji(i=1,2,,2nk)mi (i=0,1,,2n1) 中去掉 mji (i=1,,k) 后剩下的极小项,则