北大集合论与图论.ppt

《北大集合论与图论.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、第1讲命题逻辑基础1.命题、命题符号化2.合式公式、真值表、永真式3.逻辑等值式、推理定律4.形式化证明2021/8/311《集合论与图论》第1讲命题符号化简单命题：p,q,r,p1,q1,r1,…联结词：合取联结词：析取联结词：否定联结词：蕴涵联结词：等价联结词：逻辑真值：0，12021/8/312《集合论与图论》第1讲真值表(truth-table)赋值(assignment)：给变元指定0、1值n个变元，共有2n种不同的赋值pqppqpqpqpq00110101110000010111110110012021/8/313《集合论与图论》

2、第1讲真值表(续)pqr(pq)rpqr00001111001100110101010111111101111111012021/8/314《集合论与图论》第1讲永真式(tautology)永真式:在各种赋值下取值均为真(重言式)永假式:在各种赋值下取值均为假(矛盾式)可满足式：非永假式pq(pq)pq(pq)(pq)001101011110111011112021/8/315《集合论与图论》第1讲逻辑等值式(identities)等值：AB读作：A等值于B含义：A与B在各种赋值下取值均相等AB当且仅当AB是永真式例如：(

3、pq)rpqr2021/8/316《集合论与图论》第1讲常用逻辑等值式(关于与)幂等律(idempotentlaws)AAAAAA交换律(commutativelaws)ABBAABBA2021/8/317《集合论与图论》第1讲常用逻辑等值式(关于与)结合律(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)2021/8/318《集合论与图论》第1讲常用逻辑等值式

4、(关于与)吸收律(absorptionlaws)A(AB)AA(AB)A2021/8/319《集合论与图论》第1讲常用逻辑等值式(关于)双重否定律(doublenegationlaw)AA德●摩根律(DeMorgan’slaws)(AB)AB(AB)AB2021/8/3110《集合论与图论》第1讲常用逻辑等值式(关于0,1)零律(dominancelaws)A11A00同一律(identitylaws)A0AA1A2021/8/3111《集合论与图论》第1讲常用逻辑等值式(关于0,1)排中律(exc

5、ludedmiddle)AA1矛盾律(contradiction)AA02021/8/3112《集合论与图论》第1讲常用逻辑等值式(关于)蕴涵等值式(conditionalasdisjunction)ABAB假言易位(contrapositivelaw)ABBA归谬论(AB)(AB)A2021/8/3113《集合论与图论》第1讲常用逻辑等值式(关于)等价等值式(biconditionalasimplication)AB(AB)(BA)等价否定等值式ABAB2021/8/3114《集合论与图论》第1

6、讲等值式模式A，B，C代表任意的公式上述等值式称为等值式模式每个等值式模式都给出了无穷多个同类型的具体的等值式。2021/8/3115《集合论与图论》第1讲等值式模式(举例)蕴涵等值式模式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)2021/8/3116《集合论与图论》第1讲对偶原理一个逻辑等值式，如果只含有，，，0，1那么，同时把与互换把0与1互换得到的还是等值式2021/8/3117《集合论与图论》第1讲对偶原理(举例)分配律A(BC)(A

7、B)(AC)A(BC)(AB)(AC)排中律(excludedmiddle)AA1矛盾律(contradiction)AA02021/8/3118《集合论与图论》第1讲对偶原理(举例、续)零律(dominancelaws)A11A00同一律(identitylaws)A0AA1A2021/8/3119《集合论与图论》第1讲等值演算（举例）例：(pq)rpqr解：(pq)r(pq)r（蕴涵等值式）(pq)r（德●摩根律）pqr（结合律）2021/8/3120《集合论与图论》

8、第1讲推理定律(dedu