北京大学：《离散数学》系列课程之一《集合论与图论》第1讲 命题逻辑基础

第1讲命题逻辑基础 1.命题、命题符号化 2.合式公式、真值表、永真式 3.逻辑等值式、推理定律 4.形式化证明 《集合论与图论》第1讲

《集合论与图论》第1讲 1 第1讲 命题逻辑基础 1. 命题、命题符号化 2. 合式公式、真值表、永真式 3. 逻辑等值式、推理定律 4. 形式化证明

命题符号化 静简单命题:p,qr;p1q1r1 癱联结词 合取联结词:∧ 析取联结词:√ 否定联结词: 蕴涵联结词:→ 等价联结词: 逻辑真值:0,1 《集合论与图论》第1讲

《集合论与图论》第1讲 2 命题符号化 简单命题： p,q,r,p1,q1,r1,… 联结词： 合取联结词：∧ 析取联结词：∨ 否定联结词：¬ 蕴涵联结词：→ 等价联结词：↔ 逻辑真值： 0，1

真值表 truth-table 壽赋值( assignment):给变元指定0、1值 n个变元,共有2种不同的赋值 pq-0p0∧qpvq0->q0>q 00 010 000 00 1101 《集合论与图论》第1讲

《集合论与图论》第1讲 3 真值表(truth-table) 赋值(assignment)：给变元指定0、1值 n个变元，共有2n种不同的赋值 1 1 0 0 ¬p 1 0 0 1 1 1 0 1 0 1 1 1 0 0 0 1 0 1 0 1 0 0 1 1 p q p∧q p∨q p→q p↔q

真值表(续) p q (pq)→r|-0-qMr 000 001 00 00 《集合论与图论》第1讲

《集合论与图论》第1讲 4 真值表(续) 1 1 1 1 1 1 0 1 ¬p∨¬q∨r 0 1 0 1 0 1 0 1 r 1 1 1 1 1 1 0 1 0 0 1 1 0 0 1 1 0 0 0 0 1 1 1 1 p q (p∧q)→r

永真式 tautology ●永真式在各种赋值下取值均为真(重言式) 永假式在各种赋值下取值均为假(矛盾式 可满足式:非永假式 pq-(p)-py-g-(×Q)(-p~ 001 1111 10 《集合论与图论》第1讲

《集合论与图论》第1讲 5 永真式(tautology) 永真式:在各种赋值下取值均为真(重言式) 永假式:在各种赋值下取值均为假(矛盾式) 可满足式：非永假式 1 1 1 1 1 1 1 0 1 1 1 0 0 1 0 1 0 0 1 1 p q ¬(p∧q) ¬p∨¬q ¬(p∧q)↔(¬p∨¬q)

逻辑等值式( dentities 等值:AB是永真式 例如:(pAq)-xr分-0Vqr 《集合论与图论》第1讲

《集合论与图论》第1讲 6 逻辑等值式(identities) 等值： A⇔B 读作：A等值于B 含义：A与B在各种赋值下取值均相等 A⇔B 当且仅当 A↔B是永真式 例如： (p∧q)→r ⇔ ¬p∨¬q∨r

常用逻辑等值式(关于v与入) 壽幂等律( idempotent laws) AAVA A→AAA 秦交换律( commutative laws) AVBOBVA AABOBAA 《集合论与图论》第1讲

《集合论与图论》第1讲 7 常用逻辑等值式(关于∨与∧) 幂等律(idempotent laws) A⇔A∨A A⇔A∧A 交换律(commutative laws) A∨B⇔B∨A A∧B⇔B∧A

常用逻辑等值式(关于v与入) 律( associative laws) (AvBC←Av(BvC) (AABACSAA BAC 秦分配律( distributive laws AVBACOAVB A(AVC) AA BVC(AAB VAAC) 《集合论与图论》第1讲

《集合论与图论》第1讲 8 常用逻辑等值式(关于∨与∧) 结合律(associative laws) (A∨B)∨C⇔A∨(B∨C) (A∧B)∧C⇔A∧(B∧C) 分配律(distributive laws) A∨(B∧C)⇔(A∨B )∧(A∨C ) A∧(B∨C)⇔(A∧B )∨(A∧C )

常用逻辑等值式(关于v与入) 秦吸收律( absorption laws) AVAABOA AA(AVBOA 《集合论与图论》第1讲

《集合论与图论》第1讲 9 常用逻辑等值式(关于∨与∧) 吸收律(absorption laws) A∨(A∧B)⇔A A∧(A∨B)⇔A

常用逻辑等值式(关于 双重否定律( double negation law - AeA 壽德●摩根律( DeMorgan's laws) (AVBe-AA-B (AABS-AV-B 《集合论与图论》第1讲

《集合论与图论》第1讲 10 常用逻辑等值式(关于¬) 双重否定律(double negation law) ¬¬A⇔A 德●摩根律(DeMorgan’s laws) ¬(A∨B)⇔¬A∧¬B ¬(A∧B)⇔¬A∨¬B