离散数学全课件含复习题1数理逻辑

离散数学(DiscreteMathematics)是一门 于著名的哥尼斯堡七桥问题：18世 于两岛间架有七座桥。问题是：一个人怎样走才可以不重 独立完成作业是学习的重要。学时所悉的运用，掌握基本解题方法，从而达到 概念 判断

)：所有金属都导电。(一般规律) 第一章命题逻辑第一章命题逻辑称该命题的真值为真，记作T(True)。则称该命题的真值为假，记作F(False)。

管怎样的推论，理发师所说的话总是自相矛盾简单命题(原子命题)：由最简单的陈述 1-21-2(1否定“”(3析取

(2合取(4)异或 (5)蕴涵“fi (6)等价“«（一元联结词（一元联结词用于：对一个命题P的否定，写成P，并读成PPFTTFPPFTTF ...”“尽管…还

QQFFFFTFTFFTTT PQPQFFFFTTTFTTTT 22”（二元联结词PQ PQ FFFFTTTFTTTF可写成PQ，读PQ的真值为 Q(P∧Q)∨(Q∧Pfifi表示“如果 PfiQ：也称之为蕴涵式，读成“若P则Q”。称P是PfiQ的前件，Q是PfiQ的后PPfiQ的真值PfiQ的真值为假，当且仅当P为真，Q为假。注意：当前件PPfiQ为T。PF

F

Pfi T令：P：天气好。Q注：联结词fi较、∧、∨难于理解，然而由于PfiQ真假值的这种取法也有人为因素，表现在：若前件P为假，不论后件QPfiQ为真。PQ：⊿ABC是等边三角形当且仅当PPQ的真值PQP⇆FFTFTFTFFTTTPQP⇆FFFFTTFTFTTFTFFTFFTTTTTT特别要注意“fi”的用法，它既表示“充分条 全没有联系题可加以联结词而形成新的复P：2+2=4；Q：雪是黑的。 P⋀Q：2+2=4并且雪是黑的。P→Q：若2+2=4，则雪是黑的。P⇄Q：2+2=4当且仅当雪是黑的。已知 已知Q为

PfiQ为T，则Q为( 。已知P已知P

Q为T，P为T,则Q为( Q为F，P为T,则Q为 P⇆P的真值为 PfiP的真值为 体含义(真值)的。例如：“3是素数。” ，则A是合 (AfiB)和(A⇆B)都是合 。 ：P∧Q，(P∧Q)，PfiR，(PfiR)， 运算次序优先级：┐，，，→，«式可以写成：P∧Q，Pfi (PfiQ)∨Q的真值表如PQPPfi(PfiFFTFFFTTTTTFFTTTTFTTPQRFFFTTFFTTTFTFFTFTTTTTFFTTTFTTTTTFFFTTTTT (P∧Q) 。 去。R：小 该命题可写成：(P∧Q)fiR 该命题可写成：(P∧Q)fiR(P∨Q)fi例3.仅当天不下雨且我有时间，才上街。Rfi该命题可写成：( Q)∧(Pfi或写成：P⇆Q P是Q 例5.若天不下雨，我就上街；否则在家。P：天下雨。Q：我上街。R：我在家。该(PfiQ)∧(PfiR).注意：中间的联结词一定是“∧”，而不是“∨定是“∧”。如果写成(PfiQ)∨(Pfi 1，6，8， PFTFTTF可见不论P取什么真值P∨P的真值总是为真，P∧P的真值总是为假。故称P∨P为重言式(永真式)，称P∧P为2.重言式 A(P1,P2,…,Pn)是含有命题变元P1,P2,…,Pn题，如不论对P1,P2…,Pn作任何指派，都使得A(P1,P,…Pn)为真 式),也称之永真式(永假式)。不是 方法1例如，证明(P∧(PfiQ))fiQ为重言PQPfiP∧(Pfi(P∧(PfiQ))fiFFTFTFTTFTTFFFTTTTTT如果A是永真式，则A(AfiB)和(A⇆B)置换式A(P1,P2,…,Pn)是含有命题变元P1,P2,…,Pn 某个Pi(如果Pi在A(P1,P2,…,Pn)中多处出现，则各处均用X替换)，其余变元不变，替换后得到 B，则称B是A(P1,P2,…,Pn)的置换式。1-51-5PQPfiPQPfi FFTTTFTTTTTFFFFTTTTT派，都使得PfiQ、P∨Q和QfiP的 注：“⇔”是关系符号，表示两个命题之间的关系，而“⇆”是联结词符号，联结两个原子等值定理：A⇔B当且仅当AB证明：P⇄Q⇔（P∧Q）∨（P∧ P⇄Q（P∧Q)∨(P∧FFTTFTFFTFFFTTTT 结合律P∧(Q∧R) 分配律P∧(Q∨R) P∨ P∧

吸收律 互补律P∨P«

(P∨Q)∧(P∨

P∧ Q→P⇄P⇄ P⇄Q⇔（P∧Q）∨（P∧ ，如果XY，用Y B，则AB。 P→(Q→R)⇔P→(Q∨R)化归 P∨(Q∨R)化归⇔(P∨Q)∨R结合律⇔(P∧Q)∨R(德 ⇔P∧Q→R化归 则A(P1,P2,…, B(P1,P2,…,1-5.重言 有些重言()式，如(P∧(PfiQ))fiQ，公式中间是“fi”联结词，是很重要的，称之为重定义：如果AfiB是重言式，则称A重言(永真)蕴涵B，记作AB。上式可以写成(P∧(Pfi AAAAfi T T F T先看一看AfiB的真值表，如果AfiB为 \P∧(PfiQ)前件P(PfiQ) （Q∧（P→Q）⇒P？Q∧（P→Q）⇒证法1假设（P→Q）∧（Q→R）为真，有R为真，故（P→Q）∧（Q→R）⇒P→R Q为真，则Q→R为假，(1)(3) PPfi (Pfi(9)P,Q

(2)(4)(6)QPfi (Pfi P∧(PfiQ∧(Pfi (PfiQ)∧(QfiR)Pfi(14)(15)B(16)B 其真值为T，即P↑Q=(P∧Q)。 其真值为F，即P↓Q=(P∨Q). P

f8 TTFTTFFTFTFTFTFTFTTFTFFTFTTFFTFTTFFT T F F F T F F TTFTTFFTFTFTFTFTFTTFTFFTFTTFFTFTTFf1T，f2F，f3P，f4Q，f5┐P，f6┐Q，f7PQ，f8P↑Qf9PQ，f10P↓Q，f11f13P«Q，f14 ┐(P«Q)，f15Q→P，f16┐(Q→P)定理2：｛┐，｝｛｝，｛P P→Q= Q= Q=┐P= Q=例子：｛↑｝、｛↓｝、｛┐｝、｛┐，｝尽管｛┐｝、｛┐，｝为极小联结词完备集，但使用起来不够方便，一般采用｛┐1-6.等 例如:：P(P∨T)∧注意：否定

(P∧F)∨ 定理1-5.1令A(P,P2,…,P)是一个只含有联结 A*(P1,P2,…, 令A(P,Q) A*( P∧ A*(P,推论:A(P1,P2,…, (((P∧Q)∨(P∧((P∨Q)∧(P∨Q))∧ 13，14，23， 式中只含有联结词、∨和∧。如P、P、P∧Q、P∧Q∧析取式：是用“∨联结命题变元或变元的否定如P、P、P∨Q、P∨Q∨ P P∴P是合(析)取式A1∨A2∨...∨An(n≥1其中每个AiA1∧A2∧...∧An(n≥1)其中每个Ai(P∧Q)∨(P∧ (P∨Q)∧(P∨ 4. Pfi (P∧Q)∨(P∧ (PfiQ)∧(Qfi (P∨Q)∧(P∨ 定律将后移到命题变元之 P∧ P∨ (PQ)fiR((P∨Q)∧(P∨(P∧Q)∨( 式(P«Q)fiR ((P∧Q)∨(P∧Q))∨((P∨(P∨ 式一个的析取范式与合取范式的形式P∧Q、P∧QP∧QP∧ P∧ P∧ 如果变元P被指派为F,P在小项中以P形式出现PQPfiFFTTPQPfiFFTTFTTFTFFFTTTT(P∧Q)∨(P« (P∧ A1∨A2∨...∨An真式(R∨R)形式补R。 Pfi (P∧(Q∨Q))∨((P∨P)∧(P∧Q)∨(P∧Q)∨(P∧Q)∨((P∧Q)∨(P∧PQP∨P∨FFFTTTFTTFTTTFTTFTTTTTTFA1∧A2∧∧An其中每个 如变元P被指派为T，P在大项中以P形式出现。PQPfiFFTTFTTFTFFFTTTTPfi P« (P∨Q)∧(PQRTTFTTTFFm011,m101,m111求它的主合取范式. A1∧A2∧...∧An联结永假式(R∧R)形式补R。 (PfiQ)fi(P∨Q)∨R(P∧Q)∨R(P∨R)∧(Q∨R)(P∨(Q∧Q)∨R)∧((P∧P)∨Q∨R)(P∨Q∨R)∧(P∨Q∨R)∧(P∨Q∨R)∧(P∨例.安排课表，教语言课的教师希望将课程安排(L1∨L3)∧(M2∨M3)∧(P1∨P2将(L1∨L3