离散数学电子教材1

1第1章命题逻辑逻辑是研究人的思维的科学，包括辩证逻辑和形式逻辑。辩证逻辑是研究反映客观世界辩证发展过程的人类思维的形态的。形式逻辑是研究思维的形式结构和规律的科学，它撇开具体的、个别的思维内容，从形式结构方面研究概念、判断和推理及其正确联系的规律。数理逻辑是用数学方法研究推理的形式结构和推理的规律的数学学科。所谓的数学方法也就是用一套有严格定义的符号，即建立一套形式语言来研究。因此数理逻辑也称为符号逻辑。数理逻辑的基础部分是命题逻辑和谓词逻辑。本章主要讲述命题逻辑，谓词逻辑将在第2章进行讨论。1.1命题及其表示1.1.1命题的基本概念数理逻辑研究的中心问题是推理（Inference)，而推理就必然包含前提和结论，前提和结论都是表达判断的陈述句，因而表达判断的陈述句就成为推理的基本要素。在数理逻辑中，将能够判断真假的陈述句称为命题。因此命题就成为推理的基本单位。在命题逻辑中，对命题的组成部分不再进一步细分。定义1.1.1能够判断真假的陈述句称为命题（Proposition）。命题的判断结果称为命题的真值，常用T(True)（或1）表示真，F(False)（或0）表示假。真值为真的命题称为真命题，真值为假的命题称为假命题。从上述的定义可知，判定一个句子是否为命题要分为两步：一是判定是否为陈述句，二是能否判定真假，二者缺一不可。例1.1.1判断下列句子是否为命题（1）北京是中国的首都。（2）请勿吸烟！（3）雪是黑的。（4）明天开会吗？（5）x+y=5。（6）我正在说谎。（7）9+5≤12。（8）1+101=110。（9）今天天气多好啊！（10）别的星球上有生物。解在上述的十个句子中，（2）、（9）为祈使句，（4）为疑问句，（5）、（6）虽然是陈述句，但（5）没有确定的真值，其真假随x、y取值的不同而有改变，（6）是悖论(Paradox)（即由真能推出假，由假也能推出真），因而（2）、（4）、（5）、（6）、（9）均不是命题。（1）、（3）、（7）、（8）、（10）都是命题，其中（10）虽然现在无法判断真假，但随着科技的进步是可以判定真假的。需要进一步指出的是，命题的真假只要求它有就可以，而不要求立即给出。如例1.1.1的（8）1+101=110，它的真假意义通常和上下文有关，当作为二进制的加法时，它是真命题，否则为假命题。还有的命题的真假不能马上给出，如例1.1.1的（10），但它确实有真假意义。1.1.2命题分类根据命题的结构形式，命题分为原子命题和复合命题。2定义1.1.2不能被分解为更简单的陈述语句的命题称为原子命题(SimpleProposition)。由两个或两个以上原子命题组合而成的命题称为复合命题(CompoundProposition)。例如，例1.1.1中的命题全部为原子命题，而命题“小王和小李都去公园。”是复合命题，是由“小王去公园。”与“小李去公园。”两个原子命题组成的。1.1.3命题标识符定义1.1.3表示原子命题的符号称为命题标识符(Identifier)。通常用大写字母A，B，C，…，P，Q，…等表示命题，如P：今天下雨。命题标识符依据表示命题的情况，分为命题常元和命题变元。一个表示确定命题的标识符称为命题常元（或命题常项）(Propositionalconstant)；没有指定具体内容的命题标识符称为命题变元（或命题变项）(PropositionalVariable)。命题变元的真值情况不确定，因而命题变元不是命题。只有给命题变元P一具体的命题取代时，P有了确定的真值，P才成为命题。习题1.11．判断下列语句是否为命题，若是，指出其真值。（1）外面下雨吗？（2）7能被2整除。（3）2x+34。（4）请关上门。（5）小红在教室里。2．指出下列命题是原子命题还是复合命题。（1）小李一边看书，一边听音乐。（2）北京不是中国的首都。（3）大雁北回，春天来了。（4）不是东风压倒西风，就是西风压倒东风。（5）张三与李四在吵架。1.2逻辑联结词本节主要介绍5种常用的逻辑联结词(LogicalConnectives)，分别是“非”（否定联结词）、“与”（合取联结词）、“或”（析取联结词）、“若…则…”（条件联结词）、“…当且仅当…”（双条件联结词），通过这些联结词可以把多个原子命题复合成一个复合命题。下面分别给出各自的符号形式及真值情况。1.2.1否定联结词定义1.2.1设P为一命题，P的否定(Negation)是一个新的命题，记为P（读作非P）。规定若P为T，则P为F；若P为F，则P为T。P的取值情况依赖于P的取值情况，真值情况见表1-1。表1-1PP1001在自然语言中，常用“非”、“不”、“没有”、“无”、“并非”等来表示否定。3例1.2.1P：上海是中国的城市。P：上海不是中国的城市。P是真命题，P是假命题。Q：所有的海洋动物都是哺乳动物。Q：不是所有的海洋动物都是哺乳动物。Q为假命题，Q为真命题。1.2.2合取联结词定义1.2.2设P、Q为两个命题，P和Q的合取(Conjunction)是一个复合命题，记为PQ（读作P与Q），称为P与Q的合取式。规定P与Q同时为T时，PQ为T，其余情况下，PQ均为F。联结词“”的定义见表1-2。表1-2联结词“”的定义PQPQ000010100111显然PP的真值永远是假，称为矛盾式。在自然语言中，常用“既…又…”、“不但…而且…”、“虽然…但是…”、“一边…一边…”等表示合取。例1.2.2（1）今天下雨又刮风。设P：今天下雨。Q：今天刮风。则（1）可表示为PQ（2）猫吃鱼且太阳从西方升起。设P：猫吃鱼。Q：太阳从西方升起。则（2）可表示为PQ（3）张三虽然聪明但不用功。P：张三聪明。Q：张三用功。则（3）可表示为PQ需要注意的是，在自然语言中，命题（2）是没有实际意义的，因为P与Q两个命题是互不相干的，但在数理逻辑中是允许的，数理逻辑中只关注复合命题的真值情况，并不关心原子命题之间是否存在着内在联系。1.2.3析取联结词定义1.2.3设P、Q为两个命题，P和Q的析取(Disjunction)是一个复合命题，记为PQ（读作P或Q），称为P与Q的析取式。规定当且仅当P与Q同时为F时，PQ为F，否则PQ均为T。析取联结词“”的定义见表1-3。表1-3联结词“”的定义PQPQ000011101111显然PP的真值永远为真，称为永真式。析取联结词“”与汉语中的“或”二者表达的意义不完全相同，汉语中的“或”可4表达“排斥或”，也可以表达“可兼或”，而从析取联结词的定义可看出，“”允许P、Q同时为真，因而析取联结词“”是可兼或。对于“排斥或”将在1.6中论述。例1.2.3（1）小王爱打球或跑步。（2）他身高1.8m或1.85m。（1）为可兼或，（2）为排斥或。设P：小王爱打球。Q：小王爱跑步。则（1）可表示为PQ设P：他身高1.8米。Q：他身高1.85米。则（2）可表示为（PQ）（PQ）1.2.4条件联结词定义1.2.4设P、Q为两个命题，P和Q的条件(Conditional)命题是一个复合命题，记为PQ（读作若P则Q），其中P称为条件的前件，Q称为条件的后件。规定当且仅当前件P为T，后件Q为F时，PQ为F，否则PQ均为T。条件联结词“”的定义见表1-4。表1-4联结词“”的定义PQPQ001011100111在自然语言中，常会出现的语句如“只要P就Q”、“因为P所以Q”、“P仅当Q”、“只有Q才P”、“除非Q才P”等都可以表示为“PQ”的形式。例1.2.4（1）如果雪是黑色的，则太阳从西方升起。（2）仅当天气好，我才去公园。对于（1），设P：雪是黑色的。Q：太阳从西方升起。则（1）可表示为PQ（2）设R：天气好。S：我去公园。则（2）可表示为SR1.2.5双条件联结词定义1.2.5设P、Q为两个命题，其复合命题PQ称为双条件(Biconditional)命题，PQ读作P当且仅当Q。规定当且仅当P与Q真值相同时，PQ为T，否则PQ均为F。双条件联结词“”的定义如表1-5所示。表1-5PQPQ001010100111例1.2.5（1）雪是黑色的当且仅当2+24。（2）燕子北回，春天来了。（1）设P：雪是黑色的。Q：2+24。则（1）可表示为PQ，其真值为T。（2）设R：燕子北回。S：春天来了。则（2）可表示为RS，其真值为T。与前面的联结词一样，条件联结词和双条件联结词连接的两个命题之间可以没有任何的因果联系，只要能确定复合命题的真值即可。5习题1.21．指出下列命题的真值：（1）若2+24，则太阳从西方升起。（2）若a，则aA。（3）胎生动物当且仅当是哺乳动物。（4）指南针永指北方，除非它旁边有磁铁。（5）除非ABCD是平行四边形,否则它的对边不都平行。2．令P：天气好。Q：我去公园。请将下列命题符号化。（1）如果天气好，我就去公园。（2）只要天气好，我就去公园。（3）只有天气好，我才去公园。（4）我去公园，仅当天气好。（5）或者天气好，或者我去公园。（6）天气好，我去公园。1.3命题公式与翻译1.3.1命题公式上一节介绍了5种常用的逻辑联结词，利用这些逻辑联结词可将具体的命题表示成符号化的形式。对于较为复杂的命题，需要由这5种逻辑联结词经过各种相互组合以得到其符号化的形式，那么怎样的组合形式才是正确的、符合逻辑的表示形式呢？定义1.3.1（1）单个的命题变元是命题公式。（2）如果A是命题公式，那么A也是命题公式。（3）如果A、B是命题公式，那么(A∧B),（A∨B),(A→B)和(AB)也是命题公式。（4）当且仅当能够有限次地应用（1）、（2）、（3）所得到的包含命题变元、联结词和括号的符号串是命题公式（又称为合式公式，或简称为公式）。上述定义是以递归的形式给出的，其中（1）称为基础，（2）、（3）称为归纳，（4）称为界限。由定义知,命题公式是没有真假的，仅当一个命题公式中的命题变元被赋以确定的命题时，才得到一个命题。例如在公式QP中，把命题“雪是白色的。”赋给P，把命题“2+24。”赋给Q，则公式QP被解释为假命题；但若P的赋值不变，而把命题“2+2=4。”赋给Q，则公式QP被解释为真命题。定义中的符号A,B不同于具体公式里的P、Q、R等符号，它可以用来表示任意的命题公式。例1.3.1)(QP，))((RQP，))()((RQQP等都是命题公式，而6)(QP，QP(，))(RQP等都不是命题公式。为了减少命题公式中使用括号的数量，规定：（1）逻辑联结词的优先级别由高到低依次为、∧、∨、→、。（2）具有相同级别的联结词，按出现的先后次序进行计算，括号可以省略。（3）命题公式的最外层括号可以省去。例1.3.2RQP)(也可以写成RQP，RQP)(也可写成RQP，))((RQP也可写成RQP)(，而)(RQP中的括号不能省去。定义1.3.2设P是命题公式Q的一部分，且P也是命题公式，则称P为Q的子公式。例如QP及R都是公式RQP的子公式；P、QP及RP都是公式()()PQPR的子公式。1.3.2命题的符号化有了命题公式的概念之后，就可以把自然语言中的一些命题翻译成命题逻辑中的符号化形式。把一个文字描述的命题相应地写成由命题标识符、逻辑联结词和圆括号表示的命题形式称为命题的符号化或翻译。命题符号化的一般步骤：（1）明确给定命题的含义；（2）找出命题中的各原子命题，分别符号化。（3）使用合适的逻辑联结词，将原子命题分别连接起来，组成复合命题的符号化形式。把命题符号化，是不管具体内容而突出思维形式的一种方法。注意在命题符号化时，要正确地分析和理解自然语言命题，不能仅凭文字的字面意思进行翻译。例1.3.3张三或李四都可以做这件事。设P：张三可以做这件事。Q：李四可以做这件事。则命题符号化为：QP，而不是QP。例1.3.4（1）只有你走，我才留下。这个命题的意义也可