数理逻辑 命题逻辑ppt课件.ppt

《数理逻辑 命题逻辑ppt课件.ppt》由会员分享，可在线阅读，更多相关《数理逻辑 命题逻辑ppt课件.ppt（126页珍藏版）》请在三一办公上搜索。

1、命题逻辑,马殿富北航计算机学院2010-9,集合论,定义：一些对象聚集为一个整体，称为集合。这些对象称为集合的元素。元素与集合的关系a是集合S的元素，记为aSa不是集合S的元素，记为aS集合的表示法空集：有穷集合：枚举法，S=x1,x2,xn无穷集合：描述法x|x是自然数,集合外延、内涵,外延原则与概括原则外延原则：一个集合由它的元素唯一地确定。概括原则：每一性质(或谓词)产生一个集合。集合外延集合所包含的元素全体。集合内涵集合元素所共有的性质。非负偶数集合外延0,2,4,内涵x|x是被2整除的自然数 ,集合的关系,集合的关系包含关系：如果集合A的元素都是集合B的元素，则称A为B的子集，记为A

2、B真包含关系：AB不包含关系:AB等关系：如果集合A和集合B包含相同元素，则称A和B相等，记为A=B,函数,An=AAAAn=(x1,x2,xn)|xiAA=0, 1A3 =0, 13=(0,0,0),(0,0,1),(0,1,0),(0,1,1) (1,0,0),(1,0,1),(1,1,0),(1,1,1)设A和B是集合，如果对于集合A中每个元素x，都有集合B中唯一元素f(x)与之对应，则称f是函数。若f是从An到B的函数，则称f(x1,x2,xn)为A上的n元函数，也称 f(x1,x2,xn)为A上的n元运算。f：AAAA,归纳定义,归纳定义自然数集合：n是n的后继（函数），N是满足以下

3、条件的S中的最小集合 0S对于任何n，如果nS，则nS。,归纳证明,归纳证明设R是一个性质，R(x)表示x有R性质。定理证明归纳基础R(0)归纳假设对于任何kN,R(k);证明R(k);归纳结论对于任何nN，R(n)。,排序概念,数理逻辑基本概念,真可证性,数理逻辑,数理逻辑是用数学语言表述的推理形式有效性的学问。命题逻辑、谓词逻辑数理逻辑使用特制的表意符号，亦称为符号逻辑。逻辑研究对象逻辑真值真，表示为T或1假，表示为F或0正确的推理形式正确前提正确的推理形式必然得出正确的结论,1.1命题和联结词,什么是命题？命题的运算符是什么？如何表示命题？有多少种命题的运算符？,语句表达,陈述句疑问句祈

4、使句感叹句,雪是白的。 2是奇数。X+Y5。你是谁？我正在说谎。北京是中国的首都。前进！天空多漂亮!,特点：有的语句可以判断真假。,自然语言、命题,语言是人们思维和交际的工具，也是一种表达观念的符号系统。自然语言由各种句式组成，如陈述句、疑问句、感叹句、祈使句等等。陈述句是陈述一个事实或者说话人的看法，它包括肯定句和否定句两种。一般来说，仅有陈述句能够确定句子的意义是真还是假。命题表达为具有确定真假意义的陈述句。,命题示例,雪是白的。 2是奇数。X+Y5。你是谁？我正在说谎。北京是中国的首都。每个不小于6的偶数都是两个奇素数之和（歌德巴赫猜想）21世纪有人住在月球上。他很高。一个自然数不是合数

5、就是素数,命题，真 命题，假不确定，非命题疑问句，非命题悖论，非命题命题，真命题，真，有唯一真假值。命题，真，有唯一真假值。无法确定，非命题命题，假，1不是合数和素数,简单命题与复合命题,简单命题由简单陈述句表述的命题称为简单命题。命题逻辑不再进一步分析简单命题的内部结构p:孔子是圣人,语句联接词并且或否定如果,则。当且仅当既不，也不。,复合命题用联接词可以将若干个简单句组合成复合句。子命题,命题逻辑如何运算？,数计算启示自然数运算：+、*整数运算：+、-、*有理数运算：+、-、*、/,命题逻辑命题小写字母表示真1，假0运算：？,命题的抽象表示,自然语言具有二义性命题逻辑不关注语句的内容，也不

6、关注语句为何是真或为假，而是仅仅关注语句能够为真或假。命题的抽象用小写字母表示命题，取值为0,1。命题真值陈述句的意义为真，称为真命题，真值为1。陈述句的意义为假，称为假命题，真值为0。命题逻辑的研究对象命题。数理逻辑从形式结构方面研究命题。,逻辑联结词,定义0和1称为0元函数。设n0,称为0,1n到0,1的函数为n元函数，真值函数也称为联结词。命题的操作符（联结词）非 与 或 如果,则。 当且仅当 异或 ,真值表真值形式可以用图表来说明。这种表称为真值图表。,0元函数0，11元函数2元函数、 、,逻辑联结词 ,命题p的否定记为p,读作非p,真值表,逻辑联接词的含义自然语言中，并非的含义,逻辑

7、联结词 ,真值表,q称为p和q的合取读作p且q,逻辑联接词的含义自然语言中，并且的含义,逻辑联结词,真值表,q称为p和q的析取，读作p或q,逻辑联接词的含义自然语言中，或的含义,逻辑联结词 ,真值表,逻辑联接词的含义自然语言中，如果,则.的含义,q称为p蕴涵q读作p则qp称为前件q称为后件,逻辑联结词 ,真值表, q称为p与q等值，读作p当且仅当q, p与q互蕴含。pq=(pq)(qp),逻辑联接词的含义自然语言中，当且仅当的含义,逻辑联结词 ,北航在海淀区或北航在西城区。 比较李明学习英语或学习法语,真值表, q称为p与q异或，读作p异或q。pq= (pq)(qp),逻辑域、逻辑运算,逻辑域

8、0，1,运算，定义域0, 1值域0,1,命题逻辑运算符数目,运算符变量数为1个变量，2个变量，,n个变量的运算符数目,命题逻辑函数数目,变量数为n变量组合数运算符数,Fi(p,q)=？,命题形式结构,复合命题是命题及真值联结词构成的形式结构六个真假形式最基本的，或最简单的形式，称为简单命题。由这六个真假形式，经过各种各种的互相组合，还可以变成更多的各种复杂真值形式。真值形式数量无穷无尽。示例并非p并且q。(pq)如果非p，那么非q。pq如果p或q,那么r。pqr,命题形式结构,例1：如果n是奇数，那么n2也是奇数。n是奇数所以n2也是奇数。例2：如果ABCD是平行四边形，那么AD=BC。ABC

9、D是平行四边形所以AD=BC。,逻辑形式结构如果A，那么B。并且A所以B。(A B) AB,命题形式结构,例1：角A和角B或相等或互补。角A与角B不相等所以角A与角B互补。例2：函数y=f(x)或是奇函数或是偶函数。函数y=f(x)不是奇函数所以函数y=f(x)是偶函数。,逻辑形式结构A或B。并且非A所以B。(AB) AB,1.2公式和真值赋值,合式公式真值表计算语义可满足性,合式公式,命题逻辑中0和1是常元。 变元是命题变元，其值取为真值。用小写英文字母p，q，r，s，t等表示命题变元。定义：命题变元称为原子公式。,合式公式（命题形式）,定义：(1).符号0和1是合式公式；(2).原子公式是

10、合式公式；(3).若Q,R是合式公式，则(Q)、(QR) 、(QR) 、(QR) 、(QR) 、(QR)是合式公式；(4).只有有限次应用(1)(3)构成的公式是合式公式。,合式公式是命题逻辑的语法概念，它仅仅是符合语法结构的公式，是一个没有任何意义的符号串。0和1是符号，没有表示逻辑真值的意思； 、和是逻辑运算符号，也没有表示逻辑运算的意思；命题变元也是符号。由于合式公式的定义具有抽象性和严格性，人们对于一个合式公式的理解是相同的，不会产生二义性。,合式公式,定义1.5 设S是联结词的集合。由S生成的公式定义如下：若c是S中的0元联结词，则c是由S生成的公式。原子公式是由S生成的公式。若n1

11、，F是S中的n元联结词，A1,An是由S生成的公式，则FA1An是由S生成的公式。上面采用了前缀记法即把联结词写在运算对象的前面如pq。采用前缀记法不需要用括号也不会引起歧义。,合式公式,设S是联结词的集合是， ，。合式公式：(pq) (pq ),(pq)， (pq )是合式公式,，q ，pq是合式公式, q是合式公式,(pq) (pq )是合式公式,(p 0) (q 1)是合式公式0,1合式公式p, q是合式公式(p 0)， (q 1)是合式公式(p 0) (q 1)是合式公式,命题逻辑语言,定义：所有的命题合式公式集合构成了命题逻辑语言，记为L 。一般来说，命题逻辑语言L 是无穷集合，也就

12、是说合式公式有无穷多个。,公式复杂度,公式A的复杂度表示为FC(A)常元复杂度为0。命题变元复杂度为0，如果P是命题变元，则FC (P)=0。如果公式A=B，则FC (A)=FC(B)+1。如果公式A=B1 B2，或 A=B1 B2，或 A=B1B2，或 A=B1 B2，或 A=B1 B2，或 则FC (A)=maxFC(B1), FC(B2)+1。,联结词的优先级,联结词的优先级从高到低的顺序排列为：、 、同一个联结词连续多次出现且无括号，则按从左至右的顺序运算在满足运算次序不变的情况下，运用联结词的优先级规则可以减少合适公式括号。,联结词的优先级,(pq)r)q)p) q)r= (pqr)

13、q)p) q)r= (pqrq)p) q)r=(pqrqp) q)r=(pqrqp) qr,真值表计算,命题逻辑语言L的合式公式仅仅是一个符号串。对于一个合式公式，我们关注点之一是它在什么情况下为真？在什么情况下为假？即一个合式公式的逻辑真值是什么？。一个合式公式与逻辑真值之间的对应关系。,真值表计算,(pq) (pq ),(pq) (pq),p q pq,(pq) (pq ),求一个公式值，一个公式与另一个公式是否等值等等真值表的方法不适应对命题演算进行整体的讨论或探究命题之间的逻辑关系。真值表优缺点容易、直观 多变量及公式复杂难易操作,命题合式公式语义,语义：研究公式与所指称对象的关系。论

14、域：研究对象的集合。解释用论域的对象、对象的运算对应形式系统的抽象符号。结构论域和解释称为形式系统的结构。语义结构连同该结构下公式所取真值的规定称为语义。数理逻辑的语义研究合式公式与真值的关系。,常元和运算符语义,合式公式的常元0和1的语义分别对应逻辑真值0和1；合式公式中的、或等逻辑运算符的语义分别是逻辑真值集合上的、或运算等。合式公式的语义是逻辑真值。,真值赋值函数,定义1.6从合式公式集合到逻辑集合0,1的函数称为真值赋值函数。V：A 0,1设v是真值赋值函数，用pv表示v赋给命题变元p的真值。卢卡西维茨运算符表示法前缀表示，FA1,An;中缀表示，A1FA2;后缀表示，A1,AnF,合

15、式公式语义,设S是联结词的集合是， ，。由S生成的合式公式A在真值赋值v下的真值指派v(A)定义如下：v(0)=0, v(1)=1。若A是命题变元p，则v(A)= pv。若A1,A2是合式公式若A= A1，则v(A)= v(A1)若A=A1 A2，则v(A)=v(A1) v(A2)若A=A1A2，则v(A)=v(A1)v(A2)若A=A1 A2，则v(A)=v(A1) v(A2)若A=A1 A2，则v(A)=v(A1) v(A2)若A=A1 A2，则v(A)=v(A1) v(A2),真值赋值,由S生成的公式A在真值赋值v下的真值v(A)定义如下：若A是S中的0元联结词c，则v(A)=c。若A是

16、命题变元p，则v(A)= pv。若A是FA1,An，其中n1， F是S中的n元联结词， Ai是公式，则v(A)=v(FA1An)=Fv(A1)v(An)。,语义方法的计算,(qr)真值赋值函数： v(p)=1, v(q)=1, v(r)=0v(p(qr)=v(p) v(qr)=v(p) (v(q)v(r)=1(10)=10=0,(qr)真值赋值函数： v(p)=0, v(q)=1, v(r)=0v(p(qr)=v(p) v(qr)=v(p) (v(q)v(r)=0(10)=00=1,简化计算,(pq)pqv(p)=0或v(q)=0v(pq)pq)= (v(p)v(q)v(p)v(q)= (v(

17、p)v(q)11,简化计算（续）,v(p)=1并且v(q)=1v(pq)pq)= (v(p)v(q)v(p)v(q)= 1001,定理1.1设A是公式，v1和v2是真值赋值，对于A中出现的每个命题变元p， ；则v1(A)=v2(A)。证明 对A的长度(复杂度)进行归纳。若A的长度是0，则A是命题变元或0元联结词。若A是0元联结词c，则v1(A)=c=v2(A)。若A是命题变元p ， 则v1(A) = =v2(A)。,设m大于1，对于每个复杂度小于m的由S生成的公式B，v1(B)=v2(B)。(3)若A是FA1An，其中n1，F是S中的n元联结词，则A1,An的复杂度都小于m，由归纳假设知道，v

18、1(Ai)=v2(Ai) i=1,nv1(FA1An )=F v1(A1 )v1(An) =F v2(A1 )v2(An) =v2(FA1An )因此，v1(FA1An)= v2(FA1An )证毕,定理1.1的涵义,若公式A中出现的命题变元为p1,pn，v是真值赋值，则v(A)只与 有关。用 表示满足 的真值赋值v例1 设公式A为p0q1,真值赋值v=(p/1,q/0)v(A)=v(p0q1) =v(p) v(0)v(q) v(1) = 1 00 1 =10 =0,如果对公式中出现的每个命题变元都指派了确定的真值，则该公式的真值也就唯一确定了。因此，可将公式看做真值函数。 (pq) pq,v

19、(p)=0,v(q)=0v(pq) pq)= (v(p)v(q) v(p)v(q)= (00) 00=0 11=11=1,(p/0,q/1)v(pq) pq) =1(p/1,q/0)v(pq) pq) =1(p/1,q/1)v(pq) pq) =1,可满足式,定义1.7 设A是公式。如果真值赋值v使得v(A)=1，则称v满足A。如果每个真值赋值都满足A，则称A为永真式，也称为重言式。如果每个真值赋值都不满足A，则称A为永假式，也称为矛盾式，不可满足式。如果至少有一个真值赋值满足A，则称A为可满足式。,替换,定义1.8用 公式分别替换公式A中的不同命题变元 得到的公式记为 ，称为A的替换实例。替

20、换产生新的公式,= (r p)(r p) r (p/r p, q/r),定理1.2 设 是不同命题变元， 是公式。则对于每个真值赋值v，其中真值赋值v=vp1/v(B1), pn/v(Bn)定义如下：,证明：对A进行归纳。若A是pi，其中1in，则 是Bi，若A是除 之外的命题变元p，则 仍是p，(3)若A是0元联结词c，则 仍是c，,(4)设A1,Ak是长度小于m的公式，并且若A是F A1,Ak，其中F是k元联结词，是长度等于m的公式,则是,定理1.3设A是公式。若A是永真式，则A的每个替换实例都是永真式。若A是永假式，则A的每个替换实例都是永假式。证明任取永真式A的替换实例 ，对于每个真值

21、赋值v，所以 是永真式。可同样证明。证毕, ( q p)是永真式设A,B是任意公式p/A, q/BA= p q , B=(p r)( p q ) (p r) ( p q ) )是永真式,1.3等值演算,定义1.9 设A,B是公式，如果对于每个真值赋值v，v(A)=v(B)，则称A和B等值，也称A与B逻辑等价，记为AB。判断(pq)和pq是否等值。,等值式模式,零律A11 A00 幂等律AAA AAA 吸收律A(AB)A A(AB)A 同一律A1A A0A A0A,双重否定AA矛盾律AA0 排中律AA1假言易位ABBA,等值式模式,德摩根律(AB)AB(AB)AB 交换律ABBAABBAABBA

22、,等值式模式,结合律(AB)CA(BC)(AB)CA(BC)(AB)CA(BC) 分配律A(BC)(AB)(AC) A(BC)(AB)(AC)A(BC)(AB)(AC),等值式模式,AA0A1AABABAB(AB)(BA)AB(AB)(AB)AB(AB),定理：设Q是合式公式，R1是Q的子公式，若R1R2，则Q R1/R2Q。 证明：因为R1R2，所以，v(R1)= v(R2) 。首先选择一个不是公式Q中的命题变元p。不妨设命题变元p取代公式Q中的一个R1而得公式为Q。因此，有 p/R1Q=Q， p/R2Q= R1/R2Q。,又因为v ( p/R1 Q)= v(p/v(R1)Q)， v( p/

23、R2Q)= v( p/v(R2)Q)因此，有v( p/v(R1)Q)= v(p/v(R2)Q)。有v( p/R1Q)= v( p/R2Q)有v(Q)= v( R1/R2Q)。有Q R1/R2Q。因此，若R1R2，有Q R1/R2Q,例1.5证明p(qr)pqr证明：p(qr)p(qr) ABAB(pq)r 结合律(pq)r 摩根律pqr ABAB,(pr) (q r) (pq) r(pr) (q r)(pr) (q r) ABAB(p q ) p r q r r r 分配律(p q ) p r q r r 同一律(p q ) r 吸收律 (pq) r 摩根律 (pq) r ABAB,(q r)

24、 (p q) (p r) p(q r) p (q r) ABAB p q r ABAB p q(p p ) r 排中律 p qp q p r 分配律 p qp r 吸收律 qp p r 交换律 ( p q) p r 摩根律 (p q) (p r) ABAB(p q) (p r) ABAB,例1.6用等值演算证明p(qr)pqr是永真式。p(qr)pqr (p(qr)pqr (p(qr)(p(qr)pqr (p(qr)(p(qr)pqr(p(qr)(p(qr)pqr(p(qr)(pqr)pqr(p(qr)pqr)(pqrpqr)(pp(qr)qr)(pqpqrr)(1(qr)qr)(pqpq1)

25、 11 1,1.4对偶定理,(pq)r (pq)r(p0) 1 (p1)0定义1.10设A是由0,1,生成的公式，将A中的和互换，0和1互换得到A*，称A*与A互为对偶式。定义1.11如果真值赋值v1和v2满足对每个命题变元p， ， 则称v1和v2是相反的。(pq)r互为对偶(pq)r(p0) 1互为对偶(p1)0,(pq0)r1 v(p)=1,v(q)=0,v(r)=1(pq1)r0 v(p)=0,v(q)=1,v(r)=0v(pq0)r1)=(v(p)v(q)v(0)v(r)v(1)=(100)11=1v(pq1)r0 )= (v(p) v( q)v(1)v(r)v(0) = (010)0

26、0=0= 1,对偶定理,定理1.14设A是由0,1,生成的公式，A*与A互为对偶式，v和v是相反的真值赋值，则v(A*)=v(A)。证明：1.A的复杂度为0，定理成立若A为命题变元p，则A*也为p，v(p)=v(p)。若A为0，则A*为1，v(1)=v(0)。若A为1，则A*为0，v(0)=v(1)。,2.假设对于复杂度不超过n的每个公式B，v(B*)=v(B)。3.证明复杂度等于n，定理成立。(1)若A为B，v(B*)=v(B)，并且A*为B*。因此，v(A*)=v(B*)=v(B*)=v(B)=v(B)= v(A)(2)若A为BC，v(B*)=v(B)且v(C*)=v(C)，并且A*为B*

27、C*。因此，v(A*)=v(B*C*)=v(B*)v(C*)=v(B)v(C)= v(BC)=v(BC)= v(BC) = v(A),(3)若A为BC，v(B*)=v(B)且v(C*)=v(C)，并且A*为B*C*。因此，v(A*)=v(B*C*)=v(B*)v(C*)=v(B)v(C)= v(BC)=v(BC)= v(BC)= v(A),定理1.5（对偶定理）设A,B是由0,1,生成的公式，A*与A互为对偶式，B*与B互为对偶式。如果A B，则A* B*。证明：任取真值赋值v，令v是与v相反的真值赋值，因为AB，所以v(A)=v(B)，因此，v(A*)=v(A)= v(B)=v(B*)所以，

28、A* B*。证毕,证明等值式：(1) (pq)(p(p q) p q(2) (p q) (p (p q) p q证明：等值式(1)(pq)(p(p q) (pq)(pp q) (pq)pq pq证明：等值式(2)对偶定理,1.5联结词的完全集,q=pqpq=(pq)(qp)=(pq)(pq)pq=(pq) (pq)结论：，不是独立的逻辑的最少联接词是什么？,完全集,定义1.12设F是n元联结词，p1,p2,pn是不同的命题变元。如果公式A中不出现除p1,p2,pn之外的命题变元，并且AFp1,p2,pn，则称A定义F。如果存在由联结词集合S生成的公式来定义F，则称F可由S定义。如：S=, ,

29、pq=pqpq=(pq)(qp)=(pq)(pq)pq=(pq)(pq),真值表的启示,(p/0,q/1), (p/1,q/0) F7=pqpq(p/0,q/1) ,(p/1,q/1) F11=pqpq(p/0,q/1) , (p/1,q/0),(p/1,q/1) F15=pqpqpq,完全集,定义1.13设S是联结词集合。如果每个n(n0)元的联结词都可由S定义，则称S为完全集。,完全集定理,定理 ,是完全集。证明：设n0，F是n元联结词，p1,p2,pn是不同命题变元，可以找出定义F的由,生成的公式A。若Fp1p2pn是永假式，取A为p1 p1。若Fp1p2pn是可满足式，满足Fp1p2p

30、n=1的真值赋值为 ，则取A为其中,完全集定理,任取真值赋值v，v(A)= 1当且仅当有1in，使当且仅当有1in，使当且仅当有1in，使当且仅当有1in，使所以AF p1p2pn ，,是完全集。证毕,定理如果完全集S1中的每个联结词都可由联结词集合S2定义，则S2也是完全集。,极小完全集,定义如果从完全集S中去掉任何一个联结词就成为不完全的了，就称S为极小完全集。,极小完全集定理,定理以下联结词集合是极小完全集。 , ， , ， , 证明：因为pq(pq)，所以可由,定义。,都可由,定义，并且,是完全集，所以,也是完全集。,证明,是极小完全集。证明不是完全集。任取由生成的公式A，其中A不出现

31、除p之外的命题变元，公式模式： ppp 令真值赋值v=(p/1)，则v(A)=1，但v(p)=0，所以A不能定义。结论:不能由定义。,再证明不是完全集。取一元联结词F使F(0)=F(1)。令真值赋值v1=(p/1)和v2=(p/0)，任取由生成只出现命题变元p的公式A，公式:p则v1(A)v2(A)，而v1(Fp)=v2(Fp)，所以A不能定义F。F不能由定义。不是完全集。, , 是完全集,因为pq=(pq)=(pq)，所以可由,定义。,都可由,定义，并且,是完全集，所以,也是完全集。,证明不是完全集。取真值赋值v=(p/1)。任取由生成的仅出现命题变元p的公式A，v(A)=1，而v(p)=0

32、，A不能定义。所以不能由定义。不是完全集。也不是完全集。结论：,是极小完全集。,与非（ ）、或非（）,是完备集是完备集,1.6范式,(pq)r=(pq)r=(p r)(q r)=(p q r) (p q r)(p q r)(p q r)结论：公式唯一性？等值公式有唯一的表示？判断公式等值范式比较,范式定义,定义 原子公式和原子公式的否定统称为文字。如果一个文字恰为另一个文字的否定，则称它们为相反文字。文字:p,相反文字:p定义 设n是正整数，A1,An都是文字，称A1An为简单析取式，称A1 An为简单合取式。(p q r)，(p q r),定义 设n是正整数。若B1,Bn都是简单合取式，则称

33、B1Bn为析取范式。若B1,Bn都是简单析取式，则称B1 Bn为合取范式。简单合取式的析取是析取范式,(p q r)(p q r)(p q r)简单析取式的和取是和取范式,(p q r) (p q r)(p q r),合取范式与析取范式,(pqr) p (pq) r) p (pq) r) p(pq) r p (pq p) ( r p) (pq) ( r p) 合取范式 p ( r p) q ( r p) p q rq p p (q r ) 析取范式 p (r r ) (q r ) p r p r (q r ) 不唯一,主析取范式与主合取范式,定义 设n是正整数，p1,pn是不同的命题变元。若对

34、于每个i，Ai是pi或pi，则称A1 An为关于p1,pn极大项，A1An为关于p1,pn的极小项。,定义 设m是自然数。若B1,Bm是关于p1,pn的不同极小项，则称B1Bn为关于p1,pn的主析取范式。若B1,Bm是关于p1,pn的不同极大项，则称B1Bn为关于p1,pn的主合取范式。主析取范式和主合取范式统称为主范式。,定义 设公式A中出现的命题变元为p1,p2,pn， B是关于p1,p2,pn的主析取范式（主合取范式），并且AB，则称B为A的主析取范式（主合取范式）。,主范式变换步骤,联接词等值变换（1）消去联接词、将公式由、表示AB ABAB (AB)(BA)AB (AB)(AB)德

35、.摩根律（2）应用德.摩根律内移或消去约束公式的变换为约束变元(AB) AB (AB) AB,主范式变换步骤,分配律（3）应用分配律求取合取范式或析取范式A(BC) (AB)(AC) A(BC) (AB)(AC)矛盾律与排中律（4）应用矛盾律与排中律求主合取范式或主析取范式AA 0 AA 1交换律（5）应用交换律变元位置排序AB BA AB BA,主合取范式,(pr)(qp) (pr)(qp)(pq)(pr)(qp)(pq)(prqq)(qprr)(pqrr)(prq)(prq)(qpr) (qpr)(pqr)(pqr)(pqr)(pqr)(pqr) (pqr)(pqr)(pqr),主析取范式

36、,(p q) (p q) pq(pq) (p q) p q (pq) (p q) p q (pq) (p q) p q p qp qp q p qp(q q) qp q p q pq p q qp q p q pq p q (p p) qp q p q pq p q p q p qp q p q p q pq p q,定理：任何公式等值于某一析取范式任何公式等值于某一合取范式每一公式有唯一的主析取范式每一公式有唯一的主合取范式,定理设在公式A中出现n个命题变元，以下条件是等价的。A是永真式。A的主析取范式中包含了所有的极小项，即它是2n个极小项的析取。A的主合取范式中不包含任何极大项，即它是个

37、极大项的合取，也就是。,定理设在公式A中出现n个命题变元，则以下条件是等价的。A是永假式。A的主合取范式中包含了所有的极大项，即它是2n个极大项的合取。A的主析取范式中不包含任何极小项，即它是个极小项的析取，也就是。,逻辑门,数字逻辑与数字部件设计,译码器、寄存器、加法器、移位器、控制器、多路选择器、计数器、比较器,译码器 (2输入4输出译码器),B,A,Y3,Y2,Y1,Y0,1.7逻辑推论从三段论看,公式取值，v(A)=?任意赋值函数为真任意赋值函数为假有的赋值函数为真，有的赋值函数为假可满足的公式之间的关系？当v(AB)=1, V(A)=1, v(B)=?,1.7逻辑推论从传递律看,当V

38、(AB)=1,v(BC)=1, v(AC)=?,1.7逻辑推论,=A1,An定义 若真值赋值v满足公式集合中的每个公式，则称v满足。若有真值赋值满足，则称是可满足的，否则称是不可满足的。V(A1)=1, V(An)=1定义 设是公式的集合，A是公式。如果每个满足的真值赋值都满足A，则称A是的逻辑推论， 记为 A。若 A不成立，记为 A。如果V()= 1，则v(A)=1只要前提真，结论就一定真真值表的含义若=A1,An，则将简记为A1,An A。,推理形式,每一推理形式都相当于一个真值形式。正确的推理形式相当于一个重言式。错误的推理形式虽然也有一个相当的真值形式，但不是重言式。判别一推理形式是否

39、正确，就是要判别其相当的蕴涵式是不是一个重言式。正确推理形式(pq)p)q错误推理形式(pq)p)q,三段论证明,例1.14 证明A, AB B证明：若真值赋值v使v(A)=1， v(AB)=1， v(A)v(B)=1, 则v(B)=1。所以A, AB B,传递律证明,例1.15 证明AB, B C A C证明：设真值赋值v使v(AB)=v(B C)=1若v(A)=0，则v(A C)=1若v(A)=1， v(A)v(B)=1，则v(B)=1v(B)v(C)=1，所以v(C)=1，因此，v(A)v(C)=1因此，AB, B C A C,例1.16 AB，CD，AC BD。证明：设真值赋值v使v(

40、AB)=v(CD)=v(AC)=1,则v(A)=1或v(C)=1。若v(A)=1，则由v(AB)=1得出v(B)=1。若v(C)=1，则由v(CD)=1得出v(D)=1。无论哪种情况皆有v(BD)=1。,例11.17 pq pqr。证明：需要找出一个真值赋值v使v(pq)=1且v(pqr)=0。这样的v使v(p)=v(q)=1，v(qr)=0。所以，只要取真值赋值v=(p/1,q/1,r/1)就能满足上述要求。,定理 设A是公式，则 A当且仅当A是永真式。证明 充分性：设 A，任取真值赋值v，因为v(A)=1。因此，A是永真式。必要性：设A是永真式，显然 A。证毕,定理 设A1,An，B是公式

41、，A1,An B，当且仅当A1 AnB是永真式。证明充分性：设A1,An B。 A1 An B任取真值赋值v。因为v(A1)=v(An)=1 所以v(A1An)=1，又因为v(B)=1。所以v(A1An)v(B)=v(A1AnB)=1。因此A1AnB是永真式。必要性：设A1 AnB是永真式，任取真值赋值v，若v(A1An)=1，则v(A1)=v(An)=1，故v(B)=1所以A1,An B,定理 设A，B是公式。AB当且仅当 A B且B A。证明AB当且仅当 AB是永真式当且仅当 AB和BA都是永真式当且仅当 A B且B A证毕,定理 设是公式的集合，A和B是公式，则A B当且仅当 AB。证明

42、 证明A B当且仅当 AB。若A B，则有真值赋值v使中公式皆真且v(A)=1，而v(B)=0。所以v(AB)=0， AB。若 AB，则有真值赋值v使中公式皆真且v(AB)=0，则v(A)=1且v(B)=0。所以A B。证毕,定理 设是公式的集合，A和B是公式，则A B当且仅当 AB。证明 若A B，则有真值赋值v使中公式皆真且v(A)=1，v(B)=1。所以v(AB)=1， AB。若 AB，则有真值赋值v使中公式皆真且v(AB)=1。又如果v(A)=1，则v(B)=1。所以A B。证毕,定理 设n是正整数。公式集A1,An是可满足的当且仅当A1An是可满足式。证明：v(A1An)=v(A1)v(An)v(A1)= v(An)=1当且仅当v(A1An)=1,定理 设是公式集合。是不可满足的当且仅当每个公式都是的逻辑推论。证明 充分性：设是不可满足的，A为任意公式，则显然每个满足的真值赋值使A为真，因为满足的真值赋值根本不存在。故 A。必要性：设每个公式都是的逻辑推论，则 0。若有真值赋值v满足，则v(0)=1，这是不可能的。所以，不可满足。证毕,谢谢,