命题逻辑(数据库)
时间：2022-11-01 20:30:01 | 来源：信息时代
时间：2022-11-01 20:30:01 来源：信息时代
命题逻辑 : 以命题为研究对象,研究基于命题的符号,逻辑体系及推理规律。命题逻辑是数理逻辑中研究最早也是最成熟的一门学科,对它的研究始于19世纪,而至20世纪初已趋成熟,它是数理逻辑的基础,它的成果广泛应用于计算机及数据库领域中。
1. 命题
命题逻辑的基础是命题。凡能分辨真假的语句称命题。它可用P、Q、R等表示,而其中真假分别可用T、F表示。
2. 原子命题
凡不能进一步分解成更简单的命题称原子命题。
3.命题联结词
命题间可用命题联结词相连,常用的有五个联系词, 它们是:⌝(否定)、 ∧(并且、合取)、 ∨(或者、析取)、→(蕴涵)及↔(等价), 它们可用表1和表2中的真值表示。
表1 命题联结词否定的真值表
表2 命题联结词并且、或者、蕴涵及等价的真值表
| P | Q | P∧Q | P∨Q | P→Q | P↔Q |
T T
F F | T F
T F | T F
F F | T T
T F | T F
T T | T F
F T |
4. 公式
由命题及命题联结词可组成公式,公式组成规则如下:
(1)原子命题是公式。
(2)如P、 Q为公式, 则P、(P∧Q)、(P∨Q)、(P→Q)、(P↔Q)为公式。
(3)公式由且仅由有限次使用(1)、(2)而得。
5. 范式
由于命题逻辑公式结构混乱不易实际使用,因此一般采用具统一结构的范式,它们是:
(1)特异析取范式: 是一种析取式,其每个析取项是一个合取式,在合取式中公式的所有命题变元均出现,它或以命题变元或以其否定形式出现且仅出现一次。
(2)特异合取范式: 是一种合取式,其每个合取项是一个析取式,在析取式中公式的所有命题变元均出现,它或以命题变元或以其否定形式出现且仅出现一次。
6. 重言式
一公式对其所有指派均取值为真则称该公式为重言式。
7.命题演算
命题逻辑的形式系统称命题演算,有关形式系统的介绍可见参考文献[1]。
8. 公理系统
在命题演算中取一些重言式为公理,并规定一些推理规则组成一个公理系统,它可以推出所有的重言式,命题逻辑中常用的推理规则有分离规则:P→Q, P⊦Q, 该规则表示如P→Q, P为重言式必可推出Q为重言式。
9.一个典型的公理系统
命题演算中可以有很多个公理系统,现介绍一个典型的公理系统。
(1)系统的组成部分:
基本符号:①命题: P,Q,R,…;②联结词:, ∧, ∨,→,↔;③括号: (, )。
公式: ①命题是公式; ②如P、Q是公式,则(P)、(P∨Q)、(P∧Q)、(P→Q)、(P↔Q)是公式;③公式由且仅由有限次使用前面的①、②而得。
(2)系统的推理部分:
公理: 如P、Q、R为公式,则有下述的公理:
P→P;
(P→(Q→R))→(Q→(P→R));
(P→Q)→((Q→R)→(P→R));
(P→(P→Q))→(P→Q);
(P↔Q)→(P→Q);
(P↔Q)→(Q→P);
(P→Q)∧(Q→P)→(P↔Q));
P∧Q→Q;
P∧Q→P;
P→(Q→P∧Q);
P→P∨Q;
Q→P∨Q;
(Q→P)→((R→P)→(Q∨R→P));
(P→Q)→(Q→P);
P→P。
推理规则: 分离规则:P→Q, P⊦Q。
证明(过程)与定理:证明(过程)给出了公理系统中定理生成的过程,它是一个公式序列“P
1,P
2,…,P
n”,其中,每个P
i(i=1,2,…,n)必须满足下列条件之一:①P
i是公理;②P
i是由P
k、P
r、(k,r<i)施行分离规则而得; ③P
n＝Q即为定理。
可以证明该公理系统是不矛盾的、完全的,但是是不独立的。
在线咨询
