命题逻辑202010-910-91计算机学院2计算机学院2集合集合论定义：定义：一些对象聚集为一个整体，称为一些对象聚集为一个整体，称为集合集合。这些。这些对象称为集合的对象称为集合的元素元素。元素与集合的关系元素与集合的关系a a是集合是集合S S的元素，记为的元素，记为a aSa a不是集合不是集合S S的元素，记为的元素，记为a aS集合的表示法集合的表示法空集：空集：有穷集合：枚举法，有穷集合：枚举法，S=xS=x1 1,x,x2 2, ,x,xn n 无穷集合：描述法无穷集合：描述法x|xx|x是自然数是自然数 2计算机学院3计算机学院3集合外延、内涵集合外延、内涵外延原则与概括原则外延原则与概括原则外延原则：一个集合由它的元素唯一地确定。外延原则：一个集合由它的元素唯一地确定。概括原则：每一性质概括原则：每一性质( (或谓词或谓词) )产生一个集合。产生一个集合。集合外延集合外延集合所包含的元素全体。集合所包含的元素全体。集合内涵集合内涵集合元素所共有的性质。集合元素所共有的性质。非负偶数集合非负偶数集合外延外延0,2,4,0,2,4,内涵内涵x|xx|x是被是被2 2整除的自然数整除的自然数 3计算机学院4计算机学院4集合的关系集合的关系集合的关系集合的关系包含关系：包含关系：如果集合如果集合A A的元素都是集合的元素都是集合B B的元素，则称的元素，则称A A为为B B的子集，记为的子集，记为A AB真包含关系：真包含关系：A AB不包含关系不包含关系:A:AB等关系：等关系：如果集合如果集合A A和集合和集合B B包含相同元素，则称包含相同元素，则称A A和和B B相相等，记为等，记为A=BA=B4计算机学院5计算机学院5函数函数A An n=AAA=AAAA An n=(x=(x1 1,x,x2 2, ,x,xn n)|x)|xi iAAA=0, 1A=0, 1A A3 3 =0, 1=0, 13 3=(0,0,0),(0,0,1),(0,1,0),(0,1,1)=(0,0,0),(0,0,1),(0,1,0),(0,1,1) (1,0,0),(1,0,1),(1,1,0),(1,1,1) (1,0,0),(1,0,1),(1,1,0),(1,1,1)设设A A和和B B是集合，如果对于集合是集合，如果对于集合A A中每个元素中每个元素x x，都有，都有集合集合B B中唯一元素中唯一元素f(x)f(x)与之对应，则称与之对应，则称f f是是函数函数。若若f f是从是从A An n到到B B的函数，则称的函数，则称f(xf(x1 1,x,x2 2, ,x,xn n) )为为A A上的上的n n元函数，也称元函数，也称 f(x f(x1 1,x,x2 2, ,x,xn n) )为为A A上的上的n n元运算。元运算。f f：AAAAAAA A5计算机学院6计算机学院6归纳定定义归纳定义归纳定义自然数集合：自然数集合：n n 是是n n的后继（函数），的后继（函数），N N是满足以下是满足以下条件的条件的S S中的最小集合中的最小集合 0 0S S对于任何对于任何n n，如果，如果n nS S，则，则n S S。6计算机学院7计算机学院7归纳证明明归纳证明归纳证明设设R R是一个性质，是一个性质，R(x)R(x)表示表示x x有有R R性质。性质。定理证明定理证明归纳基础归纳基础R(0)R(0)归纳假设归纳假设对于任何对于任何k kN,R(k);N,R(k);证明证明R(kR(k ););归纳结论归纳结论对于任何对于任何n nN，R(n)。排序概念排序概念7计算机学院8计算机学院8数理数理逻辑基本概念基本概念真真可证性可证性8计算机学院9计算机学院9数理数理逻辑数理逻辑是用数学语言表述的推理形式有效性的学问。数理逻辑是用数学语言表述的推理形式有效性的学问。命题逻辑、谓词逻辑命题逻辑、谓词逻辑数理逻辑使用特制的表意符号，亦称为符号逻辑。数理逻辑使用特制的表意符号，亦称为符号逻辑。逻辑研究对象逻辑研究对象逻辑真值逻辑真值真，表示为真，表示为T T或或1 1假，表示为假，表示为F F或或0 0正确的推理正确的推理形式形式正确前提正确前提正确的推理形式正确的推理形式必然得出正确的结论必然得出正确的结论9计算机学院10计算机学院101.1命命题和和联结词 什么是命题？什么是命题？命题的运算符是什么？命题的运算符是什么？如何表示命题？如何表示命题？有多少种命题的运算符？有多少种命题的运算符？10计算机学院11计算机学院11语句表达句表达陈述句陈述句疑问句疑问句祈使句祈使句感叹句感叹句雪是白的。雪是白的。 2 2是奇数。是奇数。X+Y5X+Y5。你是谁？你是谁？我正在说谎。我正在说谎。北京是中国的首都。北京是中国的首都。前进！前进！天空多漂亮天空多漂亮! !特点：有的语句可以特点：有的语句可以判断真假。判断真假。11计算机学院12计算机学院12自然自然语言、命言、命题语言是人们思维和交际的工具，也是一种语言是人们思维和交际的工具，也是一种表达观念的符号系统。表达观念的符号系统。自然语言由各种句式组成，如陈述句、疑自然语言由各种句式组成，如陈述句、疑问句、感叹句、祈使句等等。问句、感叹句、祈使句等等。陈述句是陈述一个事实或者说话人的看法，陈述句是陈述一个事实或者说话人的看法，它包括肯定句和否定句两种。一般来说，它包括肯定句和否定句两种。一般来说，仅有陈述句能够确定句子的意义是真还是仅有陈述句能够确定句子的意义是真还是假。假。命题表达为具有命题表达为具有确定真假意义确定真假意义的的陈述句陈述句。12计算机学院13计算机学院13命命题示例示例雪是白的。雪是白的。 2 2是奇数。是奇数。X+Y5X+Y5。你是谁？你是谁？我正在说谎。我正在说谎。北京是中国的首都。北京是中国的首都。每个不小于每个不小于6 6的偶数都是两个的偶数都是两个奇素数之和（歌德巴赫猜想）奇素数之和（歌德巴赫猜想）2121世纪有人住在月球上。世纪有人住在月球上。他很高。他很高。一个自然数不是合数就是素数一个自然数不是合数就是素数命题，真命题，真 命题，假命题，假不确定，非命题不确定，非命题疑问句，非命题疑问句，非命题悖论，非命题悖论，非命题命题，真命题，真命题，真，有唯一真假值。命题，真，有唯一真假值。命题，真，有唯一真假值。命题，真，有唯一真假值。无法确定，非命题无法确定，非命题命题，假，命题，假，1 1不是合数和素数不是合数和素数13计算机学院14计算机学院14简单命命题与复合命与复合命题简单命题简单命题由简单陈述句表述的命由简单陈述句表述的命题称为简单命题。题称为简单命题。命题逻辑不再进一步分命题逻辑不再进一步分析简单命题的内部结构析简单命题的内部结构p:p:孔子是圣人孔子是圣人语句联接词语句联接词并且并且或或否定否定如果如果, ,则则。当且仅当当且仅当既不既不，也不，也不。复合命题复合命题用联接词可以将若干个用联接词可以将若干个简单句组合成复合句。简单句组合成复合句。子命题子命题14计算机学院15计算机学院15命命题逻辑如何运算？如何运算？数计算启示数计算启示自然数自然数运算：运算：+ +、* *整数整数运算：运算：+ +、- -、* *有理数有理数运算：运算：+ +、- -、* *、/ /命题逻辑命题小写字母表示真1，假0运算：？15计算机学院16计算机学院16命命题题的抽象表示的抽象表示自然语言具有自然语言具有二义性二义性命题逻辑不关注语句的内容，也不关注语句为何是命题逻辑不关注语句的内容，也不关注语句为何是真或为假，而是仅仅关注语句能够为真或假。真或为假，而是仅仅关注语句能够为真或假。命题的命题的抽象抽象用小写字母表示命题，取值为用小写字母表示命题，取值为0,10,1。命题命题真值真值陈述句的意义为真，称为陈述句的意义为真，称为真命题真命题，真值为，真值为1 1。陈述句的意义为假，称为陈述句的意义为假，称为假命题假命题，真值为，真值为0 0。命题逻辑的研究对象命题逻辑的研究对象命题。命题。数理逻辑从数理逻辑从形式结构形式结构方面研究命题。方面研究命题。16计算机学院17计算机学院17逻辑联结词定义定义0 0和和1 1称为称为0 0元函数。设元函数。设n0,n0,称为称为0,10,1n n到到0,10,1的函数的函数为为n n元函数，真值函数也称元函数，真值函数也称为为联结词联结词。命题的操作符（联结词）命题的操作符（联结词）非非 与与 或或 如果如果, ,则则。 当且仅当当且仅当 异或异或 真值真值表表真值形式可以用图真值形式可以用图表来说明。这种表表来说明。这种表称为称为真值真值图表。图表。0 0元函数元函数0 0，1 11 1元函数元函数 2 2元函数元函数 、 、 、 17计算机学院18计算机学院18逻辑联结词 命题p的否定记为p,读作非p真值表真值表逻辑联接词的含义自然语言中，并非的含义18计算机学院19计算机学院19逻辑联结词 真值表pq称为p和q的合取读作p且q 逻辑联接词的含义自然语言中，并且的含义19计算机学院20计算机学院20逻辑联结词 真值表pq称为p和q的析取，读作p或q 逻辑联接词的含义自然语言中，或的含义20计算机学院21计算机学院21逻辑联结词 真值表逻辑联接词的含义自然语言中，如果,则.的含义pq称为p蕴涵q读作p则qp称为前件q称为后件21计算机学院22计算机学院22逻辑联结词 真值表p q称为p与q等值，读作p当且仅当q, p与q互蕴含。pq=(pq)(qp)逻辑联接词的含义自然语言中，当且仅当的含义22计算机学院23计算机学院23逻辑联结词 北航在海淀区或北航在西城区。 比较李明学习英语或学习法语真值表p q称为p与q异或，读作p异或q。pq= (pq)(qp)23计算机学院24计算机学院24逻辑逻辑域、域、逻辑逻辑运算运算逻辑域逻辑域00，11运算运算 ， ， ， 定义域定义域0, 10, 1值域值域0,10,124计算机学院25计算机学院25命命题逻辑运算符数目运算符数目运算符变量数为运算符变量数为1 1个变量，个变量，2 2个变量，个变量，,n,n个变量的运算符数目个变量的运算符数目pF1F2F3F40001110101pqpqpqpqpqpq000011001011011001001111111025计算机学院26计算机学院26命命题逻辑函数数目函数数目变量数为变量数为n n变量组合数变量组合数运算符数运算符数 pqF1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16000101010101010101010011001100110011100000111100001111110000000011111111Fi(p,q)=？26计算机学院27计算机学院27命命题形式形式结构构复合命题复合命题是命题及真值联结词构成的形式是命题及真值联结词构成的形式结构结构六个真假形式最基本的，或最简单的形式，称六个真假形式最基本的，或最简单的形式，称为为简单命题简单命题。由这六个真假形式，经过各种各种的互相组合，由这六个真假形式，经过各种各种的互相组合，还可以变成更多的各种复杂真值形式。还可以变成更多的各种复杂真值形式。真值形式数量无穷无尽。真值形式数量无穷无尽。示例示例并非并非p p并且并且q q。(p(pq q) )如果非如果非p p，那么非，那么非q q。 p p q q如果如果p p或或q,q,那么那么r r。p pq qr r27计算机学院28计算机学院28命命题形式形式结构构例例1 1：如果如果n n是奇数，那么是奇数，那么n n2 2也是也是奇数。奇数。n n是奇数是奇数所以所以n n2 2也是奇数。也是奇数。例例2 2：如果如果ABCDABCD是平行四边形，是平行四边形，那么那么AD=BCAD=BC。ABCDABCD是平行四边形是平行四边形所以所以AD=BCAD=BC。逻辑形式结构逻辑形式结构如果如果A A，那么，那么B B。并且并且A A所以所以B B。(A B) AB28计算机学院29计算机学院29命命题形式形式结构构例例1 1：角角A A和角和角B B或相等或互补。或相等或互补。角角A A与角与角B B不相等不相等所以角所以角A A与角与角B B互补。互补。例例2 2：函数函数y=f(x)y=f(x)或是奇函数或是或是奇函数或是偶函数。偶函数。函数函数y=f(x)y=f(x)不是奇函数不是奇函数所以函数所以函数y=f(x)y=f(x)是偶函数。是偶函数。逻辑形式结构逻辑形式结构A A或或B B。并且非并且非A A所以所以B B。(AB) AB29计算机学院30计算机学院301.2公式和真公式和真值赋值合式公式合式公式真值表计算真值表计算语义语义可满足性可满足性30计算机学院31计算机学院31合式公式合式公式命题逻辑中命题逻辑中0 0和和1 1是常元。是常元。 变元是命题变元，其值取为真值。变元是命题变元，其值取为真值。用小写英文字母用小写英文字母p p，q q，r r，s s，t t等表示命题等表示命题变元。变元。定义：命题变元称为定义：命题变元称为原子公式原子公式。31计算机学院32计算机学院32合式公式（命合式公式（命题形式）形式）定义：定义：(1).(1).符号符号0 0和和1 1是合式公式；是合式公式；(2).(2).原子公式是合式公式；原子公式是合式公式；(3).(3).若若Q,RQ,R是合式公式，则是合式公式，则( ( Q)Q)、(Q(Q R) R) 、(Q(Q R) R) 、(Q(QR) R) 、(Q(QR) R) 、(Q(Q R)R)是是合式公式；合式公式；(4).(4).只有有限次应用只有有限次应用(1)(1)(3)(3)构成的公式是构成的公式是合式公式。合式公式。32计算机学院33计算机学院33合式公式是命题逻辑的语法概念，它仅仅是合式公式是命题逻辑的语法概念，它仅仅是符合语法结构的公式，是一个没有任何意义符合语法结构的公式，是一个没有任何意义的符号串。的符号串。0 0和和1 1是符号，没有表示逻辑真值的意思；是符号，没有表示逻辑真值的意思； 、 、 、和和 是逻辑运算符号，是逻辑运算符号，也没有表示逻辑运算的意思；也没有表示逻辑运算的意思；命题变元也是符号。命题变元也是符号。由于合式公式的定义具有抽象性和严格性，由于合式公式的定义具有抽象性和严格性，人们对于一个合式公式的理解是相同的，不人们对于一个合式公式的理解是相同的，不会产生二义性。会产生二义性。33计算机学院34计算机学院34合式公式合式公式定义定义1.5 1.5 设设S S是联结词的集合。由是联结词的集合。由S S生成的公式生成的公式定义如下：定义如下：若若c c是是S S中的中的0 0元联结词元联结词，则，则c c是由是由S S生成的公式。生成的公式。原子公式原子公式是由是由S S生成的公式。生成的公式。若若n1n1，F是是S S中的中的n n元联结词，元联结词，A A1 1, ,A,An n是由是由S S生成的公式，则生成的公式，则FA A1 1A An n是由是由S S生成的公式。生成的公式。上面采用了上面采用了前缀记法前缀记法即把联结词写在运算对象的前面即把联结词写在运算对象的前面如如 pqpq。采用前缀记法不需要用括号也不会引起。采用前缀记法不需要用括号也不会引起歧义。歧义。 34计算机学院35计算机学院35合式公式合式公式设设S S是联结词的集合是是联结词的集合是 ， ， ， 。合式公式：合式公式： (p q q) ( ( p q q ) ) (p q q)， ( ( p q q ) )是是合式合式公公式式 p， q q ，p q q是是合式合式公公式式p, q是是合式合式公式公式 (p q q) ( ( p q q ) )是是合式合式公公式式(p 0) (q 1)是是合合式式公式公式0,1合式合式公式公式p, q是是合式合式公式公式(p 0)， (q 1)是是合式合式公式公式(p 0) (q 1)是是合式合式公式公式35计算机学院36计算机学院36命命题逻辑语题逻辑语言言定义：所有的命题合式公式集合构成了定义：所有的命题合式公式集合构成了命题逻辑语言，记为命题逻辑语言，记为L 。一般来说，命题逻辑语言一般来说，命题逻辑语言L 是无穷集合，是无穷集合，也就是说合式公式有无穷多个。也就是说合式公式有无穷多个。36计算机学院37计算机学院37公式复公式复杂度度公式公式A A的复杂度表示为的复杂度表示为FC(A)FC(A)常元复杂度为常元复杂度为0 0。命题变元复杂度为命题变元复杂度为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。37计算机学院38计算机学院38联结词的的优先先级联结词的优先级联结词的优先级从高到低的顺序排列为：从高到低的顺序排列为：、 、同一个联结词连续多次出现且无括号，同一个联结词连续多次出现且无括号，则按从左至右的顺序运算则按从左至右的顺序运算在满足运算次序不变的情况下，运用联在满足运算次序不变的情况下，运用联结词的优先级规则可以结词的优先级规则可以减少合适公式括减少合适公式括号号。38计算机学院39计算机学院39联结词的的优先先级(pq)r)q)p) q)r= (p q r) q)p) q)r= (p q r q)p) q)r=(p q r qp) q)r=(p q r qp) qr39计算机学院40计算机学院40真真值值表表计计算算命题逻辑语言命题逻辑语言L L的合式公式仅仅是一个的合式公式仅仅是一个符号串。符号串。对于一个合式公式，我们关注点之一对于一个合式公式，我们关注点之一是它在什么情况下为真？在什么情况是它在什么情况下为真？在什么情况下为假？即一个合式公式的逻辑真值下为假？即一个合式公式的逻辑真值是什么？。是什么？。一个合式公式与逻辑真值之间的对应一个合式公式与逻辑真值之间的对应关系。关系。40计算机学院41计算机学院41真真值表表计算算 (p q q) ( ( p q q ) ) pqp q(pq)pq pq(pq)pq00011111010110111001011111100001(pq) (pq) p q pq (pq) (pq ) 求一个公式值，一个公式与另一个公式求一个公式值，一个公式与另一个公式是否是否等值等值等等等等真值表的方法不适应对命题演算进行整真值表的方法不适应对命题演算进行整体的讨论或探究命题之间的逻辑关系。体的讨论或探究命题之间的逻辑关系。真值表优缺点真值表优缺点容易、直观容易、直观 多变量及公式复杂难易操作多变量及公式复杂难易操作41计算机学院42计算机学院42命命题合式公式合式公式语义语义：研究公式与所指称对象的关系。语义：研究公式与所指称对象的关系。论域：研究对象的集合。论域：研究对象的集合。解释解释用论域的对象、对象的运算对应形式系统的抽象用论域的对象、对象的运算对应形式系统的抽象符号。符号。结构结构论域和解释称为形式系统的结构。论域和解释称为形式系统的结构。语义语义结构连同该结构下公式所取真值的规定称为语义。结构连同该结构下公式所取真值的规定称为语义。数理逻辑的语义研究合式公式与真值的关系。数理逻辑的语义研究合式公式与真值的关系。42计算机学院43计算机学院43常元和运算符常元和运算符语义语义合式公式的常元合式公式的常元0 0和和1 1的语义分别对应逻的语义分别对应逻辑真值辑真值0 0和和1 1；合式公式中的合式公式中的 、 、 、或或 等等逻辑运算符的语义分别是逻辑真值集合逻辑运算符的语义分别是逻辑真值集合上的上的 、 、 、或或 运算等。运算等。合式公式的语义是逻辑真值。合式公式的语义是逻辑真值。43计算机学院44计算机学院44真真值赋值值赋值函数函数定义定义1.61.6从合式公式从合式公式集合集合到逻辑到逻辑集合集合0,10,1的函数称为的函数称为真值赋值函数真值赋值函数。V V：A A 0,10,1设设v是真值赋值函数，用是真值赋值函数，用p pv表示表示v v赋给命赋给命题变元题变元p p的真值。的真值。卢卡西维茨运算符表示法卢卡西维茨运算符表示法前缀表示，前缀表示，FA A1 1,A,An n; ;中缀表示，中缀表示，A A1 1FA A2 2; ;后缀表示，后缀表示，A A1 1,A,An nF44计算机学院45计算机学院45合式公式合式公式语义设设S S是联结词的集合是是联结词的集合是 ， ， ， ， 。由由S S生生成的合式公式成的合式公式A A在真值赋值在真值赋值v v下的下的真值指派真值指派v(A)v(A)定义如下：定义如下：v(0)=0, v(1)=1v(0)=0, v(1)=1。若若A A是命题变元是命题变元p p，则，则v(A)= pv(A)= pv v。若若A A1 1,A,A2 2是合式公式是合式公式若若A= A= A A1 1，则，则v(A)= v(A)= v(Av(A1 1) )若若A=AA=A1 1 A A2 2，则，则v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) )若若A=AA=A1 1 A A2 2，则，则v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) )若若A=AA=A1 1 A A2 2，则，则v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) )若若A=AA=A1 1 A A2 2，则，则v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) )若若A=AA=A1 1 A A2 2，则，则v(A)=v(Av(A)=v(A1 1) ) v(Av(A2 2) )45计算机学院46计算机学院46真真值赋值由由S S生成的公式生成的公式A A在真值赋值在真值赋值v v下的真值下的真值v(A)v(A)定义如下：定义如下：若若A A是是S S中的中的0 0元联结词元联结词c c，则，则v(A)=cv(A)=c。若若A A是是命题变元命题变元p p，则，则v(A)= pv(A)= pv v。若若A A是是FA A1 1,A,An n，其中，其中n1n1， F是是S S中中的的n n元联结词，元联结词， A Ai i是公式，则是公式，则v(A)=v(v(A)=v(FA A1 1A An n)=)=Fv(Av(A1 1) )v(Av(An n) )。46计算机学院47计算机学院47语义方法的方法的计算算p p(q(qr)r)真值赋值函数：真值赋值函数： v(p)=1, v(q)=1, v(r)=0v(p p(q(qr)r)=v(p) v v(q(qr)r)=v(p) ( (v v(q)(q)v(v(r)r)=1(1(10)0)= =10 0=0=0p p(q(qr)r)真值赋值函数：真值赋值函数： v(p)=0, v(q)=1, v(r)=0v(p p(q(qr)r)=v(p) v v(q(qr)r)=v(p) ( (v v(q)(q)v(v(r)r)=0(1(10)0)=0=00 0=1=147计算机学院48计算机学院48简化化计算算 (p(p q)q) p pq qv(p)=0或或v(q)=0v( (p(p q)q) p pq q)= (v(p)(v(p) v(v(q)q) v(v(p)p)v(v(q)q)= (v(p)(v(p) v(v(q)q)1 11 148计算机学院49计算机学院49简化化计算（算（续）v(p)=1并且v(q)=1v(pq)pq)= (v(p)v(q)v(p)v(q)= 100149计算机学院50计算机学院50定理定理1.11.1设设A A是公式，是公式，v v1 1和和v v2 2是真值赋值，对于是真值赋值，对于A A中出现的每个命题变元中出现的每个命题变元p p， ；则；则v v1 1(A)=v(A)=v2 2(A)(A)。证明证明 对对A A的的长度长度( (复杂度复杂度) )进行归纳。进行归纳。若若A A的长度是的长度是0 0，则，则A A是命题变元或是命题变元或0 0元联结词。元联结词。若若A A是是0 0元联结词元联结词c c，则，则v v1 1(A)=c=v(A)=c=v2 2(A)(A)。若若A A是命题变元是命题变元p p ， 则则v v1 1(A) = =v(A) = =v2 2(A)(A)。50计算机学院51计算机学院51设设m m大于大于1 1，对于每个复杂度小于，对于每个复杂度小于m m的由的由S S生成生成的公式的公式B B，v v1 1(B)=v(B)=v2 2(B)(B)。(3)(3)若若A A是是FA A1 1A An n，其中，其中n1n1，F是是S S中的中的n n元元联结词，则联结词，则A A1 1, ,A,An n的复杂度都小于的复杂度都小于m m，由归，由归纳假设知道，纳假设知道，v v1 1(A(Ai i)=v)=v2 2(A(Ai i) ) i=1, i=1,n,nv1 1(FA A1 1A An n )= =F v1 1(A A1 1 )v1 1(A An n) = =F v2 2(A A1 1 )v2 2(A An n) = =v2 2(FA A1 1A An n )因此，因此，v1 1(FA A1 1A An n)= v2 2(FA A1 1A An n )证毕证毕51计算机学院52计算机学院52定理定理1.1的涵的涵义若公式若公式A A中出现的命题变元为中出现的命题变元为p p1 1, ,p,pn n，v v是是真值赋值，则真值赋值，则v(A)v(A)只与只与 有关。有关。用用 表示满足表示满足 的真值赋值的真值赋值v v例例1 1 设公式设公式A A为为p p 0q0q 1,1,真值赋值真值赋值v=(p/1,q/0)v=(p/1,q/0)v(A)=v(p0q1) =v(p) v(0)v(q) v(1) = 1 00 1 =10 =0 52计算机学院53计算机学院53如果对公式中出现的每个命题变元都指派了确定的如果对公式中出现的每个命题变元都指派了确定的真值，则该公式的真值也就唯一确定了。因此，可真值，则该公式的真值也就唯一确定了。因此，可将公式看做真值函数。将公式看做真值函数。 (pq) pq v(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) =153计算机学院54计算机学院54可可满足式足式定义定义1.7 1.7 设设A A是公式。是公式。如果真值赋值如果真值赋值v v使得使得v(A)=1v(A)=1，则称，则称v v满足满足A A。如果每个真值赋值都满足如果每个真值赋值都满足A A，则称，则称A A为为永真式永真式，也称为也称为重言式重言式。如果每个真值赋值都不满足如果每个真值赋值都不满足A A，则称，则称A A为为永假式永假式，也称为也称为矛盾式矛盾式，不可满足式不可满足式。如果至少有一个真值赋值满足如果至少有一个真值赋值满足A A，则称，则称A A为为可满可满足式足式。54计算机学院55计算机学院55替替换定义定义1.81.8用用 公式公式分别替换公式分别替换公式A A中中的不同的不同命题变元命题变元 得到的公式记为得到的公式记为 ，称为，称为A A的替换实例。的替换实例。替换产生新的公式替换产生新的公式= (r p)(r p) r (p/r p, q/r)55计算机学院56计算机学院56定理定理1.2 1.2 设设 是不同命题变元，是不同命题变元， 是公式。则对于每个真值赋值是公式。则对于每个真值赋值v v，其中真值赋值其中真值赋值v v =v=vpp1 1/v(B/v(B1 1),), p, pn n/v(B/v(Bn n)定义如下：定义如下：56计算机学院57计算机学院57证明：对证明：对A进行归纳。进行归纳。若若A是是pi，其中，其中1in，则，则 是是Bi，若若A A是除是除 之外的命题变元之外的命题变元p p，则，则 仍是仍是p p，(3)(3)若若A A是是0 0元联结词元联结词c c，则，则 仍是仍是c c，57计算机学院58计算机学院58(4)(4)设设A A1 1, ,A,Ak k是长度小于是长度小于m m的公式，并且的公式，并且若若A A是是F A A1 1, ,A,Ak k，其中，其中F是是k k元联结词，是元联结词，是长度等于长度等于m m的公式的公式, ,则是则是 58计算机学院59计算机学院59定理定理1.31.3设设A A是公式。是公式。若若A A是永真式，则是永真式，则A A的每个替换实例都是的每个替换实例都是永真式永真式。若若A A是永假式，则是永假式，则A A的每个替换实例都是的每个替换实例都是永假式永假式。证明证明任取永真式任取永真式A A的替换实例的替换实例 ，对于每，对于每个真值赋值个真值赋值v v，所以所以 是永真式。是永真式。可同样证明。可同样证明。证毕证毕59计算机学院60计算机学院60p ( q p)是永真式是永真式设设A,B是任意公式是任意公式p/A, q/BA= p q , B=(p r)( p q ) (p r) ( p q ) )是永真式是永真式60计算机学院61计算机学院611.3等等值演算演算 定义定义1.9 1.9 设设A,BA,B是公式，如果对于每个真值赋是公式，如果对于每个真值赋值值v v，v(A)=v(B)v(A)=v(B)，则称，则称A A和和B B等值，也称等值，也称A A与与B B逻辑等价，记为逻辑等价，记为A AB B。判断判断(pq)(pq)和和ppq q是否等值。是否等值。 pqp q (p q) p q p q000111101101001010010111000061计算机学院62计算机学院62等等值式模式式模式 零律零律A1A11 1 A0A00 0 幂等律幂等律AAAAA AAA AAA A 吸收律吸收律A(AB)A(AB)A A A(AB)A(AB)A A 同一律同一律A1A1A A A0A0A A A A0 0A A 双重否定双重否定A AA A矛盾律矛盾律AA A A0 0 排中律排中律AA A A1 1假言易位假言易位ABAB BB A A 62计算机学院63计算机学院63等等值式模式式模式 德德 摩根律摩根律 (AB)(AB) AA B B (AB)(AB) AA B B 交换律交换律ABABBABAABABBABAA AB BB BA A 63计算机学院64计算机学院64等等值式模式式模式结合律结合律(AB)C(AB)CA(BC)A(BC)(AB)C(AB)CA(BC)A(BC)(A(AB)B)C CA A(B(BC) C) 分配律分配律A(BC)A(BC)(AB)(AC) (AB)(AC) A(BC)A(BC)(AB)(AC)(AB)(AC)A(BA(BC)C)(AB)(AB)(AC) (AC) 64计算机学院65计算机学院65等等值式模式式模式A AA A0 0A A1 1A AABABABABA AB B(AB)(BA)(AB)(BA)A AB B( (AB)(AAB)(AB)B)A AB B(A(AB)B)65计算机学院66计算机学院66定理：设定理：设Q Q是合式公式，是合式公式，R R1 1是是Q Q的子公式，若的子公式，若R R1 1R R2 2，则，则Q Q R R1 1/R/R2 2QQ。 证明：证明：因为因为R R1 1R R2 2，所以，所以，v(Rv(R1 1)= v(R)= v(R2 2) ) 。首先选择一个不是公式首先选择一个不是公式Q Q中的命题变元中的命题变元p p。不。不妨设命题变元妨设命题变元p p取代公式取代公式Q Q中的一个中的一个R R1 1而得公式而得公式为为QQ。因此，有因此，有 p/R p/R1 1Q=QQ=Q， p/R p/R2 2Q= RQ= R1 1/R/R2 2QQ。66计算机学院67计算机学院67又因为又因为v v ( p/R ( p/R1 1 Q)= v(p/v(R Q)= v(p/v(R1 1)Q)Q)， v( p/Rv( p/R2 2Q)= v( Q)= v( p/v(Rp/v(R2 2)Q)Q)因此，有因此，有v( p/v(Rv( p/v(R1 1)Q)= v(p/v(R)Q)= v(p/v(R2 2)Q)Q)。有有v( p/Rv( p/R1 1Q)= v( p/RQ)= v( p/R2 2Q)Q)有有v(Q)= v( Rv(Q)= v( R1 1/R/R2 2Q)Q)。有有Q Q R R1 1/R/R2 2QQ。因此，若因此，若R R1 1R R2 2，有，有Q Q R R1 1/R/R2 2QQ67计算机学院68计算机学院68例例1.51.5证明证明p(qr)p(qr)pqrpqr证明：证明：p(qr)p(qr)p(p(qr) qr) ABABABAB( (ppq)r q)r 结合律结合律(pq)r (pq)r 摩根律摩根律pqr pqr ABABABAB68计算机学院69计算机学院69(pr) (q r) (p q) r(pr) (q r)( p r) ( q r) ABABABAB( p q ) p r q r r r 分配律分配律( p q ) p r q r r 同一律同一律( p q ) r 吸收律吸收律 (p q) r 摩根律摩根律 (p q) r ABABABAB69计算机学院70计算机学院70p(q r) (p q) (p r) p(q r) p (q r) AB AB p q r AB AB p q (p p ) r 排中排中律律 p q p q p r 分配分配律律 p q p r 吸收吸收律律 q p p r 交换交换律律 ( p q) p r 摩根律摩根律 (p q) (p r) AB AB(p q) (p r) AB AB70计算机学院71计算机学院71例例1.61.6用等值演算证明用等值演算证明p(qr)pqrp(qr)pqr是永真式。是永真式。p(qr)p(qr)pqrpqr (p(p(qr)pqr(qr)pqr ( (p(p(qr)(qr)(p(qr)p(qr) )pqrpqr (p(p(qr)(qr)( (p(qr)pqrp(qr)pqr( (pp(qr)(qr)(pp(qr)pqr(qr)pqr( (p(qr)p(qr)(p(pqqr r)pqr)pqr( (p p(qr)(qr)p pqr)(pqr)(pqqr rpqpqr r) )( (pppp(qr)qr)(p(qr)qr)(pq qppq qrrr r) )(1(qr)qr)(p(1(qr)qr)(pqpq1)qpq1) 11 11 1 171计算机学院72计算机学院721.4对偶定理偶定理(pq)rq)r (pq)rq)r (p0) 1 (p1)0定义定义1.101.10设设A A是由是由0,1,0,1,生成的公式，将生成的公式，将A A中的中的和和互换，互换，0 0和和1 1互换得到互换得到A A* *，称，称A A* *与与A A互为互为对偶式。对偶式。定义定义1.111.11如果真值赋值如果真值赋值v v1 1和和v v2 2满足对每个命题变元满足对每个命题变元p p， ， 则称则称v v1 1和和v v2 2是相反的。是相反的。(pq)rq)r互为对偶互为对偶(pq)rq)r (p0) 1互为对偶互为对偶 (p1)072计算机学院73计算机学院73(p(pq0)r1 v(p)=1,v(q)=0,v(r)=1q0)r1 v(p)=1,v(q)=0,v(r)=1(p(pq1)r0 v(p)=0,v(q)=1,v(r)=0q1)r0 v(p)=0,v(q)=1,v(r)=0v(pv(pq0)r1)q0)r1)=(v(p)=(v(p) v(v(q)v(0)v(r)v(1)q)v(0)v(r)v(1)=(1=(1 0 00)11=10)11=1v(pv(pq1)r0 )q1)r0 )= (v(p)= (v(p) v(v( q)v(1)v(r)v(0) q)v(1)v(r)v(0) = (0= (0 1 10)00=0= 0)00=0= 1 173计算机学院74计算机学院74对偶定理偶定理定理定理1.141.14设设A A是由是由0,1,0,1,生成的公式，生成的公式，A A* *与与A A互为对偶式，互为对偶式，v v和和vv是相反的真值赋值，是相反的真值赋值，则则v(Av(A* *)=)=v(A)v(A)。证明：证明：1.A1.A的的复杂度为复杂度为0 0，定理成立，定理成立若若A A为命题变元为命题变元p p，则则A A* *也为也为p p，v(p)=v(p)=v(p)v(p)。若若A A为为0 0，则，则A A* *为为1 1，v(1)=v(1)=v(0)v(0)。若若A A为为1 1，则，则A A* *为为0 0，v(0)=v(0)=v(1)v(1)。74计算机学院75计算机学院752.2.假设对于复杂度不超过假设对于复杂度不超过n n的每个公式的每个公式B B，v(Bv(B* *)=)=v v (B)(B)。3.3.证明复杂度等于证明复杂度等于n n，定理成立。，定理成立。(1)(1)若若A A为为B B，v(Bv(B* *)=)=v(B)v(B)，并且，并且A A* *为为B B* *。因此，因此，v(Av(A* *)=v()=v(B B* *)=)=v(Bv(B* *)=)=v(B)=v(B)=v(v(B)= B)= v(A)v(A)(2)(2)若若A A为为BCBC，v(Bv(B* *)=)=v(B)v(B)且且v(Cv(C* *)=)=v(C)v(C)，并且，并且A A* *为为B B* *CC* *。因此，因此，v(Av(A* *)=v(B)=v(B* *CC* *)=v(B)=v(B* *)v(C)v(C* *) )= =v(B)v(B)v(C)= v(v(C)= v(BBC)=v(C)=v(BC)(BC)= = v(BC) = v(BC) = v(A)v(A)75计算机学院76计算机学院76(3)(3)若若A A为为BCBC，v(Bv(B* *)=)=v(B)v(B)且且v(Cv(C* *)=)=v(C)v(C)，并且，并且A A* *为为B B* *CC* *。因此，因此，v(Av(A* *)=v(B)=v(B* *CC* *)=v(B)=v(B* *)v(C)v(C* *) )= =v(B)v(B)v(C)= v(C)= v(v(BBC)=v(C)=v(BC)= (BC)= v(BC)= v(BC)= v(A)v(A)76计算机学院77计算机学院77定理定理1.51.5（对偶定理）（对偶定理）设设A,BA,B是由是由0,1,0,1,生成的公式，生成的公式，A A* *与与A A互为对偶式，互为对偶式，B B* *与与B B互为对偶式。如果互为对偶式。如果A A B B，则，则A A* * B B* *。证明：证明：任取真值赋值任取真值赋值v v，令，令vv是与是与v v相反的真值赋相反的真值赋值，因为值，因为A AB B，所以，所以v(A)=v(B)v(A)=v(B)，因此，因此，v v(A(A* *)=)=v(A)= v(A)= v(B)=v(Bv(B)=v(B* *) )所以，所以，A A* * B B* *。证毕证毕77计算机学院78计算机学院78证明等值式：证明等值式：(1) (p q) ( p ( p q) p q(2) (p q) ( p ( p q) p q证明：等值式证明：等值式(1)(p q) ( p ( p q) (p q) ( p p q) (p q) p q p q证明：等值式证明：等值式(2)对偶定理对偶定理78计算机学院79计算机学院791.5联结词的完全集的完全集 pq=pq=p pq qp pq=(pq)q=(pq)(qp)=(qp)=(p pq)q)(p(pq)q)p pq=(pq=(pq)q) ( (p pq)q)结论：结论：，不是独立的不是独立的逻辑的最少联接词是什么？逻辑的最少联接词是什么？79计算机学院80计算机学院80完全集完全集定义定义1.121.12设设F是是n n元联结词，元联结词，p p1 1,p,p2 2, ,p,pn n是不同的是不同的命题变元。如果公式命题变元。如果公式A A中不出现除中不出现除p p1 1,p,p2 2, ,p,pn n之之外的命题变元，并且外的命题变元，并且A AFp p1 1,p,p2 2, ,p,pn n，则称，则称A A定定义义F。如果存在由联结词集合如果存在由联结词集合S S生成的公式来定义生成的公式来定义F，则，则称称F可由可由S S定义定义。如：。如：S=S=, , pq=pq=p pq qp pq=(pq)q=(pq)(qp)=(qp)=(p pq)q)(p(pq)q)p pq=(pq=(pq)q)( (p pq)q)80计算机学院81计算机学院81真真值表的启示表的启示(p/0,q/1), (p/1,q/0) F7 7= = p p q q p pq q(p/0,q/1) ,(p/1,q/1) F1111= = p p q q p p q q(p/0,q/1) , (p/1,q/0),(p/1,q/1) F1515= = p p q q p pq q p p q qpqF1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F1600010101010101010101001100110011001110000011110000111111000000001111111181计算机学院82计算机学院82完全集完全集定义定义1.131.13设设S S是联结词集合。如果每个是联结词集合。如果每个n(n0)n(n0)元元的联结词都可由的联结词都可由S S定义，则称定义，则称S S为为完全完全集集。82计算机学院83计算机学院83完全集定理完全集定理定理定理 , , 是完全集。是完全集。证明：证明：设设n0n0，F是是n n元联结词，元联结词，p p1 1,p,p2 2, ,p,pn n是不同命是不同命题变元，可以找出定义题变元，可以找出定义F的由的由 , , 生成的公式生成的公式A A。若若Fp p1 1p p2 2p pn n是永假式，取是永假式，取A A为为p p1 1 p p1 1。若若Fp p1 1p p2 2p pn n是可满足式，满足是可满足式，满足Fp p1 1p p2 2p pn n=1=1的真值赋的真值赋值为值为 ，则取，则取A A为为其中其中83计算机学院84计算机学院84完全集定理完全集定理任取真值赋值任取真值赋值v v，v(A)= 1v(A)= 1当且仅当有当且仅当有1in1in，使，使当且仅当有当且仅当有1in1in，使，使当且仅当有当且仅当有1in1in，使，使当且仅当有当且仅当有1in1in，使，使所以所以A AF p p1 1p p2 2p pn n ， , 是完全集。是完全集。证毕证毕 84计算机学院85计算机学院85定理定理如果完全集如果完全集S S1 1中的每个联结词都中的每个联结词都可由联结词集合可由联结词集合S S2 2定义，则定义，则S S2 2也是完全集。也是完全集。85计算机学院86计算机学院86极小完全集极小完全集定义定义 如果从完全集如果从完全集S S中去掉任何一个联结中去掉任何一个联结词就成为不完全的了，就称词就成为不完全的了，就称S S为为极小极小完全集完全集。86计算机学院87计算机学院87极小完全集定理极小完全集定理定理定理以下联结词集合是极小完全集。以下联结词集合是极小完全集。 , , ， , , ， , , 证明：证明：因为因为p pq q( (p pq)q)，所以，所以可由可由 , , 定义。定义。, , ,都可由都可由 , , 定义，并且定义，并且 , , , 是完全集，所以是完全集，所以 , , 也是完全集。也是完全集。87计算机学院88计算机学院88证明证明 , , 是极小完全集。是极小完全集。证明证明 不是完全集。不是完全集。任取任取由由生成的公式生成的公式A A，其中其中A A不出现除不出现除p p之之外的命题变元，外的命题变元，公式模式：公式模式： p pp pp p 令真值赋值令真值赋值v=(p/1)v=(p/1)，则，则v(A)=1v(A)=1，但，但v(v(p)=0p)=0，所以，所以A A不能定义不能定义。结论结论: :不能由不能由定义。定义。88计算机学院89计算机学院89再证明再证明 不是完全集。不是完全集。取取一元联结词一元联结词F使使F(0)=(0)=F(1)(1)。令真值赋值令真值赋值v v1 1=(p/1)=(p/1)和和v v2 2=(p/0)=(p/0)，任取由任取由 生成只出现命题变元生成只出现命题变元p p的公式的公式A A，公式公式: :p则则v v1 1(A)v(A)v2 2(A)(A)，而，而v v1 1( (Fp)=vp)=v2 2( (Fp)p)，所以，所以A A不能定义不能定义F。F不能由不能由 定义。定义。 不是完全集。不是完全集。89计算机学院90计算机学院90 , , 是完全集是完全集90计算机学院91计算机学院91因为因为p pq=q=( (p pq)=q)=(p(pq)q)，所，所以以可由可由 , , 定义。定义。, ,都可由都可由 , , 定义，并且定义，并且 , , 是是完全集，所以完全集，所以 , , 也是完全集。也是完全集。91计算机学院92计算机学院92证明证明 不是完全集。取真值赋值不是完全集。取真值赋值v=(p/1)v=(p/1)。任取由任取由 生成的仅出现命题变元生成的仅出现命题变元p p的公的公式式A A，v(A)=1v(A)=1，而，而v(v(p)=0p)=0，A A不能定义不能定义。所以所以不能由不能由 定义。定义。 不是完全集。不是完全集。 也不是完全集。也不是完全集。结论：结论： , , 是极小完全集。是极小完全集。92计算机学院93计算机学院93与非（与非（ ）、或非（）、或非（）p pq qpqpqpqpq0 00 01 11 10 01 11 10 01 10 01 10 01 11 10 00 0是完备集是完备集是完备集是完备集93计算机学院94计算机学院941.6范式范式 (pq) r=(pq) r=(p r) ( q r)=(p q r) (p q r) (p q r) ( p q r)结论：结论：公式唯一性？公式唯一性？等值公式有唯一的表示？等值公式有唯一的表示？判断公式等值判断公式等值范式比较范式比较94计算机学院95计算机学院95范式定范式定义定义定义 原子公式和原子公式的否定统原子公式和原子公式的否定统称为称为文字文字。如果一个文字恰为另一个文字的。如果一个文字恰为另一个文字的否定，则称它们为否定，则称它们为相反文字相反文字。文字文字: :p,相反文字相反文字: : p定义定义 设设n n是正整数，是正整数，A A1 1, ,A,An n都是都是文字文字，称，称A A1 1A An n为为简单析取式简单析取式，称，称A A1 1 A An n为为简单合取式简单合取式。(p q r)，(p q r) 95计算机学院96计算机学院96定义定义 设设n n是正整数。若是正整数。若B B1 1, ,B,Bn n都是都是简单合取式简单合取式，则称，则称B B1 1B Bn n为为析取范式析取范式。若。若B B1 1, ,B,Bn n都是简单析取式，则称都是简单析取式，则称B B1 1 B Bn n为为合取范式合取范式。简单合取式简单合取式的析取是的析取是析取范式析取范式, ,(p q r) (p q r) ( p q r)简单析取式简单析取式的和取是的和取是和取范式和取范式, ,(p q r) (p q r) (p q r) 96计算机学院97计算机学院97合取范式与析取范式合取范式与析取范式(p qr) p (p q) r) p (p q) r) p(p q) r p (p q p) ( r p) (p q) ( r p) 合取范式合取范式 p ( r p) q ( r p) p q r q p p (q r ) 析取范式析取范式 p (r r ) (q r ) p r p r (q r ) 不唯一不唯一97计算机学院98计算机学院98主析取范式主析取范式与主合取范式与主合取范式定义定义 设设n n是正整数，是正整数，p p1 1, ,p,pn n是不同的命题变元。若对于每个是不同的命题变元。若对于每个i i，A Ai i是是p pi i或或p pi i，则称，则称A A1 1 A An n为关于为关于p p1 1, ,p,pn n极大项极大项，A A1 1A An n为关于为关于p p1 1, ,p,pn n的的极小项极小项。98计算机学院99计算机学院99定义定义 设设m m是自然数。是自然数。若若B B1 1, ,B,Bm m是关于是关于p p1 1, ,p,pn n的不同极小项，的不同极小项，则称则称B B1 1B Bn n为关于为关于p p1 1, ,p,pn n的的主析取范式主析取范式。若若B B1 1, ,B,Bm m是关于是关于p p1 1, ,p,pn n的不同极大项，的不同极大项，则称则称B B1 1B Bn n为关于为关于p p1 1, ,p,pn n的的主合取范式主合取范式。主析取范式和主合取范式统称为主析取范式和主合取范式统称为主范式主范式。99计算机学院100计算机学院100定义定义 设公式设公式A A中出现的命题变元中出现的命题变元为为p p1 1,p,p2 2, ,p,pn n， B B是关于是关于p p1 1,p,p2 2, ,p,pn n的主析取范式（主合的主析取范式（主合取范式），并且取范式），并且A AB B，则称则称B B为为A A的主析取范式（主合取范式）。的主析取范式（主合取范式）。100计算机学院101计算机学院101主范式主范式变换步步骤联接词等值变换联接词等值变换（1 1）消去联接词）消去联接词、 将公式由将公式由、 表示表示A AB B ABABA AB B (A(AB)(BB)(BA)A)A A B B ( ( AB)(AAB)(A B)B)德德. .摩根律摩根律（2 2）应用）应用德德. .摩根律摩根律 内移或消去内移或消去约束公式的约束公式的 变换为变换为约束变元约束变元(AB) (AB) AAB B (AB) (AB) AAB B101计算机学院102计算机学院102主范式主范式变换步步骤分配律分配律（3 3）应用分配律求取合取范式或析取范式）应用分配律求取合取范式或析取范式A(BC) A(BC) (AB)(AC) (AB)(AC) A(BC) A(BC) (AB)(AC)(AB)(AC)矛盾律与排中律矛盾律与排中律（4 4）应用矛盾律与排中律求主合取范式或主析）应用矛盾律与排中律求主合取范式或主析取范式取范式AA A A 0 A0 A A A 1 1交换律交换律（5 5）应用交换律变元位置排序）应用交换律变元位置排序AB AB BA AB BA AB BABA102计算机学院103计算机学院103主合取范式主合取范式( pr)(qp) ( pr)(qp)(pq)(pr)( qp)( pq)(prq q)( qpr r)( pqr r)(prq)(pr q)( qpr) ( qp r)( pqr)( pq r)(pqr)(p qr)(p qr) (p q r)( pqr)( pq r)103计算机学院104计算机学院104主析取范式主析取范式(p q) ( p q) p q( p q) ( p q) p q ( p q) ( p q) p q ( p q) ( p q) p q p q p q p q p qp (q q) q p q p q p q p q q p q p q p q p q (p p) q p q p q p q p q p q p q p q p q p q p q p q104计算机学院105计算机学院105定理：定理：任何公式等值于某一析取范式任何公式等值于某一析取范式任何公式等值于某一合取范式任何公式等值于某一合取范式每一公式有唯一的主析取范式每一公式有唯一的主析取范式每一公式有唯一的主合取范式每一公式有唯一的主合取范式105计算机学院106计算机学院106定理定理设在公式设在公式A A中出现中出现n n个命题变个命题变元，以下条件是等价的。元，以下条件是等价的。AA是是永真式永真式。AA的主析取范式中包含了所有的极小的主析取范式中包含了所有的极小项，即它是项，即它是2 2n n个极小项的析取个极小项的析取。AA的主合取范式中不包含任何极大项，的主合取范式中不包含任何极大项，即它是即它是个极大项的合取个极大项的合取，也就是。，也就是。106计算机学院107计算机学院107定理定理设在公式设在公式A A中出现中出现n n个命题个命题变元，则以下条件是等价的。变元，则以下条件是等价的。AA是永假式。是永假式。AA的主合取范式中包含了所有的极大的主合取范式中包含了所有的极大项，即它是项，即它是2 2n n个极大项的合取个极大项的合取。AA的主析取范式中不包含任何极小项，的主析取范式中不包含任何极小项，即它是个极小项的析取，也就是。即它是个极小项的析取，也就是。107计算机学院108计算机学院108逻辑门108计算机学院109计算机学院109数字数字逻辑与数字部件与数字部件设计译码器、寄存器、加法器、移位器、译码器、寄存器、加法器、移位器、控制器、多路选择器、计数器、比控制器、多路选择器、计数器、比较器较器109计算机学院110计算机学院110译码器器 (2输入入4输出出译码器器)Y0=BAY1=BAY2=BAY3=BABAY3Y2Y1Y0B BA AY Y3 3Y Y2 2Y Y1 1Y Y0 00 00 01 10 00 00 00 01 10 01 10 00 01 10 00 00 01 10 01 11 10 00 00 01 1110计算机学院111计算机学院1111.7逻辑推推论从三段从三段论看看ABAABB00010010111010011111公式取值，公式取值，v(A)=?v(A)=?任意赋值函数为真任意赋值函数为真任意赋值函数为假任意赋值函数为假有的赋值函数为真，有的赋值函数为假有的赋值函数为真，有的赋值函数为假可满足的公式之间的关系？可满足的公式之间的关系？当当v(v(AB)=1, V()=1, V(A)=1, v()=1, v(B)=)=?111计算机学院112计算机学院1121.7逻辑推推论从从传递律看律看A AB BC CA ABB BCA AC0 00 00 01 11 11 10 00 01 11 11 11 10 01 10 01 10 01 10 01 11 11 11 11 11 10 00 00 01 10 01 10 01 10 01 11 11 11 10 01 10 00 01 11 11 11 11 11 1当当V(AV(AB)=1,v(B)=1,v(BC)=1, v(A)=1, v(AC)=)=?112计算机学院113计算机学院1131.7逻辑推推论=A=A1 1, ,A,An n 定义定义 若真值赋值若真值赋值v v满足公式集合满足公式集合中的每个公式，中的每个公式，则称则称v v满足满足。若有真值赋值满足。若有真值赋值满足，则称，则称是可满足是可满足的的，否则称，否则称是不可满足的是不可满足的。V(AV(A1 1)=1,)=1, V(An)=1, V(An)=1定义定义 设设是公式的集合，是公式的集合，A A是公式。如果每个满是公式。如果每个满足足的真值赋值都满足的真值赋值都满足A A，则称，则称A A是是的的逻辑推论逻辑推论， 记记为为 A A。若。若 A A不成立，记为不成立，记为 A A。如果如果V()= 1V()= 1，则，则v(A)=1v(A)=1只要前提真，结论就一定真只要前提真，结论就一定真真值表的含义真值表的含义若若=A=A1 1, ,A,An n ，则将，则将简记为简记为A A1 1, ,A,An n A A。113计算机学院114计算机学院114推理形式推理形式每一推理形式都相当于一个真值形式。每一推理形式都相当于一个真值形式。正确的推理形式相当于一个重言式。正确的推理形式相当于一个重言式。错误的推理形式虽然也有一个相当的真值形式，但不错误的推理形式虽然也有一个相当的真值形式，但不是重言式。是重言式。判别一推理形式是否正确，就是要判别其相当的蕴涵判别一推理形式是否正确，就是要判别其相当的蕴涵式是不是一个重言式。式是不是一个重言式。正确推理形式正确推理形式(pq)p)q错误推理形式错误推理形式(pq)p)q114计算机学院115计算机学院115三段三段论证明明例例1.14 证明证明A, AB B证明：证明：若真值赋值若真值赋值v使使v(A)=1， v(AB)=1， v(A)v(B)=1, 则则v(B)=1。所以所以A, AB B115计算机学院116计算机学院116传递律律证明明例例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)=1 v(B)v(C)=1，所以，所以v(C)=1，因此，因此，v(A)v(C)=1因此，因此，AB, B C A C116计算机学院117计算机学院117例例1.16 AB1.16 AB，CDCD，A AC BC BD D。证明：证明：设真值赋值设真值赋值v v使使v(AB)=v(CD)=v(Av(AB)=v(CD)=v(AC)=1,C)=1,则则v(A)=1v(A)=1或或v(C)=1v(C)=1。若若v(A)=1v(A)=1，则由，则由v(AB)=1v(AB)=1得出得出v(B)=1v(B)=1。若若v(C)=1v(C)=1，则由，则由v(CD)=1v(CD)=1得出得出v(D)=1v(D)=1。无论哪种情况皆有无论哪种情况皆有v(Bv(BD)=1D)=1。117计算机学院118计算机学院118例例11.17 pq pq11.17 pq pqr r。证明：证明：需要找出一个真值赋值需要找出一个真值赋值v v使使v(pq)=1v(pq)=1且且v(pqv(pqr)=0r)=0。这样的这样的v v使使v(p)=v(q)=1v(p)=v(q)=1，v(qv(qr)=0r)=0。所。所以，只要取真值赋值以，只要取真值赋值v=(p/1,q/1,r/1)v=(p/1,q/1,r/1)就就能满足上述要求。能满足上述要求。118计算机学院119计算机学院119定理定理 设设A A是公式，则是公式，则 A A当且仅当且仅当当A A是永真式。是永真式。证明证明 充分性：充分性：设设 A A，任取真值赋值，任取真值赋值v v，因为，因为v(A)=1v(A)=1。因此，。因此，A A是永真式。是永真式。必要性：必要性：设设A A是永真式，显然是永真式，显然 A A。证毕证毕119计算机学院120计算机学院120定理定理 设设A A1 1, ,A,An n，B B是公式，是公式，A A1 1, ,A,An n B B，当且，当且仅当仅当A A1 1 A An nBB是永真式。是永真式。证明证明充分性：充分性：设设A A1 1, ,A,An n B B。 A A1 1 A An n B B任取真值赋值任取真值赋值v v。因为因为v(Av(A1 1)=)=v(A=v(An n)=1)=1 所以所以v(Av(A1 1A An n)=1)=1， 又因为又因为v(B)=1v(B)=1。所以。所以 v(Av(A1 1A An n)v(B)=v(A)v(B)=v(A1 1A An nB)=1B)=1。 因此因此A A1 1A An nBB是永真式。是永真式。必要性：必要性：设设A A1 1 A An nBB是永真式，任取真值赋值是永真式，任取真值赋值v v，若，若v v(A(A1 1A An n)=1)=1，则，则v(Av(A1 1)=)=v(A=v(An n)=1)=1，故，故v(B)=1v(B)=1所以所以A A1 1, ,A,An n B B120计算机学院121计算机学院121定理定理 设设A A，B B是公式。是公式。A AB B当且仅当当且仅当 A A B B且且B AB A。证明证明A AB B当且仅当当且仅当 A AB B是永真式是永真式当且仅当当且仅当 A AB B和和B BA A都是永真式都是永真式当且仅当当且仅当 A BA B且且B AB A证毕证毕121计算机学院122计算机学院122定理定理 设设是公式的集合，是公式的集合，A A和和B B是公式，则是公式，则AA B B当且仅当当且仅当 A AB B。证明证明 证明证明A BA B当且仅当当且仅当 A AB B。若若A BA B，则有真值赋值，则有真值赋值v v使使中中公式皆真公式皆真且且v(A)=1v(A)=1，而，而v(B)=0v(B)=0。所以。所以v(AB)=0v(AB)=0， A AB B。若若 A AB B，则有真值赋值，则有真值赋值v v使使中中公式皆真且公式皆真且v(Av(AB)=0B)=0，则，则v(A)=1v(A)=1且且v(B)=0v(B)=0。所以。所以A A B B。证毕证毕122计算机学院123计算机学院123定理定理 设设是公式的集合，是公式的集合，A A和和B B是公式，则是公式，则AA B B当且仅当当且仅当 A AB B。证明证明 若若A BA B，则有真值赋值，则有真值赋值v v使使中中公式皆真公式皆真且且v(A)=1v(A)=1，v(B)=1v(B)=1。所以。所以v(AB)=1v(AB)=1， A AB B。若若 A AB B，则有真值赋值，则有真值赋值v v使使中中公式皆真且公式皆真且v(Av(AB)=1B)=1。又如果又如果v(A)=1v(A)=1，则，则v(B)=1v(B)=1。所以。所以A BA B。证毕证毕123计算机学院124计算机学院124定理定理 设设n n是正整数。公式集是正整数。公式集AA1 1, ,A,An n 是可满足的当且仅当是可满足的当且仅当A A1 1A An n是可满足式。是可满足式。证明：证明：v(Av(A1 1A An n)=v(A)=v(A1 1) )v(Av(An n) )v(Av(A1 1)=)= v(A= v(An n)=1)=1当且仅当当且仅当v(Av(A1 1A An n)=1)=1124计算机学院125计算机学院125定理定理 设设是公式集合。是公式集合。是不可满足的当是不可满足的当且仅当且仅当每个公式每个公式都是都是的逻辑推论。的逻辑推论。证明证明 充分性：充分性：设设是不可满足的，是不可满足的，A A为任意公式，则显为任意公式，则显然每个满足然每个满足的真值赋值使的真值赋值使A A为真，因为满足为真，因为满足的的真值赋值根本不存在。故真值赋值根本不存在。故 A A。必要性：必要性：设每个公式都是设每个公式都是的逻辑推论，则的逻辑推论，则 0 0。若有真值赋值。若有真值赋值v v满足满足，则，则v(0)=1v(0)=1，这是不可能，这是不可能的。所以，的。所以，不可满足。不可满足。证毕证毕125126