復(fù)習(xí)命題：能判斷真假的陳述句。判斷是否命題P81.整理ppt復(fù)習(xí)聯(lián)結(jié)詞

P┐P

T

F

F

T

P

QP∧Q

T

T

T

T

F

F

F

T

F

F

F

F整理ppt整理ppt

P

QP→Q

T

T

T

T

F

F

F

T

T

F

F

T

P

QP

Q

T

T

T

T

F

F

F

T

F

F

F

T整理ppt名稱記號(hào)記法真值否定┐┐P┐P為真當(dāng)且僅當(dāng)P為假合取∧P∧QP∧Q為真當(dāng)且僅當(dāng)P,Q全為真析取∨P∨QP∨Q為假當(dāng)且僅當(dāng)P,Q全為假條件

P

QP

Q為假當(dāng)且僅當(dāng)P為真，Q為假雙條件

P

QP

Q為真當(dāng)且僅當(dāng)P,Q同為真假整理ppt復(fù)習(xí)合式公式

wff

歸納定義

P111.2.整理ppt本次課內(nèi)容真值表重言式等價(jià)公式蘊(yùn)含式其他連接詞重點(diǎn)：構(gòu)造真值表；證明重言式與蘊(yùn)含式難點(diǎn)：等價(jià)式的證明；證明重言式與蘊(yùn)含式

。

整理ppt一、真值表定義1-4.1

對(duì)命題變?cè)牡拿恳环N可能的真值指派，以及由此得出的命題公式的真值所列出的表，稱為命題公式的真值表。

考慮：含有n個(gè)命題變項(xiàng)的公式共有多少個(gè)不同的賦值？命題公式真值的取值數(shù)目，取決于分量的個(gè)數(shù)。對(duì)于含有n個(gè)命題變?cè)墓?，?n個(gè)真值指派，即在該公式的真值表中有2n行。整理ppt對(duì)公式A構(gòu)造真值表的具體步驟為：（1）找出公式中所有的全體命題變項(xiàng)p1，

p2，

…，pn，列出2n個(gè)賦值(可按二進(jìn)制數(shù)的順序0—2n-1)。（2）按運(yùn)算的先后順序?qū)懗銎鋵?duì)應(yīng)的真值,直到最后計(jì)算出公式的真值。見課本例題。從例1-4可以看出：有些公式恒為真（重言式），或恒為假(矛盾式)，有時(shí)為真有時(shí)為假（可滿足式）；從表1-4.5，表1-4.6可以看出：有些公式在不同指派下對(duì)應(yīng)的真值完全相同（等價(jià)公式）。整理ppt

二、公式分類

定義

設(shè)A為任意公式，則①對(duì)應(yīng)每一個(gè)指派，公式A均相應(yīng)確定真值為真，稱A

為重言式，或永真式。②對(duì)應(yīng)每一個(gè)指派，公式A均相應(yīng)確定真值為假，稱A

為矛盾式，或永假式。③至少存在一個(gè)指派，公式A相應(yīng)確定真值為真，稱A為可滿足式。由定義可知，重言式必是可滿足式，反之一般不真。整理ppt

P

Q┐(P∧Q)(┐P∨┐Q)

T

T

T

T

F

T

F

T

T

F

F

T

P

Q

(P∧Q)∧┐P

T

T

F

T

F

F

F

T

F

F

F

F整理ppt定理1：任何兩個(gè)重言式（矛盾式）的合取或析取，仍是一個(gè)重言式（矛盾式）。

定理2：一個(gè)重言式（矛盾式），對(duì)同一分量都用任何合式公式置換，其結(jié)果仍為一重言式（矛盾式）。

證明：設(shè)A和B為兩個(gè)重言式，則不論A和B的分量指派任何真值，總有A為T，B為T，故A∧B為T，A∨B為T。

證明：由于重言式的真值與分量的指派無關(guān)，故對(duì)同一分量以任何合式公式置換后，重言式的真值仍永為T。重要結(jié)論例1：證明((P∨S)∧R)∨┐((P∨S)∧R)為重言式。證明:∵P∨┐PT,用(P∨S)∧R)置換P,即得.整理ppt重點(diǎn)將研究重言式，它最有用，因?yàn)橛幸韵绿攸c(diǎn)：①重言式的否定是矛盾式，矛盾式的否定是重言式，這樣只研究其一就可以了。②兩重言式的合取式、析取式、條件式和雙條件式等都仍是重言式。于是，由簡(jiǎn)單的重言式可構(gòu)造出復(fù)雜的重言式。③由重言式使用公認(rèn)的規(guī)則可以產(chǎn)生許多有用等價(jià)式和蘊(yùn)涵式。整理ppt三、等價(jià)公式定義1-4.2：設(shè)A，B為兩命題公式，所有出現(xiàn)于A，B中的原子變?cè)娜我唤M真值指派，A和B的真值都相同，則稱A和B是等價(jià)的或邏輯相等，記為A

B。例如?P∨Q與P

Q注意

和

的區(qū)別

區(qū)別：

是邏輯聯(lián)結(jié)詞，它出現(xiàn)在命題公式中，可用它進(jìn)行一些運(yùn)算；

不是邏輯聯(lián)結(jié)詞，表示兩個(gè)命題公式的一種關(guān)系，不屬于這兩個(gè)公式的任何一個(gè)公式中的符號(hào)。整理ppt等價(jià)式有下列性質(zhì)：

①自反性，即對(duì)任意公式A，有A

A。②對(duì)稱性，即對(duì)任意公式A和B，若A

B，則B

A。③傳遞性，即對(duì)任意公式A、B和C，若A

B、B

C，則A

C。整理ppt真值表法：例5：證明PQ（P→Q）∧（Q→P）證明：列出真值表

T

F

T

TQ→P

T

F

F

T

T

T

F

TP→Q

T

F

F

F

T

F

F

F

T

T

T

TPQ

Q

P教材P15表1-4.8列出的命題定律,都可以用真值表予以驗(yàn)證。證明等價(jià)式的方法有兩種：

（P→Q）∧（Q→P）(P→Q)∧(Q→P)整理ppt例如：火車8：00或9：00到站。（排斥或）設(shè)P：火車8：00到站。Q：火車9：00到站。則上述命題就不可簡(jiǎn)單符號(hào)化為：P∨Q

而應(yīng)描述為(P∧┐Q)∨(┐P∧Q)或者

P

Q命題P

Q┐（P

Q）

T

T

F

T

F

T

F

T

F

T

F

T

T

F

T

F

F

F

T

F整理ppt需要記憶的16組重要等值式1、雙重否定律

P

┐┐P2、冪等律

P

P∧PP

P∨P3、交換律

P∨QQ

∨PP∧QQ

∧P4、結(jié)合律

(P∨Q)∨R

P∨(Q∨R)(P∧Q)∧R

P∧(Q∧R)記憶技巧：借助集合的運(yùn)算式，∨看成并，∧看成交，┐看成補(bǔ)，T看成全集，F(xiàn)看成空集，再加12-16條。整理ppt5、分配律

P∨(Q∧R)(P∨Q)∧

(P∨R)P∧(Q∨R)(P∧Q)∨

(P∧R)6、吸收律

P∨(P∧Q)

PP∧(P∨Q)

P7、德摩根律

┐

(P∨Q)

┐P∧┐Q

┐(P∧Q)

┐P∨

┐Q8、零律

P∨TTP∧FF9、同一律

P∨FPP∧TP整理ppt10、排中律

P∨

┐PT11、矛盾律

P∧

┐PF12、蘊(yùn)涵等值式

PQ

┐P∨Q13、等價(jià)等值式

P

Q

（PQ）∧

（QP）14、假言易位

PQ

┐Q┐P15、等價(jià)否定等值式

P

Q

┐P

┐Q16、歸謬論

（PQ）∧

（P

┐Q）

┐

P整理ppt

定義1-4.3：如果X是合式公式A的一部分，且X本身也是一個(gè)合式公式，則稱X為公式A的子公式。例如：Q→（P∨（P∧Q））定理1：設(shè)X是合式公式A的子公式，若XY，如將A中的X用Y來置換，所得到的公式B與公式A等價(jià)，即AB，該置換稱為等價(jià)置換(等價(jià)代換)。

證明：∵X是A的一部分，在任意指派下X與Y真值相同，用Y置換X，得到的B與A的真值相同，∴AB2.公式證明法整理ppt例7：證明：Q→（P∨（P∧Q））Q→P證明：∵（P∨（P∧Q））P（吸收律）

左：Q→P∴左右例8：證明：（P∧Q）∨（P∧┐Q）P

證明：（P∧Q）∨（P∧┐Q）

P∧（Q∨┐Q）P∧TP整理ppt

例10：證明：((P∨Q)∧┐(┐P∧(┐Q∨┐R)))∨(┐P∧┐Q)∨(┐P∧┐R)

T證明：左=((P∨Q)∧┐(┐P∧(┐Q∨┐R)))∨(┐P∧┐Q)∨(┐P∧┐R)

((P∨Q)∧(P∨(Q∧R)))∨(┐(P∨Q))∨(┐(P∨R))

((P∨Q)∧((P∨Q)∧(P∨R)))∨┐((P∨Q)∧(P∨R))

((P∨Q)∧(P∨R))∨┐((P∨Q)∧(P∨R))

T整理ppt等價(jià)式的用途證明如剛才幾個(gè)題目化簡(jiǎn)補(bǔ)充例1開關(guān)電路

PQRR

PSQPRS(P∧Q∧R)∨(P∧R∧S)(P∧R)∧(Q∨R)整理ppt

TF

TFTF執(zhí)行X:(A∧B)∨(┐A∧B)B執(zhí)行Y:(A∧┐B)∨(┐A∧┐B)┐BstartABBXYendstartBXYend補(bǔ)充例2流程圖TF整理ppt雙條件重言式定理3

A

B當(dāng)且僅當(dāng)A

B是永真式。證明：若A

B，則A，B有相同的真值，即A

B永為T。反之，若A

B為重言式，則A

B永為T，故A、B的真值相同，A

B。例2:證明┐(P∧Q)

(┐P∨┐Q)證明:由前面可知:┐(P∧Q)

(┐P∨┐Q)為重言式,由定理可得。

四、蘊(yùn)含式整理ppt2.條件重言式(蘊(yùn)含式)定義3:當(dāng)且僅當(dāng)P→Q是一個(gè)重言式時(shí)稱P蘊(yùn)含Q,記為PQ另外,若P→Q,則Q→P稱為逆換式;┐P→┐Q稱為反換式;┐Q→┐P稱為逆反式.由真值表可知:P→Q

┐Q→┐PQ→P

┐P→┐Q證明PQ：方法1:使得P為真的指派,可推出Q也為真,則P→Q為重言式.方法2:使得Q為假的指派,可推出P也為假,那么┐Q→┐P為重言式,則P→Q為重言式.整理ppt例1:推證:┐Q∧(P→Q)┐P

證法1:假定┐Q∧(P→Q)為T,則┐Q為T,且(P→Q)為T.

推出Q為F,P→Q為F,故┐P為T.證法2:假定┐P為F,則P為T.

若Q為F,P→Q為F,┐Q∧(P→Q)為F.

若Q為T,┐Q為F,┐Q∧(P→Q)為F.命題得證.掌握表1-5.2所列的蘊(yùn)含式。整理ppt設(shè)A、B、C為合式公式，若AB且A是重言式，則B必是重言式。若AB，BC，則AC，即蘊(yùn)含關(guān)系是傳遞的。蘊(yùn)含的性質(zhì)證明:∵AB,BC,∴A→B,B→C為重言式,(A→B)∧(B→C)為重言式.由基本蘊(yùn)含可得(A→B)∧(B→C)A→C,由性質(zhì)1,可得A→C為重言式.整理ppt（4）若AB且CB，則A∨CB證明:∵A→B為T,C→B為T,故(┐A∨B)∧(┐C∨B)為