北大集合论与图论

2020/6/10,集合论与图论第1讲,1,第1讲命题逻辑基础,1.命题、命题符号化2.合式公式、真值表、永真式3.逻辑等值式、推理定律4.形式化证明,2020/6/10,集合论与图论第1讲,2,命题符号化,简单命题：p,q,r,p1,q1,r1,联结词：合取联结词：析取联结词：否定联结词：蕴涵联结词：等价联结词：逻辑真值：0，1,2020/6/10,集合论与图论第1讲,3,真值表(truth-table),赋值(assignment)：给变元指定0、1值n个变元，共有2n种不同的赋值,2020/6/10,集合论与图论第1讲,4,真值表(续),2020/6/10,集合论与图论第1讲,5,永真式(tautology),永真式:在各种赋值下取值均为真(重言式)永假式:在各种赋值下取值均为假(矛盾式)可满足式：非永假式,2020/6/10,集合论与图论第1讲,6,逻辑等值式(identities),等值：AB读作：A等值于B含义：A与B在各种赋值下取值均相等AB当且仅当AB是永真式例如：(pq)rpqr,2020/6/10,集合论与图论第1讲,7,常用逻辑等值式(关于与),幂等律(idempotentlaws)AAAAAA交换律(commutativelaws)ABBAABBA,2020/6/10,集合论与图论第1讲,8,常用逻辑等值式(关于与),结合律(associativelaws)(AB)CA(BC)(AB)CA(BC)分配律(distributivelaws)A(BC)(AB)(AC)A(BC)(AB)(AC),2020/6/10,集合论与图论第1讲,9,常用逻辑等值式(关于与),吸收律(absorptionlaws)A(AB)AA(AB)A,2020/6/10,集合论与图论第1讲,10,常用逻辑等值式(关于),双重否定律(doublenegationlaw)AA德摩根律(DeMorganslaws)(AB)AB(AB)AB,2020/6/10,集合论与图论第1讲,11,常用逻辑等值式(关于0,1),零律(dominancelaws)A11A00同一律(identitylaws)A0AA1A,2020/6/10,集合论与图论第1讲,12,常用逻辑等值式(关于0,1),排中律(excludedmiddle)AA1矛盾律(contradiction)AA0,2020/6/10,集合论与图论第1讲,13,常用逻辑等值式(关于),蕴涵等值式(conditionalasdisjunction)ABAB假言易位(contrapositivelaw)ABBA归谬论(AB)(AB)A,2020/6/10,集合论与图论第1讲,14,常用逻辑等值式(关于),等价等值式(biconditionalasimplication)AB(AB)(BA)等价否定等值式ABAB,2020/6/10,集合论与图论第1讲,15,等值式模式,A，B，C代表任意的公式上述等值式称为等值式模式每个等值式模式都给出了无穷多个同类型的具体的等值式。,2020/6/10,集合论与图论第1讲,16,等值式模式(举例),蕴涵等值式模式ABAB取A=p，B=q时，得到pqpq取A=pqr，B=pq时，得到(pqr)(pq)(pqr)(pq),2020/6/10,集合论与图论第1讲,17,对偶原理,一个逻辑等值式，如果只含有，0，1那么，同时把与互换把0与1互换得到的还是等值式,2020/6/10,集合论与图论第1讲,18,对偶原理(举例),分配律A(BC)(AB)(AC)A(BC)(AB)(AC)排中律(excludedmiddle)AA1矛盾律(contradiction)AA0,2020/6/10,集合论与图论第1讲,19,对偶原理(举例、续),零律(dominancelaws)A11A00同一律(identitylaws)A0AA1A,2020/6/10,集合论与图论第1讲,20,等值演算（举例）,例：(pq)rpqr解：(pq)r(pq)r（蕴涵等值式）(pq)r（德摩根律）pqr（结合律）,2020/6/10,集合论与图论第1讲,21,推理定律(deductionlaws),推出：AB读作：A推出B含义：当A为真时，B也为真AB当且仅当AB是永真式例如：(pq)pq,2020/6/10,集合论与图论第1讲,22,推理定律（举例）,(pq)pq(pq)pq是永真式,2020/6/10,集合论与图论第1讲,23,常见推理定律,附加律A(AB)化简律(AB)A,2020/6/10,集合论与图论第1讲,24,常见推理定律（续）,假言推理(AB)AB拒取式(AB)BA析取三段论(AB)BA,2020/6/10,集合论与图论第1讲,25,常见推理定律（续）,假言三段论(AB)(BC)(AC)等价三段论(AB)(BC)(AC),2020/6/10,集合论与图论第1讲,26,常见推理定律（续）,构造性两难(AB)(CD)(AC)(BD)构造性两难(特殊形式)(AB)(AB)(AA)B破坏性两难(AB)(CD)(BD)(AC),2020/6/10,集合论与图论第1讲,27,推理规则,前提引入规则：在证明的任何步骤上都可以引入前提结论引入规则：在证明的任何步骤上所得到的结论都可以做为后继证明的前提置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中又一个公式,2020/6/10,集合论与图论第1讲,28,推理规则（续）,附加规则：A(AB)AAB化简规则：(AB)A,2020/6/10,集合论与图论第1讲,29,推理规则（续）,假言推理规则：(AB)ABABAB拒取式规则：(AB)BA,2020/6/10,集合论与图论第1讲,30,推理规则（续）,假言三段论规则：(AB)(BC)(AC)ABBCAC析取三段论规则：(AB)BA,2020/6/10,集合论与图论第1讲,31,推理规则（续）,构造性两难推理规则：(AB)(CD)(AC)(BD)破坏性两难推理规则：(AB)(CD)(BD)(AC),2020/6/10,集合论与图论第1讲,32,推理规则（续）,合取引入规则：(A)(B)(AB)ABAB,2020/6/10,集合论与图论第1讲,33,证明(举例),证明：(pq)rq(pr)(pq)r(pq)r(蕴涵等值式)(pq)r(德摩根律)q(pr)(交换律、结合律)q(pr)(蕴涵等值式)q(pr)(蕴涵等值式),2020/6/10,集合论与图论第1讲,34,总结,等值式（16组、24条）幂等律、交换律、结合律、分配律、吸收律；双重否定律、德摩根律；零律、同一律、排中律、矛盾律；蕴涵等值式、等价等值式、假言易位、等价否定等值式归谬