《集合论与图论》第1讲1 第1讲命题逻辑基础 ? 1. 命题、命题符号化 ? 2. 合式公式、真值表、永真式 ? 3. 逻辑等值式、推理定律 ? 4. 形式化证明 《集合论与图论》第1讲2 命题符号化 ?简单命题：p,q,r,p 1 ,q 1 ,r 1 ,… ?联结词： ?合取联结词：∧ ?析取联结词：∨ ?否定联结词：? ?蕴涵联结词：→ ?等价联结词：? ?逻辑真值：0，1 《集合论与图论》第1讲3 真值表(truth-table) ?赋值(assignment)：给变元指定0、1值 ?n个变元，共有2 n 种不同的赋值 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?qp→qp∨qp∧qqp 《集合论与图论》第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)→rqp 《集合论与图论》第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)qp 《集合论与图论》第1讲6 逻辑等值式(identities) ?等值：A?B ?读作：A等值于B ?含义：A与B在各种赋值下取值均相等 ?A?B 当且仅当A?B是永真式 ?例如：(p∧q)→r ??p∨?q∨r 《集合论与图论》第1讲7 常用逻辑等值式(关于∨与∧) ?幂等律(idempotent laws) A?A∨A A?A∧A ?交换律(commutative laws) A∨B?B∨A A∧B?B∧A 《集合论与图论》第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 ) 《集合论与图论》第1讲9 常用逻辑等值式(关于∨与∧) ?吸收律(absorption laws) A∨(A∧B)?A A∧(A∨B)?A 《集合论与图论》第1讲10 常用逻辑等值式(关于?) ?双重否定律(double negation law) ??A?A ?德●摩根律(DeMorgan’s laws) ?(A∨B)??A∧?B ?(A∧B)??A∨?B 《集合论与图论》第1讲11 常用逻辑等值式(关于0,1) ?零律(dominance laws) A∨1?1 A∧0?0 ?同一律(identity laws) A∨0?A A∧1?A 《集合论与图论》第1讲12 常用逻辑等值式(关于0,1) ?排中律(excluded middle) A∨?A?1 ?矛盾律(contradiction) A∧?A?0 《集合论与图论》第1讲13 常用逻辑等值式(关于→) ?蕴涵等值式(conditional as disjunction) A→B??A∨B ?假言易位(contrapositive law) A→B??B→?A ?归谬论 (A→B )∧( A→?B )??A 《集合论与图论》第1讲14 常用逻辑等值式(关于?) ?等价等值式(biconditional as implication) A?B?(A→B)∧(B→A) ?等价否定等值式 A?B??A??B 《集合论与图论》第1讲15 等值式模式 ? A，B，C代表任意的公式 ?上述等值式称为等值式模式 ?每个等值式模式都给出了无穷多个同类型的具 体的等值式。 《集合论与图论》第1讲16 等值式模式(举例) ?蕴涵等值式模式 A→B??A∨B ?取A=p，B=q时，得到 p→q??p∨q ?取A=p∨q∨r，B=p∧q时，得到 (p∨q∨r)→(p∧q)??(p∨q∨r)∨(p∧q) 《集合论与图论》第1讲17 对偶原理 一个逻辑等值式，如果 ?只含有∧，∨，?，0，1 那么，同时 ?把∨与∧互换 ?把0 与1互换 得到的还是等值式 《集合论与图论》第1讲18 对偶原理(举例) ?分配律 A∨(B∧C)?(A∨B )∧(A∨C ) A∧(B∨C)?(A∧B )∨(A∧C ) ?排中律(excluded middle) A∨?A?1 ?矛盾律(contradiction) A∧?A?0 《集合论与图论》第1讲19 对偶原理(举例、续) ?零律(dominance laws) A∨1?1 A∧0?0 ?同一律(identity laws) A∨0?A A∧1?A 《集合论与图论》第1讲20 等值演算（举例） ?例：(p∧q)→r??p∨?q∨r 解： (p∧q)→r ??(p∧q)∨r （蕴涵等值式） ? (?p∨?q)∨r （德●摩根律） ??p∨?q∨r （结合律） 《集合论与图论》第1讲21 推理定律(deduction laws) ?推出：A?B ?读作：A推出B ?含义：当A为真时，B也为真 ?A?B 当且仅当A → B是永真式 ?例如：(p∨q ) ∧?p ?q 《集合论与图论》第1讲22 推理定律（举例） ?(p∨q )∧?p ? q ?(p∨q )∧?p → q是永真式 1 1 0 0 ?p 1 1 1 1 0 1 0 0 0 1 1 1 0 1 0 1 0 0 1 1 (p∨q)∧?p→q(p∨q)∧?pp∨qqp 《集合论与图论》第1讲23 常见推理定律 ?附加律 A?(A∨B) ?化简律 (A∧B)?A 《集合论与图论》第1讲24 常见推理定律（续） ?假言推理 (A→B ) ∧ A?B ?拒取式 (A→B ) ∧?B ??A ?析取三段论 (A∨B )∧?B ?A 《集合论与图论》第1讲25 常见推理定律（续） ?假言三段论 (A→B)∧(B→C)?(A→C) ?等价三段论 (A?B)∧(B?C)?(A?C) 《集合论与图论》第1讲26 常见推理定律（续） ?构造性两难 (A→B)∧(C→D)∧(A∨C)?(B∨D) ?构造性两难(特殊形式) (A→B)∧(?A→B)∧(A∨?A)?B ?破坏性两难 (A→B)∧(C→D)∧(?B∨?D)?(?A∨?C) 《集合论与图论》第1讲27 推理规则 ?前提引入规则：在证明的任何步骤上都 可以引入前提 ?结论引入规则：在证明的任何步骤上所 得到的结论都可以做为后继证明的前提 ?置换规则：在证明的任何步骤上，命题 公式中的子公式都可以用与之等值的公 式置换，得到公式序列中又一个公式 《集合论与图论》第1讲28 推理规则（续） ?附加规则：A?(A∨B) A ———— ∴ A∨B ?化简规则：(A∧B)?A 《集合论与图论》第1讲29 推理规则（续） ?假言推理规则：(A→B )∧A?B A→B A ———— ∴ B ?拒取式规则：(A→B )∧?B ??A 《集合论与图论》第1讲30 推理规则（续） ?假言三段论规则： (A→B)∧(B→C)?(A→C) A→B B→C ———— ∴ A → C ?析取三段论规则：(A∨B )∧?B ?A 《集合论与图论》第1讲31 推理规则（续） ?构造性两难推理规则： (A→B)∧(C→D)∧(A∨C)?(B∨D) ?破坏性两难推理规则： (A→B)∧(C→D)∧(?B∨?D)?(?A∨?C) 《集合论与图论》第1讲32 推理规则（续） ?合取引入规则：(A)∧(B)?(A∧B) A B ———— ∴ A∧B 《集合论与图论》第1讲33 证明(举例) ?证明：(p∧q)→r?q→(p→r) (p∧q) → r ??(p∧q)∨r (蕴涵等值式) ? (?p∨?q)∨r (德●摩根律) ??q∨(?p∨r)(交换律、结合律) ? q →(?p∨r)(蕴涵等值式) ? q→(p→r)(蕴涵等值式) 《集合论与图论》第1讲34 总结 ?等值式（16组、24条） ?幂等律、交换律、结合律、分配律、吸收律； ?双重否定律、德●摩根律； ?零律、同一律、排中律、矛盾律； ?蕴涵等值式、等价等值式、假言易位、等价否定等值式 ?归谬论 ?推理定律（9条） ?附加、化简 ?假言推理、拒取式、析取三段论、假言三段论、 ?等价三段论、构造性两难（特殊形式）、破坏性两难 《集合论与图论》第1讲35 习题 ?证明下面的等值式： (1) (p→q )∧(p→r) ? p→(q∧r) (2) (p∧?q)∨(?p∧q) ? (p∨q)∧?(p∧q) ?证明本次课讲的基本等值式和推理定律