离散数学第1章命题逻辑

1、An Introduction to Database Systenm 重庆文理学院计算机学院重庆文理学院计算机学院离散数学离散数学20102010年年9 9月月An Introduction to Database Systenm离散数学离散数学第一篇第一篇 数理逻辑数理逻辑An Introduction to Database Systenm 数理逻辑数理逻辑n逻辑学是一门研究人的思维形式和规律的学科。 n逻辑学可分为形式逻辑、辩证逻辑和数理逻辑三大类。 n数理逻辑是数学的一个分支，它用数学的方法研究推理的过程。推理是从一种判断推出另一种判断的思维过程。 An Introduction t

2、o Database Systenm 数理逻辑数理逻辑n数学方法：n采用一套符号、公式表示体系，使用已有的数学成果和方法，尤其是形式化的公理方法，对具体事物进行抽象的形式化研究。n数理逻辑的优点：表达简洁、推理方便、概括性好、易于分析。 An Introduction to Database Systenm离散数学离散数学第一章第一章 命题逻辑命题逻辑An Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式与对偶式1.5 其他连接词与最小连接词组1.6 范式

3、1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm1.1 命题与连接词命题与连接词 1.1.1 命题的概念 1.1.2 逻辑连接词 An Introduction to Database Systenm1.1.1 命题的概念命题的概念 定义定义1.1.1 命题是具有真假意义的陈述句。 命题总是具有一个“值”，称为真值。真值只有“真”和“假”两种，“真”用符号T或1表示，“假”用符号F或0表示。 只有能够确定或能够分辨其真假的陈述句才能称为命题。一切没有判断内容的句子、无所谓是非的句子，如感叹句、疑问句、祈使句等不是命题。An Introd

4、uction to Database Systenm1.1.1 命题的概念命题的概念n例1.1.1 判断下列各语句是否为命题。n(1). 神州七号的成功发射是中国航天业的又一个壮举。n(2). 地震是地球各大板块相互挤压造成的。n(3). 北京举办了2008年奥林匹克运动会。n(4). 游客止步！n(5). 明天是否要下雨？n(6). 校园的景色真美！n(7). 如果功课不多，那么放学后我去打篮球。n(8). 我选修数学专业，或者我选修英语专业。n(9). xy5。An Introduction to Database Systenm1.1.1 命题的概念命题的概念 有两点需要注意： 命题是可

5、分辨真假的陈述句，但不一定必须知道它的真假。 悖论的陈述句不是命题，因为悖论往往产生自相矛盾的结论。An Introduction to Database SystenmAn Introduction to Database Systenm1.1.1 命题的概念命题的概念 命题分为原子命题和复合命题两种类型。复合命题是由原子命题和连接词复合而成。判断一个命题是否为复合命题，其关键是连接词是否出现。若出现，则是复合命题；若不出现，则是原子命题。 一个原子命题通常用大写字母或带下标的大写字母表示，如P，Q，或Pi ，Qi ，。表示原子命题的符号称为命题标识符。一个命题标识符如果表示确定的命题，称为

6、命题常量。如果命题标识符只表示命题的位置标志，称为命题变元。命题变元不能确定真值，只有当命题变元用一个特定命题取代时，命题变元才有真值。 例如：用P和Q分别表示原子命题“我是中国人”和“我为中国的进步感到骄傲”，那么复合命题“我是中国人而且我为中国的进步感到骄傲”，则可表示为“P而且Q”。自然语言中“而且”这样的连接词是可用逻辑符号表示的。 An Introduction to Database Systenm1.1 命题与连接词命题与连接词 1.1.1 命题的概念 1.1.2 逻辑连接词 An Introduction to Database Systenm1.1.2 逻辑连接词逻辑连接词

7、自然语言中，常使用“或”、“与”、“如果，那么”等一些连接词。连接词是复合命题的重要组成部分，为了便于书写和推理，必须对连接词作出明确规定和符号化。 下面介绍常用的五种连接词： 1. 否定 2. 合取 3. 析取 4. 条件 5. 双条件 An Introduction to Database Systenm1. 否定否定 定义定义1.1.2 设P是一个命题，P的否定是一个新的命题，记作P，读作“非P ”。连接词“”表示命题的否定。 若P为T，则P为F；若P为F，则P为T。命题P与其否定P的关系如表1.1.1所示。 表 1.1.1 连接词“”的真值表 连接词“” 表示自然语言中“非”、“不”、

8、“没有”的逻辑抽象。 An Introduction to Database Systenm2. 合取合取 定义定义1.1.3 设P和Q是两个命题，由连接词将P、Q联接成复合命题，记作PQ ，读作“P和Q的合取 ”，或“P合取Q ”。 当且仅当P、Q同时为T 时， PQ为T。在其它情况下，PQ的真值为F。连接词的真值如表1.1.2所示。表 1.1.2 连接词“”的真值表 连接词“” 表示自然语言中“而且”、“并且”、“既，又”等的逻辑抽象。An Introduction to Database Systenm3. 析取析取 定义定义1.1.4 设P 和Q是两个命题，由连接词将P、Q 联接成复合

9、命题，记作PQ ，读作“P 和Q的析取 ”，或“P 析取Q ”。 当且仅当P、Q同时为F 时， PQ为F。在其它情况下，PQ的真值为T。连接词的真值如表1.1.3所示。表 1.1.3 连接词“”的真值表 连接词“” 表示自然语言中“或”、“或者”等逻辑抽象。 在自然语言中的“或”是多义的，可表示“排斥或”，也可表示“可兼或”。析取连接词表示的是“可兼或”。An Introduction to Database Systenm3. 析取析取n“排斥或”也是一种连接词，用 表示。连接词的真值如表1.1.4所示。 QPAn Introduction to Database Systenm4. 条件条

10、件 定义定义1.1.5 设P 和Q是两个命题，由连接词将P、Q 联接成复合命题，记作P Q ，读作“如果P，那么Q ”，或“若P 则Q ”。在P Q 中，P 称为前件，Q 称为后件。 当且仅当P 的真值为T，Q 的真值为F 时， P Q 的真值为F，否则P Q 的真值为T。连接词的真值如表1.1.5所示。 表 1.1.5 连接词“”的真值表 An Introduction to Database Systenm4. 条件条件n在自然语言中，“如果，则”常常表示一种因果关系，否则无意义。但对数理逻辑中的条件命题PQ来说，只要P、Q能够分别确定真值， PQ即成为命题。n在自然语言中，“如果”为假时

11、，则往往无法判断“如果，则”的真假。但在数理逻辑的条件命题中，该情况规定为“善意的推定”，即当前提为F时，结论不论真假，条件命题的真值都为T。 An Introduction to Database Systenm5. 双条件双条件 定义定义1.1.6 设P 和Q是两个命题，由连接词将P、Q联接成复合命题，记作PQ ，读作“P当且仅当Q ”。 当且仅当P、Q的真值相同时，PQ为T，在其它情况下，PQ 的真值为F。连接词的真值如表1.1.6所示。表 1.1.6 连接词“”的真值表 双条件运算符“” 表示自然语言中的“充分必要条件”、“当且仅当”等逻辑抽象。An Introduction to D

12、atabase Systenm逻辑连接词小结逻辑连接词小结 从上述对五个基本联接词的介绍，可得到以下几个结论：n复合命题的真值只取决于构成它们的各原子命题的真值，而与它们的内容、意义无关，并且与连接词所连接的两个原子命题之间是否有关系无关。 n, 和具有可交换性，而, 不具有交换性。n连接词具有操作或运算的意义。n五个连接词的优先次序依次为五个连接词的优先次序依次为 ，, ， ， An Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式1.5 其他连接词与最

13、小连接词组1.6 范式1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm 1.2 命题公式及命题公式的翻译命题公式及命题公式的翻译 1.2.1 命题公式 1.2.2 命题的翻译 1.2.3 命题公式的解释 An Introduction to Database Systenm 1.2.1 命题公式命题公式 命题公式（也称合式公式）的构成必须遵循一定的规则，下面用归纳法定义合式公式。 定义1.2.1 合式公式是由下列规则形成的字符串： 原子命题变元是一个合式公式。 若A是合式公式，则(A) 是合式公式。 若A和B是合式公式，则(AB)、(A

14、B)、(AB)和(AB)都是合式公式。 经过有限次地使用、所得到的结果，都是合式公式。 以上定义中， 称为基础，、 称为归纳， 称为界限或结论。 以下几点需要注意：（1）命题公式是没有真值的，只有对其变元进行真值指派后，才具有真值；（2）命题公式无限多。 An Introduction to Database Systenm 1.2 命题公式及命题公式的翻译命题公式及命题公式的翻译 1.2.1 命题公式 1.2.2 命题的翻译 1.2.3 命题公式的解释 An Introduction to Database Systenm 1.2.2 命题的翻译命题的翻译 命题的翻译在数理逻辑中很重要，进行

15、逻辑推理的第一步就是将自然语言中表述的命题翻译成命题公式，然后再进行推理求解或证明。 定义定义1.2.2 把一个文字叙述的命题相应地写成由命题标识符、连接词和圆括号表示的合式公式，称为命题的翻译，或命题的符号化。 命题符号化的步骤如下： （1）确定给定的句子是否为命题。若是命题，分解出原子命题，分别用不同的符号表示不同的原子命题。 （2）判断句子的连接词是否为命题连接词。若是，分解出连接词，将其用相应逻辑连接词符号表示。 （3）将表示各原子命题的符号、连接词符号以及圆括号形成符号串，正确地表示命题。An Introduction to Database Systenm1.2 命题公式及命题公式

16、的翻译命题公式及命题公式的翻译 1.2.1 命题公式 1.2.2 命题的翻译 1.2.3 命题公式的解释 An Introduction to Database Systenm1.2.3 命题公式的翻译命题公式的翻译 定义1.2.3 对于命题公式A中的每个命题变元Pi ，任给一个指派S(Pi)或解释I(Pi)，得到一种真值的组合S(P1), S(P2), , S(Pn)或I(P1), I(P2), , I(Pn)，称为A的一个真值指派，或称为A的一种解释，记为S(A)或I(A)。 例1.2.7 设公式A为(PQ)R，若将P、Q、R分别用(0, 0, 0)替换，得到公式A的一种解释，在这种解释下

17、，A的真值为假。同理还可用(0, 0, 1)、(0, 1, 0)、(0, 1, 1)、(1, 0, 0)、(1, 0, 1)、(1, 1, 0)、(1, 1, 1)其它7种不同的指派来对公式进行解释。 由于公式中有P、Q、R三个不同的命题变元，每个命题变元只有0或1两种方式的替换，因此公式A的不同指派有238种。 An Introduction to Database Systenm1.2.3 命题公式的翻译命题公式的翻译 定理定理1.2.1 若公式A中有n个不同的命题变元，则公式A具有2n种不同的真值指派。 定义定义1.2.4 设A为一命题公式，对其中出现的命题变元做所有可能的真值指派S，连

18、同在其解释下A的取真值情况S(A)组成一个表，称为A的真值表。 为了真值表的书写规范和方便，规定如下： （1）命题变元按英文字母字典序进行排列，如A, B, C, ；带有下标的命题变元，则按下标由小到大的数序排列，如P1, P2, 。 （2）对公式的每种解释，以二进制从小到大或从大到小的顺序列出。 （3）若公式较为复杂，遵循从简单到复杂，由括号里面到外面的原则。An Introduction to Database Systenm计算机题目计算机题目n1、已知命题p和q的真值，求它们的合取、析取、条件和双条件语句的真值。n2、已知长度为n的两个位串，求他们按位的AND、OR和XORn*3、给定

19、m、n，交互玩曲奇饼游戏。An Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式与对偶式1.5 其他连接词与最小连接词组1.6 范式1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm等价公式及公式的分类等价公式及公式的分类 有上一节例1.2.11可知，存在一些形式不相同的公式但它们的真值表是相同的，即一个真值表可表示多种形式不同的公式。若两个公式的真值表完全相同，则这两个公式等价。 本节主要学习等价公

20、式的定义和性质、基本等价公式、置换规则及公式的分类等内容。An Introduction to Database Systenm1.3 等价公式及公式的分类等价公式及公式的分类 1.3.1 等价公式的定义和性质 1.3.2 基本等价公式 1.3.3 置换规则 1.4.3 公式的分类An Introduction to Database Systenm1.3.1 等价公式的定义和性质等价公式的定义和性质 定义定义1.3.1 设A和B是两个公式，设P1, P2, , Pn为所有出现于A和B中的原子变元，若给P1, P2, , Pn任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等，记

21、为AB。 例1.3.1 证明P Q (P Q )(P Q ) 表1.3.1 P Q (P Q )(P Q ) PQ与(PQ )(PQ)的真值表相同，所以得证两命题等价。An Introduction to Database Systenm1.3.1 等价公式的定义和性质等价公式的定义和性质 等价式具有如下性质： （1）自反性：对任意公式A，都有AA。 （2）对称性：对任意公式A和B，若AB ，则BA 。 （3）传递性：对任意公式A，B和C，若AB且BC ， 则AC 。 注意不要将符号“”和符号“”混淆。 “”是一个逻辑连接词，表示当且仅当的逻辑含义。“”不是逻辑连接词，它表示两个公式之间的一种

22、等价关系。 “”可连接任意两个公式A、B，即A B，表示A当且仅当B。但任意两个公式之间不一定具有等价关系。An Introduction to Database Systenm1.3 等价公式及公式的分类等价公式及公式的分类 1.3.1 等价公式的定义和性质 1.3.2 基本等价公式 1.3.3 置换规则 1.4.3 公式的分类An Introduction to Database Systenm1.3.2 基本等价公式基本等价公式 下表列出了一些基本的等价式，利用这些基本的等价式可进行复杂公式的证明和推理。它们可由真值表予以验证。 AA )()(CBACBA)()(CBACBA)()(CB

23、ACBAABBAABBA)()()(CABACBA)()()(CABACBAABAA)(ABAA)(BABA)(BABA)(AFAATATTAFFATPPFPPBABAABBAAn Introduction to Database Systenm分配律分配律n在抽象代数中，分配律是二元运算的一个性质，它是基本代数中的分配律的推广。例如：n2 (1 + 3) = (21) + (23). n由于以上的等式对于任何实数都是成立的，我们称实数的乘法对实数的加法满足分配律。An Introduction to Database Systenm1.3 等价公式及公式的分类等价公式及公式的分类 1.3.1

24、 等价公式的定义和性质 1.3.2 基本等价公式 1.3.3 置换规则 1.4.3 公式的分类An Introduction to Database Systenm1.3.3 置换规则置换规则 定义定义1.3.2 若X是公式A的一部分，且X本身也是一个公式，则称X为公式A的子公式。 例1.3.3 若公式A为Q(PR)，则Q、P、R、 PR均为公式A的子公式，而Q、P、R均不为公式A的子公式。 定理定理1.3.1 设X是合式公式A的子公式，若X Y ，如果将A中的X用Y来置换，所得到的公式B与公式A等价，即AB。 证明：因为X Y ，所以在相同变元的任一种指派下，X与Y真值相同。以Y取代X后，公

25、式B与公式A在相应的指派情况下，其真值必相同，故A B 。 An Introduction to Database Systenm1.3 等价公式及公式的分类等价公式及公式的分类 1.3.1 等价公式的定义和性质 1.3.2 基本等价公式 1.3.3 置换规则 1.3.4 公式的分类An Introduction to Database Systenm1. 3. 4 公式的分类公式的分类 定义定义1.3.3 设A是一个公式，对A做所有可能的解释I，对于这些解释I： （1）若所有I(A)皆为真，则A为永真式或重言式。 （2）若所有I(A)皆为假，则A为永假式。 （3）若至少存在一个I(A)为真，

26、则A为可满足式。 由定义1.3.3可知，永真式一定是可满足式，但可满足式不一定是永真式。永假式一定是不可满足式，非永假式一定是可满足式。 利用等价推导可判断公式A的类型，规则如下： （1）若A T，则是永真式。 （2）若A F，则是永假式。 （3）若A B，B是可满足式，则A是可满足式，反之亦然。An Introduction to Database Systenm1.3.4 公式的分类公式的分类 定理定理1.3.2 任何两个永真式的合取或析取，仍是一个永真式。 证明：设和为两个永真式，则不论对A、B作何真值指派，总有A为T，B为T，因此(AB)T，(AB)T 。 定理定理1.3.3 一个永真

27、式A ，在任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍为永真式。 本定理称为代入规则。 证明：公式是A永真式，不论R做何种真值指派，A的真值永远是T。因此，用一个命题公式代入到原子变元R出现的每一处后，所得的命题公式的真值仍为真。 An Introduction to Database Systenm1.3.4 公式的分类公式的分类n 从上述定理可看出代入和置换的三点区别：n （1）代入规则只能对永真式适用，置换规则可对任何公式适用。n （2）代入是对原子命题而言，置换可对命题公式实行。n （3）代入必须是处处代入，置换则可部分置换，也可全部置换。n 定理定理1.3.4

28、设A、B是公式，则AB等价于AB是永真式。n 证明：若AB ，则A、B具有相同的真值，即AB为永真式。n 若AB为永真式，则A、B具有相同的真值，即AB。 An Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式与对偶式1.5 其他连接词与最小连接词组1.6 范式1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm1.4 蕴含式与对偶式蕴含式与对偶式 1.4.1 蕴含式 1.4.2 对偶式An Intro

29、duction to Database Systenm1.4 蕴含式与对偶式蕴含式与对偶式 1蕴含式的定义 定义定义1.4.1 设A和B是两个公式，如果AB是永真式，则称A蕴含B，记作AB。 注意符号和的区别： 是逻辑连接词，代表“如果那么”的逻辑关系； 不是连接词，它表示两个公式之间的一种蕴含关系。 AB成立，当且仅当AB是永真式。 An Introduction to Database Systenm1.4 蕴含式与对偶式蕴含式与对偶式 蕴含式具有如下性质： （1）自反性：即对任意公式A，有AA。 （2）传递性：即对任意公式A、B 和C，若AB，BC，则AC。 （3）对任意公式A、B 和C

30、，若AB，AC，则A(BC)。 （4）对任意公式A、B 和C，若AC，BC，则ABC。 常用蕴含式：PQPQQPQPPQPQQPPQPQPQP)(QQP)(QPQP,QQPP ,QQPP,PQPQ ,RPRQQP,RRQRPQP,)()(RQRPQP)()(RQRPQPAn Introduction to Database Systenm1.4 蕴含式与对偶式蕴含式与对偶式2. 蕴含式的证明（1）对PQ来说，QP称作它的逆换式；?P?Q称为它的反换式；?Q?P称为它的逆反式。含条件连接词的公式与其逆反式等价，即PQ?Q?P。因此要证明PQ，只需证明?Q?P，反之亦然。（2）要证PQ，即证PQ是

31、永真式。 An Introduction to Database Systenm1.4 蕴含式与对偶式蕴含式与对偶式 常用的蕴含式证明有三种方法。 （1）真值表法。用真值表证明PQ是永真式，即真值表中的最后一列都是1。该方法的优点是直观明了，缺点是当命题变元较多时，构造真值表的工作量较大。 （2）通过等价式的推导。 例1.4.2 求证?Q(PQ)?P 证明：?Q(PQ)?P?(?Q(PQ)?P 条件转化律 ?(?Q(?PQ)?P 德摩根律 (Q(P?Q)?P 分配律 (QP)(Q?Q)?P 否定律 (QP)T)?P 同一律 Q(P?P) 否定律 QT 零律 TAn Introduction t

32、o Database Systenm1.4 蕴含式与对偶式蕴含式与对偶式 （3）条件假定推演法 对于式PQ，除P的真值取T、Q的真值取F 这种指派的情况下 PQ的真值为F ，其余情况PQ的真值为T。因此，要证明PQ，只需对条件命题PQ的前件P指定真值为T时，能推出后件Q的真值也为T。该证明方法为肯定前件推导后件为真的方法。同理，由于PQ?Q?P，还存在否定后件推导前件为假的方法。 肯定前件推导后件为真的方法 假定条件式的前件为真，若能推导出后件也为真，则条件式是永真式，即蕴含式成立。 下面用肯定前件推导后件为真的方法证明例1.4.2。 证明方法3：假定Q(PQ)为T，则Q为T，且PQ为T。因此

33、Q为F，要使PQ为T，则必须P为F，故P为T。 否定后件推导前件为假的方法 假定条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴含式成立。An Introduction to Database Systenm1.4 蕴含式与对偶式蕴含式与对偶式 1.4.1 蕴含式 1.4.2 对偶式An Introduction to Database Systenm1.4.2 对偶式对偶式 通过观察可以发现，很多基本等价式都是成对出现的。这些成对出现的基本等价式就是对偶式。 定义定义1.4.2 在给定的仅使用、和的命题公式A中，若把 和互换，F和T互换而得到一个命题公式A*，则称A*为A的对偶式

34、。 显然，A也是A*的对偶式，即A与A*互为对偶式。 例1.4.3 写出下列公式的对偶式： (PQ)R (PQ)S 解：的对偶式为(PQ)R 的对偶式为(PQ)S 定理定理1.4.1 设A和A*互为对偶式，P1, P2, , Pn是出现在A和A*中的原子变元，则 A(P1, P2, , Pn)A*(P1, P2, , Pn)； A(P1, P2, , Pn)A*(P1, P2, , Pn)。 An Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式与对偶式1

35、.5 其它连接词与最小连接词组1.6 范式1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm1.5 其它连接词与最小连接词组其它连接词与最小连接词组 1.5.1 其它连接词 1.5.2 最小连接词组An Introduction to Database Systenm1.5.1 其它连接词其它连接词 定义定义1.5.1 设P和Q是两个命题公式，复合命题PQ称作P和Q的“与非”。当且仅当P和Q的真值均为T时， PQ为F，否则PQ的真值为T。 PQ的真值表 从上表可知PQ(PQ)。 连接词“”具有如下性质： （1）PP(PP)P （2）(PQ

36、)(PQ)?(PQ)PQ （3）(PP)(QQ)?P?Q?(?P?Q)PQAn Introduction to Database Systenm1.5.1 其它连接词其它连接词 定义定义1.5.2 设P和Q是两个命题公式，复合命题PQ称作P和 Q的“或非”。当且仅当P和Q的真值均为F 时， PQ的真值为T，否则PQ的真值为F。 PQ的真值表 从上表可知PQ(PQ)。 连接词“”或具有如下性质： （1）PP?(PP)?P （2）(PQ)(PQ)?(PQ)PQ （3）(PP)(QQ)?P?Q?(?P?Q)PQQP An Introduction to Database Systenm1.5.1 其

37、它连接词其它连接词 定义定义1.5.3 设P和Q是两个命题公式，复合命题 称作命题P和Q的条件否定， 的真值为T，当且仅当P真值为T，Q真值为F，否则 的真值为F。 的真值表 由定理1.2.1可知，含有2个命题变元的公式具有4种不同的真值指派。在每种指派下，公式的真值只能取真、假两种情况。因此，2个命题变元可构成24个不等价的命题公式。如表1.5.4所示。 QPCQPCQPCQPCQPCAn Introduction to Database Systenm1.5.1 其它连接词其它连接词表1.5.4 2个变元构成的不等价命题公式由表1.5.4可看出：F0 和F1分别表示永真式和永假式； F2和

38、F3分别表示命题变元P、Q；F4和F5分别表示命题变元的否定?P、?Q； F6表示“合取”命题PQ；F7表示“与非”命题PQ ； F8表示“析取”命题PQ ；F9表示“或非”命题PQ ； F10、F14分别表示条件命题PQ、QP；F11、F15分别表示条件否定命题 、 ； F12表示双条件命题PQ； F13表示“排斥或”命题 。 QPC PQC QPAn Introduction to Database Systenm1.5 其它连接词与最小连接词组其它连接词与最小连接词组 1.5.1 其它连接词 1.5.2 最小联接词组An Introduction to Database Systenm1

39、.5.2 最小连接词组最小连接词组 定义定义1.5.4 如果连接词组G满足下列两个条件： （1）由G中的连接词构成的公式能等价表示任意命题公式。 （2）G中的任一连接词不能用其余的连接词表示；则称G为最小连接词组。 , ，, ，, ， 都是最小连接词组。 例1.5.1 证明, 是一个最小连接词组。 证明：对任意公式P、Q， , 可等价表示其余7个连接词构成的公式，且, 中任一连接词不能用该集合中余下的连接词等价表示。得证, 是一个最小连接词组。 ?, ?, , , , 和?, , 虽然不是最小连接词组，但为了表示方便，仍经常使用联接词组, ,。 )(QPQPQPQP)()(QPQPQP)()(

40、QPQPQPQPQP)(QPQP)(QPQPCAn Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式与对偶式1.5 其它连接词与最小连接词组1.6 范式1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm1.6 范式范式 1.6.1 简单合取式与简单析取式 1.6.2 公式的范式An Introduction to Database Systenm1.6 范式范式 一个公式可以具有多种相互等价的表达方式

41、，例如：PQ(PQ)(QP)(PQ)(?P?Q)。为了减少同一公式的不同表达形式对解决推理问题所带来的麻烦，需要将公式标准化。 另外，使用真值表、对偶定理可判断两个公式是否等价。除此之外，还可以通过比较公式的标准形式的方法来判断公式的等价性。 公式的标准形式就是范式。An Introduction to Database Systenm1.6.1 简单合取式与简单析取式简单合取式与简单析取式 定义定义1.6.1 在一公式中，仅由命题变元及其否定构成的合取式，称为该公式为简单合取式，其中每个命题变元或者其否定，称为合取项。 例如：P、Q、P、Q、PQ、PQ、PQ、PQQ均是简单合取式。(PQ)Q

42、、(PQ)Q均不是简单合取式。 定义定义1.6.2 在一公式中，仅由命题变元及其否定构成的析取式，称为该公式为简单析取式，其中每个命题变元或者其否定，称为析取项。 例如：P、Q、P、Q、PQ、PQ、PQ、PQQ均是简单析取式。(PQ)Q、(PQ)Q均不是简单析取式。 注意：单独一个命题变元或其否定既可以是简单合取式，也可以是简单析取式。例如P、P等既是简单合取式，也是简单析取式。 定理定理1.6.1 设A是一个公式，那么 （1）若A是简单合取式，则A是永假式等价于A的合取项中同时有某个命题变元及其否定。 （2）若A是简单析取式，则A是永真式（或重言式）等价于A的析取项中同时有某个命题变元及其否

43、定。An Introduction to Database Systenm1.6 范式范式 1.6.1 简单合取式与简单析取式 1.6.2 公式的范式An Introduction to Database Systenm1.6.2 公式的范式公式的范式 定义定义1.6.3 一个命题公式A称为合取范式，当且仅当A可表示为简单析取式的合取，即A=A1A2An，其中A1, A2, An为简单析取式。 例如： (PQ)(PR)R，PQ ，Q均是合取范式。 定义定义1.6.4 一个命题公式A称为析取范式，当且仅当A可表示为简单合取式的析取，即 A=A1A2An，其中A1, A2, An为简单合取式。 例

44、如：(PQ)R，PQ，PQ ，Q均是析取范式。 定理定理1.6.2 任何一个命题公式都存在与其等价的析取范式和合取范式。 通过以下三个步骤可对任何命题公式求取等价的析取范式或合取范式。 （1）将公式化为只含有，及连接词的公式。 （2）利用徳摩根律将否定符号直接转移到各个命题变元之前。 （3）利用分配律、结合律将公式归为合取范式或析取范式。An Introduction to Database Systenm1.6.2 公式的范式公式的范式 定理定理1.6.3 设A是一个公式，那么 （1）A为永假式等价于A的析取范式中每个简单合取式至少包含一个命题变元及其否定。 （2）A为永真式等价于A的合取范

45、式中每个简单析取式至少包含一个命题变元及其否定。 An Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式与对偶式1.5 其它连接词与最小连接词组1.6 范式1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm1.7 公式的主范式公式的主范式 1.7.1 主析取范式 1.7.2 主合取范式 1.7.3 主析取范式与主合取范式之间的关系 1.7.4 主范式的应用An Introduction to Data

46、base Systenm1.7.1 主析取范式主析取范式 1 小项的定义及性质 定义定义1.7.1 在含有n个命题变元的简单合取式中，若每个命题变元与其否定不同时存在，但两者之一出现一次且仅出现一次，则称该简单合取式为小项，或布尔积。 例如，对两个命题变元P和Q，其小项为： PQ，PQ，PQ，PQ。小项的真值表如下表所示。 An Introduction to Database Systenm1.7.1 主析取范式主析取范式 在表1.7.2中，如果将命题变元按字典序排列，并把命题变元与命题变元与1对应，命题变对应，命题变元的否定与元的否定与0对应对应，则可对2n个小项依二进制数编码，记为mi，

47、下标i是由二进制数转化的十进制数。即 由n个命题变元生成的小项具有如下性质： （1）每个小项具有一个相应的编码，当该编码与其真值指派相同时，该小项真值为T，在其余2n-1种指派情况下为F。任何两个不同的小项不等价。 （2）任何两个不同小项的合取为永假式，即 。 （3）所有小项的析取为永真式 。)(jiFmmjiTmini120RQPmRQPm10RQPmRQPm32RQPmRQPm54RQPmRQPm76An Introduction to Database Systenm1.7.1 主析取范式主析取范式 2. 主析取范式的定义及求法 定义定义1.7.2 对于给定的命题公式，若有一等价公式仅由

48、小项的析取组成，则该等价式称作原式的主析取范式。 定理定理1.7.1 在真值表中，一个公式的真值为T 的指派所对应小项的析取，即为此公式的主析取范式。 定理定理1.7.2 任意含n个命题变元的非永假命题公式都存在且唯一存在与其等价的主析取范式。 An Introduction to Database Systenm1.7.1 主析取范式主析取范式 求主析取范式的方法有真值表法和基本等价公式化归法。定理1.7.1已给出真值表求主析取范式法。 基本等价公式化归法的推演步骤如下： （1）将给定公式化为析取范式。 （2）删除析取范式中永假的析取项。 （3）应用等幂律将重复出现的命题变元合并，化简为一次

49、出现，如PPP。 （4）在简单合取式中补入没有出现的命题变元，即添加(PP)式，然后应用分配律展开。 An Introduction to Database Systenm1.7 公式的主范式公式的主范式 1.7.1 主析取范式 1.7.2 主合取范式 1.7.3 主析取范式与主合取范式之间的关系 1.7.4 主范式的应用An Introduction to Database Systenm1.7.2 主合取范式主合取范式 1. 大项的定义 定义定义1.7.3 在含有n个命题变元的简单析取式中，若每个命题变元及其否定不同时存在，但二者之一出现一次且仅出现一次，则称该简单析取式为大项，或布尔和。

50、 例如，对于两个命题变元P和Q，其大项为：PQ，PQ，PQ，PQ，共4个。其真值表见表1.7.5。 An Introduction to Database Systenm1.7.2 主合取范式主合取范式n如果将命题变元按字典序排序，并把命题变元与命题变元与0对应，命题变对应，命题变元的否定与元的否定与1对应对应，则可对2n个大项依二进制编码，记为Mi，下标i是由二进制数转化的十进制数。n例如：当有2个命题变元时， M0=PQ M1 =P QM2=PQ M3 =P Qn当有3个命题变元时， M0=PQR M1=P QRM2=PQR M3=P QRM4=PQR M5=PQRM6=PQR M7=P

51、QRAn Introduction to Database Systenm1.7.2 主合取范式主合取范式 大项的性质： （1）每个大项具有一个相应的编码，当该编码与其真值指派相同时，该大项真值为F，在其余2n-1种指派下均为T。任何两个不同的大项不等价。 （2）任何2个不同大项的析取为永真式，即MiMj T ( i j )。 （3）所有大项的合取为永假，即 FMini120An Introduction to Database Systenm1.7.2 主合取范式主合取范式 2. 主合取范式的定义及求法 定义定义1.7.4 对于给定的命题公式，若有一等价公式仅由大项的合取所组成，则该等价式称

52、为原式的主合取范式。 定理定理1.7.3 在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。 例1.7.4 求(PQ)Q的主合取范式。 解：公式(PQ)Q的真值表如表1.7.7所示。 因此，(PQ)Q(PQ)(PQ)。 An Introduction to Database Systenm1.7.2 主合取范式主合取范式 定理定理1.7.4 任意含n个命题变元的非永真命题公式都存在且唯一存在与其等价的主合取范式。 求主合取范式有真值表法和基本等价化归法。 基本等价化归法的推演步骤： （1）将给定公式化为合取范式。 （2）删除合取范式中所有为永真的合取项。 （3）应

53、用等幂律合并相同的简单合取式和相同的变元。 （4）对简单析取式补入没有出现的命题变元，即添加(PP)式，然后应用分配律展开。An Introduction to Database Systenm1.7 公式的主范式公式的主范式 1.7.1 主析取范式 1.7.2 主合取范式 1.7.3 主析取范式与主合取范式之间的关系 1.7.4 主范式的应用An Introduction to Database Systenm1.7.3 主析取范式与主合取范式之间的关系主析取范式与主合取范式之间的关系n 主析取范式由小项构成，主合取范式由大项构成。n 小项与大项的关系：miMi Mimi n 为了使主范式表

54、示得更加简洁、明了，可用符号表示小项的析取，如i, j, k表示mimjmk，用表示大项的合取，如i, j, k表示MiMjMk 。 An Introduction to Database Systenm1.7.3 主析取范式与主合取范式之间的关系主析取范式与主合取范式之间的关系 定理定理1.7.5 如果含有n个命题变元的公式A的主析取范式为 则的主合取范式为 。 由定理1.7.5可知，从公式A的主析取范式可求其主合取范式。步骤为： （1）求出A的主析取范式中没有包含的小项。 （2）求出与(1)中小项的下标相同的大项。 （3）将(2)中大项进行合取，即为A的主合取范式。 例1.7.8 求 的主

55、析取范式和主合取范式。 解：主析取范式： 主合取范式： kiii,2112 , 1, 1, 1, 1, 2 , 1 , 011nkkiiii)()(RPQP)()()()()()(RQPRQPRQPRQPRPQP7 , 6 , 3 , 11367mmmm5420)()(MMMMRPQP)()()()(RQPRQPRQPRQPAn Introduction to Database Systenm1.7 公式的主范式公式的主范式 1.7.1 主析取范式 1.7.2 主合取范式 1.7.3 主析取范式与主合取范式之间的关系 1.7.4 主范式的应用An Introduction to Databas

56、e Systenm1.7.4 主范式的应用主范式的应用 1.公式类型的判定 根据给定含有n个变元公式A的主范式按下述条件可判定公式的类型。 （1）若公式A可化为含2n个不同小项的等价主析取范式，则A为永真式。 （2）若公式A可化为含2n个不同大项的等价主合取范式，则A为永假式。 （3）若公式A可化为含小项且小项个数小于2n个的主析取范式，或可化为含大项且大项个数小于2n个的主合取范式，则A为可满足式。An Introduction to Database Systenm1.7.4 主范式的应用主范式的应用 2.等价式的证明 由于任一公式的主范式是唯一的，所以若两个公式的主范式相同则给定的两个公

57、式是等价的。 例1.7.10 证明 证明： 由于两公式具有相同的主析取范式，则两公式等价。)()()()(ABBABABA)()()()(BABABABA)()(BABA3 , 2)()(BABA)()()()(ABBAABBA)(BBA3 , 2)()(BABAAn Introduction to Database Systenm第一章第一章 命题逻辑命题逻辑1.1 命题与连接词1.2 命题公式及命题公式的翻译1.3 等价公式及公式的分类1.4 蕴含式与对偶式1.5 其他连接词与最小连接词组1.6 范式1.7 公式的主范式1.8 推理理论An Introduction to Database Systenm1.8 推理理论推理理论 1.8.1 有效论证 1.8.2 推理方法An Introduction to Database Systenm1.8.1 有效论证有效论证 定义1.8.1 设A和B是两个命题公式，当且仅当AB为一永真式 (或重言式) ，即AB，称B是A的有效结论，或B可由A逻辑推出。 上述定义可推广至n个前提的情况。设H1, H2, , Hn, B是命题公式，当且仅当H1H2HnB才称B是前提集合H1, H2, , Hn的有效结论，或由H1, H2,