下载文档原格式
第二篇集合论第四章集合及其运算4.1 集合的基本概念容提要4.1.1集合及其元素集合是一些确定的、作为整体识别的、互相区别的对象的总体。
组成集合的对象称为集合的成员或元素（member）。
通常用一对“{ }”把集合的元素括起来，表示一个集合。
元素对于集合的隶属关系是集合论的另一基本概念。
即当对象a是集合A的元素时，称元素a属于集合A，记为a∈A当对象a不是集合A的元素时，称a不属于A，记为⌝(a∈A)或a∉A对任何对象a和任何集合A，或者a∈A或者a∉A,两者恰居其一。
这正是集合对其元素的“确定性”要求。
定义4．1空集和只含有有限多个元素的集合称为有限集（finite sets），否则称为无限集（infinite sets）。
有限集合中元素的个数称为基数（cardina lit y）（无穷集合的基数概念将在以后重新严格定义）。
集合A的基数表示为|A|。
4.1.2 外延公理、概括公理和正规公理集合论依赖于三大基本原理：外延公理（extensionality axiom）、概括公理（comprehension axiom）和正规公理（regularity axiom）。
它们从根本上规定了集合概念的意义。
外延公理：两个集合A和B相等当且仅当它们具有相同的元素。
即对任意集合A，B,A=B ↔∀x(x∈A↔x∈B)外延公理事实上刻划了集合的下列特性：集合元素的“相异性”、“无序性”，及集合表示形式的不唯一性。
概括公理: 对任意个体域，任一谓词公式都确定一个以该域中的对象为元素的集合。
即对给定个体域U，对任意谓词公式P(x)，存在集合S，使得S＝{x ⎢x∈U∧P(x)}概括公理规定了集合元素的确定性,以及集合的描述法表示的理论依据，它还规定了空集的存在性。
正规公理：不存在集合A1，A2, A3，…，使得…∈A3 ∈ A2 ∈A1正规公理的一个自然推论是：对任何集合A，{A}≠A（否则有…∈A∈A∈A）。
从而规定了集合{A}与A的不同层次性,因而正规公理也就规定了集合不能是自己的元素。
1命题演算及其形式系统1.1 命题与联结词内容提要1.1.1 命题我们把对确定的对象作出判断的陈述句称作命题（propositions），当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。
“真、假”常被称为命题的真值。
自然语言中“并非、或者、并且、如果…，那么…、当且仅当” 这样的联结词称为逻辑联结词（logical connectives）。
通常把不含有逻辑联结词的命题称为原子命题或原子（atoms），而把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositive propositions）。
1.1.2 联结词否定词(negation)“并非”（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”。
蕴涵词(implication)“如果……，那么……”（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-way implication)“当且仅当”（if and only if），用符号↔表示之。
第三篇图论第八章图图的基本知识内容提要8.1.1 图的定义及有关术语定义图（graph）G由三个部分所组成：（1）非空集合V(G)，称为图G的结点集，其成员称为结点或顶点（nodes or vertices）。
（2）集合 E(G)，称为图G的边集，其成员称为边(edges)。
I（3）函数ΨG：E(G)→(V(G)，V(G))，称为边与顶点的关联映射（associatve mapping）。
这里（V(G)，V(G)）称为VG的偶对集，其成员偶对（pair）形如（u，v），u，v为结点，它们未必不同。
ΨG(e) = (u,v)时称边e关联端点u，v。
当(u,v)用作序偶时(V(G)，V(G)) =V(G) ?V(G)，e称为有向边，e以u为起点,以v为终点, 图G称为有向图（directed graph）；当(u,v)用作无序偶对时，(u,v) = (v,u)，称e为无向边（或边），图G称为无向图（或图）。
图G常用三元序组< V(G)，E(G)，ΨG>,或< V，E，Ψ>来表示。
显然，图是一种数学结构，由两个集合及其间的一个映射所组成。
定义8. 2 设图G为< V，E，Ψ>。
（l）当V和E为有限集时，称G为有限图，否则称G为无限图。
本书只讨论有限图。
（2）当ΨG 为单射时，称G为单图；当ΨG为非单射时，称G为重图，又称满足Ψ(e1) = Ψ(e2)的不同边e1,e2,为重边,或平行边。
（3）当Ψ(e)＝(v,v)（或<v,v>）时，称e为环（loops）。
无环和重边的无向单图称为简单图。
当G为有限简单图时，也常用（n，m）表示图G，其中n = ?V ?，m = ?E ? 。
（4）Ψ为双射的有向图称为有向完全图；对每一(u，v)，u ? v，均有e使Ψ(e)＝(u,v)的简单图称为无向完全图，简称完全图，n个顶点的完全图常记作Kn。
（5）在单图G中，Ψ(e)＝(u,v)（或<u，v>）时，也用(u,v)(或<u,v>)表示边e，这时称u，v邻接e, u,v是e的端点（或称u为e的起点，v为e的终点）;也称e关联结点u , v 。
离散数学王元元习题解答-（)————————————————————————————————作者: ————————————————————————————————日期：ﻩ＊第三章消解原理3.１斯柯伦标准形内容提要我们约定，本章只讨论不含自由变元的谓词公式(也称语句，seｎteｎcｅs),所说前束范式均指前束合取范式。
全称量词的消去是简单的。
因为约定只讨论语句,所以可将全称量词全部省去,把由此出现于公式中的“自由变元”均约定为全称量化的变元。
例如A(x）实指∀xA(x)。
存在量词的消去要复杂得多。
考虑∃xＡ（ｘ)。
(1）当Ａ(x）中除x外没有其它自由变元,那么,我们可以像在自然推理系统中所做那样,可引入A(e/ｘ）,其中ｅ为一新的个体常元,称e为斯柯伦(Skolem)常元，用Ａ(e/x)代替∃ｘＡ(ｘ),但这次我们不把A(e/ｘ)看作假设,详见下文。
(2)当A中除x外还有其它自由变元y1,…,yｎ,那么∃ｘA(ｘ,y1,…,yｎ）来自于∀y1…∀y n∃ｘＡ（x, ｙ1,…,y n)，其中“存在的x”本依赖于ｙ1,…，ｙn的取值。
因此简单地用A(ｅ/x,ｙ１,…,y n)代替∃xA(x,y1,…,y n）是不适当的,应当反映出x对ｙ１,…,ｙn的依赖关系。
为此引入函数符号f,以Ａ(ｆ(y1,…，ｙn)/x，ｙ1,…,y n)代替∃xA(x, y１,…,ｙn），它表示：对任意给定的y1,…,y n, 均可依对应关系f确定相应的x,使x, ｙ1,…,yｎ满足Ａ。
这里f是一个未知的确定的函数,因而应当用一个推理中尚未使用过的新函数符号，称为斯柯伦函数。
定理３.１(斯柯伦定理)对任意只含自由变元x,y1，…,yｎ的公式Ａ(x，y１，…,y n),∃xA(x, y1,…,y n）可满足，当且仅当A（f(y1,…,y n), y1，…,y n)可满足。
这里ｆ为一新函数符号；当n = 0时,f为新常元。
定义3．1设公式Ａ的前束范式为B。
第九章特殊图9.1 二分图内容提要9.1.1 二分图的基本概念定义9.1无向图G = <V，E，ψ>称为二分图（bipartite graph），如果有非空集合X，Y 使X∪Y = V，X∩Y = ∅，且对每一e∈E，ψ(e) = (x, y)，x∈X，y∈Y。
此时常用<X，E，Y>表示二分图G。
若对X中任一x及Y中任一y恰有一边e∈E，使ψ(e) = (x, y), 则称G为完全二分图（complete bipartite graph）。
当|X| = m，|Y| = n时，完全二分图G记为K m,n。
定理9.1无向图G为二分图的充分必要条件是，G至少有两个顶点,且其所有回路的长度均为偶数。
9.1.2 匹配定义9.2设G = <X，E，Y>为二分图，M⊆E。
称M为G的一个匹配（matching），如果M中任何两条边都没有公共端点。
G的所有匹配中边数最多的匹配称为最大匹配（maximal matching）。
如果X(Y)中任一顶点均为匹配M中边的端点，那么称M为X(Y)-完全匹配(perfect matching)。
若M既是X-完全匹配又是Y-完全匹配，则称M为G的完全匹配。
定义9.3设G = <X，E，Y>，M为G的一个匹配。
（1）M中边的端点称为M-顶点，其它顶点称为非M-顶点。
（2）G中v k到v l的通路P称为交替链，如果P的起点v k和终点v l为非M-顶点，而其边的序列中非匹配边与匹配边交替出现（从而首尾两边必为非匹配边，除顶点v k，v l以外各顶点均为M-顶点）。
特别地，当一边（v, v'）两端点均为非M-顶点，通路（v, v'）亦称为交替链。
以下算法可把G中任一匹配M扩充为最大匹配，此算法是Edmonds于1965年提出的，被称为匈牙利算法，其步骤如下：（1）首先用（*）标记X中所有的非M-顶点，然后交替进行步骤（2），（3）。
1命题演算及其形式系统1.1 命题与联结词内容提要1.1.1 命题我们把对确定的对象作出判断的陈述句称作命题（propositions），当判断正确或符合客观实际时，称该命题真（true），否则称该命题假（false）。
“真、假”常被称为命题的真值。
自然语言中“并非、或者、并且、如果…，那么…、当且仅当” 这样的联结词称为逻辑联结词（logical connectives）。
通常把不含有逻辑联结词的命题称为原子命题或原子（atoms），而把由原子命题和逻辑联结词共同组成的命题称为复合命题（compositive propositions）。
1.1.2 联结词否定词(negation)“并非”（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”。
蕴涵词(implication)“如果……，那么……”（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-way implication)“当且仅当”（if and only if），用符号表示之。
设p，q为两命题，那么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统称为命题常元（proposition constant）。
深入的讨论还需要引入命题变元（proposition variable）的概念，它们是以“真、假”或“1，0”为取值范围的变元，为简单计，命题变元仍用p，q，r，s等表示。
定义1.1 以下三条款规定了命题公式（proposition formula）的意义：（1）命题常元和命题变元是命题公式，也称为原子公式或原子。
（2）如果A，B是命题公式，那么（┐A），（A∧B），（A∨B），（A→B），（A B）也是命题公式。
（3）只有有限步引用条款（1），（2）所组成的符号串是命题公式。
如果公式A含有命题变元p1，p2，…，p n，记为A(p1,…,p n)，并把联结词看作真值运算符，那么公式A可以看作是p1,…,p n的真值函数。
对任意给定的p1,…,p n的一种取值状况，称为指派（assignments），用希腊字母，等表示，A均有一个确定的真值。
当A对取值状况为真时，称指派弄真A，或是A的成真赋值，记为 (A) = 1；反之称指派弄假A，或是A的成假赋值，记为 (A) = 0。
对一切可能的指派,公式A的取值可能可用一张表来描述,这个表称为真值表（truth table）。
当A(p1,…,p n)中有k个联结词时，公式A的真值表应为2n行、k+n列（不计表头）。
1.1.4 语句的形式化用我们已有的符号语言，可以将许多自然语言语句形式化。
语句形式化要注意以下几个方面。
要善于确定原子命题，不要把一个概念硬拆成几个概念，例如“弟兄”是一个概念，不要拆成“弟”和“兄”、“我和他是弟兄”是一个原子命题。
要善于识别自然语言中的联结词（有时它们被省略）。
例如“风雨无阻，我去上学”一句，可理解为“不管是否刮风、是否下雨我都去上学”。
否定词的位置要放准确。
需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。
另外要注意的是,语句的形式化未必是唯一的。
习题解答练习1.11、判断下列语句是否是命题，若是命题则请将其形式化：（1）a+b（2）x>0（3）“请进！”（4）所有的人都是要死的，但有人不怕死。
（5）我明天或后天去苏州。
（6）我明天或后天去苏州的说法是谣传。
（7）我明天或后天去北京或天津。
（8）如果买不到飞机票，我哪儿也不去。
（9）只要他出门，他必买书，不管他余款多不多。
（10）除非你陪伴我或代我雇辆车子，否则我不去。
（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。
（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。
（13）不管你和他去不去，我去。
（14）侈而惰者贫，而力而俭者富。
（韩非：《韩非子显学》）（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。
（荀况：《荀子劝学》）解（1）a+b 不是命题（2）x>0 不是命题（x是变元）（3）“请进！”不是命题（4）所有的人都是要死的，但有人不怕死。
是命题可表示为p∧┐q，其中p：所有的人都是要死的，q：所有的人都怕死（5）我明天或后天去苏州。
是命题可表示为p∨q，其中p：我明天去苏州；q：我后天去苏州（6）我明天或后天去苏州的说法是谣传。
是命题可表示为┐(p∨q)，其中p、q同（5）（7）我明天或后天去北京或天津。
是命题可表示为p∨q∨r∨s，其中p：我明天去北京，q：我明天去天津，r：我后天去北京，s：我后天去天津（8）如果买不到飞机票，我哪儿也不去。
是命题可表示为┐p→┐q，其中，p：我买到飞机票，q：我出去（9）只要他出门，他必买书，不管他余款多不多。
是命题可表示为(p∧q→r)∧(┐p∧q→r)或q→r，其中p：他余款多，q：他出门，r：他买书（10）除非你陪伴我或代我雇辆车子，否则我不去。
是命题可表示为(p∨q) r，其中p：你陪伴我，q：你代我雇车，r：我去（11）只要充分考虑一切论证，就可得到可靠见解；必须充分考虑一切论证，才能得到可靠见解。
是命题可表示为(p→q) ∧(q→p )或p q，其中p：你充分考虑了一切论证，q：你得到了可靠见解（12）如果只有懂得希腊文才能了解柏拉图，那么我不了解柏拉图。
是命题可表示为(q→p ) →┐q，其中p：我懂得希腊文，q：我了解柏拉图（13）不管你和他去不去，我去。
是命题可表示为(p→r) ∧(q→r) ∧( ┐p→r) ∧( ┐q→r)或r，其中p：你去，q：他去，r：我去（14）侈而惰者贫，而力而俭者富。
（韩非：《韩非子显学》）是命题可表示为((p∧q)→r) ∧((┐p∧┐q)→┐r)，其中p：你奢侈，q：你懒惰，r：你贫困（15）骐骥一跃，不能十步；驽马十驾，功在不舍；锲而舍之，朽木不折；锲而不舍，金石可镂。
（荀况：《荀子劝学》）是命题可表示为(p→┐q) ∧(s→r) ∧(m∧n→┐o) ∧(m∧┐n→v)，其中p：骐骥一跃，q：骐骥一跃十步，r：驽马行千里，s：驽马不断奔跑，m：你雕刻，n：你放弃，o：将朽木折断，v：金石可雕刻2、判定下列符号串是否为公式，若是，请给出它的真值表，并请注意这些真值表的特点（公式中省略了可以省略的括号）：（1）┐(p)（p为原子命题）（2）(p∨qr)→s（3）(p∨q)→p（4）p→(p∨q)（5）┐(p∨┐p)（6）p∧(p→q)→q（7）p∧(p→q)∧(p→┐q)（8）(p→q) (┐q→┐p)（9）┐(p∨q) ┐q∧┐p（10）┐p∨q (p→q)（11）(p→q)∧(q→r)→(p→r)（12）(p∨q→r) (p→r)∧(q→r)解（1）┐(p) 不是公式（2）(p∨qr)→s 不是公式（4）p→(p∨q) 是公式（真值表见上表，恒真）（5（6（7（8(p→q) (┐q→┐p)（9┐(p∨q) ┐q∧┐p（10┐p∨q (p→q)（11（(p∨q→r) (p→r)∧(q→r)*3、A国的人只有两种，一种永远说真话，一种永远说假话。
你来到A国，并在一个二叉路口不知如何走才能到达首都。
守卫路口的士兵只准你问一个问题，而且他只答“是”或“不是”。
你应该如何发问，才能从士兵处获知去首都的道路。
解设p：你是说真话的；q：我应当向右走去首都你应当问：p q ?当回答“是 (真)”，你选择向右走；当回答“不（假）”时，你选择向左走。
因为p q真，当且仅当p真且q真（士兵说真话且应当向右走）或p假且q假（士兵说假话且应当向左走）p q假，当且仅当p真且q假（士兵说真话且应当向左走）或p假且q假（士兵说假话且应当向右走）1.2 重言式内容提要1.2.1 重言式概念定义1.2命题公式A称为重言式（tautology），如果对A中命题变元的一切指派均弄真A，因而重言式又称永真式；A称为可满足式（satisfactable formula），如果至少有一个指派弄真A，否则称A为不可满足式或永假式、矛盾式。
1.2.2 逻辑等价式和逻辑蕴涵式定义1.3 当命题公式A B为永真式时，称A逻辑等价于B，记为A┝┥B，它又称为逻辑等价式(logically equivalent)。
以下是一些重要的逻辑等价式，其中A，B，C表示任意命题公式：E1┐┐A┝┥A 双重否定律E2 A∨A┝┥A 幂等律E3 A∧A┝┥A 幂等律E4 A∨B┝┥B∨A 交换律E5 A∧B┝┥B∧A 交换律E6 (A∨B)∨C┝┥A∨(B∨C) 结合律E7 (A∧B)∧C┝┥A∧(B∧C) 结合律E8 A∧(B∨C)┝┥(A∧B)∨(A∧C) 分配律E9 A∨(B∧C)┝┥(A∨B)∧(A∨C) 分配律E10┐(A∨B)┝┥┐A∧┐B 德摩根律E11┐(A∧B)┝┥┐A∨┐B 德摩根律E12 A∨(A∧B)┝┥A 吸收律E13 A∧(A∨B)┝┥A 吸收律E14 A→B┝┥┐A∨BE 15 A B┝┥(A→B)∧(B→A)E16 A∨t┝┥tE17 A∧t┝┥AE18 A∨f┝┥AE19 A∧f┝┥fE20 A∨┐A┝┥tE21 A∧┐A┝┥fE22┐t┝┥f, ┐f┝┥tE23 A∧B→C┝┥A→(B→C)E24 A→B┝┥┐B→┐AE25 (A→B)∧(A→┐B)┝┥┐A定义1.4当命题公式A→B为永真式时，称A逻辑蕴涵B，记为A┝ B，它又称为逻辑蕴涵式(logically implication)。
