离散数学 第一章：命题逻辑

数理逻辑部分第1章命题逻辑命题符号化及联结词命题: 判断结果惟一的陈述句命题的真值: 判断的结果真值的取值: 真与假真命题: 真值为真的命题假命题: 真值为假的命题注意: 感叹句、祈使句、疑问句都不是命题，陈述句中的悖论以及判断结果不惟一确定的也不是命题。

简单命题(原子命题)：简单陈述句构成的命题复合命题：由简单命题与联结词按一定规则复合而成的命题简单命题符号化用小写英文字母p, q, r, … ,p i,q i,r i (i≥1）表示简单命题用“1”表示真，用“0”表示假例如，令p：是有理数，则p 的真值为 0q：2 + 5 = 7，则q 的真值为 1联结词与复合命题1.否定式与否定联结词“”定义设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p. 符号称作否定联结词，并规定p为真当且仅当p为假.2.合取式与合取联结词“∧”定义设p,q为二命题,复合命题“p并且q”(或“p与q”)称为p与q 的合取式，记作p∧q. ∧称作合取联结词，并规定 p∧q为真当且仅当p 与q同时为真注意：描述合取式的灵活性与多样性分清简单命题与复合命题例将下列命题符号化.(1) 王晓既用功又聪明.(2) 王晓不仅聪明，而且用功.(3) 王晓虽然聪明，但不用功.(4) 张辉与王丽都是三好生.(5) 张辉与王丽是同学.解令p：王晓用功，q：王晓聪明，则(1) p∧q(2) p∧q(3) p∧q.令r : 张辉是三好学生，s :王丽是三好学生(4) r∧s.(5) 令t : 张辉与王丽是同学，t 是简单命题 .说明:(1)~(4)说明描述合取式的灵活性与多样性.(5) 中“与”联结的是两个名词，整个句子是一个简单命题.3.析取式与析取联结词“∨”定义设p,q为二命题，复合命题“p或q”称作p与q的析取式，记作p∨q. ∨称作析取联结词，并规定p∨q为假当且仅当p与q同时为假.例将下列命题符号化(1) 2或4是素数.(2) 2或3是素数.(3) 4或6是素数.(4) 小元元只能拿一个苹果或一个梨.(5) 王晓红生于1975年或1976年.解令p:2是素数, q:3是素数, r:4是素数, s:6是素数,则 (1), (2), (3) 均为相容或.分别符号化为: p∨r , p∨q, r∨s,它们的真值分别为 1, 1, 0.而 (4), (5) 为排斥或.令t :小元元拿一个苹果，u:小元元拿一个梨，则 (4) 符号化为 (t∧u) ∨(t∧u).令v :王晓红生于1975年,w:王晓红生于1976年,则 (5) 既可符号化为 (v∧w)∨(v∧w), 又可符号化为v∨w , 为什么?4.蕴涵式与蕴涵联结词“”定义设p,q为二命题，复合命题“如果p,则q” 称作p与q的蕴涵式，记作p q，并称p是蕴涵式的前件，q为蕴涵式的后件. 称作蕴涵联结词，并规定，p q为假当且仅当p 为真q 为假.p q 的逻辑关系：q 为p 的必要条件“如果p，则q ” 的不同表述法很多：若p，就q只要p，就qp 仅当q只有q 才p除非q, 才p 或除非q, 否则非p.当p 为假时，p q 为真常出现的错误：不分充分与必要条件5.等价式与等价联结词“”定义设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作p q. 称作等价联结词.并规定p q为真当且仅当p与q同时为真或同时为假.说明:(1) p q 的逻辑关系:p与q互为充分必要条件(2) p q为真当且仅当p与q同真或同假联结词优先级:( ),, , , ,同级按从左到右的顺序进行以上给出了5个联结词：, , , , ，组成一个联结词集合{, , , , }，联结词的优先顺序为：, , , , ; 如果出现的联结词同级，又无括号时，则按从左到右的顺序运算; 若遇有括号时，应该先进行括号中的运算.注意: 本书中使用的括号全为园括号.命题常项命题变项命题公式及分类命题变项与合式公式命题常项：简单命题命题变项：真值不确定的陈述句定义合式公式 (命题公式, 公式) 递归定义如下：(1) 单个命题常项或变项p,q,r,…,p i ,q i ,r i ,…,0,1是合式公式(2) 若A是合式公式，则 (A)也是合式公式(3) 若A, B是合式公式，则(A B), (A B), (A B), (A B)也是合式公式(4) 只有有限次地应用(1)~(3)形成的符号串才是合式公式说明: 元语言与对象语言, 外层括号可以省去合式公式的层次定义(1) 若公式A是单个的命题变项, 则称A为0层公式.(2) 称A是n+1(n≥0)层公式是指下面情况之一：(a) A=B, B是n层公式；(b) A=B C, 其中B,C分别为i层和j层公式，且n=max(i, j)；(c) A=B C, 其中B,C的层次及n同(b)；(d) A=B C, 其中B,C的层次及n同(b)；(e) A=B C, 其中B,C的层次及n同(b).例如公式p 0层p 1层p q 2层(p q)r 3层((p q) r)(r s) 4层公式的赋值定义给公式A中的命题变项p1, p2, … , p n指定一组真值称为对A的一个赋值或解释成真赋值: 使公式为真的赋值成假赋值: 使公式为假的赋值说明：赋值=12…n之间不加标点符号，i=0或1.A中仅出现p1, p2, …, p n，给A赋值12…n是指p1=1, p2=2, …, p n=nA中仅出现p,q, r, …, 给A赋值123…是指p=1,q=2 , r= 3 …含n个变项的公式有2n个赋值.真值表真值表: 公式A在所有赋值下的取值情况列成的表例给出公式的真值表A= (q p) q p的真值表例 B = (p q) q的真值表例C= (p q) r的真值表命题的分类重言式矛盾式可满足式定义设A为一个命题公式(1) 若A无成假赋值，则称A为重言式(也称永真式)(2) 若A无成真赋值，则称A为矛盾式(也称永假式)(3) 若A不是矛盾式，则称A为可满足式注意：重言式是可满足式，但反之不真.上例中A为重言式，B为矛盾式，C为可满足式A= (q p)q p，B =(p q)q，C= (p q)r等值演算等值式定义若等价式A B是重言式，则称A与B等值，记作A B，并称A B是等值式说明：定义中，A,B,均为元语言符号, A或B中可能有哑元出现.例如，在 (p q) ((p q) (r r))中，r为左边公式的哑元.用真值表可验证两个公式是否等值请验证：p(q r) (p q) rp(q r) (p q) r基本等值式双重否定律 : A A等幂律：A A A, A A A交换律: A B B A, A B B A结合律: (A B)C A(B C)(A B)C A(B C)分配律: A(B C)(A B)(A C)A(B C) (A B)(A C)德·摩根律: (A B)A B(A B)A B吸收律: A(A B)A, A(A B)A零律: A11, A00同一律: A0A, A1A排中律: A A1矛盾律: A A0等值演算:由已知的等值式推演出新的等值式的过程置换规则：若A B, 则(B)(A)等值演算的基础：(1) 等值关系的性质：自反、对称、传递(2) 基本的等值式(3) 置换规则应用举例——证明两个公式等值例1 证明p(q r) (p q)r证p(q r)p(q r) （蕴涵等值式，置换规则）(p q)r（结合律，置换规则）(p q)r（德摩根律，置换规则）(p q) r（蕴涵等值式，置换规则）说明:也可以从右边开始演算（请做一遍）因为每一步都用置换规则，故可不写出熟练后，基本等值式也可以不写出应用举例——证明两个公式不等值例2 证明: p(q r) (p q) r用等值演算不能直接证明两个公式不等值,证明两个公式不等值的基本思想是找到一个赋值使一个成真,另一个成假.方法一真值表法（自己证）方法二观察赋值法. 容易看出000, 010等是左边的的成真赋值，是右边的成假赋值.方法三用等值演算先化简两个公式，再观察.应用举例——判断公式类型例3 用等值演算法判断下列公式的类型(1) q(p q)解q(p q)q(p q) （蕴涵等值式）q(p q) （德摩根律）p(q q) （交换律，结合律）p0 （矛盾律）0 （零律）由最后一步可知，该式为矛盾式.(2) (p q)(q p)解 (p q)(q p)(p q)(q p) （蕴涵等值式）(p q)(p q) （交换律）1由最后一步可知，该式为重言式.问：最后一步为什么等值于1？(3) ((p q)(p q))r)解 ((p q)(p q))r)(p(q q))r（分配律）p1r（排中律）p r（同一律）这不是矛盾式，也不是重言式，而是非重言式的可满足式.如101是它的成真赋值,000是它的成假赋值.总结：A为矛盾式当且仅当A0A为重言式当且仅当A1说明：演算步骤不惟一,应尽量使演算短些对偶与范式对偶式与对偶原理定义在仅含有联结词, ∧,∨的命题公式A中，将∨换成∧, ∧换成∨，若A中含有0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记为A*.从定义不难看出，(A*)* 还原成A定理设A和A*互为对偶式，p1,p2,…,p n是出现在A和A*中的全部命题变项，将A和A*写成n元函数形式，则 (1) A(p1,p2,…,p n) A* (p1, p2,…, p n) (2) A(p1, p2,…, p n) A* (p1,p2,…,p n) 定理（对偶原理）设A，B为两个命题公式，若A B，则A* B*.析取范式与合取范式文字:命题变项及其否定的总称简单析取式:有限个文字构成的析取式如p, q, p q, p q r, …简单合取式:有限个文字构成的合取式如p, q, p q, p q r, …析取范式:由有限个简单合取式组成的析取式A 1A2Ar, 其中A1,A2,,A r是简单合取式合取范式:由有限个简单析取式组成的合取式A 1A2Ar, 其中A1,A2,,A r是简单析取式范式:析取范式与合取范式的总称公式A的析取范式: 与A等值的析取范式公式A的合取范式: 与A等值的合取范式说明：单个文字既是简单析取式，又是简单合取式p q r, p q r既是析取范式，又是合取范式(为什么?)命题公式的范式定理任何命题公式都存在着与之等值的析取范式与合取范式.求公式A的范式的步骤：(1) 消去A中的, （若存在）(2) 否定联结词的内移或消去(3) 使用分配律对分配（析取范式）对分配（合取范式）公式的范式存在，但不惟一求公式的范式举例例求下列公式的析取范式与合取范式(1) A=(p q)r解 (p q)r(p q)r（消去）p q r（结合律）这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2) B=(p q)r解 (p q)r(p q)r（消去第一个）(p q)r（消去第二个）(p q)r（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续： (p q)r(p r)(q r) （对分配律）这一步得到合取范式（由两个简单析取式构成）极小项与极大项定义在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1i n）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.说明：n个命题变项产生2n个极小项和2n个极大项2n个极小项（极大项）均互不等值用m i表示第i个极小项，其中i是该极小项成真赋值的十进制表示. 用M i 表示第i个极大项，其中i是该极大项成假赋值的十进制表示, m i(M i)称为极小项(极大项)的名称.m与M i的关系: m i M i , M i m ii主析取范式与主合取范式主析取范式: 由极小项构成的析取范式主合取范式: 由极大项构成的合取范式例如，n=3, 命题变项为p, q, r时，(p q r)(p q r) m1m3是主析取范式(p q r)(p q r) M1M5 是主合取范式A的主析取范式: 与A等值的主析取范式A的主合取范式: 与A等值的主合取范式.定理任何命题公式都存在着与之等值的主析取范式和主合取范式, 并且是惟一的.用等值演算法求公式的主范式的步骤：(1) 先求析取范式（合取范式）(2) 将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3) 极小项（极大项）用名称m i（M i）表示，并按角标从小到大顺序排序.求公式的主范式例求公式A=(p q)r的主析取范式与主合取范式.(1) 求主析取范式(p q)r(p q)r , （析取范式）①(p q)(p q)(r r)(p q r)(p q r)m 6m7,r(p p)(q q)r(p q r)(p q r)(p q r)(p q r)m 1m3m5m7③②, ③代入①并排序，得(p q)r m1m3m5m6m7（主析取范式）(2) 求A的主合取范式(p q)r(p r)(q r) , （合取范式）①p rp(q q)r(p q r)(p q r)M 0M2,②q r(p p)q r(p q r)(p q r)M 0M4③②, ③代入①并排序，得(p q)r M0M2M4 （主合取范式）主范式的用途——与真值表相同(1) 求公式的成真赋值和成假赋值例如 (p q)r m1m3m5m6m7，其成真赋值为001, 011, 101, 110, 111，其余的赋值 000, 010, 100为成假赋值.类似地，由主合取范式也可立即求出成假赋值和成真赋值.(2) 判断公式的类型设A含n个命题变项，则A为重言式A的主析取范式含2n个极小项A的主合取范式为1.A为矛盾式A的主析取范式为0A的主合取范式含2n个极大项A为非重言式的可满足式A的主析取范式中至少含一个且不含全部极小项A的主合取范式中至少含一个且不含全部极大项例某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习. 选派必须满足以下条件：(1)若赵去，钱也去；(2)李、周两人中至少有一人去；(3)钱、孙两人中有一人去且仅去一人；(4)孙、李两人同去或同不去；(5)若周去，则赵、钱也去.试用主析取范式法分析该公司如何选派他们出国？解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式解①设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.② (1) (p q)(2) (s u)(3) ((q r)(q r))(4) ((r s)(r s))(5) (u(p q))③ (1) ~ (5)构成的合取式为A=(p q)(s u)((q r)(q r))((r s)(r s))(u(p q))④ A (p q r s u)(p q r s u)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.A的演算过程如下:A (p q)((q r)(q r))(s u)(u(p q)) ((r s)(r s)) （交换律) B1= (p q)((q r)(q r))((p q r)(p q r)(q r)) （分配律）B2= (s u)(u(p q))((s u)(p q s)(p q u)) （分配律）B 1B2(p q r s u)(p q r s u) (q r s u)(p q r s)(p q r u)再令B3 = ((r s)(r s))得A B1B2B3(p q r s u)(p q r s u)注意：在以上演算中多次用矛盾律要求：自己演算一遍推理理论推理的形式结构推理的形式结构—问题的引入推理举例:(1) 正项级数收敛当且仅当部分和有上界.(2) 若推理: 从前提出发推出结论的思维过程上面(1)是正确的推理，而(2)是错误的推理.证明: 描述推理正确的过程.判断推理是否正确的方法•真值表法•等值演算法判断推理是否正确•主析取范式法•构造证明法证明推理正确说明：当命题变项比较少时，用前3个方法比较方便, 此时采用形式结构“” . 而在构造证明时，采用“前提: , 结论: B”.推理定律与推理规则推理定律——重言蕴涵式构造证明——直接证明法例构造下面推理的证明：若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.解设p：明天是星期一，q：明天是星期三，r：我有课，s：我备课推理的形式结构为例构造下面推理的证明:2是素数或合数. 若2是素数，则是无理数.若是无理数，则4不是素数. 所以，如果4是素数，则2是合数.用附加前提证明法构造证明解设p：2是素数，q：2是合数，r：是无理数，s：4是素数推理的形式结构前提：p∨q, p r, r s结论：s q证明① s附加前提引入②p r前提引入③r s前提引入④p s②③假言三段论⑤p①④拒取式⑥p∨q前提引入⑦q⑤⑥析取三段论请用直接证明法证明之。

离散数学结构第1章命题逻辑基本概念第1章命题逻辑基本概念主要内容1. 命题与真值（或真假值）。

2. 简单命题与复合命题。

3. 联结词：否定联结词┐，合取联结词∧，析取联结词∨，蕴涵联结词→，等价联结词。

4. 命题公式（简称公式）。

5. 命题公式的层次和公式的赋值。

6. 真值表。

7. 公式的类型（重⾔式（或永真式），⽭盾式（或永假式），可满⾜式）。

学习要求1. 在5种联结词中，要特别注意蕴涵联结的应⽤，要弄清三个问题：① p→q的逻辑关系② p→q的真值③ p→q的灵活的叙述⽅法2. 写真值表要特别仔细认真，否则会出错误。

3. 深刻理解各联结词的逻辑含义。

4. 熟练地将复合命题符号化。

6. 会⽤真值表求公式的成真赋值和成假赋值。

1.1 命题与联结词 (2)⼀、命题的概念 (2)⼆、复合命题与联结词 (2)三、复合命题真假值 (5)1.2 命题公式及其赋值 (6)⼀、命题公式的定义 (6)⼆、公式的层次 (6)三、公式的赋值 (6)四、真值表 (7)五、公式的真假值分类 (8)1.1 命题与联结词⼀、命题的概念引⾔中的例⼦就是要对“我戴的是⿊帽⼦”进⾏判断。

这样的陈述句称为命题。

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

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

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

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

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

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

(1) 4是素数。

(2) 是⽆理数。

(3) x⼤于y。

(4) ⽉球上有冰。

(5) 2100年元旦是晴天。

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

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

剩下的6个句⼦都是陈述句，但(3)⽆确定的真值，根据x,y的不同取值情况它可真可假，即⽆唯⼀的真值，因⽽不是命题。

离散数学第一章命题逻辑定义1。

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

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

联结词“¬”表示命题的否定。

否定联结词有时亦可记作“¯”。

（P3）定义2。

两个命题P和Q的合取是一个复合命题，记作P∧Q。

当且仅当P,Q同时为T时，P∧Q为T，在其他情况下，P∧Q的真值都是F。

（P4）定义3。

两个命题P和Q的析取是一个复合命题，记作P∨Q。

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

（P5）定义4。

给定两个命题P和Q，其条件命题是一个复合命题，记作P→Q，读作“如果P，那么Q”或者“若P则Q”。

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

我们称P为前件，Q为后件。

（P6）定义5。

给定两个命题P和Q，其复合命题P⇆Q的真值为F。

（P7）定义6。

命题演算的合式公式（wff），规定为：（1）单个命题变元本身是一个合式公式。

（2）如果A是合式公式，那么¬A是合式公式。

（3）如果A和B是合式公式，那么（A∧B），（A∨B），（A→B）和（A⇆B）都是合式公式。

（4）当且仅当能够有限次地应用（1），（2），（3）所得到的包含命题变元，联结词和括号的符号串是合式公式。

（P9）定义7。

在命题公式中，对于分量指派真值得各种可能组合，就确定了这个命题公式的各种真值情况，把它汇列成表，就是命题公式的真值表。

（P12）定义8。

给定两个命题公式A和B，设P1，P2，…，P n为所有出现于A和B中的原子变元，若给P1，P2，…，P n任一组真值指派，A和B的真值都相同，则称A和B是等价的或逻辑相等。

记作A⇔B。

（P15）定义9。

如果X是合式公式的A的一部分，且X本身也是一个合式公式，则称X为公式A 的字公式。

（P16）定理1。

设X是合式公式A的字公式，若X⇔Y，如果将A中的X用Y来置换，所得到公式B 与公式A等价，即A⇔B。

第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.2 联结词1.3 命题公式与翻译1.4 真值表与等价公式1.5 重言式与蕴含式1.6 其它联结词1.7 对偶与范式1.8 推理理论1.1 命题及其表示方法命题：具有确定真值的陈述句命题的类型（原子命题和复合命题）命题的表示（一个命题标识符（比如P）表示确定的命题）重点：如何判断语句是否为命题。

1.2 联结词否定⌝合取∧析取∨条件→双条件↔重点：五种联结词的含义、真值表1.3 命题公式与翻译命题公式符号化：所谓命题的符号化就是把一个用文字叙述的句子相应地写成由命题标识符、联结词和括号表示的合式公式。

命题符号化的重要性命题符号化是很重要的，一定要掌握好，在命题推理中最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。

重点：命题的符号化符号化应该注意下列事项:①确定给定句子是否为命题。

②句子中连词是否为命题联结词。

③要正确地表示原子命题和适当选择命题联结词。

1.4 真值表与等价公式真值表的构造方法(1) 找出公式中所含的全体命题变元P1, P2, …, Pn, (若无下角标就按字典顺序排列), 列出2n个赋值. 赋值从00…0开始, 然后按二进制加法依次写出各赋值, 直到11…1为止.(2) 按从低到高的顺序写出公式的各个层次.(3) 对应各个赋值计算出各层次的真值, 直到最后计算出公式的真值.等价关系的含义等价式的判别方法•真值表法•等价演算法基本等价式（必须掌握）(1)对合律（双重否定）：⌝⌝P⇔P(2)幂等律：P∧P⇔P，P∨P⇔P(3)结合律：(P∧Q)∧R⇔P∧(Q∧R)，(P∨Q)∨R⇔P∨(Q∨R)(4)交换律：P∧Q⇔Q∧P，P∨Q⇔Q∨P(5)分配律：P∧(Q∨R)⇔(P∧Q)∨(P∧R)，P∨(Q∧R)⇔(P∨Q)∧(P∨R)(6)德·摩根律：⌝ (P∧Q) ⌝⇔P∨⌝Q，⌝ (P∨Q) ⌝⇔P∧⌝Q(7)吸收律：P∧(P∨Q)⇔P，P∨(P∧Q)⇔P(8)同一律：P∧T⇔P，P∨F⇔P(9)零律：P∧F⇔F，P∨T⇔T(10)否定律：P∧⌝P⇔F，P∨⌝P⇔T(11) 条件式转化律：P→Q⌝⇔P∨Q，P→Q⌝⇔Q→⌝P(12) 双条件式转化律：P↔Q ⇔(P→Q)∧(Q→P) ⇔(P∧Q)∨(⌝P∧⌝Q)⌝ (P↔Q) ⇔P⌝↔Q ⌝⇔P↔Q(13) 输出律(CP规则)：P→(Q→R) ⇔(P∧Q)→R重点：等价式的证明、基本等价式1.5 重言式与蕴含式重言式或永真公式定义1-5.1 给定一命题公式，若无论对分量作怎样的指派，其对应的真值永为真，则称该命题公式为重言式或永真公式。

第一章命题逻辑原子命题：不包含任何联结词的命题叫做原子命题。

复合命题：至少包含一个联结词的命题称作复合命题。

重言式：给定一个命题公式，若无论对分量作怎样的指派，其对应的真值用为T。

蕴含：当且仅当P→Q是一个重言式时，我们称“P蕴含Q”，并记作P⇒Q对偶：在给定的命题公式中，将联结词⋁换成⋀，将⋀换成⋁，若有特殊边缘F和T亦相互取代，所得公式A*称为A的对偶式。

主析取范式：对于给定的命题公式，如果有一个等价公式，它仅小项的析取所组成，则该等价式称作原式的主析取范式。

主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。

第二章谓词逻辑不可满足的：一个谓词公式wff A，如果在所有赋值下都为假，则称该wff A为不可满足的。

可满足的：一个谓词公式wff A，如果至少在一种赋值下为真，则称该wff A为可满足的。

前束范式：一个公式，如果两次均在全式的开头，它们的作用域，延伸到整个公式末尾，则该公式叫做前束范式。

第三章集合与关系包含：设A，B是任意两个集合，假如A的每一个元素是B的成员，则称A为B的子集，或A包含在B内，或B包含A。

记作A⊆B，或B⊇A。

真子集：如果集合A的每一个元素都属于B，但集合B中至少有一个元素不属于A，则称A为B的真子集，记作A⊂B。

幂集：给定集合A，由集合A的所有子集为元素组成的集合，称为集合A的幂集。

集合的交：设任意两个集合A和B，由集合A和B的所有共同元素组成的集合S，称为A和B的交集，记作A⋂B。

集合的并：设任意两个集合A和B，所有属于A或属于B的元素组成的集合S，称为A和B的集合，记作A⋃B。

集合的绝对补：设E为全集，对任一集合A关于E的补E-A，称为集合A的绝对补，记作~A。

对称差：设A，B为任意两个集合，A和B的对称差为集合S，其元素或属于A，或属于B，但不能既属于A又属于B，记作A⊕B。

序偶相等：两个序偶相等，<x，y>=<u，v>，iffx=u,y=v。

离散数学的基础知识点总结第一章命题逻辑1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假；2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积；3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反；4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假；5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写；6.真值表中值为1的项为极小项，值为0的项为极大项；7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取；8.永真式没有主合取范式，永假式没有主析取范式；9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假)10.命题逻辑的推理演算方法：P规则，T规则①真值表法；②直接证法；③归谬法；④附加前提法；第二章谓词逻辑1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质；多元谓词：谓词有n个个体，多元谓词描述个体之间的关系；2.全称量词用蕴含→，存在量词用合取^;3.既有存在又有全称量词时，先消存在量词，再消全称量词；第四章集合1.N，表示自然数集，1,2,3……，不包括0；2.基：集合A中不同元素的个数，|A|；3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)；4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2；5.集合的分划：(等价关系)①每一个分划都是由集合A的几个子集构成的集合；②这几个子集相交为空，相并为全(A)；6.集合的分划与覆盖的比较：分划：每个元素均应出现且仅出现一次在子集中；覆盖：只要求每个元素都出现，没有要求只出现一次；第五章关系1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基数2种不同的关系；为mn，A到B上可以定义mn2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系；3.全关系的性质：自反性，对称性，传递性；空关系的性质：反自反性，反对称性，传递性；全封闭环的性质：自反性，对称性，反对称性，传递性；4.前域(domR)：所有元素x组成的集合；后域(ranR)：所有元素y组成的集合；5.自反闭包：r(R)=RUI;x对称闭包：s(R)=RU1-R;传递闭包：t(R)=RU2R U3R U……6.等价关系：集合A上的二元关系R满足自反性，对称性和传递性，则R称为等价关系；7.偏序关系：集合A上的关系R满足自反性，反对称性和传递性，则称R是A上的一个偏序关系；8.covA={<x,y>|x,y属于A，y盖住x}；9.极小元：集合A中没有比它更小的元素(若存在可能不唯一)；极大元：集合A中没有比它更大的元素(若存在可能不唯一)；最小元：比集合A中任何其他元素都小(若存在就一定唯一)；最大元：比集合A中任何其他元素都大(若存在就一定唯一)；10.前提：B是A的子集上界：A中的某个元素比B中任意元素都大，称这个元素是B的上界(若存在，可能不唯一)；下界：A中的某个元素比B中任意元素都小，称这个元素是B的下界(若存在，可能不唯一)；上确界：最小的上界(若存在就一定唯一)；下确界：最大的下界(若存在就一定唯一)；第六章函数2种不同的关系，有m n种不同的函数；1.若|X|=m,|Y|=n,则从X到Y有mn2.在一个有n个元素的集合上，可以有22n种不同的关系，有n n种不同的函数，有n!种不同的双射；3.若|X|=m,|Y|=n，且m<=n，则从X到Y有A m n种不同的单射；4.单射：f:X-Y，对任意x,2x属于X,且1x≠2x，若f(1x)≠f(2x)；1满射：f:X-Y，对值域中任意一个元素y在前域中都有一个或多个元素对应；双射：f:X-Y，若f既是单射又是满射，则f是双射；5.复合函数：fºg=g(f(x));6.设函数f:A-B，g:B-C，那么①如果f,g都是单射，则fºg也是单射；②如果f,g都是满射，则fºg也是满射；③如果f,g都是双射，则fºg也是双射；④如果fºg是双射，则f是单射，g是满射；第七章代数系统1.二元运算：集合A上的二元运算就是2A到A的映射；2. 集合A上可定义的二元运算个数就是从A×A到A上的映射的个数，即从从A×A到A上函数的个数，若|A|=2,则集合A上的二元运算的个数为2*22=42=16种；3. 判断二元运算的性质方法：①封闭性：运算表内只有所给元素；②交换律：主对角线两边元素对称相等；③幂等律：主对角线上每个元素与所在行列表头元素相同；④有幺元：元素所对应的行和列的元素依次与运算表的行和列相同；⑤有零元：元素所对应的行和列的元素都与该元素相同；4.同态映射：<A,*>,<B,^>,满足f(a*b)=f(a)^f(b),则f为由<A,*>到<B,^>的同态映射；若f是双射，则称为同构；第八章群1.广群的性质：封闭性；半群的性质：封闭性，结合律；含幺半群(独异点)：封闭性，结合律，有幺元；群的性质：封闭性，结合律，有幺元，有逆元；2.群没有零元；3.阿贝尔群(交换群)：封闭性，结合律，有幺元，有逆元，交换律；4.循环群中幺元不能是生成元；5.任何一个循环群必定是阿贝尔群；第十章格与布尔代数1.格：偏序集合A中任意两个元素都有上、下确界；2.格的基本性质：1) 自反性a≤a 对偶: a≥a2) 反对称性a≤b ^ b≥a => a=b对偶:a≥b ^ b≤a => a=b3) 传递性a≤b ^ b≤c => a≤c对偶:a≥b ^ b≥c => a≥c4) 最大下界描述之一a^b≤a 对偶avb≥aA^b≤b 对偶avb≥b5）最大下界描述之二c≤a,c≤b => c≤a^b对偶c≥a,c≥b =>c≥avb6) 结合律a^(b^c)=(a^b)^c对偶av(bvc)=(avb)vc7) 等幂律a^a=a 对偶ava=a8) 吸收律a^(avb)=a 对偶av(a^b)=a9) a≤b <=> a^b=a avb=b10) a≤c,b≤d => a^b≤c^d avb≤cvd11) 保序性b≤c => a^b≤a^c avb≤avc12）分配不等式av(b^c)≤(avb)^(avc)对偶a^(bvc)≥(a^b)v(a^c)13）模不等式a≤c <=>av(b^c)≤(avb)^c3.分配格：满足a^(bvc)=(a^b)v(a^c)和av(b^c)=(avb)^(avc)；4.分配格的充要条件：该格没有任何子格与钻石格或五环格同构；5.链格一定是分配格，分配格必定是模格；6.全上界：集合A中的某个元素a大于等于该集合中的任何元素，则称a为格<A,<=>的全上界，记为1；(若存在则唯一)全下界：集合A中的某个元素b小于等于该集合中的任何元素，则称b为格<A,<=>的全下界，记为0；(若存在则唯一)7.有界格：有全上界和全下界的格称为有界格，即有0和1的格；8.补元：在有界格内，如果a^b=0,avb=1，则a和b互为补元；9.有补格：在有界格内，每个元素都至少有一个补元；10.有补分配格(布尔格)：既是有补格，又是分配格；11.布尔代数：一个有补分配格称为布尔代数；第十一章图论1.邻接：两点之间有边连接，则点与点邻接；2.关联：两点之间有边连接，则这两点与边关联；3.平凡图：只有一个孤立点构成的图；4.简单图：不含平行边和环的图；5.无向完全图：n个节点任意两个节点之间都有边相连的简单无向图；有向完全图:n个节点任意两个节点之间都有边相连的简单有向图；6.无向完全图有n(n-1)/2条边，有向完全图有n(n-1)条边；7.r-正则图：每个节点度数均为r的图；8.握手定理：节点度数的总和等于边的两倍；9.任何图中，度数为奇数的节点个数必定是偶数个；10.任何有向图中，所有节点入度之和等于所有节点的出度之和；11.每个节点的度数至少为2的图必定包含一条回路；12.可达：对于图中的两个节点v,j v，若存在连接i v到j v的路，则称i vi与v相互可达，也称i v与j v是连通的；在有向图中，若存在i v到j v的j路，则称v到j v可达；i13.强连通：有向图章任意两节点相互可达；单向连通：图中两节点至少有一个方向可达；弱连通：无向图的连通；(弱连通必定是单向连通)14.点割集：删去图中的某些点后所得的子图不连通了，如果删去其他几个点后子图之间仍是连通的，则这些点组成的集合称为点割集；割点：如果一个点构成点割集，即删去图中的一个点后所得子图是不连通的，则该点称为割点；15.关联矩阵：M(G)，m是i v与j e关联的次数，节点为行，边为列；ij无向图：点与边无关系关联数为0，有关系为1，有环为2；有向图：点与边无关系关联数为0，有关系起点为1终点为-1，关联矩阵的特点：无向图：①行：每个节点关联的边，即节点的度；②列：每条边关联的节点；有向图：③所有的入度(1)=所有的出度(0);16.邻接矩阵：A(G)，a是i v邻接到j v的边的数目，点为行，点为列；ij17.可达矩阵：P(G)，至少存在一条回路的矩阵，点为行，点为列；P(G)=A(G)+2A(G)+3A(G)+4A(G)可达矩阵的特点：表明图中任意两节点之间是否至少存在一条路，以及在任何节点上是否存在回路；A(G)中所有数的和：表示图中路径长度为1的通路条数；2A(G)中所有数的和：表示图中路径长度为2的通路条数；3A(G)中所有数的和：表示图中路径长度为3的通路条数；4A(G)中所有数的和：表示图中路径长度为4的通路条数；P(G)中主对角线所有数的和：表示图中的回路条数；18.布尔矩阵：B(G)，v到j v有路为1，无路则为0，点为行，点为列；i19.代价矩阵：邻接矩阵元素为1的用权值表示，为0的用无穷大表示，节点自身到自身的权值为0；20.生成树：只访问每个节点一次，经过的节点和边构成的子图；21.构造生成树的两种方法：深度优先；广度优先；深度优先：①选定起始点v；②选择一个与v邻接且未被访问过的节点1v；③从v出发按邻接方向继续访问，当遇到一个节点所1有邻接点均已被访问时，回到该节点的前一个点，再寻求未被访问过的邻接点，直到所有节点都被访问过一次；广度优先：①选定起始点v；②访问与v邻接的所有节点1v,2v,……,k v,这些作为第一层节点；③在第一层节点中选定一个节点v为起点；1④重复②③，直到所有节点都被访问过一次；22.最小生成树：具有最小权值(T)的生成树；23.构造最小生成树的三种方法：克鲁斯卡尔方法；管梅谷算法；普利姆算法；（1）克鲁斯卡尔方法①将所有权值按从小到大排列；②先画权值最小的边，然后去掉其边值；重新按小到大排序；③再画权值最小的边，若最小的边有几条相同的，选择时要满足不能出现回路，然后去掉其边值；重新按小到大排序；④重复③，直到所有节点都被访问过一次；（2）管梅谷算法(破圈法)①在图中取一回路，去掉回路中最大权值的边得一子图；②在子图中再取一回路，去掉回路中最大权值的边再得一子图；③重复②，直到所有节点都被访问过一次；（3）普利姆算法①在图中任取一点为起点v，连接边值最小的邻接点2v；1②以邻接点v为起点，找到2v邻接的最小边值，如果最小边值2比v邻接的所有边值都小(除已连接的边值)，直接连接，否则退回1v，1连接v现在的最小边值(除已连接的边值)；1③重复操作，直到所有节点都被访问过一次；24.关键路径例2 求PERT图中各顶点的最早完成时间, 最晚完成时间, 缓冲时间及关键路径.解：最早完成时间TE(v1)=0TE(v2)=max{0+1}=1TE(v3)=max{0+2,1+0}=2TE(v4)=max{0+3,2+2}=4TE(v5)=max{1+3,4+4}=8TE(v6)=max{2+4,8+1}=9TE(v7)=max{1+4,2+4}=6TE(v8)=max{9+1,6+6}=12 最晚完成时间TL(v8)=12TL(v7)=min{12-6}=6TL(v6)=min{12-1}=11TL(v5)=min{11-1}=10TL(v4)=min{10-4}=6TL(v3)=min{6-2,11-4,6-4}=2TL(v2)=min{2-0,10-3,6-4}=2TL(v1)=min{2-1,2-2,6-3}=0 缓冲时间TS(v1)=0-0=0TS(v2)=2-1=1TS(v3)=2-2=0TS(v4)=6-4=2TS(v5=10-8=2TS(v6)=11-9=2TS(v7)=6-6=0TS(v8)=12-12=0关键路径: v1-v3-v7-v825.欧拉路：经过图中每条边一次且仅一次的通路；欧拉回路：经过图中每条边一次且仅一次的回路；欧拉图：具有欧拉回路的图；单向欧拉路：经过有向图中每条边一次且仅一次的单向路；欧拉单向回路：经过有向图中每条边一次且仅一次的单向回路；26.（1）无向图中存在欧拉路的充要条件：①连通图；②有0个或2个奇数度节点；（2）无向图中存在欧拉回路的充要条件：①连通图；②所有节点度数均为偶数；（3）连通有向图含有单向欧拉路的充要条件：①除两个节点外，每个节点入度=出度；②这两个节点中，一个节点的入度比出度多1，另一个节点的入；度比出度少1；（4）连通有向图含有单向欧拉回路的充要条件：图中每个节点的出度=入度；27.哈密顿路：经过图中每个节点一次且仅一次的通路；哈密顿回路：经过图中每个节点一次且仅一次的回路；哈密顿图：具有哈密顿回路的图；28.判定哈密顿图（没有充要条件）必要条件：任意去掉图中n个节点及关联的边后，得到的分图数目小于等于n；充分条件：图中每一对节点的度数之和都大于等于图中的总节点数；29.哈密顿图的应用：安排圆桌会议；方法：将每一个人看做一个节点，将每个人与和他能交流的人连接，找到一条经过每个节点一次且仅一次的回路(哈密顿图)，即可；30.平面图：将图形的交叉边进行改造后，不会出现边的交叉，则是平面图；31.面次：面的边界回路长度称为该面的次；32.一个有限平面图，面的次数之和等于其边数的两倍；33.欧拉定理：假设一个连通平面图有v个节点，e条边，r个面，则v-e+r=2；34.判断是平面图的必要条件：(若不满足，就一定不是平面图)设图G是v个节点，e条边的简单连通平面图，若v>=3，则e<=3v-6；35.同胚：对于两个图G1,G2，如果它们是同构的，或者通过反复插入和除去2度节点可以变成同构的图，则称G1，G2是同胚的；36.判断G是平面图的充要条件：图G不含同胚于K3.3或K5的子图；37.二部图：①无向图的节点集合可以划分为两个子集V1，V2；②图中每条边的一个端点在V1，另一个则在V2中；完全二部图：二部图中V1的每个节点都与V2的每个节点邻接；判定无向图G为二部图的充要条件：图中每条回路经过边的条数均为偶数；38.树：具有n个顶点n-1条边的无回路连通无向图；39.节点的层数：从树根到该节点经过的边的条数；40.树高：层数最大的顶点的层数；41.二叉树：①二叉树额基本结构状态有5种；②二叉树内节点的度数只考虑出度，不考虑入度；③二叉树内树叶的节点度数为0，而树内树叶节点度数为1；④二叉树内节点的度数=边的总数(只算出度)；握手定理“节点数=边的两倍”是在同时计算入度和出度的时成立；⑤二叉树内节点的总数=边的总数+1；⑥位于二叉树第k层上的节点，最多有12 k个(k>=1)；⑦深度为k的二叉树的节点总数最多为k2-1个，最少k个(k>=1)；⑧如果有n个叶子，2n个2度节点，则0n=2n+1；42.二叉树的节点遍历方法：先根顺序（DLR）；中根顺序（LDR）；后根顺序（LRD）；43.哈夫曼树：用哈夫曼算法构造的最优二叉树；44.最优二叉树的构造方法：①将给定的权值按从小到大排序；②取两个最小值分支点的左右子树(左小右大)，去掉已选的这两个权值，并将这两个最小值加起来作为下一轮排序的权值；③重复②，直达所有权值构造完毕；45.哈夫曼编码：在最优二叉树上，按照左0右1的规则，用0和1代替所有边的权值；每个节点的编码：从根到该节点经过的0和1组成的一排编码；。