离散数学王元元习题解答.doc

《离散数学王元元习题解答.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、.1命题演算及其形式系统1.1命题与联结词内容提要1.1.1命题我们把对确定的对象作出判断的陈述句称作命题（propositions），当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。“真、假”常被称为命题的真值。自然语言中“并非、或者、并且、如果…，那么…、当且仅当”这样的联结词称为逻辑联结词（logicalconnectives）。通常把不含有逻辑联结词的命题称为原子命题或原子（atoms），而把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositivepropositions）。1.1.2联结词否定词(nega

2、tion)“并非”（not），用符号┐表示。设p表示一命题，那么┐p表示命题p的否定。p真时┐p假，而p假时┐p真。┐p读作“并非p”或“非p”。合取词(conjunction)“并且”（and），用符号∧表示。设p，q表示两命题，那么p∧q表示合取p和q所得的命题，即p和q同时为真时p∧q真，否则p∧q为假。p∧q读作“p并且q”或“p且q”。析取词(disjunction)“或”（or）用符号∨表示。设p，q表示两命题，那么p∨q表示p和q的析取，即当p和q有一为真时，p∨q为真，只有当p和q均假时p∨q为假。p∨q读作“p或者q”、“p或q”。蕴涵词(imp

3、lication)“如果……，那么……”（if…then…），用符号→表示。设p，q表示两命题，那么p→q表示命题“如果p，那么q”。当p真而q假时，命题p→q为假，否则均认为p→q为真。p→q中的p称为蕴涵前件，q称为蕴涵后件。p→q的读法较多，可读作“如果p则q”，“p蕴涵q”，“p是q的充分条件”，“q是p的必要条件”，“q当p”，“p仅当q”等等。数学中还常把q→p，┐p→┐q，┐q→┐p分别叫做p→q的逆命题，否命题，逆否命题。双向蕴涵词(two-wayimplication)“当且仅当”（ifandonlyif），用符号«表示之。设p，q为两命题，那么

4、p«q表示命题“p当且仅当q”，“p与q等价”，即当p与q同真值时p«q为真，否则为假。p«q读作“p双向蕴涵q”，“p当且仅当q”，“p等价于q”。由于“当且仅当”“等价”常在其它地方使用，因而用第一种读法更好些。1.1.3命题公式及其真值表我们把表示具体命题及表示常命题的p，q，r，s与f，t统称为命题常元（propositionconstant）。深入的讨论还需要引入命题变元（propositionvariable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。定义1.1以下三条款规定了命题公式（prop

5、ositionformula）的意义：（1）命题常元和命题变元是命题公式，也称为原子公式或原子。（2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A«B）也是命题公式。（3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。如果公式A含有命题变元p1，p2，…，pn，记为A(p1,…,pn)，并把联结词看作真值运算符，那么公式A可以看作是p1,…,pn的真值函数。对任意给定的p1,…,pn的一种取值状况，称为指派（assignments），用希腊字母a，b等表示，A均有一个确定的真值。当A对取值状况a为真时，称指派a弄真A，或

6、a是A的成真赋值，记为a(A)=1；反之称指派a弄假A，或a是A的成假赋值，记为a(A)=0。对一切可能的指派,公式A的取值可能可用一张表来描述,这个表称为真值表（truthtable）。当A(p1,…,pn)中有k个联结词时，公式A的真值表应为2n行、k+n列（不计表头）。1.1.4语句的形式化用我们已有的符号语言，可以将许多自然语言语句形式化。语句形式化要注意以下几个方面。要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”..是一个概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。要善于识别自然语言中的联结词（有时它们被省略）。例如“风

7、雨无阻，我去上学”一句，可理解为“不管是否刮风、是否下雨我都去上学”。否定词的位置要放准确。需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。另外要注意的是,语句的形式化未必是唯一的。习题解答练习1.11、判断下列语句是否是命题，若是命题则请将其形式化：（1）a+b（2）x>0（3）“请进！”（4）所有的人都是要死的，但有人不怕死。（5）我明天或后天去苏州。（6）我明天或后天去苏州的说法是谣传。（7）我明天或后天去北京或天津。（8）如果买不到飞机票，我哪儿也不去。（9）只要他出门，他必买书，不管他余款多不多。（10）除非你陪伴我或代我雇辆车子

8、，否则我不