北大计算机考研离散数学集合论图论chapter

第1讲命题逻辑基础2021/6/26《集合论与图论》第1讲11.

命题、命题符号化2.

合式公式、真值表、永真式3.

逻辑等值式、推理定律4.

形式化证明命题符号化2021/6/26《集合论与图论》第1讲2p,q,r,p1,q1,r1,…简单命题：联结词：合取联结词：析取联结词：否定联结词：蕴涵联结词：fi等价联结词：«逻辑真值：

0，1真值表(truth-table)2021/6/26《集合论与图论》第1讲3赋值(assignment)：给变元指定0、1值n个变元，共有2n种不同的赋值pqpp

qp

qpfi

qp«

q0010011011011010001001101111真值表(续)2021/6/26《集合论与图论》第1讲4pqr(p

q)fi

rp

q

r0001100111010110111110011101111100011111永真式(tautology)2021/6/26《集合论与图论》第1讲5永真式:在各种赋值下取值均为真(重言式)永假式:在各种赋值下取值均为假(矛盾式)可满足式：非永假式pq(p

q)p

q(p q)«

(

p

q)00111011111011111001逻辑等值式(identities)2021/6/26《集合论与图论》第1讲6等值：

A

B读作：A等值于B含义：A与B在各种赋值下取值均相等A B

当且仅当A«B是永真式例如：

(p

q)fi

r

p

q

r常用逻辑等值式(关于与)2021/6/26《集合论与图论》第1讲7幂等律(idempotent

laws)A

A

AA

A

A交换律(commutative

laws)ABBAABBA常用逻辑等值式(关于与)2021/6/26《集合论与图论》第1讲8结合律(associative

laws)(AB)CA(BC)(AB)CA(BC)分配律(distributive

laws)A(BC)(AB

)(AC

)A(BC)(AB

)(AC

)常用逻辑等值式(关于与)2021/6/26《集合论与图论》第1讲9吸收律(absorption

laws)A(AB)AA(AB)A常用逻辑等值式(关于)2021/6/26《集合论与图论》第1讲10双重否定律(double

negation

law)A

A德●摩根律(DeMorgan’s

laws)(AB)AB(AB)AB常用逻辑等值式(关于0,1)2021/6/26《集合论与图论》第1讲11零律(dominance

laws)A

1

1A

0

0同一律(identity

laws)A

0

AA

1

A常用逻辑等值式(关于0,1)2021/6/26《集合论与图论》第1讲12排中律(excluded

middle)A

A

1矛盾律(contradiction)A

A

0常用逻辑等值式(关于fi

)2021/6/26《集合论与图论》第1讲13蕴涵等值式(conditional

as

disjunction)Afi

B

A

B假言易位(contrapositive

law)Afi

B

Bfi

A归谬论(Afi

B

)(

Afi

B

)

A常用逻辑等值式(关于«)2021/6/26《集合论与图论》第1讲14等价等值式(biconditional

as

implication)(Afi

B)

(Bfi

A)A«

B等价否定等值式A«

B

A«

B等值式模式2021/6/26《集合论与图论》第1讲15A，B，C代表任意的公式上述等值式称为等值式模式每个等值式模式都给出了无穷多个同类型的具体的等值式。等值式模式(举例)2021/6/26《集合论与图论》第1讲16蕴涵等值式模式Afi

B

A

B取A=p，B=q时，得到pfi

q

p

q取A=p

q

r，B=p q时，得到(p

qr)fi

(p

q)(p

q

r)

(p

q)对偶原理2021/6/26《集合论与图论》第1讲17一个逻辑等值式，如果只含有

，

，

，0，1那么，同时把与互换把0

与1互换得到的还是等值式对偶原理(举例)2021/6/26《集合论与图论》第1讲18分配律A(BC)(AB

)(AC

)A(BC)(AB

)(AC

)排中律(excluded

middle)A

A

1矛盾律(contradiction)A

A

0对偶原理(举例、续)2021/6/26《集合论与图论》第1讲19零律(dominance

laws)A

1

1A

0

0同一律(identity

laws)A

0

AA

1

A等值演算（举例）2021/6/26《集合论与图论》第1讲20例：(p

q)fi

r

p

q

r解：(p

q)fi

r(p

q)

r（蕴涵等值式）(

p

q)

r

（德●摩根律）p

q

r

（结合律）推理定律(deduction

laws)2021/6/26《集合论与图论》第1讲21推出：AB读作：A推出B含义：当A为真时，B也为真AB

当且仅当A

fi

B是永真式例如：

(p q

)

p

q推理定律（举例）2021/6/26《集合论与图论》第1讲22(p q

)

p

q(p q

)

p

fi

q

是永真式pqp

qp(p

q)

p(p

q)

pfi

q000101011111101001111001常见推理定律2021/6/26《集合论与图论》第1讲23附加律A(A

B)化简律(A

B)A常见推理定律（续）2021/6/26《集合论与图论》第1讲24假言推理(Afi

B

)

AB拒取式(Afi

B

)

B

A析取三段论(A B

)

B

A常见推理定律（续）2021/6/26《集合论与图论》第1讲25假言三段论(Afi

B)

(Bfi

C)(Afi

C)等价三段论(A«

B) (B«

C)(A«

C)常见推理定律（续）2021/6/26《集合论与图论》第1讲26构造性两难(Afi

B)

(Cfi

D)

(A

C)(B

D)构造性两难(特殊形式)A)B(Afi

B)

(

Afi

B)∧(A破坏性两难(Afi

B)

(Cfi

D)

(

B

D)(

A

C)推理规则2021/6/26《集合论与图论》第1讲27前提引入规则：在证明的任何步骤上都可以引入前提结论引入规则：在证明的任何步骤上所得到的结论都可以做为后继证明的前提置换规则：在证明的任何步骤上，命题公式中的子公式都可以用与之等值的公式置换，得到公式序列中又一个公式推理规则（续）2021/6/26《集合论与图论》第1讲28附加规则：A(A

B)A————\

A

B化简规则：(A

B)A推理规则（续）2021/6/26《集合论与图论》第1讲29假言推理规则：

(Afi

B

)

ABAfi

BA————\

B拒取式规则：(Afi

B

)

B

A推理规则（续）2021/6/26《集合论与图论》第1讲30假言三段论规则：(Afi

B)

(Bfi

C)(Afi

C)Afi

BBfi

C————\

A

fi

C析取三段论规则：(A B

)

B

A推理规则（续）2021/6/26《集合论与图论》第1讲31构造性两难推理规则：(Afi

B)

(Cfi

D)

(A

C)(B

D)破坏性两难推理规则：(Afi

B)

(Cfi

D)

(

B

D)(

A

C)推理规则（续）2021/6/26《集合论与图论》第1讲32合取引入规则：(A)

(B)(A

B)AB————\

A

B证明(举例)2021/6/26《集合论与图论》第1讲33qfi

(pfi

r)证明：

(p

q)fi

r(p q)

fi

r(p

q)

r(

p

q)

rq

(

p

r)(蕴涵等值式)(德●摩根律)(交换律、结合律)q

fi

(

p

r)qfi

(pfi

r)(蕴涵等值式)(蕴涵等值式)总结2021/6/26《集合论与图论》第1讲34等值式（16组、24条）幂等律、交换律、结合律、分配律、吸收律；双重否定律、德●摩根律；零律、同一律