电子行业企业管理离散数学电子教材.docx
《电子行业企业管理离散数学电子教材.docx》由会员分享，可在线阅读，更多相关《电子行业企业管理离散数学电子教材.docx（54页珍藏版）》请在冰点文库上搜索。
电子行业企业管理离散数学电子教材
第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命题分类
根据命题的结构形式，命题分为原子命题和复合命题。
定义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.1
1．判断下列语句是否为命题，若是，指出其真值。
（1）外面下雨吗？
（2）7能被2整除。
（3）2x+3<4。
（4）请关上门。
（5）小红在教室里。
2．指出下列命题是原子命题还是复合命题。
（1）小李一边看书，一边听音乐。
（2）北京不是中国的首都。
（3）大雁北回，春天来了。
（4）不是东风压倒西风，就是西风压倒东风。
（5）张三与李四在吵架。
1.2逻辑联结词
本节主要介绍5种常用的逻辑联结词（LogicalConnectives），分别是“非”（否定联结词）、“与”（合取联结词）、“或”（析取联结词）、“若…则…”（条件联结词）、“…当且仅当…”（双条件联结词），通过这些联结词可以把多个原子命题复合成一个复合命题。
下面分别给出各自的符号形式及真值情况。
1.2.1否定联结词
定义1.2.1设P为一命题，P的否定（Negation）是一个新的命题，记为（读作非P）。
规定若P为T，则为F；若P为F，则为T。
的取值情况依赖于P的取值情况，真值情况见表1-1。
表1-1
P
1
0
0
1
在自然语言中，常用“非”、“不”、“没有”、“无”、“并非”等来表示否定。
例1.2.1P：
上海是中国的城市。
：
上海不是中国的城市。
P是真命题，是假命题。
Q：
所有的海洋动物都是哺乳动物。
：
不是所有的海洋动物都是哺乳动物。
Q为假命题，为真命题。
1.2.2合取联结词
定义1.2.2设P、Q为两个命题，P和Q的合取（Conjunction）是一个复合命题，记为PQ（读作P与Q），称为P与Q的合取式。
规定P与Q同时为T时，PQ为T，其余情况下，PQ均为F。
联结词“”的定义见表1-2。
表1-2联结词“”的定义
P
Q
PQ
0
0
0
0
1
0
1
0
0
1
1
1
显然P的真值永远是假，称为矛盾式。
在自然语言中，常用“既…又…”、“不但…而且…”、“虽然…但是…”、“一边…一边…”等表示合取。
例1.2.2
（1）今天下雨又刮风。
设P：
今天下雨。
Q：
今天刮风。
则
（1）可表示为PQ
（2）猫吃鱼且太阳从西方升起。
设P：
猫吃鱼。
Q：
太阳从西方升起。
则
（2）可表示为PQ
（3）张三虽然聪明但不用功。
P：
张三聪明。
Q：
张三用功。
则（3）可表示为PQ
需要注意的是，在自然语言中，命题
（2）是没有实际意义的，因为P与Q两个命题是互不相干的，但在数理逻辑中是允许的，数理逻辑中只关注复合命题的真值情况，并不关心原子命题之间是否存在着内在联系。
1.2.3析取联结词
定义1.2.3设P、Q为两个命题，P和Q的析取（Disjunction）是一个复合命题，记为PQ（读作P或Q），称为P与Q的析取式。
规定当且仅当P与Q同时为F时，PQ为F，否则PQ均为T。
析取联结词“”的定义见表1-3。
表1-3联结词“”的定义
P
Q
PQ
0
0
0
0
1
1
1
0
1
1
1
1
显然的真值永远为真，称为永真式。
析取联结词“”与汉语中的“或”二者表达的意义不完全相同，汉语中的“或”可表达“排斥或”，也可以表达“可兼或”，而从析取联结词的定义可看出，“”允许P、Q同时为真，因而析取联结词“”是可兼或。
对于“排斥或”将在1.6中论述。
例1.2.3
（1）小王爱打球或跑步。
（2）他身高1.8m或1.85m。
（1）为可兼或，
（2）为排斥或。
设P：
小王爱打球。
Q：
小王爱跑步。
则
（1）可表示为PQ
设P：
他身高1.8米。
Q：
他身高1.85米。
则
（2）可表示为（PQ）（PQ）
1.2.4条件联结词
定义1.2.4设P、Q为两个命题，P和Q的条件（Conditional）命题是一个复合命题，记为PQ（读作若P则Q），其中P称为条件的前件，Q称为条件的后件。
规定当且仅当前件P为T，后件Q为F时，PQ为F，否则PQ均为T。
条件联结词“”的定义见表1-4。
表1-4联结词“”的定义
P
Q
PQ
0
0
1
0
1
1
1
0
0
1
1
1
在自然语言中，常会出现的语句如“只要P就Q”、“因为P所以Q”、“P仅当Q”、“只有Q才P”、“除非Q才P”等都可以表示为“PQ”的形式。
例1.2.4
（1）如果雪是黑色的，则太阳从西方升起。
（2）仅当天气好，我才去公园。
对于
（1），设P：
雪是黑色的。
Q：
太阳从西方升起。
则
（1）可表示为PQ
（2）设R：
天气好。
S：
我去公园。
则
（2）可表示为SR
1.2.5双条件联结词
定义1.2.5设P、Q为两个命题，其复合命题PQ称为双条件（Biconditional）命题，PQ读作P当且仅当Q。
规定当且仅当P与Q真值相同时，PQ为T，否则PQ均为F。
双条件联结词“”的定义如表1-5所示。
表1-5
P
Q
PQ
0
0
1
0
1
0
1
0
0
1
1
1
例1.2.5
（1）雪是黑色的当且仅当2+2>4。
（2）燕子北回，春天来了。
（1）设P：
雪是黑色的。
Q：
2+2>4。
则
（1）可表示为PQ，其真值为T。
（2）设R：
燕子北回。
S：
春天来了。
则
（2）可表示为RS，其真值为T。
与前面的联结词一样，条件联结词和双条件联结词连接的两个命题之间可以没有任何的因果联系，只要能确定复合命题的真值即可。
习题1.2
1．指出下列命题的真值：
（1）若2+2>4，则太阳从西方升起。
（2）若a，则aA。
（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）如果是命题公式，那么也是命题公式。
（3）如果、是命题公式，那么（∧）,（∨）,（→）和
（）也是命题公式。
（4）当且仅当能够有限次地应用
（1）、
（2）、（3）所得到的包含命题变元、联结词和括号的符号串是命题公式（又称为合式公式，或简称为公式）。
上述定义是以递归的形式给出的，其中
（1）称为基础，
（2）、（3）称为归纳，（4）称为界限。
由定义知,命题公式是没有真假的，仅当一个命题公式中的命题变元被赋以确定的命题时，才得到一个命题。
例如在公式中，把命题“雪是白色的。
”赋给，把命题“2+2>4。
”赋给，则公式被解释为假命题；但若的赋值不变，而把命题“2+2=4。
”赋给，则公式被解释为真命题。
定义中的符号,不同于具体公式里的、、等符号，它可以用来表示任意的命题公式。
例1.3.1，，等都是命题公式，而，，等都不是命题公式。
为了减少命题公式中使用括号的数量，规定：
（1）逻辑联结词的优先级别由高到低依次为、∧、∨、→、。
（2）具有相同级别的联结词，按出现的先后次序进行计算，括号可以省略。
（3）命题公式的最外层括号可以省去。
例1.3.2也可以写成，也可写成，也可写成，而中的括号不能省去。
定义1.3.2设是命题公式的一部分，且也是命题公式，则称为的子公式。
例如及都是公式的子公式；、及都是公式的子公式。
1.3.2命题的符号化
有了命题公式的概念之后，就可以把自然语言中的一些命题翻译成命题逻辑中的符号化形式。
把一个文字描述的命题相应地写成由命题标识符、逻辑联结词和圆括号表示的命题形式称为命题的符号化或翻译。
命题符号化的一般步骤：
（1）明确给定命题的含义；
（2）找出命题中的各原子命题，分别符号化。
（3）使用合适的逻辑联结词，将原子命题分别连接起来，组成复合命题的符号化形式。
把命题符号化，是不管具体内容而突出思维形式的一种方法。
注意在命题符号化时，要正确地分析和理解自然语言命题，不能仅凭文字的字面意思进行翻译。
例1.3.3张三或李四都可以做这件事。
设：
张三可以做这件事。
：
李四可以做这件事。
则命题符号化为：
，而不是。
例1.3.4
（1）只有你走，我才留下。
这个命题的意义也可以理解为：
如果我留下了，那么你一定走了。
设：
你走。
：
我留下。
则命题符号化为：
。
与原命题类似的命题如：
仅当你走我才留下。
我留下仅当你走。
当我留下你得走。
注意：
在一般的命题表述中，“仅当”是必要条件，译成条件命题时其后的命题是后件，而“当”是充分条件，译成条件命题时其后的命题是前件。
（2）仅当天不下雨且我有时间，我才上街。
设：
天下雨。
：
我有时间。
：
我上街。
命题符号化为：
。
（3）你将失败，除非你努力。
这个命题的意义可以理解为：
如果你不努力，那么你将失败。
设：
你努力。
：
你失败。
则命题符号化为：
。
含有“除非”的命题，“非…”是充分条件，译成条件命题时，“非…”是条件的前件。
（4）中没有元素，就是空集。
设：
中有元素。
：
是空集。
则命题符号化为：
（5）张三与李四是表兄弟。
此命题是一个原子命题，“…与…是表兄弟。
”表示两个对象之间的关系。
“张三是表兄弟。
”及“李四是表兄弟。
”都不是命题。
所以上述命题只能符号化为的形式。
其中：
张三与李四是表兄弟。
例1.3.5将下列命题符号化。
（1）如果明天早上下雨或下雪，则我不去学校。
（2）如果明天早上不下雨且不下雪，则我去学校。
（3）如果明天早上不是雨夹雪，则我去学校。
（4）当且仅当明天早上不下雨且不下雪时，我才去学校。
设：
明天早上下雨。
：
明天早上下雪。
：
我去学校。
（1）符号化为：
（2）符号化为：
（3）符号化为：
（4）符号化为：
例1.3.6将下列命题符号化。
（1）如果小王和小张都不去，则小李去。
（2）如果小王和小张不都去，则小李去。
设：
小王去。
：
小张去。
：
小李去。
（1）符号化为：
（2）符号化为：
或
例1.3.7将下列命题符号化。
（1）说离散数学无用且枯燥无味是不对的。
（2）若天不下雨，我就上街；否则在家。
对于
（1），设：
离散数学是有用的。
：
离散数学是枯燥无味的。
则命题符号化为：
。
对于
（2），设：
天下雨。
：
我上街。
：
我在家。
则命题符号化为：
。
通过上述的例题可以看出，要正确地将自然语言中的联结词翻译成恰当的逻辑联结词，必须要正确地理解各原子命题之间的关系。
习题1.3
1．判断下列各式子是否是命题公式
（1）
（2）
（3）
（4）
（5）
（6）
2．将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）
（1）我去新华书店，仅当我有时间。
（2）我们不能既划船又跑步。
（3）只要努力学习，成绩就会好的。
（4）或者你没有给我写信，或者它在路上丢了。
（5）如果上午不下雨，我就去看电影，否则我就在家里读书或看报纸。
（6）我今天进城，除非下雨。
（7）如果太阳没出来，则或者下雨或者阴天而且温度下降。
（8）指南针永指南北，除非它旁边有磁铁。
（9）说逻辑枯燥无味和毫无价值是不对的。
（10）人不犯我，我不犯人；人若犯我，我必犯人。
1.4真值表与等价公式
1.4.1真值表
定义1.4.1设，，…，是出现在命题公式中的全部命题变元，给，，…，各指定一个真值，称为对公式的一个赋值（或解释或真值指派）。
若指定的一组值使公式的真值为1，则这组值称为公式的成真赋值。
若指定的一组值使公式的真值为0，则这组值称为公式的成假赋值。
例如，对公式，赋值011（即令，则可得到公式的真值为1；若赋值000，则公式真值为0。
因此，011为公式的一个成真赋值；000为公式的一个成假赋值。
除了上述的两种赋值外，公式的赋值还有000，001，…等。
一般的结论是在含有n个命题变元的命题公式中，共有种赋值。
定义1.4.2将命题公式在所有赋值下的取值情况列成表，称为公式的真值表（TruthTable）。
构造真值表的基本步骤：
（1）找出公式中所有的命题变元，，…，，按二进制从小到大的顺序列出种赋值。
（2）当公式较为复杂时，按照运算的顺序列出各个子公式的真值。
（3）计算整个命题公式的真值。
例1.4.1写出下列公式的真值表，并求其成真赋值和成假赋值。
（1）
（2）
（3）
解
（1）的真值表见表1-6。
表1-6的真值表
0
0
1
1
0
1
1
1
1
0
0
0
1
1
0
1
成真赋值为00，01，11，成假赋值为10。
（2）的真值表见表1-7。
表1-7的真值表
0
0
1
0
0
0
1
1
0
0
1
0
0
1
0
1
1
1
0
0
无成真赋值，成假赋值为00，01，10，11。
（3）的真值表见表1-8。
表1-8的真值表
0
0
0
1
1
1
0
1
0
1
1
1
1
0
0
1
1
1
1
1
1
0
0
1
成真赋值为00，01，10，11，无成假赋值。
1.4.2等价公式
定义1.4.3给定两个命题公式，设，，…，是出现在命题公式中的全部命题变元，若给，，…，任一组赋值，公式和的真值都对应相同，则称公式与等价或逻辑相等（Equivalence），记作。
需要注意的是，“”不是逻辑联结词，因而“”不是命题公式，只是表示两个命题公式之间的一种等价关系，即若，和没有本质上的区别，最多只是和具有不同的形式而已。
“”具有如下的性质：
（1）自反性：
。
（2）对称性：
若，则。
（3）传递性：
若，，则。
给定n个命题变元，根据公式的形成规则，可以形成许多个形式各异的公式，但是有很多形式不同的公式具有相同的真值表。
因此引入公式等价的概念，其目的就是将复杂的公式简化。
下面介绍两种证明公式等价的方法。
1．真值表法
由公式等价的定义可知，利用真值表可以判断任何两个公式是否等价。
例1.4.2证明
证明命题公式与的真值表见表1-9。
由表1-9可知，在任意赋值下与两者的真值均对应相同。
因此
表1-9与的真值表
0
0
1
1
1
1
0
1
1
0
0
0
1
0
0
1
0
0
1
1
1
1
1
1
例1.4.3判断公式与二者是否等价。
证明公式与的真值表见表1-10。
表1-10与的真值表
0
0
1
1
0
1
1
0
1
0
0
1
1
1
1
1
可见真值表中的最后两列值不完全相同，因此公式与不等价。
从理论上来讲，利用真值表法可以判断任何两个命题公式是否等价，但是真值表法并不是一个非常好的方法，因为当公式中命题变元较多时，其计算量较大，例如当公式中有四个变元时，需要列出=16种赋值情况，计算较为繁杂。
因此，通常采用其他的证明方法。
这种证明方法是先用真值表法验证出一些等价公式，再用这些等价公式来推导出新的等价公式，以此作为判断两个公式是否等价的基础。
下面给出12组常用的等价公式，它们是进一步推理的基础。
牢记并熟练运用这些公式是学好数理逻辑的关键之一。
（1）双重否定律：
（2）结合律：
，，
（3）交换律：
，，
（4）分配律：
，
（5）幂等律：
，
（6）吸收律：
，
（7）德.摩根律：
，
（8）同一律：
（9）零律：
（10）否定律：
（11）条件等价式：
（12）双条件等价式：
上述12组公式均可以通过构造真值表法来证明。
2．等值演算法
定理1.4.1（代入规则）在一个永真式中，任何一个原子命题变元出现的每一处用另一个公式代入，所得的公式仍为永真式。
证明：
因为永真式对于任何指派，其真值都是1，与每个命题变元指派的真假无关，所以，用一个命题公式代入到原子命题变元出现的每一处，所得到的命题公式的真值仍为1。
例如，是永真式，将原子命题变元用代入后得到的式子仍为永真式。
定理1.4.2（置换规则）设是命题公式的一个子公式，若，如果将公式中的用来置换，则所得到的公式与公式等价，即。
证明：
因为，所以在相应变元的任一种指派情况下，与的真值相同，故以取代后，公式与公式在相应的指派情况下真值也必相同，因此。
例如，利用置换，则。
从定理可以看出，代入规则是对原子命题变元而言，而置换规则可对命题公式进行；代入必须处处代入，替换可以部分或全部替换；代入规则可以用来扩大永真式的个数，替换规则可以增加等价式的个数。
有了上述的12组等价公式及代入规则和置换规则后，就可以推演出更多的等价式。
由已知等价式推出另外一些等价式的过程称为等值演算（EquivalentCalculation）。
例1.4.4证明下列公式等价。
（1）
（2）
证明
（1）
（2）
例1.4.5某件事情是甲、乙、丙、丁4人中某一个人干的。
询问4人后回答如下：
（1）甲说是丙干的；
（2）乙说我没干；（3）丙说甲讲的不符合事实；（4）丁说是甲干的。
若其中3人说的是真话，一人说假话，问是谁干的？
解设：
这件事是甲干的。
：
这件事是乙干的。
：
这件事是丙干的。
：
这件事是丁干的。
4个人所说的命题分别用、、、表示，则
（1）、
（2）、（3）、（4）分别符号化为：
；；；
则3人说真话，一人说假话的命题符号化为：
其中
同理
所以，当为真时，为真，即这件事是甲干的。
本题也可以从题干直接找出相互矛盾的两个命题作为解题的突破口。
甲、丙两人所说的话是相互矛盾的，必有一人说真话，一人说假话，而4个人中只有一人说假话，因此乙、丁两人必说真话，由此可断定这件事是甲干的。
例1.4.6在某次球赛中，3位球迷甲、乙、丙对某球队的比赛结果进行猜测。
甲说：
该球队不会得第一名，是第二名。
乙说：
该球队不会得第二名，是第一名。
丙说：
该球队不会得第二名，也不会是第三名。
比赛结束后，结果证实甲、乙、丙3人中有一人猜的全对，有一人猜对一半，有一人猜的全错。
试分析该球队究竟是第几名。
解设：
该球队获得第一名。
：
该球队获得第二名。
：
该球队获得第三名。
则、、中必然有一个真命题，两个假命题。
设甲、乙、丙3人所说的命题分别用，，表示。
则有，，。
设甲、乙、丙的判断全对分别用、、表示，甲、乙、丙的判断对一半分别用、、表示，甲、乙、丙的判断全错分别用、、表示。
则有：
。
（由于该球队不可能既是第一名又是第二名，所以）。
。
。
。
。
。
。
。
甲、乙、丙3人中有一人全对，有一人猜对一半，有一人全错的命题符号化为
其中，。
同理，，，
（由于该球队不可能既是第一名，又是第三名），
。
因此，若为真，只有为真。
因而为真命题，为假命题。
即该球队获得第二名。
甲的判断全对，乙的判断全错，丙的判断对一半。
例1.4.7、、、4人进行百米竞赛，观众甲、乙、丙对比赛的结果进行预测。
甲：
第一，第二；乙：
第二，第三；丙：
第二，第四。
比赛结束后发现甲、乙、丙每
升级会员 