北大集合论与图论1

2020/7/8《集合论与图论》第1讲1第1讲命题逻辑基础1.命题、命题符号化2.合式公式、真值表、永真式3.逻辑等值式、推理定律4.形式化证明2020/7/8《集合论与图论》第1讲2命题符号化简单命题：p,q,r,p1,q1,r1,…联结词：合取联结词：析取联结词：否定联结词：蕴涵联结词：等价联结词：逻辑真值：0，12020/7/8《集合论与图论》第1讲3真值表(truth-table)赋值(assignment)：给变元指定0、1值n个变元，共有2n种不同的赋值pqppqpqpqpq00110101110000010111110110012020/7/8《集合论与图论》第1讲4真值表(续)pqr(pq)rpqr00001111001100110101010111111101111111012020/7/8《集合论与图论》第1讲5永真式(tautology)永真式:在各种赋值下取值均为真(重言式)永假式:在各种赋值下取值均为假(矛盾式)可满足式：非永假式pq(pq)pq(pq)(pq)001101011110111011112020/7/8《集合论与图论》第1讲6逻辑等值式(identities)等值：AB读作：A等值于B含义：A与B在各种赋值下取值均相等AB当且仅当AB是永真式例如：(pq)rpqr2020/7/8《集合论与图论》第1讲7常用逻辑等值式(关于与)幂等律(idempotentlaws)AAAAAA交换律(commutativelaws)ABBAABBA2020/7/8《集合论与图论》第1讲8常用逻辑等值式(关于与)结合律(associativelaws)(AB)CA(BC)(AB)CA(BC)分配律(distributivelaws)A(BC)(AB)(AC)A(BC)(AB)(AC)2020/7/8《集合论与图论》第1讲9常用逻辑等值式(关于与)吸收律(absorptionlaws)A(AB)AA(AB)A2020/7/8《集合论与图论》第1讲10常用逻辑等值式(关于)双重否定律(doublenegationlaw)AA德●摩根律(DeMorgan’slaws)(AB)AB(AB)AB2020/7/8《集合论与图论》第1讲11常用逻辑等值式(关于0,1)零律(dominancelaws)A11A00同一律(identitylaws)A0AA1A2020/7/8《集合论与图论》第1讲12常用逻辑等值式(关于0,1)排中律(excludedmiddle)AA1矛盾律(contradiction)AA02020/7/8《集合论与图论》第1讲13常用逻辑等值式(关于)蕴涵等值式(conditionalasdisjunction)ABAB假言易位(contrapositivelaw)ABBA归谬论(AB)(AB)A2020/7/8《集合论与图论》第1讲14常用逻辑等值式(关于)等价等值式(biconditionalasimplication)AB(AB)(BA)等价否定等值式ABAB2020/7/8《集合论与图论》第1讲15等值式模式A，B，C代表任意的公式上述等值式称为等值式模式每个等值式模式都给出了无穷多个同类型的具体的等值式。2020/7/8《集合论与图论》第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)2020/7/8《集合论与图论》第1讲17对偶原理一个逻辑等值式，如果只含有，，，0，1那么，同时把与互换把0与1互换得到的还是等值式2020/7/8《集合论与图论》第1讲18对偶原理(举例)分配律A(BC)(AB)(AC)A(BC)(AB)(AC)排中律(excludedmiddle)AA1矛盾律(contradiction)AA02020/7/8《集合论与图论》第1讲19对偶原理(举例、续)零律(dominancelaws)A11A00同一律(identitylaws)A0AA1A2020/7/8《集合论与图论》第1讲20等值演算（举例）例：(pq)rpqr解：(pq)r(pq)r（蕴涵等值式）(pq)r（德●摩根律）pqr（结合律）2020/7/8《集合论与图论》第1讲21推理定律(deductionlaws)推出：AB读作：A推出B含义：当A为真时，B也为真AB当且仅当AB是永真式例如：(pq)pq2020/7/8《集合论与图论》第1讲22推理定律（举例）(pq)pq(pq)pq是永真式pqpqp(pq)p(pq)pq0011010101111100010011112020/7/8《集合论与图论》第1讲23常见推理定律附加律A(AB)化简律(AB)A2020/7/8《集合论与图论》第1讲24常见推理定律（续）假言推理(AB)AB拒取式(AB)BA析取三段论(AB)BA2020/7/8《集合论与图论》第1讲25常见推理定律（续）假言三段论(AB)(BC)(AC)等价三段论(AB)(BC)(AC)2020/7/8《集合论与图论》第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)2020/7/8《集合论与图论》第1讲27推理规则前提引入规则：在证明的任何步骤上都可以引入前提结论引入规则：在证明的任何步骤上所得到的结论都可以做为后继证明的前提置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中又一个公式2020/7/8《集合论与图论》第1讲28推理规则（续）附加规则：A(AB)A————AB化简规则：(AB)A2020/7/8《集合论与图论》第1讲29推理规则（续）假言推理规则：(AB)ABABA————B拒取式规则：(AB)BA2020/7/8《集合论与图论》第1讲30推理规则（续）假言三段论规则：(AB)(BC)(AC)ABBC————AC析取三段论规则：(AB)BA2020/7/8《集合论与图论》第1讲31推理规则（续）构造性两难推理规则：(AB)(CD)(AC)(BD)破坏性两难推理规则：(AB)(CD)(BD)(AC)2020/7/8《集合论与图论》第1讲32推理规则（续）合取引入规则：(A)(B)(AB)AB————AB2020/7/8《集合论与图论》第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)(蕴涵等值式)2020/7/8《集合论与图论》第1讲34总结等值式（16组、24条）幂等律、交换律、结合律、分配律、吸收律；双重否定律、德●摩根律；零律、同一律、排中律、矛盾律；蕴涵等值式、等价等值式、假言易位、等价否定等值式归谬论推理定律（9条）附加、化简假言推理、拒取式、析取三段论、假言三段论、等价三段论、构造性两难（特殊形式）、破坏性两难2020/7/8《集合论与图论》第1讲35习题证明下面的等值式：(1)(pq)(pr)p(qr)(2)(pq)(pq)(pq)(pq)证明本次课讲的基本等值式和推理定律