北大計(jì)算機(jī)考研離散數(shù)學(xué)集合論圖論chapter

第1講命題邏輯基礎(chǔ)2021/6/26《集合論與圖論》第1講11.

命題、命題符號(hào)化2.

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

邏輯等值式、推理定律4.

形式化證明命題符號(hào)化2021/6/26《集合論與圖論》第1講2p,q,r,p1,q1,r1,…簡單命題：聯(lián)結(jié)詞：合取聯(lián)結(jié)詞：析取聯(lián)結(jié)詞：否定聯(lián)結(jié)詞：蘊(yùn)涵聯(lián)結(jié)詞：fi等價(jià)聯(lián)結(jié)詞：?邏輯真值：

0，1真值表(truth-table)2021/6/26《集合論與圖論》第1講3賦值(assignment)：給變?cè)付?、1值n個(gè)變?cè)?，共?n種不同的賦值pqpp

qp

qpfi

qp?

q0010011011011010001001101111真值表(續(xù))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

當(dāng)且僅當(dāng)A?B是永真式例如：

(p

q)fi

r

p

q

r常用邏輯等值式(關(guān)于與)2021/6/26《集合論與圖論》第1講7冪等律(idempotent

laws)A

A

AA

A

A交換律(commutative

laws)ABBAABBA常用邏輯等值式(關(guān)于與)2021/6/26《集合論與圖論》第1講8結(jié)合律(associative

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

laws)A(BC)(AB

)(AC

)A(BC)(AB

)(AC

)常用邏輯等值式(關(guān)于與)2021/6/26《集合論與圖論》第1講9吸收律(absorption

laws)A(AB)AA(AB)A常用邏輯等值式(關(guān)于)2021/6/26《集合論與圖論》第1講10雙重否定律(double

negation

law)A

A德●摩根律(DeMorgan’s

laws)(AB)AB(AB)AB常用邏輯等值式(關(guān)于0,1)2021/6/26《集合論與圖論》第1講11零律(dominance

laws)A

1

1A

0

0同一律(identity

laws)A

0

AA

1

A常用邏輯等值式(關(guān)于0,1)2021/6/26《集合論與圖論》第1講12排中律(excluded

middle)A

A

1矛盾律(contradiction)A

A

0常用邏輯等值式(關(guān)于fi

)2021/6/26《集合論與圖論》第1講13蘊(yùn)涵等值式(conditional

as

disjunction)Afi

B

A

B假言易位(contrapositive

law)Afi

B

Bfi

A歸謬論(Afi

B

)(

Afi

B

)

A常用邏輯等值式(關(guān)于?)2021/6/26《集合論與圖論》第1講14等價(jià)等值式(biconditional

as

implication)(Afi

B)

(Bfi

A)A?

B等價(jià)否定等值式A?

B

A?

B等值式模式2021/6/26《集合論與圖論》第1講15A，B，C代表任意的公式上述等值式稱為等值式模式每個(gè)等值式模式都給出了無窮多個(gè)同類型的具體的等值式。等值式模式(舉例)2021/6/26《集合論與圖論》第1講16蘊(yùn)涵等值式模式Afi

B

A

B取A=p，B=q時(shí)，得到pfi

q

p

q取A=p

q

r，B=p q時(shí)，得到(p

qr)fi

(p

q)(p

q

r)

(p

q)對(duì)偶原理2021/6/26《集合論與圖論》第1講17一個(gè)邏輯等值式，如果只含有

，

，

，0，1那么，同時(shí)把與互換把0

與1互換得到的還是等值式對(duì)偶原理(舉例)2021/6/26《集合論與圖論》第1講18分配律A(BC)(AB

)(AC

)A(BC)(AB

)(AC

)排中律(excluded

middle)A

A

1矛盾律(contradiction)A

A

0對(duì)偶原理(舉例、續(xù))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（蘊(yùn)涵等值式）(

p

q)

r

（德●摩根律）p

q

r

（結(jié)合律）推理定律(deduction

laws)2021/6/26《集合論與圖論》第1講21推出：AB讀作：A推出B含義：當(dāng)A為真時(shí)，B也為真AB

當(dāng)且僅當(dāng)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常見推理定律（續(xù)）2021/6/26《集合論與圖論》第1講24假言推理(Afi

B

)

AB拒取式(Afi

B

)

B

A析取三段論(A B

)

B

A常見推理定律（續(xù)）2021/6/26《集合論與圖論》第1講25假言三段論(Afi

B)

(Bfi

C)(Afi

C)等價(jià)三段論(A?

B) (B?

C)(A?

C)常見推理定律（續(xù)）2021/6/26《集合論與圖論》第1講26構(gòu)造性兩難(Afi

B)

(Cfi

D)

(A

C)(B

D)構(gòu)造性兩難(特殊形式)A)B(Afi

B)

(

Afi

B)∧(A破壞性兩難(Afi

B)

(Cfi

D)

(

B

D)(

A

C)推理規(guī)則2021/6/26《集合論與圖論》第1講27前提引入規(guī)則：在證明的任何步驟上都可以引入前提結(jié)論引入規(guī)則：在證明的任何步驟上所得到的結(jié)論都可以做為后繼證明的前提置換規(guī)則：在證明的任何步驟上，命題公式中的子公式都可以用與之等值的公式置換，得到公式序列中又一個(gè)公式推理規(guī)則（續(xù)）2021/6/26《集合論與圖論》第1講28附加規(guī)則：A(A

B)A————\

A

B化簡規(guī)則：(A

B)A推理規(guī)則（續(xù)）2021/6/26《集合論與圖論》第1講29假言推理規(guī)則：

(Afi

B

)

ABAfi

BA————\

B拒取式規(guī)則：(Afi

B

)

B

A推理規(guī)則（續(xù)）2021/6/26《集合論與圖論》第1講30假言三段論規(guī)則：(Afi

B)

(Bfi

C)(Afi

C)Afi

BBfi

C————\

A

fi

C析取三段論規(guī)則：(A B

)

B

A推理規(guī)則（續(xù)）2021/6/26《集合論與圖論》第1講31構(gòu)造性兩難推理規(guī)則：(Afi

B)

(Cfi

D)

(A

C)(B

D)破壞性兩難推理規(guī)則：(Afi

B)

(Cfi

D)

(

B

D)(

A

C)推理規(guī)則（續(xù)）2021/6/26《集合論與圖論》第1講32合取引入規(guī)則：(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)(蘊(yùn)涵等值式)(德●摩根律)(交換律、結(jié)合律)q

fi

(

p

r)qfi

(pfi

r)(蘊(yùn)涵等值式)(蘊(yùn)涵等值式)總結(jié)2021/6/26《集合論與圖論》第1講34等值式（16組、24條）冪等律、交換律、結(jié)合律、分配律、吸收律；雙重否定律、德●摩根律；零律、同一律