命题演算是最简单、最基本的形式系统,主要用来表示较为简单的逻辑推理的一种数学模型. 其简单性表现为:当它把复合命题分解成简单命题后,就把简单命题视为最小考察对象,不再继续对简单命题进行分解.
定义1.1 命题
具有确切真值的陈述句(或断言)称为命题(proposition).
命题的取值称为真值. 真值只有“真”和“假”两种,分别用
( )和 ( )表示. 命题的真值非真即假,只有两种取值,这样的系统称为二值逻辑系统.
注意:
命题一定是通过陈述句来表达;反之,并非一切的陈述句都是命题.
命题的真值有时可明确给出,有时还需要依靠环境条件、实际情况、时间等才能确定其真值,但其真值一定是唯一确定的.
命题的类型:
若一个命题已不能分解成更简单的命题,则该命题叫原子命题或本原命题或简单命题(simple proposition);
若一个命题可以分解为简单命题,而且这些简单命题之间是通过关联词和标点符号复合而构成的,则该命题叫复合命题(compound proposition).
命题通常用大写英文字母(可带下标)来表示.
命题通常可以通过一些联结词复合而构成新的命题,这些联结词被称为逻辑联结词. 在命题演算中,这些联结词可以看作运算符,因此也叫作逻辑运算符.
定义1.2 否定联结词
设
是任一命题,复合命题”非 “(或” 的否定“)称为 的否定式(negation),记作 ,” “ 称为否定联结词.
为真当且仅当 为假.
定义1.3 合取联结词
设
、 是任意两个命题,复合命题 ” 并且 “(或“ 与 ”)称为 与 的合取式(conjunction),记作 ,“ ” 称为合取联结词.
为真当且仅当 , 同为真; 为假当且仅当 与 二者至少有一为假.
定义1.4 析取联结词
设
、 是任意两个命题,复合命题“ 或 ” 称为 与 的析取式(disjunction),记作 ,“ ” 称为析取联结词.
为真当且仅当 , 至少一个为真.
这里的“或”是“相容或”(“可兼或”).
定义1.5 蕴涵联结词
设
、 是任意两个命题,复合命题“如果 那么 ” 称为 与 的蕴涵式(implication),记作 ,“ ” 称为蕴涵联结词, 称为蕴涵式的前提、假设或前件, 称为结论或后件.
为真当且仅当 为真 为假.
蕴涵式
可以用多种方式陈述:
“若
,则 ”; “
是 的充分条件”; “
是 的必要条件”; “
每当 ”; “
仅当 ”.
给定命题
,
是其逆命题;
是其反命题;
是其逆反命题.
定义1.6 等价联结词
设
、 是任意两个命题,复合命题“ 当且仅当 ” 称为 与 的等价式(equivalence),记作 ,“ ” 称为等价联结词.
为真当且仅当 、 同为真假.
一般约定:
运算符(联结词)结合力强弱顺序为
凡符合此顺序的,括号可省略;
相同的运算符,从左到右次序计算时,括号可省去;
最外层括号可省.
定义1.7
一个特定的命题是一个常值命题(constant proposition),它不是具有值“
”(“ ”)就是具有值“ ”(“ ”); 一个任意的没有赋予具体内容的原子命题是一个变量命题,常称它为命题变量(命题变元、命题变项)(proposition variable),命题变量无具体的真值,它的值域是集合
(或 ).
原子命题在不指派真值时称为命题变元,而复合命题由原子命题和联结词构成,可以看作是命题变元的函数,且该函数的值仍为“真”或“假”,可以称为真值函数(true value function)或命题公式(propositional formula).
不是原子命题和联结词的任意组合都可以为命题公式. 我们用递归的方法来定义命题公式.
定义1.8 命题公式(合式公式、形式命题)
命题变元本身是一个公式;
如果
是公式,则 也是公式; 如果
、 是公式,则 、 、 、 也是公式; 命题公式是仅由有限步使用规则 1 ~ 3 后产生的结果,公式常用符号
、 等表示.
注意:
如果
原子命题变元是最简单的公式,也叫原子公式;
合式公式没有真值,只有对其变元进行指派后才有真值;
合式公式无限多.
公式本身没有真值,只有在对其所有命题变元指定真值后才变成一个具有真值的命题.
定义1.9 公式的解释
设
是出现在公式 中的所有命题变元,指定 一组真值,则这组真值称为 的一个解释(explanation)或真值指派,记作 . 一般来说,若有
个命题变元,则应有 个不同的解释.
定义1.10 公式的真值表
公式
在其所有可能的解释下所取真值的表,称作 的真值表(truth).
定义1.11
公式
称为永真公式(重言式),如果在它的所有解释下都为“真”,记作 ; 公式
称为可满足的,如果它不是永假的; 公式
称为永假公式(矛盾式),如果在它的所有解释下都为“假”,有时也称为不可满足公式.
注意:
重言式的否定是矛盾式,矛盾式的否定是重言式,因此只需研究其中一种情形;
重言式的合取、析取、蕴涵、等价等都是重言式;
重言式中有许多非常有用的恒等式和永真蕴涵式;
命题的永真(永假)性是可判定的,其判定方法有真值表法和公式推演法.
定义1.12
公式
、 ,如果在其任意解释下,其真值相同,则称 是 的等价式(equivalent)或称 恒等于 ,记作 或 .
定理1.1
对于公式
、 , 的充分必要条件是公式 是重言式.
常用逻辑恒等式:
E1 双重否定律:
E2
E3
E4
E5
E6
E7
E8
E9
E10、E11 德·摩根定律(De Morgan's Law):
E12、E13 吸收律:
E14 蕴涵等值式:
E15 等价等值式:
E16、E17 零律:
E18、E19 幺律:
E20 排中律:
E21 矛盾律:
E22 等价否定等值式:
E23 归谬律:
E24 逆反律(假言异位):
定义1.13
若
是一永真式,那么称其为永真蕴涵式,记为 ,读作“ 永真蕴涵 ”.
常用永真蕴涵式:
I1 同一律
I2
I3
I4
I5
I6
I7
I8
I9
逻辑恒等(“
若
定理1.2 代入定理
设
是一个命题公式,其中 是命题变元, , , 为任意的命题公式,此时若 是永真公式或永假公式,则用 取代 , 取代 后得到的新命题公式 也是一个永真公式或永假公式.
定理1.3 替换定理
设
是 的子公式, 是任意的命题公式,在 中凡出现 处都以 替换后得到新的命题公式 . 若 ,则 .
定义1.4 对偶公式
设公式
中仅有联结词 , , . 在 中将 , , , 分别换以 , , , 得到公式 ,则 称为 的对偶公式, 与 互为对偶.
定理1.4
设
和 是对偶式, 是出现于 和 中所有命题变元,于是
定理1.5 对偶原理
若
,且 , 为命题变元 及联结词 构成的公式,则 .
定理1.6
若
,且 , 为命题变元 及联结词 构成的公式,则 .
首先考虑一元运算.
最多只能定义 4 种运算,但除了否定之外,永假、永真、恒等作为运算意义不大,所以一般不再定义其它一元运算.
考虑两变元在一个二元运算作用下可能的真值表.
为了叙述方便,引进下面四个联结词.
这九个联结词(否定、合取、析取、蕴涵、等价、异或、蕴含否定、与非、或非)构成命题演算中的所有联结词.
与非的性质:
或非的性质:
异或的性质:
定义1.15
设
的联结词的集合.
用
中的联结词表示的公式可以等价地表示任何命题公式,则称 是一个联结词完备集(或全功能集合)(adequate set of connectives);
是一个联结词的完备集,且 中无冗余的联结词(即集合中不存在可以被其中的其它联结词所定义的联结词),则称 为极小联结词完备集.
实际应用中经常采取的联结词集合为
同一个命题有不同的表达形式,这样给命题演算带来了一定的困难. 为了使命题公式规范化,引入范式的概念.
定义1.16
命题变元或命题变元的否定称为文字;
有限个文字的析取式称为简单析取式(基本和),有限个文字的合取式称为简单合取式(基本积);
由有限个简单合取式构成的析取式称为析取范式(disjunctive normal form),由有限个简单析取式构成的合取式称为合取范式(conjunctive normal form).
性质:
一个文字既是一个析取范式又是一个合取范式;
一个析取范式为矛盾式当且仅当它的每个简单合取式是矛盾式;
一个合取范式为重言式当且仅当它的每个简单析取式是重言式.
定理1.7
任一命题公式都存在着与之等值的析取范式和合取范式.
证明:对于任一公式,可用下面的方法构造出与之等值的范式:
利用等价公式
使公式中仅含联结词
、 、 ; 利用德·摩根定律
和双重否定律
将否定符
移到命题变元前,并去掉多余的否定符; 利用分配律
将公式化成析取范式或合取范式,所得即与原公式等价.
范式虽然为命题公式提供了一种统一的表达形式,但这种表达形式却不是唯一的,这种不唯一的表达形式给研究问题带来了不便,因此有必要引进更为标准的范式.
定义1.17
包含
中所有命题变元或其否定一次仅一次的简单合取式称为极小项; 包含
中所有命题变元或其否定一次仅一次的简单析取式称为极大项; 由有限个极小项组成的析取范式称为主析取范式;
由有限个极大项组成的合取范式称为主合取范式.
一般来说,对于
性质:
没有两个不同的极小项是等价的,且每个极小项只有一组真值指派使得该极小项的真值为真,因此可给极小项编码,使极小项为
没有两个不同的极大项是等价的,且每个极大项只有一组真值指派使得该极大项的真值为假,因此可给极小项编码,使极小项为
极小项 | 极大项 | |||
---|---|---|---|---|
0 | 0 | 0 | ||
0 | 0 | 1 | ||
0 | 1 | 0 | ||
0 | 1 | 1 | ||
1 | 0 | 0 | ||
1 | 0 | 1 | ||
1 | 1 | 0 | ||
1 | 1 | 1 |
任意两极小项的合取必假,任意两极大项的析取必真,
极大项的否定是极小项,极小项的否定是极大项,
所有极小项的析取为永真公式,所有极大项的合取为永假公式,即
定理1.8
任何命题公式的主析取范式和主合取范式存在且唯一,即任何命题公式有且仅有一个与之等价的主析取范式和主合取范式.
求主析取范式和主合取范式的方法:
真值表技术:
公式转换法:
在公式中的命题变元较少时,利用真值表技术更为简单;当命题变元较多时,一般采用公式转换法.
(1) 已知公式
求
即,若
为
为
(2) 已知公式
求
即,若
为
为