《第1章离散数学命题逻辑剖析.》由会员分享，可在线阅读，更多相关《第1章离散数学命题逻辑剖析.（66页珍藏版）》请在金锄头文库上搜索。
1、数理逻辑概述,逻辑：逻辑是人的一种抽象思维，是人通过概念、判断、推理、论证来理解和区分客观世界的思维过程。 数理逻辑：是用数学方法研究逻辑学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。 数理逻辑的发展： 莱布尼兹的设想：能不能创造一种“通用的科学语言”，可以把推理过程象数学一样利用公式来进行计算，从而得出正确的结论。 布尔、弗雷格的符号化 数理逻辑的基本内容：命题演算和谓词演算,推论 ：每个X都是Y，一些Z是X，因此一些Z是Y 填入内容：每个传记作者都是作家，有些政治家是传记作者，因此，有些政治家是作家 在上述推理中，论证的合理性与内容无关，而是由一般形式的逻辑正确性来
2、保证的 推论中的X，Y和Z表明了插入语句的位置，在数理逻辑中称为“逻辑变量”,第1章 命题逻辑,命题逻辑：也称命题演算，它与一阶逻辑构成数理逻辑的基础，而命题逻辑又是一阶逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。 命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。,学习要求 深刻理解命题、逻辑连接词以及复合命题的概念。 深刻理解公式及其解释的概念。 深刻理解原子、公式的永真性、永假性、可满足 性。 掌握用基本等价公式对公式进行等价变换的方 法。 深刻理解公式范式的概念。 熟练掌握用主析取范式判断任意两个公式是否等 价的方法。
3、掌握命题逻辑的判定方法。 掌握形式演绎的方法。,1.1 命题符号化与联结词,一 命题的概念：（描述） 所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值-真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定,问题：如何判断句子是命题？（P1） 如何判断命题的真值？ 例： P1例1.1,二 命题的种类： 简单命题（原子命题）：如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。本书
4、中用小写英文字母表示简单命题 复合命题：它由原子命题、命题联结词和圆括号组成。例： P2例1.2,命题常项（命题常元）；命题变项（命题变元）,三 、联结词与复合命题符号化 1.联结词,否定联结词： P2定义1.1 合取联结词： P2定义1.2 析取联结词： P3定义1.3 蕴涵联结词： P3定义1.4 等价联结词 ： P4定义1.5,定义1.1 设p表示一个命题，由命题联 结词和命题p连接成 p，称 p为 p的否定式复合命题， p读“非p” 。称 为否定联结词。 p是真，当 且仅当p为假； p是假，当且仅当p 为真。否定联结词“”的定义可由 表1.1表示之。,定义1.2 设p和q为两个命题，由
5、命题联结词将p和q连接成pq，称pq为命题p和q的合取式复合命题，pq读做“p与q”，或“p且q”。称为合取联结词。当且仅当p和q的真值同为真，命题pq的真值才为真；否则，pPq的真值为假。合取联结词的定义由表1.2表示之。,p与q的合取表达的逻辑关系是：p与q两个命题同时成立。因而自然语言中“既又”，“不仅而且”，“虽然但是 ”等，都可以符号化为,（1）李平既聪明又用功,（2）李平虽然聪明，但不用功,（3）李平不但聪明而且用功,注意：句中的“和”、“与” 例：王兰和陈芳是好朋友,（4）李平不是不聪明而是不用功,定义1.3 设p和q为两个命题，由命题联结词把p和q连接成pq，称pq为命题p和q
6、的析取式复合命题，pq读做“p或q”。称为析取联结词。当且仅当p和q的真值同为假，pq的真值为假；否则，pq的真值为真。析取联结词的定义由表1.3表示之。,析取式p q表示的是一种相容或，即允许p与q同时为真 自然语言中的或具有二义性，即有时表现为相容或，有时表现为排斥或 例,王燕学过英语或法语 派小王或小李中的一人去开会,p q,(p q) ( p q),定义1.4 设p和q为两个命题，由命题联结词把p和q连接成pq，称pq为命题p和q的蕴涵式复合命题，简称条件命题。pq读做“p蕴涵q”或者“如果p则q”。称为蕴涵联结词。 当p的真值为真而q的真值为假时，命题pq的真值为假；否则，pq的真值
7、为真。条件联结词的定义由表1.4表示之。,在蕴涵命题 pq 中，命题p称为 pq 的前件或前提，命题q称为pq的后件或结论。pq 表示的基本逻辑关系是：“p是q的充分条件”或“q是p的必要条件”。 条件命题pq有多种方式陈述： “如果p，那么q”；“只要p，就q”： “p仅当q”；“只有q才p”；等。,在日常生活中，用条件式表示前提和结论之间的因果或实质关系，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关系，这种条件式称为实质条件命题。采用实质条件式作定义，不单是出于“善意推断”，主要是因为前提与结论间有无因果和实质关系难以区分，而且实质条件式已包含了形式
8、条件式，更便于应用。 因此在数理逻辑中，p与q不必一定有内在必然联系,只要天不下雨，我就骑自行车上班 只有天不下雨，我才骑自行车上班 若2+2=4，则太阳从东方升起 如果明天天气晴朗，我们就去郊游,pq,pq,pq,注意：在数理逻辑中，pq中的p与q不一定有内在联系,注意：在数理逻辑中，当前件p为假时，pq为真。这一点与日常逻辑不同,q p,定义1.5 令p、q是两个命题，由命题联结词把p和q连接成p q，称p q为命题p和q的等价式复合命题，简称等价命题，p q读做“p当且仅当q”，或“p等价q”。称为等价联结词。当p和q的真值相同时，p q的真值为真；否则，p q的真值为假。等价联结词的定
9、义由表1.5表示之。,2.复合命题的符号化（重点内容） 步骤： (1) 分析出各简单命题，将它们符号化； （2）分析各简单命题之间的关系，选择使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示； 例： P4 例1.6,作业：P32 1.4 1.5,1.2 命题公式及分类,命题常元与命题变元的概念 在命题逻辑中，命题有命题常元（常值命题）和命题变元（命题变项）之分。一个有确定的具体值的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值。命题常元和命题变元均可用字母p、
10、q、r或pi、qi、ri等表示,命题公式和合式公式的概念： 命题公式：从形式上看，命题公式由命题常元（常值命题）、命题变元（命题变项）和括号经命题联结词构成的字符串，但这个字符串必须按一定的规则构成，即它是合式公式 合式公式：经定义的，有规则可循的命题公式。通常我们将合式公式称为命题公式,定义1.6 合式公式是由下列规则生成的公式： 单个命题常元或变元是合式公式。 若A是一个合式公式，则(A)也是一个合式公式。 若A、B是合式公式，则(AB)、(AB)、(AB)和(A B)都是合式公式。 只有有限次使用、和生成的公式才是合式公式。(P5),三 命题公式的层次和真值表（重点内 容）,命题公式的层
11、次定义 见书P5 什么是真值表：将命题公式在所有赋值之下取 值的情况列成的表 构造真值表的步骤：见P6 例：P6例1.7,作业：P32 1.6（1）， P33 1.7（1）,（5）,（10）,设 A 为任意公式，则 对应每一个赋值，公式 A的真值均相应确定为真，称 A 为重言式，或永真式。 对应每一个赋值，公式 A的真值均相应确定为假，称 A 为矛盾式，或永假式。 至少存在一个赋值，公式 A的真值相应确定为真，称 A 为可满足式。,四 公式分类,例：P7的表1-1,1-2,1-3,由定义可知，重言式必是可满足式，反之一般不真。 今后重点将研究重言式，因为它最有用，它有以下特点： 重言式的否定是
12、矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。 两个重言式的合取式、析取式、蕴涵式和等价式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。,1.3 等值演算,一 等价公式 定义：设A和B是两个命题公式，如果A、B在其任意赋值下，其真值都是相同的，则称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。 显然，若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。 例：P8 例1.8,注意：和的区别 是逻辑联结词，它出现在命题公式中，表示两个命题之间的一种逻辑关系。 不是逻辑联结词，表示两个命题公式的一种关系，不属于这两
13、个公式的任何一个公式中的符号。,等价式有下列性质： 自反性，即对任意公式A，有A A 对称性，即对任意公式A和B， 若A B，则B A 传递性，即对任意公式A、B和C， 若A B、B C，则A C,二 基本等价式命题定律 给定n（n1）个命题变项，按合式公式的形式规则可以形成无穷多个命题公式，但其中只有22n个真值不同的命题公式。见P8 表1-4 在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律（24个）。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一。 见书P9,三 等值演算（重点内容） 根据已知的等值式推演出另外一些等值式的过程。,1.演算规则：代入规则
14、和替换规则 代入规则： 在一个永真式A中，任何一个原子 命题变元r出现的每一处， 用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。 置换规则： 设A1是合式公式A的子公式，若 A1B1，并且将A中的A1用B1 替换得到公式B，则AB。称该定理为置换规则。,代入和置换有两点区别： 代入是对原子命题变元而言的， 而置换可对命题公式实行。 代入必须是处处代入，置换则可 部分替换，亦可全部替换。,2.演算举例 例1 P10 例1.9、1.10、1.11,作业： 试证语句：“不会休息的人也不会工作，没有丰富知识的人也不会工作”，与语句：“工作的好的人一定会休息并且有丰富的知识”逻辑一致,1.
15、4 范式（命题公式的标准式）,1.简单合取式和简单析取式 P12 定义1.12,2.析取范式和合取范式（非标准式） P12 定义1.13,3.主析取范式和主合取范式（标准式） P14定义1.15和P14定理1.3,例如:公式p， q，p q和 p q p等都是 简单合取式，而p，q和 p为相应的简单合取式的合取项；公式p， q，p q， p q p等都是简单析取式，而p，q和 p为相应简单析取式的析取项。 注意:一个命题变元或其否定既可以是简单 合取式，也可以是简单析取式，如例中p ， q等。,定理: 简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。 定理：简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。,范式存在定理：对于任何一命题公式，都存在与其等价的析取范式和合取范式。（P13） 求范式算法： 使用命题定律，消去公式中除、和以外 公式中出现的所有联结词； 使用 ( P)P和德摩根律，将公式中出现 的联结词都移到命题变元之前； 利用结合律、分配律等将公式化成析取范式 或合取范式。 举例：P13 例1.12（析取范式与合取范式具有不唯一性）,.主析取范式 (1) 极小项的概念和性质 定义： 在含有n个命题变元的简单合取式中， 若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现
