离散数学1-1

离散数学第一章1.1命题及其表示法1.1.1 命题的概念数理逻辑将能够判断真假的陈述句称作命题。

1.1.2 命题的表示命题通常使用大写字母A，B，…，Z或带下标的大写字母或数字表示，如A i，[10]，R等，例如A1：我是一名大学生。

A1:我是一名大学生.[10]：我是一名大学生。

R：我是一名大学生。

1.2命题联结词1.2.1 否定联结词﹁PP P0 11 01.2.2 合取联结词∧P∧P Q Q0 0 00 1 01 0 01 1 11.2.3 析取联结词∨P∨P Q Q0 0 00 1 11 0 11 1 11.2.4 条件联结词→P Q Q0 0 10 1 11 0 01 1 11.2.5 双条件联结词?P?P Q Q0 0 10 1 01 0 01 1 11.2.6 与非联结词↑P↑P Q Q0 0 10 1 11 0 11 1 0性质：（1）P↑P?﹁（P∧P）?﹁P；（2）（P↑Q）↑（P↑Q）?﹁（P↑Q）? P∧Q；（3）（P↑P）↑（Q↑Q）?﹁P↑﹁Q? P∨Q。

1.2.7 或非联结词↓P↓P Q Q0 0 10 1 01 0 0性质：（1）P↓P?﹁（P∨Q）?﹁P；（2）（P↓Q）↓（P↓Q）?﹁（P↓Q）?P∨Q；（3）（P↓P）↓（Q↓Q）?﹁P↓﹁Q?﹁（﹁P∨﹁Q）?P∧Q。

1.3 命题公式、翻译与解释1.3.1 命题公式定义命题公式，简称公式，定义为：（1）单个命题变元是公式；（2）如果P是公式，则﹁P是公式；（3）如果P、Q是公式，则P∧Q、P∨Q、P→Q、P?Q 都是公式；（4）当且仅当能够有限次的应用(1) 、(2)、(3) 所得到的包括命题变元、联结词和括号的符号串是公式。

例如，下面的符号串都是公式：（（（（﹁P）∧Q）→R）∨S）（（P→﹁Q）?（﹁R∧S））（﹁P∨Q）∧R以下符号串都不是公式：（（P∨Q）?（∧Q））（∧Q）1.3.2 命题的翻译可以把自然语言中的有些语句，转变成数理逻辑中的符号形式，称为命题的翻译。

命题逻辑的基本概念命题与联结词命题：非真即假的陈述句。

真值：命题的陈述句所表达的判断结果，真值只取真或假两种情况。

假命题：真值为假的命题。

真命题：真值为真的命题。

简单命题（原子命题）：无法继续拆分的命题。

复合命题：多个原子命题通过联结词联结而成的命题。

悖论：自相矛盾的陈述句。

否定联结词：符号﹁（复合命题非p称作p的否定式，记作﹁p）合取联结词：符号∧（复合命题p且q称作p与q的合取式记作p∧q）析取联结词：符号∨（复合命题p或q称作p与q的析取式记作p∨q）蕴涵联结词：符号→（复合命题如果p，则q称为p与q的蕴涵式记作p→q，p为蕴涵式的前件，q为蕴涵式的后件）蕴涵联结词的使用及判定方法：使用：1：因为p所以q这类直抒胸臆的表达时可以直接看作：p→q2：只有p才q这类具有转折性的表达时可以直接看作：q→p判定：1：同假时为真2：后件为真前件为假时为真3：后件为真前件为真时为真其他情况皆为假等价联结词：符号↔（复合命题p当且仅当q称为p与q的等价式）等价联结词的判定：1：当p与q同时为真时为真2：当p与q同时为假时为假命题公式及其赋值命题常项（命题常元）：可以直接理解为原子命题或简单命题命题变项（命题变元）：真值可以变化的陈述句，因此命题变项不是命题合式公式：命题变项使用联结词组合成的符号串（可以当作命题用联结词组合成的复合命题）合式公式层数的判定：下面p和q都是公式或者命题常项1：当个命题变项为0层公式。

2：﹁p为1层公式3：p∧q为n+1层公式，n=max（p的层数，q的层数）4：p∨q为n+1层公式，n=max（p的层数，q的层数）5：p→q为n+1层公式，n=max（p的层数，q的层数）6：p↔q为n+1层公式，n=max（p的层数，q的层数）赋值（解释）：对公式中的命题变项指定一个真值，真值为1即该命题变项为成真赋值，真值为0即该命题变项为成假赋值。

重言式（永真式）：即该合式公式在任意赋值下取值都是真矛盾式（永假式）：即该合式公式在任意赋值下取值都是假可满足式：即至少存在一种赋值下取值为真故重言式必是可满足式，可满足式不一定是重言式，可满足式必不是矛盾式，矛盾式必不是可满足式。

离散数学常考题型梳理第1章 集合及其运算一、题型分析本章主要介绍集合论的基本概念和结论，集合的运算及其性质，以及利用运算性质进行集合表达式的化简和集合恒等式的证明等内容．经常涉及到的题型有：1-1集合与集合之间的包含、元素与集合之间的属于关系1-2幂集的计算1-3集合之间的运算1-4利用集合运算性质证明集合恒等式因此，在本章学习过程中希望大家要清楚地知道：1．集合与集合之间存在一种包含关系，当两个集合A 和B 存在关系A 包含B ，用A ⊇B 表示，或存在关系B 被A 包含，用B ⊆A 表示，这时称B 为A 的子集．注意空集∅是任意一个集合的子集，集合A 也是自己的子集．当B ⊆A 且B ≠A ，也就是说，只有B ⊂A 或A ⊃B 成立，则称B 为A 的真子集．若B 不是A 的子集，即B ⊆A 不成立时，则称A 不包含B ，记作B ⊆A ．然而，元素与集合之间存在一种从属关系，当a 是集合A 中的元素，则称a 属于A ，记作a∈A ；若a 不是集合A 中的元素，则称a 不属于A ，记作a ∉A ．因此，这两种关系一定不要混淆．2．由集合A 的所有子集组成的集合，称为A 的幂集，记作P (A )或2A ．若集合A 是由n 个元素所组成的集合，则A 的幂集由2n 元素组成．当n =3时，A 的幂集由23=8个元素组成．例如，设集合A = {0, 1, 2 }，则A 的全部子集由以下子集组成：0元子集（即空集）：∅；1元子集：{0}，{1}，{2}；2元子集：{0, 1}，{0, 2}，{1, 2}；3元子集（即集合A ）：{0, 1, 2}．因此，计算集合A 的幂集时，首先要按照上述方法写出集合A 的全部子集，然后检验写出的子集个数是否等于2n 个，其中n 是集合A 的元素个数．3．集合之间的运算有并（⋃）、交（⋂）、差（-）、补（~）和对称差（⊕）等五种运算，在做集合运算的题目时，一定要按照它们的定义进行计算．(1) 集合A 和B 的并集A B x x A ⋃=∈{或 x B ∈} 特点：由集合A 和B 的所有元素组成的集合．见图1 图1 图2(2) 集合A 和B 的交集A B x x A ⋂=∈{ 且 x B ∈}特点：由集合A 和B 的公共元素组成的集合．见图2(3) 集合A 与B 的差集A B -=∈∉{}x x A x B 且 特点：由属于A ，而不属于B 的所有元素组成的集合．见图3(4) 集合A 的补集~A ={}x x E x A ∈∉且特点：由属于全集E 但不属于集合A 的元素组成的集合．见图4补集总相对于一个全集而言，可以看作是全集E 与集合A 的差集．(5) 集合A 与B 的对称差A ⊕B ＝(A －B )⋃(B －A )或 A ⊕B ＝(A ⋃B )－(A ⋂B )特点：由分别属于集合A 与B 的元素但不属于它们公共元素组成的集合．见图5(6) 把集合A ，B 合成集合A ×B 叫做笛卡儿积，规定A ×B ＝{<x , y >∣x ∈A 且y ∈B }注意：由于有序对<x , y >中x ，y 的位置是确定的，因此A ×B 的记法也是确定的，不能写成B ×A.．笛卡儿积的运算一般不能交换.．虽然，笛卡儿积的内容是第2章2.1.1目的内容，是二元关系的预备知识，但我们认为把它作为集合的一种运算考虑更好些。

1-1，1-2（1）指出下列哪些语句是命题，那些不是命题，如果是命题，指出它的真值。

a)离散数学是计算机科学系的一门必修课。

是命题，真值为T。

b)计算机有空吗？不是命题。

c)明天我去看电影。

是命题，真值要根据具体情况确定。

d)请勿随地吐痰。

不是命题。

e)不存在最大的质数。

是命题，真值为T。

f)如果我掌握了英语，法语，那么学习其他欧洲语言就容易多了。

是命题，真值为T。

g)9+5≤12.是命题，真值为F。

h)X=3.不是命题。

i)我们要努力学习。

不是命题。

（2）举例说明原子命题和复合命题。

原子命题：我爱北京天安门。

复合命题：如果不是练健美操，我就出外旅游拉。

（3）设P 表示命题“天下雪。

”Q 表示“我将去镇上。

”R 表示命题“我有时间。

”以符号形式写出下列命题a)如果天不下雪和我有时间，那么我将去镇上。

(┓P ∧R)→Q b)我将去镇上，仅当我有时间时。

Q→R c)天不下雪。

┓P d)天下雪，那么我不去镇上。

P→┓Q（4）用汉语写出一些句子，对应下列每一个命题。

a)()Q R P ∧¬�Q:我将去参加舞会。

R:我有时间。

P:天下雨。

Q ↔(R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。

b)R Q∧R:我在看电视。

Q:我在吃苹果。

R∧Q:我在看电视边吃苹果。

c)()()Q R R Q →∧→Q:一个数是奇数。

R:一个数不能被2除。

（Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。

(5)将下列命题符号化。

a)王强身体很好，成绩也很好。

设P：王强身体很好。

Q：王强成绩很好。

P∧Qb)小李一边看书，一边听音乐。

设P：小李看书。

Q：小李听音乐。

P∧Qc)气候很好或很热。

设P：气候很好。

Q：气候很热。

P∨Qd)如果a 和b 是偶数，则a b +是偶数。

设P：a 和b 是偶数。

Q：a+b 是偶数。

P→Qe)四边形ABCD 是平行四边形，当且仅当它的对边平行。

1.1 命题1-1-1 命题命题是一个能表达判断并具有确定真值的陈述句。

1-1-2 真值作为命题的陈述句所表达的判断结果称为命题的真值。

真值只有真和假两种，通常记为T和F。

真值为真的命题称为真命题，真值为假的命题称为假命题。

真命题表达的判断正确，假命题表达的判断错误。

任何命题的真值都是唯一的。

1-1-3 命题变项用命题标识符（大写字母）来表示任意命题时，该命题标识符称为命题变项。

1-1-4 简单命题无法继续分解的简单陈述句称为简单命题或原子命题。

(不包含任何与、或、非一类联结词的命题)1-1-5 复合命题由一个或几个简单命题通过联结词复合所构成的新的命题，称为复合命题，也称分子命题。

1.2 命题联结词及真值表1-2-1 命题联结词命题联结词可将命题联结起来构成复杂的命题，是由已有命题定义新命题的基本方法。

命题联结词又可分为一元命题联结词、二元命题联结词和多元命题联结词。

常用的命题联结词包括否定词、合取词、析取词、蕴涵词和双条件词。

其它联结词还包括异或（不可兼或）、与非和或非等。

1-2-2 否定词否定词是一元命题联结词。

设P为一命题，P的否定是一个新的命题，记作P，读作非P。

若P为T，P为T；若P为F，P为T。

1-2-3 合取词合取词是二元命题联结词。

两个命题P和Q的合取构成一个新的命题，记作P∧Q。

读作P、Q的合取（或读作P与Q，P且Q）。

当且仅当P、Q 同时为T时，P∧Q为T。

否则，P∧Q的真值为F。

1-2-4 析取词析取词是二元命题联结词。

两个命题P和Q的析取构成一个新的命题，记作P∨Q。

读作P、Q的析取（也读作P或Q）。

当且仅当P、Q同时为F 时，P∨Q的真值为F。

否则，P∨Q的真值为T。

1-2-5 蕴涵词蕴涵词是二元命题联结词。

两个命题P和Q用蕴涵词“→”联结起来，构成一个新的命题，记作P→Q。

读作如果P则Q，或读作P蕴涵Q。

当且仅当P 的真值为T，Q的真值为F时，P→Q的真值为F，否则P∨Q的真值为T。

第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）均不是命题。

离散数学习题一二参考答案----a3039d74-7162-11ec-90d9-7cb59b590d7d离散数学习题一二参考答案离散数学练习1的参考答案第一节集合的基数1.证明两个可数集的并是可数的。

证明：设a，b是两可数集，a={a1,a2,a3,,an,}，b={b1,b2,b3,,bn,}⎧ab→n⎧f:⎧ai2i-1，f是一一对应关系，所以|a∪b|=|n|=ℵ0。

⎧b2jj⎧2．证明有限可数集的并是可数集证明：设A1，A2和a3ak是有限可数集，AI=（Ai1，AI2，ai3，ain，），I=1，2，3，Kk⎧k⎧a=ai→n，f是一一对应关系，所以|a|=|ai|=|n|=ℵ0。

f:⎧i=1i=1⎧aijj（k-1）+i⎧3.证明可数个可数集的并是可数集。

证明：设A1，A2和a3ak为无限可数集，AI=（Ai1，AI2，ai3，ain，），I=1,2,3，∞⎧a=ai→n⎧⎧i=1f:⎧，1⎧aij(i+j-1)(i+j-2)+i⎧2⎧所以f是一对一的对应，所以|a |=|a |=|n |=ℵ. 我∞04.证明整系数多项式所构成的集合是可数集。

证明了具有整系数的n次多项式之和可以写成an={a0xn+a1xn-1++an-1x+an|ai∈z}那么整系数为a=an的多项式集；由于xk的系数ak是整数，那么所有xk的系数的全体所构成的集合是可数集，由习题2“有限个可数集的并是可数集”可得an是可数集，再又习题4“可数个可数集的并是可数集”得出整系数多项式所构成的集合a=an也是可数集。

5.证明不存在等于其真子集的有限集证明：设集合a是有限集，则|a|=n，若b是a的真子集，则|b|≤|a|=n，a-b≠φ，即|a-b|=|a|-|ab|＞0；又a=（a-b）∪b，（a-b）b=φ，所以，，就是|a|＞|b|，即得结论。

6.证明正有理数集是可数的，从而证明有理数集是可数的。

m证明：因为q+={|m,n∈n}，是正分数集，n∞ n+让AI={|n∈ n} ，I=1,2,3,4,m}，AI是可数集，q=AIII=1由可数集性质4“可数个可数集的并仍然是可数集”，所以正有理数集合是可数集。

第一部分数理逻辑先看著名物理学家爱因斯坦出过的一道题：一个土耳其商人想找一个十分聪明的助手协助他经商，有两人前来应聘，这个商人为了试试哪个更聪明些，就把两个人带进一间漆黑的屋子里，他打开灯后说：“这张桌子上有五顶帽子，两顶是红色的，三顶是黑色的，现在，我把灯关掉，而且把帽子摆的位置弄乱，然后我们三个人每人摸一顶帽子戴在自己头上，在我开灯后，请你们尽快说出自己头上戴的帽子是什么颜色的。

”说完后，商人将电灯关掉，然后三人都摸了一顶帽子戴在头上，同时商人将余下的两顶帽子藏了起来，接着把灯打开。

这时，那两个应试者看到商人头上戴的是一顶红帽子，其中一个人便喊道：“我戴的是黑帽子。

”请问这个人说得对吗？他是怎么推导出来的呢？要回答这样的问题，实际上就是看由一些诸如“商人戴的是红帽子”这样的前提能否推出“猜出答案的应试者戴的是黑帽子”这样的结论来。

这又需要经历如下过程：(1) 什么是前提？有哪些前提？(2) 结论是什么？(3) 根据什么进行推理？(4) 怎么进行推理？下面的第一章，第二章回答第一个问题。

第三章回答第二、三个问题。

下图给出了逻辑部分的知识体系。

1.1 命题与联结词一、命题的概念引言中的例子就是要对“我戴的是黑帽子”进行判断。

这样的陈述句称为命题。

作为命题的陈述句所表达的判断结果称为命题的真值，真值只取两个值：真或假。

真值为真的命题称为真命题，真值为假的命题称为假命题。

真命题表达的判断正确，假命题表达的判断错误。

任何命题的真值都是唯一的。

判断给定句子是否为命题，应该分两步：首先判定它是否为陈述句，其次判断它是否有唯一的真值。

例1.1 判断下列句子是否为命题。

(1) 4是素数。

(2) 是无理数。

(3) x大于y。

(4) 月球上有冰。

(5) 2100年元旦是晴天。

(6) π大于吗？ (7) 请不要吸烟！ (8)这朵花真美丽啊！ (9) 我正在说假话。

解:本题的(9)个句子中，(6)是疑问句，(7)是祈使句，(8)是感叹句，因而这3个句子都不是命题。