北邮函授考试离散数学期末考试复习题-第四章

1、第四章 数理逻辑§4.1 命题逻辑一、命题与命题公式1.命题定义 在数理逻辑中，能够判断真假的陈述句称为命题。注：命题包括两点：陈述句，能判断真假命题的真假称为命题的真值，如果一个命题是真的（正确的判断），它的真值为真，记为T或1；如果一个命题是假的（错误的判断），它的真值为假，记为F或0。简单命题: 不能分解成更简单的陈述句的命题,叫简单命题或原子命题。常用小写字母来表示简单命题。命题符号化: 将一个命题用字母表示时，称为将命题符号化。如 : 2是素数。 : 雪是黑色的。则 是真命题, 为假命题。有时用1表示真命题, 0表示假命题。一个符号若表示确定的命题,称为命题常项或命题常元。

2、上面的 , 为命题常项。当一个符号表示任一简单命题时（起着类似数学中变元的作用），这个符号称为命题变项或命题变元。严格来说: 命题变元不是命题。因它可以表示任一命题,故无确定的真值。2.逻辑连接词（1）否定联结词定义 设为任一命题，复合命题“非”称为的否定式，记为，为否定连接词。其真值为：若为1, 则为0；若为0，则为1。如下表: 0110（2）合取联结词定义 设为二命题，复合命题“”称作 和 的合取式，记作 . 为合取联结词。规定为真当且仅当同时为真。如下表000010100111（3）析取联结词定义 设为二命题，则复合命题（读作“或 ”）称为、 的析取式。 为析取联结词。其真值为：当且仅当

3、和的真值全为0时，命题 的真值才是0，否则，命题的真值为1。如下表000011101111（4）蕴涵联结词定义 设为二命题，复合命题“如果,则”称作与的蕴涵式，记作 . 为前件，为后件。 称作蕴涵联结词。“”又称为条件命题，规定当为真和 为假时，为假，否则为真。001011100111由此可知：前件为假，不论后件真假与否，条件命题为真。相当于自然语言中的“如果则”，“若则”，表明：为的必要条件（或为的充分条件）。（5）等价联结词定义 设为二命题，复合命题“当且仅当”称作与的等价式，记作. 称作等价联结词。规定当和的真值相同时，为真，否则为假，列表如下:001010100111相当于自然语言中的

4、“当且仅当”，“充分必要”。3.命题公式及分类定义 (1)单个命题常元、命题变元，0，1是命题公式； (2)如果是命题公式,则也是命题公式； (3)如果是命题公式,则，也是命题公式；(4)只有有限次地运用(1)-(3)组成的符号串才是命题公式。在定义中引用了A、B等符号，它们表示任意的命题公式。下面给出赋值的定义定义 设A是一个命题公式，是出现在公式A中的全部命题变元，给 各指定一个真值，称为对命题公式A的一个赋值或解释。若指定的一组值使A的值为1，则称这组值为A的成真赋值；若使A的值为0，则称这组值为A的成假赋值。 定义 设A为命题公式（1）如果对A中所含命题变元的任一组赋值，A的真值总为1

5、，则称A为重言式或永真式；（2）如果对A中所含命题变元的任一组赋值，A的真值总为0，则称A为矛盾式或永假式；（3）若至少有一组赋值使A为真，则称A是可满足式。 由定义可以看出，重言式一定是可满足式，但反之不一定成立。可满足式一般是指非重言式的可满足式。用真值表可以判断公式的类型；若真值表的最后一列全为1，则公式为重言式。若最后一列全为0，则公式为矛盾式；若最后一列既有1又有0，则公式为非重言式的可满足式。二、等值演算定义 设A，B为二命题公式，若等价式为重言式，则称A与B是等值的，记作 注意符号“”不是联结词，它是A与B等值的一种记法。不能将与或与= 混为一谈。 例如： 但不能写成又不是命题公

6、式。 下面给出24个常用的重要的等值式，设表示任意的命题公式，1表示永真式, 0表示永假式. 双否律 （1）幂等律 （2） （3） 结合律 （4） （5）交换律 （6） （7）分配律 （8） （9）德摩根律 （10） （11）吸收律 （12） （13）同一律 （14） （15）零一律 （16） （17）排中律 （18）矛盾律 （19）蕴涵等值式 （20）等价等值式 （21）假言易位 （22）等价否定等值式 （23）归谬论 （24）关于等值演算加几点说明（1）由于在基本等值式中出现的代表任意的命题公式，因而每个公式都是一个模式，它们中的每一个都可以对应无数个同类型的等值式。例如在（19）式中，用

7、代替，得等值式为，用代替得等值式为于是，矛盾律可以有无数种形式其它的等值式类似（2）在等值演算过程中，还经常用到置换规则，它的内容如下： 置换规则：设是含命题A的命题公式，则可用B置换中的A，得且 例如，则 （3）利用等值演算可以验证等值式，通过等值演算能将命题公式化简，还可以通过等值演算判断命题公式的类型。三、命题逻辑的推理理论定义 设，是命题公式，称蕴涵式 为推理的形式结构，为前提，为结论，若为永真式，则称从前提推出结论的推理正确，并称是的逻辑结论或有效结论，记为否则，称推理不正确。说明：（1）由定义可知的充要条件是为永真式（2）不是联结词，只是永真蕴涵式的一种表示方法，不要把与混为一谈。

8、因此，不是命题公式。（3）所谓从前提推出结论的推理正确，是指为永真式，并不是说一定是真命题（或永真式），因此我们称是前提的逻辑结论（合乎逻辑的结论）。由是永真式可知：当前提都是真命题时，也一定是真命题（此时，称为合法的结论）。数学中所证定理的结论都是这种情况。当前提中有一为假时，则可能是真命题也可能是假命题。但仍称从推出的推理正确，因在数理逻辑中主要着重于推理规则的研究，并不要求前提和结论一定是真命题。判断推理正确的方法有 真值表法 等值演算法 构造证明法推理定律（永真蕴涵式）1 附加2 化简3 假言推理4 拒取式5 析取三段论6 假言三段论7 等价三段论8 构造性二难注：除上述8条推理定律外

9、，前面介绍的每个基本等值式均可产生两个推理定律。如由可产生和两条推理定律。证明中常用的推理规则有3条 1 前提引入规则：在证明的任何步骤上，都可以引入前提。 2 结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提加以引用。3 置换规则：在证明的任何步骤上，命题公式中的任何子公式都可用与之等值的公式置换，如：可置换成。注：推理规则除上面3条外，根据推理规则2，由8条推理定律可得8条推理规则（再给出一条合取引入规则）1. 附加规则2. 化简规则3. 假言推理规则4. 拒取式规则5. 析取三段论规则6. 假言三段论规则7. 等价三段论规则8. 构造性二难规则9. 合取引入规则构造证

10、明法举例例 构造下面推理的证明前提：，结论：证 前提引入 前提引入 前提引入 构造性二难§4.2 一阶逻辑一、一阶逻辑的基本概念在一阶逻辑中，简单命题被分解成两部分：个体词、谓词。1.个体词和谓词个体词：在简单命题中可以独立存在的主体或客体称为个体词，谓词：刻画一个个体词的性质或两个及两个以上个体词之间关系的词称为谓词。个体常元：表示具体的或特定的个体的词，如：张三、李四、中国。个体变元：表示抽象的或泛指的个体的词，如：人、思想、自然数。个体常元用小写英文字母a,b,c, 表示；个体变元用小写英文字母x,y,z, 表示。谓词常元：表示具体性质和关系的词。谓词变元：表示抽象和泛指的谓词

11、。谓词用大写英文字母A,B,C, 表示。那么，怎样用个体词和谓词表示简单命题呢？个体常元a或变元x具有性质A,记A(a)或A(x)；个体常元a与b或变元x与y具有关系B，记B(a,b)或B(x,y)；个体常元a,b,c或变元x,y,z具有关系L,记L(a,b,c)或L(x,y,z).定义 在谓词中所含有的个体变元的个数称为元数，含n(n1)个个体变元的谓词称为n元谓词。如：F(x)是一元谓词，B(x,y)是二元谓词，一般一元谓词表示个体词的性质，n(n2)元谓词表示个体词间的关系，也常称不含个体变元的谓词为0元谓词。我们将个体词的取值范围（论述范围）称为个体域（或论域），个体域可以是有限集也可

12、以是无限集，将宇宙间一切事物组成的个体域称为全总个体域。2.量词量词有全称量词和存在量词两种（1）全称量词：对应于常用语言的“一切”，“所有的”，“任意的”，“每一个”等，用符号表示，表示对于个体域中的所有个体都有性质。（2）存在量词：对应于常用语言的“至少有一个”，“存在着”等，用符号表示，表示存在个体域里的某个个体具有性质。3.谓词公式在命题逻辑中，参加命题演算的是命题公式，在一阶逻辑中，进行谓词演算的是谓词公式。定义 由一个谓词，一些个体变元组成的表达式称为简单命题函数。如 是一元简单命题函数，是二元简单命题函数，是n元简单命题函数，0元谓词是命题。由一个或几个简单命题函数以及逻辑连接词

13、构成的表达式称为复合命题函数（今后简称命题函数）。如 是复合命题函数。由命题、命题变元、命题函数、逻辑连接词、量词、括号组成的符号串称为谓词公式，但并不是任何这样的符号串都是谓词公式，下面给出谓词公式的递归定义。定义（1）命题、命题变元、命题函数是谓词公式，（2）如果是谓词公式，则是谓词公式，（3）如果是谓词公式，则都是谓词公式，（4）如果是谓词公式，是中的个体变元，则都是谓词公式，（5）只有有限次利用（1）（5）所产生的符号串才是谓词公式。注意：量词后的括号不能随意省略，如不能写成。定义 在谓词公式和中，后面所跟的叫做量词的指导变元，为相应量词的辖域，在辖域中出现的称为约束出现（被相应的量词

14、约束，也称为约束变元），中不是约束出现的其他变元的出现称为自由出现，也称自由变元。 为了避免在一个谓词公式中由于变元的约束和自由同时出现，引起概念上的混乱，采用下面两条规则： 换名规则：将量词辖域中出现的某个约束出现的个体变元及对应的指导变元，改成辖域中未曾出现过的个体变元符号，公式中其余部分不变。例 (为约束出现同时又是自由出现，将换名)解 换名为： 则公式中无即是约束出现又同时是自由出现的变元。 错误的换名 错误的换名 代替规则：对某个自由出现的个体变元用与原公式中所有个体变元符号不同的变元符号去代替，且处处代替。例 ，公式中，即是约束出现又是自由出现，用代替规则将自由出现的用其他符号代替

15、。解 可代替为：例 解 公式中，变元既是约束出现又是自由出现，将自由出现的用代替，得 对谓词公式中的各种变项（个体变项，函数变项，谓词变项）指定特殊的常项去代替，就构成了一个公式的解释，常使公式成为命题。定义 一个解释由下面四部分组成 (1) 非空个体域； (2) 中一部分特定元素；（用来解释个体常元） (3) 上一些特定的函数；（用来解释函数变元） (4) 上一些特定的谓词。（用来解释谓词变元）定义 设为谓词公式，若在任何解释下都是真的，则称为逻辑有效式，或永真式；若在任何解释下，都是假的，则称为矛盾式或永假式；若至少有一个解释使为真，则为可满足式。为永真式：任何解释都为真。 逻辑有效式为永假式：任何解释都为假。 矛盾式为可满足式：存在一个解释使为真。二、 等值演算 命题公式间有等值的概念，谓词公式间也有等值的概念。定义 设为任两个谓词公式，若为永真式，则称与是等值的，记作.称为等值式。定义 设是含命题变元的命题公式，是个谓词公式，用处处代换，所得公式称为的代换实例。如 是的代换实例； 是的代换实例； 是的代换实例；（永真式）是的代换实例；（永真式） 因此，第一节给出的24个命题公式等值式及其代换实例都是谓