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

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

p

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

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

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

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

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

q)

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

q(p

q)(q

p)(p

q)(p

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

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

qpqp

q(p

q)(q

p)(p

q)(p

q)三、判斷方法

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

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

qpqp

q(p

q)(q

p)(p

q)(p

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

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

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

(pq)pp

p1，p

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

qpqp

q(p

q)(q

p)(p

q)(p

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

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

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

(pq)pp

p1，p

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

BAB第5頁，課件共27頁，創(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的過程完全一樣，即變元p/q的值只有0、1,變元p/q的組合只有0/0,0/1,1/0與1/1四種組合，即證明各組合下各值相等。第6頁，課件共27頁，創(chuàng)作于2023年2月

pqpq可推出ABAB這種將變元換成公式的方法，稱為“置換規(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頁，課件共27頁，創(chuàng)作于2023年2月因為pqpq故(pq)p

(pq)p

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

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

p

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

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

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

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

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

q)

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

q(p

q)(q

p)(p

q)(p

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

文字：命題變項(變元)及其否定稱為文字.如:p,q,r,p,q,r

簡單析取式:僅由有限個文字構(gòu)成的析取式.如:pq,pq,pq,pq,pqr簡單合取式:僅由有限個文字構(gòu)成的合取式.如:pq,pq,pq,pq,pqr定理2.1：簡單析取式與簡單合取式(1)一個簡單析取式Ai是重言式當(dāng)且僅當(dāng)同時含有某個命題變元及其否定式，如Ai=p

p…(2)一個簡單合取式Ai是矛盾式當(dāng)且僅當(dāng)同時含有某個命題變元及其否定式，如Ai=p

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

q)(p

r)定義2.3：由有限個簡單析取式的合取構(gòu)成的命題公式稱為合取范式?？傮w是合取式，每對括號內(nèi)是析取式A=(p

q)(p

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

q)(p

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

q)(p

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

q)(p

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

q)(p

r)第13頁，課件共27頁，創(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頁，課件共27頁，創(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頁，課件共27頁，創(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頁，課件共27頁，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.4：在含有n個變元的簡單合取式中,每個命題變元或其否定僅出現(xiàn)一次,且各變元按其字母順序出現(xiàn),則該簡單合取式為(極)小項。如：pqr,pqr,pqr,pqr(pq)r(pr)(qr)(pq

r)非小項定義2.4：在含有n個變元的簡單析取式中,每個命題變元或其否定僅出現(xiàn)一次,且各變元按其字母順序出現(xiàn),則該簡單析取式為(極)大項。如：pqr,pqr,pqr,pqr(pq)r(pr)(qr)(pqr)非大項第17頁，課件共27頁，創(chuàng)作于2023年2月2.2析取范式與合取范式小項的取值情況：對小項僅有一個成真的賦值如：pqr為111,記為m111或m7.pqr為101,記為m101或m5.pqr為110,記為m110或m6.pqr為011,記為m011或m3.大項的取值情況：對小項僅有一個成假的賦值。如：pqr為000,記為M000或M0.pqr為010,記為M010或M2.pqr為001,記為M001或M1.pqr為011,記為M011或M3.第18頁，課件共27頁，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.5：一個析取范式中，如果所有簡單合取式均為(極)小項，則稱為主析取范式。(pq)r(pr)(qr)(pq

r)(p1r)(1qr)(pq

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

r)(pqr)(pqr)(pqr)(pqr)(pqr)m011m001m111m011m100.第19頁，課件共27頁，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.5：一個析取范式中，如果所有簡單合取式均為(極)小項，則稱為主析取范式。(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頁，課件共27頁，創(chuàng)作于2023年2月2.2析取范式與合取范式定義2.5：一個合取范式中，如果所有簡單析取式均為(極)大項，則稱為主合取范式。(pq)r(pr)(qr)(pqr)(p0r)(0qr)(pqr)(p(qq)r)((pp)qr)(pqr)(pqr)(pqr)

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

r)(p1r)(1qr)(pq

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

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