数理逻辑基础

第一章 命题演算

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

1.1 命题与命题联结词

1.1.1 命题

定义1.1 命题

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

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

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

注意:

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

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

命题的类型:

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

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

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

1.1.2 命题联结词

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

定义1.2 否定联结词

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

¬P 为真当且仅当 为假.

定义1.3 合取联结词

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

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

定义1.4 析取联结词

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

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

 

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

定义1.5 蕴涵联结词

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

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

 

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

  • “若 ,则 Q ”;

  • Q 的充分条件”;

  • Q 的必要条件”;

  • Q 每当 ”;

  • 仅当 Q ”.

给定命题 PQ

  • QP 是其逆命题;

  • ¬P¬Q 是其反命题;

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

定义1.6 等价联结词

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

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

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 也是公式;

  3. 如果 Q 是公式,则 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,读作“ 永真蕴涵 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 对偶公式

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

定理1.4

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

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

定理1.5 对偶原理

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

定理1.6

AB,且 B 为命题变元 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

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

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

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

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

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) 后剩下的极小项,则

G¬(¬G)¬(i=12nkmji)i=12nk¬mjii=12nkMji.

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

即,若

G=ikMji

的主合取范式,则

¬G=i=12nkMji

¬G 的主合取范式,其中 Mji(i=1,2,,2nk)