第二章命題邏輯的等值推演

第二章命題邏輯的等值推演第1頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.1等值式一、復(fù)習(xí)

p

q僅在p與q均為0時(shí)結(jié)果才為0，其他為1。p

q僅在p與q均為1時(shí)結(jié)果才有1，其他為0。p

q僅在p為1、q為0才為0，其他為1。p

q僅在p與q等值時(shí)才1，其他為1。用真值表證明了p

q與pq的真值表完全一樣，即這兩者等值，根據(jù)雙條件的定義，(p

q)

(pq)為永真或重言式。p

q(p

q)(q

p)(p

q)(p

q)第2頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月二、等值式定義

公式A、B，如果其真值表完全一樣，或者AB為永真式，則稱(chēng)A與B等值，記為AB如：p

qpqp

q(p

q)(q

p)(p

q)(p

q)三、判斷方法

判斷真值表是否一樣判斷AB是否為永真。例如：p與p(pq)與pp，這是德摩律(pq)與pp與互反

第3頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月p

qpqp

q(p

q)(q

p)(p

q)(p

q)pp(pq)pp德摩律(pq)pp與對(duì)偶ppppp

p(qr)(pq)(pr)分配律p(qr)(pq)(pr)對(duì)偶式p

(pq)p吸收律(多吃少)p

(pq)pp

p1，p

p0(pq)(pq)雙條件相同為真(pq)(pq)p歸謬律第4頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月如：p

qpqp

q(p

q)(q

p)(p

q)(p

q)pp(pq)pp德摩律(pq)pp與對(duì)偶ppppp

p(qr)(pq)(pr)分配律p(qr)(pq)(pr)對(duì)偶式p

(pq)p吸收律(多吃少)p

(pq)pp

p1，p

p0(pq)(qp)(pq)(pq)p歸謬律將以上公式中命題變?cè)猵/q，換成公式A/B，一樣成立！A

BAB第5頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月

pqpq可推出ABAB盡管A/B可能很復(fù)雜，但是公式值也只有0、1二種可能，公式A/B的組合只有0/0,0/1,1/0,1/1四種，即只要證明：00與00相等0

1與01相等1

0與10相等1

1與11相等這與證明pqpq的過(guò)程完全一樣，即變?cè)猵/q的值只有0、1,變?cè)猵/q的組合只有0/0,0/1,1/0與1/1四種組合，即證明各組合下各值相等。第6頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月

pqpq可推出ABAB這種將變?cè)獡Q成公式的方法，稱(chēng)為“置換規(guī)則”，推而廣知：

已知AB，(A)是含公式A的命題公式，將(A)中A全部換成公式B，則(A)(B)

如：pqpq，(pq)=(pq)p，這里A=pq，B=pq，(A)=(pq)=(pq)p，(B)=(pq)=(pq)p，故(pq)p

(pq)p

部分等值置換后公式仍等值！可用于等值演算第7頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月因?yàn)閜qpq故(pq)p

(pq)p

部分等值置換后公式仍等值！可用于等值演算(pq)r(pq)r(因(pq)(pq))(pq)r(因(pq)r(pq)r)(pq)r(德摩律)(pq)r(雙重否定律)(pr)(qr)(雙重否定律)第8頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月證：(pq)r

(pr)(qr)盡量轉(zhuǎn)換證：(pq)pq先演算后判斷公式類(lèi)型(p(pq))r應(yīng)用題：甲：王不是蘇州人，是上海人乙：王不是上海人，是蘇州人丙：王不是上海人，也不是杭州人王說(shuō)：一人全對(duì)，一人對(duì)一半，一人全不對(duì)！解：p:王是蘇州人,q是上海人，r王是杭州人。甲:pq乙：pq丙：qr王說(shuō)的話譯成公式為，據(jù)此判斷p,q,r的值。第9頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月一、復(fù)習(xí)

p

q僅在p與q均為0時(shí)結(jié)果才為0，其他為1。p

q僅在p與q均為1時(shí)結(jié)果才有1，其他為0。p

q僅在p為1、q為0才為0，其他為1。p

q僅在p與q等值時(shí)才1，其他為1。用真值表證明了p

q與pq的真值表完全一樣，即這兩者等值，根據(jù)雙條件的定義，(p

q)

(pq)為永真或重言式。p

q(p

q)(q

p)(p

q)(p

q)第10頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式

文字：命題變項(xiàng)(變?cè)?及其否定稱(chēng)為文字.如:p,q,r,p,q,r

簡(jiǎn)單析取式:僅由有限個(gè)文字構(gòu)成的析取式.如:pq,pq,pq,pq,pqr簡(jiǎn)單合取式:僅由有限個(gè)文字構(gòu)成的合取式.如:pq,pq,pq,pq,pqr定理2.1：簡(jiǎn)單析取式與簡(jiǎn)單合取式(1)一個(gè)簡(jiǎn)單析取式Ai是重言式當(dāng)且僅當(dāng)同時(shí)含有某個(gè)命題變?cè)捌浞穸ㄊ剑鏏i=p

p…(2)一個(gè)簡(jiǎn)單合取式Ai是矛盾式當(dāng)且僅當(dāng)同時(shí)含有某個(gè)命題變?cè)捌浞穸ㄊ?，如Ai=p

p…第11頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.3：由有限個(gè)簡(jiǎn)單合取式的析取構(gòu)成的命題公式稱(chēng)為析取范式?？傮w是析取式，每對(duì)括號(hào)內(nèi)是合取式A=(p

q)(p

r)定義2.3：由有限個(gè)簡(jiǎn)單析取式的合取構(gòu)成的命題公式稱(chēng)為合取范式。總體是合取式，每對(duì)括號(hào)內(nèi)是析取式A=(p

q)(p

r)第12頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式總體是析取式，每對(duì)括號(hào)內(nèi)是合取式A=(p

q)(p

r)析取范式總體是合取式，每對(duì)括號(hào)內(nèi)是析取式A=(p

q)(p

r)合取范式定理2.2：析取范式與合取范式(1)一個(gè)析取范式A是矛盾式當(dāng)且僅當(dāng)每個(gè)簡(jiǎn)單合取式是矛盾式。A=(p

q)(p

r)(2)一個(gè)合取范式A是重言式當(dāng)且僅當(dāng)每個(gè)簡(jiǎn)單析取式是重言式。A=(p

q)(p

r)第13頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式A=(p

q)(p

r)析取范式A=(p

q)(p

r)合取范式建立范式的基本步驟：

(1)轉(zhuǎn)換條件式A

BAB(2)轉(zhuǎn)換雙條式A

B(AB)(AB)(AB)(AB)(3)否定到底

A,

(A

B),

(A

B)(4)取消公因式A

(BC),A

(BC).第14頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式(1)轉(zhuǎn)換條件式A

BAB(2)轉(zhuǎn)換雙條式A

B(AB)(AB)(AB)(AB)(3)否定到底

A,

(A

B),

(A

B)(4)取消公因式A

(BC),A

(BC).如合取式范式：(pq)r(pq)r((pq)r)((pq)r)((pq)r)((pq)r)(pr)(qr)(pqr)第15頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式(1)轉(zhuǎn)換條件式A

BAB(2)轉(zhuǎn)換雙條式A

B(AB)(AB)(AB)(AB)(3)否定到底

A,

(A

B),

(A

B)(4)取消公因式A

(BC),A

(BC).如析取式范式：(pq)r(pq)r((pq)r)(

(pq)

r)(pr)(qr)(pq

r)第16頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.4：在含有n個(gè)變?cè)暮?jiǎn)單合取式中,每個(gè)命題變?cè)蚱浞穸▋H出現(xiàn)一次,且各變?cè)雌渥帜疙樞虺霈F(xiàn),則該簡(jiǎn)單合取式為(極)小項(xiàng)。如：pqr,pqr,pqr,pqr(pq)r(pr)(qr)(pq

r)非小項(xiàng)定義2.4：在含有n個(gè)變?cè)暮?jiǎn)單析取式中,每個(gè)命題變?cè)蚱浞穸▋H出現(xiàn)一次,且各變?cè)雌渥帜疙樞虺霈F(xiàn),則該簡(jiǎn)單析取式為(極)大項(xiàng)。如：pqr,pqr,pqr,pqr(pq)r(pr)(qr)(pqr)非大項(xiàng)第17頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式小項(xiàng)的取值情況：對(duì)小項(xiàng)僅有一個(gè)成真的賦值如：pqr為111,記為m111或m7.pqr為101,記為m101或m5.pqr為110,記為m110或m6.pqr為011,記為m011或m3.大項(xiàng)的取值情況：對(duì)小項(xiàng)僅有一個(gè)成假的賦值。如：pqr為000,記為M000或M0.pqr為010,記為M010或M2.pqr為001,記為M001或M1.pqr為011,記為M011或M3.第18頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.5：一個(gè)析取范式中，如果所有簡(jiǎn)單合取式均為(極)小項(xiàng)，則稱(chēng)為主析取范式。(pq)r(pr)(qr)(pq

r)(p1r)(1qr)(pq

r)(p(qq)r)((pp)qr)(pq

r)(pqr)(pqr)(pqr)(pqr)(pqr)m011m001m111m011m100.第19頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.5：一個(gè)析取范式中，如果所有簡(jiǎn)單合取式均為(極)小項(xiàng)，則稱(chēng)為主析取范式。(pq)r(pr)(qr)(pq

r)(p1r)(1qr)(pq

r)(p(qq)r)((pp)qr)(pq

r)(pqr)(pqr)(pqr)(pqr)(pqr)m011m001m111

m011m100.m011m001m111m100.第20頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.5：一個(gè)合取范式中，如果所有簡(jiǎn)單析取式均為(極)大項(xiàng)，則稱(chēng)為主合取范式。(pq)r(pr)(qr)(pqr)(p0r)(0qr)(pqr)(p(qq)r)((pp)qr)(pqr)(pqr)(pqr)

(pqr)(pqr)(pqr)M000M010M110M101.成假賦值來(lái)編號(hào)m011m001m111m100.編號(hào)互補(bǔ)第21頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式主范式的獲取方法：先轉(zhuǎn)換析取式或合取式，再對(duì)于主析取(小項(xiàng)的析取)式，如果其中的簡(jiǎn)單合取式?jīng)]有出現(xiàn)某個(gè)變?cè)瑒t合取1.如：(pq)r(pr)(qr)(pq

r)(p1r)(1qr)(pq

r)對(duì)于主合取范式(大項(xiàng)的合取)，如果所有簡(jiǎn)單析取式?jīng)]有出現(xiàn)某個(gè)變?cè)瑒t析取0。如：(pq)r(pr)(qr)(pqr)(p0r)(0qr)(pqr)第22頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式主范式的獲取方法：1、先轉(zhuǎn)換析取式或合取式，再合取1或析取0。2、先建立真值表，取出所有成真賦值對(duì)應(yīng)的小項(xiàng)，析取所有小項(xiàng)得主析取范式。取出所有成假賦值對(duì)應(yīng)的大項(xiàng)，合取所有大項(xiàng)得主合取范式。如：(pq)r

第23頁(yè)，課件共27頁(yè)，創(chuàng)作于2023年2月2.2析取范式與合取范式主范式的獲取方法：1、先轉(zhuǎn)換析取式或合取式，再合取1或析取0。2、先建立真值表，成真賦值之小項(xiàng)析取，成假賦值的大項(xiàng)合取。如：(pq)r主范式的應(yīng)用：(1)若A去則B去(2)若B去則C不能去(3)若C不去則A或B可去。解：(pq)(qr)(r(pq))用方法1或方法2建立主析取范式，再進(jìn)一步處理。第24頁(yè)，課件共