离散数学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 是平行四边形，当且仅当它的对边平行。