第二章命题逻辑的等值推演

第二章命题逻辑的等值推演第1页，课件共27页，创作于2023年2月2.1等值式一、复习

p

q仅在p与q均为0时结果才为0，其他为1。p

q仅在p与q均为1时结果才有1，其他为0。p

q仅在p为1、q为0才为0，其他为1。p

q仅在p与q等值时才1，其他为1。用真值表证明了p

q与pq的真值表完全一样，即这两者等值，根据双条件的定义，(p

q)

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

q(p

q)(q

p)(p

q)(p

q)第2页，课件共27页，创作于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页，创作于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页，创作于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页，创作于2023年2月

pqpq可推出ABAB尽管A/B可能很复杂，但是公式值也只有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页，创作于2023年2月

pqpq可推出ABAB这种将变元换成公式的方法，称为“置换规则”，推而广知：

已知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页，创作于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页，创作于2023年2月证：(pq)r

(pr)(qr)尽量转换证：(pq)pq先演算后判断公式类型(p(pq))r应用题：甲：王不是苏州人，是上海人乙：王不是上海人，是苏州人丙：王不是上海人，也不是杭州人王说：一人全对，一人对一半，一人全不对！解：p:王是苏州人,q是上海人，r王是杭州人。甲:pq乙：pq丙：qr王说的话译成公式为，据此判断p,q,r的值。第9页，课件共27页，创作于2023年2月一、复习

p

q仅在p与q均为0时结果才为0，其他为1。p

q仅在p与q均为1时结果才有1，其他为0。p

q仅在p为1、q为0才为0，其他为1。p

q仅在p与q等值时才1，其他为1。用真值表证明了p

q与pq的真值表完全一样，即这两者等值，根据双条件的定义，(p

q)

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

q(p

q)(q

p)(p

q)(p

q)第10页，课件共27页，创作于2023年2月2.2析取范式与合取范式

文字：命题变项(变元)及其否定称为文字.如:p,q,r,p,q,r

简单析取式:仅由有限个文字构成的析取式.如:pq,pq,pq,pq,pqr简单合取式:仅由有限个文字构成的合取式.如:pq,pq,pq,pq,pqr定理2.1：简单析取式与简单合取式(1)一个简单析取式Ai是重言式当且仅当同时含有某个命题变元及其否定式，如Ai=p

p…(2)一个简单合取式Ai是矛盾式当且仅当同时含有某个命题变元及其否定式，如Ai=p

p…第11页，课件共27页，创作于2023年2月2.2析取范式与合取范式定义2.3：由有限个简单合取式的析取构成的命题公式称为析取范式。总体是析取式，每对括号内是合取式A=(p

q)(p

r)定义2.3：由有限个简单析取式的合取构成的命题公式称为合取范式。总体是合取式，每对括号内是析取式A=(p

q)(p

r)第12页，课件共27页，创作于2023年2月2.2析取范式与合取范式总体是析取式，每对括号内是合取式A=(p

q)(p

r)析取范式总体是合取式，每对括号内是析取式A=(p

q)(p

r)合取范式定理2.2：析取范式与合取范式(1)一个析取范式A是矛盾式当且仅当每个简单合取式是矛盾式。A=(p

q)(p

r)(2)一个合取范式A是重言式当且仅当每个简单析取式是重言式。A=(p

q)(p

r)第13页，课件共27页，创作于2023年2月2.2析取范式与合取范式A=(p

q)(p

r)析取范式A=(p

q)(p

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

(1)转换条件式A

BAB(2)转换双条式A

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

A,

(A

B),

(A

B)(4)取消公因式A

(BC),A

(BC).第14页，课件共27页，创作于2023年2月2.2析取范式与合取范式(1)转换条件式A

BAB(2)转换双条式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页，创作于2023年2月2.2析取范式与合取范式(1)转换条件式A

BAB(2)转换双条式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页，创作于2023年2月2.2析取范式与合取范式定义2.4：在含有n个变元的简单合取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单合取式为(极)小项。如：pqr,pqr,pqr,pqr(pq)r(pr)(qr)(pq

r)非小项定义2.4：在含有n个变元的简单析取式中,每个命题变元或其否定仅出现一次,且各变元按其字母顺序出现,则该简单析取式为(极)大项。如：pqr,pqr,pqr,pqr(pq)r(pr)(qr)(pqr)非大项第17页，课件共27页，创作于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页，创作于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页，创作于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页，创作于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页，创作于2023年2月2.2析取范式与合取范式主范式的获取方法：先转换析取式或合取式，再对于主析取(小项的析取)式，如果其中的简单合取式没有出现某个变元，则合取1.如：(pq)r(pr)(qr)(pq

r)(p1r)(1qr)(pq

r)对于主合取范式(大项的合取)，如果所有简单析取式没有出现某个变元，则析取0。如：(pq)r(pr)(qr)(pqr)(p0r)(0qr)(pqr)第22页，课件共27页，创作于2023年2月2.2析取范式与合取范式主范式的获取方法：1、先转换析取式或合取式，再合取1或析取0。2、先建立真值表，取出所有成真赋值对应的小项，析取所有小项得主析取范式。取出所有成假赋值对应的大项，合取所有大项得主合取范式。如：(pq)r

第23页，课件共27页，创作于2023年2月2.2析取范式与合取范式主范式的获取方法：1、先转换析取式或合取式，再合取1或析取0。2、先建立真值表，成真赋值之小项析取，成假赋值的大项合取。如：(pq)r主范式的应用：(1)若A去则B去(2)若B去则C不能去(3)若C不去则A或B可去。解：(pq)(qr)(r(pq))用方法1或方法2建立主析取范式，再进一步处理。第24页，课件共