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

《数理逻辑-命题逻辑ppt课件.ppt》由会员分享，可在线阅读，更多相关《数理逻辑-命题逻辑ppt课件.ppt（126页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、命题逻辑马殿富马殿富北航计算机学院北航计算机学院202010-910-9计算机学院2计算机学院2集合论集合论 定义：定义：一些对象聚集为一个整体，称为一些对象聚集为一个整体，称为集合集合。这些。这些对象称为集合的对象称为集合的元素元素。 元素与集合的关系元素与集合的关系 a a是集合是集合S S的元素，记为的元素，记为a aS a a不是集合不是集合S S的元素，记为的元素，记为a aS 集合的表示法集合的表示法 空集：空集： 有穷集合：枚举法，有穷集合：枚举法，S=xS=x1 1,x ,x2 2, ,x ,xn n 无穷集合：描述法无穷集合：描述法x|xx|x是自然数是自然数 计算机学院3计

2、算机学院3集合外延、内涵集合外延、内涵 外延原则与概括原则外延原则与概括原则 外延原则：一个集合由它的元素唯一地确定。外延原则：一个集合由它的元素唯一地确定。 概括原则：每一性质概括原则：每一性质( (或谓词或谓词) )产生一个集合。产生一个集合。 集合外延集合外延 集合所包含的元素全体。集合所包含的元素全体。 集合内涵集合内涵 集合元素所共有的性质。集合元素所共有的性质。 非负偶数集合非负偶数集合 外延外延0,2,4,0,2,4, , 内涵内涵x|xx|x是被是被2 2整除的自然数整除的自然数 计算机学院4计算机学院4集合的关系集合的关系 集合的关系集合的关系 包含关系：包含关系：如果集合如

3、果集合A A的元素都是集合的元素都是集合B B的元素，则称的元素，则称A A为为B B的子集，记为的子集，记为A AB 真包含关系：真包含关系：A AB 不包含关系不包含关系:A:AB 等关系：等关系：如果集合如果集合A A和集合和集合B B包含相同元素，则称包含相同元素，则称A A和和B B相等，记为相等，记为A=BA=B计算机学院5计算机学院5函数函数 A An n=A=AA AA A A An n=(x=(x1 1,x ,x2 2, ,x ,xn n)|x)|xi iAA A=0, 1A=0, 1 A A3 3 =0, 1=0, 13 3=(0,0,0),(0,0,1),(0,1,0),

4、(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(x

5、1 1,x ,x2 2, ,x ,xn n) )为为A A上的上的n n元运算。元运算。 f f：A AA AA AA A计算机学院6计算机学院6归纳定义归纳定义归纳定义归纳定义自然数集合：自然数集合：n n是是n n的后继（函数），的后继（函数），N N是满足以下是满足以下条件的条件的S S中的最小集合中的最小集合 0 0S S对于任何对于任何n n，如果，如果n nS S，则，则nS S。计算机学院7计算机学院7归纳证明归纳证明 归纳证明归纳证明 设设R R是一个性质，是一个性质，R(x)R(x)表示表示x x有有R R性质。性质。 定理证明定理证明归纳基础归纳基础 R(0)R(0)归纳假

6、设归纳假设 对于任何对于任何k kN,R(k);N,R(k);证明证明 R(kR(k); );归纳结论归纳结论 对于任何对于任何n nN，R(n)。排序概念排序概念计算机学院8计算机学院8数理逻辑基本概念数理逻辑基本概念真真可证性可证性计算机学院9计算机学院9数理逻辑数理逻辑 数理逻辑是用数学语言表述的推理形式有效性的学问。数理逻辑是用数学语言表述的推理形式有效性的学问。 命题逻辑、谓词逻辑命题逻辑、谓词逻辑 数理逻辑使用特制的表意符号，亦称为符号逻辑。数理逻辑使用特制的表意符号，亦称为符号逻辑。 逻辑研究对象逻辑研究对象逻辑真值逻辑真值 真，表示为真，表示为T T或或1 1 假，表示为假，表

7、示为F F或或0 0 正确的推理正确的推理形式形式 正确前提正确前提 正确的推理形式正确的推理形式 必然得出正确的结论必然得出正确的结论计算机学院10计算机学院101.11.1命题和联结词命题和联结词 什么是命题？什么是命题？命题的运算符是什么？命题的运算符是什么？如何表示命题？如何表示命题？有多少种命题的运算符？有多少种命题的运算符？计算机学院11计算机学院11语句表达语句表达陈述句陈述句疑问句疑问句祈使句祈使句感叹句感叹句 雪是白的。雪是白的。 2 2是奇数。是奇数。 X+Y5X+Y5。 你是谁？你是谁？ 我正在说谎。我正在说谎。 北京是中国的首都。北京是中国的首都。 前进！前进！ 天空多

8、漂亮天空多漂亮! !特点：有的语句可以特点：有的语句可以判断真假。判断真假。计算机学院12计算机学院12自然语言、命题自然语言、命题语言是人们思维和交际的工具，也是一种语言是人们思维和交际的工具，也是一种表达观念的符号系统。表达观念的符号系统。自然语言由各种句式组成，如陈述句、疑自然语言由各种句式组成，如陈述句、疑问句、感叹句、祈使句等等。问句、感叹句、祈使句等等。陈述句是陈述一个事实或者说话人的看法，陈述句是陈述一个事实或者说话人的看法，它包括肯定句和否定句两种。一般来说，它包括肯定句和否定句两种。一般来说，仅有陈述句能够确定句子的意义是真还是仅有陈述句能够确定句子的意义是真还是假。假。命题

9、表达为具有命题表达为具有确定真假意义确定真假意义的的陈述句陈述句。计算机学院13计算机学院13命题示例命题示例 雪是白的。雪是白的。 2 2是奇数。是奇数。 X+Y5X+Y5。 你是谁？你是谁？ 我正在说谎。我正在说谎。 北京是中国的首都。北京是中国的首都。 每个不小于每个不小于6 6的偶数都是两个的偶数都是两个奇素数之和（歌德巴赫猜想）奇素数之和（歌德巴赫猜想） 2121世纪有人住在月球上。世纪有人住在月球上。 他很高。他很高。 一个自然数不是合数就是素数一个自然数不是合数就是素数 命题，真命题，真 命题，假命题，假 不确定，非命题不确定，非命题 疑问句，非命题疑问句，非命题 悖论，非命题悖

10、论，非命题 命题，真命题，真 命题，真，有唯一真假值。命题，真，有唯一真假值。 命题，真，有唯一真假值。命题，真，有唯一真假值。 无法确定，非命题无法确定，非命题 命题，假，命题，假，1 1不是合数和素数不是合数和素数计算机学院14计算机学院14简单命题与复合命题简单命题与复合命题 简单命题简单命题 由简单陈述句表述的命由简单陈述句表述的命题称为简单命题。题称为简单命题。 命题逻辑不再进一步分命题逻辑不再进一步分析简单命题的内部结构析简单命题的内部结构p: p:孔子是圣人孔子是圣人语句联接词语句联接词并且并且或或否定否定如果如果, ,则则。当且仅当当且仅当既不既不，也，也不不。 复合命题复合命

11、题 用联接词可以将若干个用联接词可以将若干个简单句组合成复合句。简单句组合成复合句。 子命题子命题计算机学院15计算机学院15命题逻辑如何运算？命题逻辑如何运算？ 数计算启示数计算启示自然数自然数运算：运算：+ +、* *整数整数运算：运算：+ +、- -、* *有理数有理数运算：运算：+ +、- -、* *、/ / 命题逻辑命题小写字母表示真1，假0运算：？计算机学院16计算机学院16命题的抽象表示命题的抽象表示 自然语言具有自然语言具有二义性二义性 命题逻辑不关注语句的内容，也不关注语句为何是命题逻辑不关注语句的内容，也不关注语句为何是真或为假，而是仅仅关注语句能够为真或假。真或为假，而是

12、仅仅关注语句能够为真或假。 命题的命题的抽象抽象 用小写字母表示命题，取值为用小写字母表示命题，取值为0,10,1。 命题命题真值真值 陈述句的意义为真，称为陈述句的意义为真，称为真命题真命题，真值为，真值为1 1。 陈述句的意义为假，称为陈述句的意义为假，称为假命题假命题，真值为，真值为0 0。 命题逻辑的研究对象命题逻辑的研究对象命题。命题。 数理逻辑从数理逻辑从形式结构形式结构方面研究命题。方面研究命题。计算机学院17计算机学院17逻辑联结词逻辑联结词 定义定义 0 0和和1 1称为称为0 0元函数。设元函数。设n0,n0,称为称为0,10,1n n到到0,10,1的函数为的函数为n n

13、元函数，真值函数也称为元函数，真值函数也称为联结词联结词。 命题的操作符（联结词）命题的操作符（联结词） 非非 与与 或或 如果如果, ,则则。 当且仅当当且仅当 异或异或 真值真值表表 真值形式可以用图真值形式可以用图表来说明。这种表表来说明。这种表称为称为真值真值图表。图表。0 0元函数元函数 0 0，1 11 1元函数元函数 2 2元函数元函数 、 、 、 计算机学院18计算机学院18逻辑联结词逻辑联结词 0110pp 命题p的否定记为p,读作非p真值表真值表 逻辑联接词的含义 自然语言中，并非的含义计算机学院19计算机学院19逻辑联结词逻辑联结词 111001010000qpqp真值表

14、 pq称为p和q的合取 读作p且q 逻辑联接词的含义 自然语言中，并且的含义计算机学院20计算机学院20逻辑联结词逻辑联结词 111101110000qpqp真值表 pq称为p和q的析取，读作p或q 逻辑联接词的含义 自然语言中，或的含义计算机学院21计算机学院21逻辑联结词逻辑联结词 111001110100qpqp真值表 逻辑联接词的含义 自然语言中，如果,则.的含义 pq称为p蕴涵q 读作p则q p称为前件 q称为后件计算机学院22计算机学院22逻辑联结词逻辑联结词 111001010100qpqp真值表 p q称为p与q等值，读作p当且仅当q, p与q互蕴含。 pq=(pq)(qp)

15、逻辑联接词的含义 自然语言中，当且仅当的含义计算机学院23计算机学院23逻辑联结词逻辑联结词 北航在海淀区或北航在西城区。 比较 李明学习英语或学习法语011101110000qpqp真值表 p q称为p与q异或，读作p异或q。 pq= (pq)(qp)计算机学院24计算机学院24逻辑域、逻辑运算逻辑域、逻辑运算逻辑域逻辑域 00，11 运算运算 ， ， ， 定义域定义域 0, 10, 1 值域值域 0,10,1计算机学院25计算机学院25命题逻辑运算符数目命题逻辑运算符数目 运算符变量数为运算符变量数为1 1个变量，个变量，2 2个变量，个变量，,n ,n个变量的运算符数目个变量的运算符数目

16、pF1F2F3F40001110101pqpqpqpqpqpq0000110010110110010011111110计算机学院26计算机学院26命题逻辑函数数目命题逻辑函数数目 变量数为变量数为n n 变量组合数变量组合数 运算符数运算符数 pqF1F2F3F4F5F6F7F8F9F10F11F12F13F14F15F16000101010101010101010011001100110011100000111100001111110000000011111111n2n22 Fi(p,q)=？计算机学院27计算机学院27命题形式结构命题形式结构 复合命题复合命题是命题及真值联结词构成的形式是

17、命题及真值联结词构成的形式结构结构 六个真假形式最基本的，或最简单的形式，称六个真假形式最基本的，或最简单的形式，称为为简单命题简单命题。 由这六个真假形式，经过各种各种的互相组合，由这六个真假形式，经过各种各种的互相组合，还可以变成更多的各种复杂真值形式。还可以变成更多的各种复杂真值形式。 真值形式数量无穷无尽。真值形式数量无穷无尽。 示例示例 并非并非p p并且并且q q。(p(pq q) ) 如果非如果非p p，那么非，那么非q q。 p p q q 如果如果p p或或q, q,那么那么r r。p pq qr r计算机学院28计算机学院28命题命题形式结构形式结构 例例1 1： 如果如果

18、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) A B计算机学院29计算机学院29命题命题形式结构形式结构 例例1 1： 角角A A和角和角B B或相等或互补。或相等或互补。 角角A A与角与角B B不相等不相等 所以角所以角A A与角与角B

19、 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) A B计算机学院30计算机学院301.21.2公式和真值赋值公式和真值赋值 合式公式合式公式 真值表计算真值表计算 语义语义 可满足性可满足性计算机学院31计算机学院31合式公式合式公式 命题逻辑中命题逻辑中 0 0和和1 1是常元。是常元。 变元是命题变元，其值取为真值。变元是命题变

20、元，其值取为真值。 用小写英文字母用小写英文字母p p，q q，r r，s s，t t等表示命题等表示命题变元。变元。 定义：命题变元称为定义：命题变元称为原子公式原子公式。计算机学院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

21、).(4).只有有限次应用只有有限次应用(1)(1)(3)(3)构成的公式是合构成的公式是合式公式。式公式。计算机学院33计算机学院33 合式公式是命题逻辑的语法概念，它仅仅是合式公式是命题逻辑的语法概念，它仅仅是符合语法结构的公式，是一个没有任何意义符合语法结构的公式，是一个没有任何意义的符号串。的符号串。 0 0和和1 1是符号，没有表示逻辑真值的意思；是符号，没有表示逻辑真值的意思； 、 、 、和和 是逻辑运算符号，是逻辑运算符号，也没有表示逻辑运算的意思；也没有表示逻辑运算的意思； 命题变元也是符号。命题变元也是符号。 由于合式公式的定义具有抽象性和严格性，由于合式公式的定义具有抽象性

22、和严格性，人们对于一个合式公式的理解是相同的，不人们对于一个合式公式的理解是相同的，不会产生二义性。会产生二义性。计算机学院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是由

23、是由S S生成的公式。生成的公式。 上面采用了上面采用了前缀记法前缀记法 即把联结词写在运算对象的前面即把联结词写在运算对象的前面 如如pqpq。采用前缀记法不需要用括号也不会引起。采用前缀记法不需要用括号也不会引起歧义。歧义。 计算机学院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 ) )是是合式合式公式

24、公式 (p 0) (q 1)是合是合式式公式公式 0,1合式合式公式公式 p, q是是合式合式公式公式 (p 0)， (q 1)是是合式合式公式公式 (p 0) (q 1)是是合式合式公式公式计算机学院36计算机学院36命题逻辑语言命题逻辑语言 定义：所有的命题合式公式集合构成了定义：所有的命题合式公式集合构成了命题逻辑语言，记为命题逻辑语言，记为L L 。 一般来说，命题逻辑语言一般来说，命题逻辑语言L L 是无穷集合是无穷集合，也就是说合式公式有无穷多个。，也就是说合式公式有无穷多个。计算机学院37计算机学院37公式复杂度公式复杂度 公式公式A A的复杂度表示为的复杂度表示为FC(A)FC

25、(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。计算机学院38计算机学院38联结词的优先级联结词的优先级 联结词的优先级联结词的优先级 从高到低的顺序排列为：从高到低的顺序排列为：、 、 同一个联结词连续多次出现且无括号，同一个联结词连续多次出现且无括

26、号，则按从左至右的顺序运算则按从左至右的顺序运算 在满足运算次序不变的情况下，运用联在满足运算次序不变的情况下，运用联结词的优先级规则可以结词的优先级规则可以减少合适公式括减少合适公式括号号。计算机学院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) qr计算机学院40计算机学院40真值表计算真值表计算 命题逻辑语言命题逻辑语言L L的合式公式仅仅是一个的合式公式仅仅是一个符号串。符号串。 对于一个合式公式，我们关注点之一对于一个合式公式，我们关注

27、点之一是它在什么情况下为真？在什么情况是它在什么情况下为真？在什么情况下为假？即一个合式公式的逻辑真值下为假？即一个合式公式的逻辑真值是什么？。是什么？。 一个合式公式与逻辑真值之间的对应一个合式公式与逻辑真值之间的对应关系。关系。计算机学院41计算机学院41真值表计算真值表计算 (p q q) ( ( p q q ) ) pqp q(pq)pq pq(pq)pq00011111010110111001011111100001 (pq) (pq) p q pq (pq) (pq ) 求一个公式值，一个公式与另一个公式求一个公式值，一个公式与另一个公式是否是否等值等值等等等等 真值表的方法不适应

28、对命题演算进行整真值表的方法不适应对命题演算进行整体的讨论或探究命题之间的逻辑关系。体的讨论或探究命题之间的逻辑关系。真值表优缺点真值表优缺点 容易、直观容易、直观 多变量及公式复杂难易操作多变量及公式复杂难易操作计算机学院42计算机学院42命题合式公式语义命题合式公式语义 语义：研究公式与所指称对象的关系。语义：研究公式与所指称对象的关系。 论域：研究对象的集合。论域：研究对象的集合。 解释解释 用论域的对象、对象的运算对应形式系统的抽象用论域的对象、对象的运算对应形式系统的抽象符号。符号。 结构结构 论域和解释称为形式系统的结构。论域和解释称为形式系统的结构。 语义语义 结构连同该结构下公

29、式所取真值的规定称为语义。结构连同该结构下公式所取真值的规定称为语义。 数理逻辑的语义研究合式公式与真值的关系。数理逻辑的语义研究合式公式与真值的关系。计算机学院43计算机学院43常元和运算符语义常元和运算符语义 合式公式的常元合式公式的常元0 0和和1 1的语义分别对应逻的语义分别对应逻辑真值辑真值0 0和和1 1； 合式公式中的合式公式中的 、 、 、或或 等等逻辑运算符的语义分别是逻辑真值集合逻辑运算符的语义分别是逻辑真值集合上的上的 、 、 、或或 运算等。运算等。 合式公式的语义是逻辑真值。合式公式的语义是逻辑真值。计算机学院44计算机学院44真值赋值函数真值赋值函数 定义定义1.6

30、1.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 nF计算机学院45计算机学院45合式公式语义合式公式语义 设设S S是联结词的集合是是联结词的集合是 ， ， ， ， 。由由S S生生成的合式公式成的

31、合式公式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 1A A2 2，则，则v(A)=v(Av(A)=v(A1 1) )v(Av(A2

32、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) )计算机学院46计算机学院46真值赋值真值赋值 由由S S生成的公式生成的公式A A在真值赋值在真值赋值v v下的真值下的真值v(A)v(A)定义如下：定义如下： 若若A A是是S S中的中的0 0元联结词元联结词c c，则，则v(A)=cv(A

33、)=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) )。计算机学院47计算机学院47语义方法的计算语义方法的计算 p p(q (qr) r) 真值赋值函数：真值赋值函数： v(p)=1, v(q)=1, v(r)=0 v(p p(q (qr) r) =v(p) v v(q (qr) r) =v(p) (

34、 (v v(q)(q)v( v(r)r) =1(1 (10) 0) = =10 0 =0=0 p p(q(qr)r) 真值赋值函数：真值赋值函数： v(p)=0, v(q)=1, v(r)=0 v(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=1计算机学院48计算机学院48简化计算简化计算 (p(p q) q) p pq q v(p)=0或或v(q)=0 v( (p(p q) q) p pq q) = (v(p)(v(p) v( v(q)q) v( v(p)p)v( v(q) q)

35、= (v(p)(v(p) v( v(q)q)1 1 1 1计算机学院49计算机学院49简化计算（续）简化计算（续） v(p)=1并且v(q)=1 v(pq)pq) = (v(p)v(q)v(p)v(q) = 100 1计算机学院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是命

36、题变元或是命题变元或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)。21vvpp21vvpp计算机学院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元元联结词

37、，则联结词，则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 ,n v1 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 ) 证毕证毕计算机学院52计算机学院52定理定理1.11.1的涵义的涵义 若公式若公式

38、A A中出现的命题变元为中出现的命题变元为p p1 1, ,p ,pn n，v v是真是真值赋值，则值赋值，则v(A)v(A)只与只与 有关。有关。 用用 表示满足表示满足 的真值赋值的真值赋值v v 例例1 1 设公式设公式A A为为p p0q0q1, 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 vnvpp ,.,1)/,./(11nnapapnvnvapap,.,11vkp计算机学院53计算机学院53 如果对公式中出现的每个命题变元都指派了确定的如果对公式中出现的每个命题

39、变元都指派了确定的真值，则该公式的真值也就唯一确定了。因此，可真值，则该公式的真值也就唯一确定了。因此，可将公式看做真值函数。将公式看做真值函数。 (pq) pq v(p)=0,v(q)=0 v(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计算机学院54计算机学院54可满足式可满足式 定义定义1.7 1.7 设设A A是公式。是公式。 如果真值赋值如果真值赋值v v使得使得v(A)=1v(A)=1，则

40、称，则称v v满足满足A A。 如果每个真值赋值都满足如果每个真值赋值都满足A A，则称，则称A A为为永真式永真式，也称为也称为重言式重言式。 如果每个真值赋值都不满足如果每个真值赋值都不满足A A，则称，则称A A为为永假永假式式，也称为，也称为矛盾式矛盾式，不可满足式不可满足式。 如果至少有一个真值赋值满足如果至少有一个真值赋值满足A A，则称，则称A A为为可可满足式满足式。计算机学院55计算机学院55替换替换 定义定义1.81.8用用 公式公式分别替换公式分别替换公式A A中的不同中的不同命题变元命题变元 得到的公式记为得到的公式记为 ，称，称为为A A的替换实例。的替换实例。 替换

41、产生新的公式替换产生新的公式npp ,.,1nnppBBA,.,.,11nBB ,.,1qprprqpp,)( = (r p)(r p) r (p/r p, q/r)计算机学院56计算机学院56 定理定理1.2 1.2 设设 是不同命题变元，是不同命题变元， 是公式。则对是公式。则对于每个真值赋值于每个真值赋值v v， 其中真值赋值其中真值赋值v v=v=vp p1 1/v(B/v(B1 1), ), p, pn n/v(B/v(Bn n) )定义如下：定义如下：npp ,.,1nBBA,.,1)(/),.,(/()(11,.,.,11ABvpBvpvAvnnppBBnn否则是若是若vnnvp

42、ppBvppBvp)(.)(11)( )(,.,.,11AvAvnnppBB计算机学院57计算机学院57 证明：对证明：对A进行归纳。进行归纳。 若若A是是pi，其中，其中1in，则，则 是是Bi， 若若A A是除是除 之外的命题变元之外的命题变元p p，则，则 仍是仍是p p， (3)(3)若若A A是是0 0元联结词元联结词c c，则，则 仍是仍是c c，)(,.,.,11nnppBBAv)( )()(,.,.,11AvBvAvippBBnnnpp ,.,1)(,.,.,11nnppBBAv)( )()(,.,.,11AvpvAvnnppBB )(,.,.,11nnppBBAv)( )()

43、(,.,.,11AvcvAvnnppBB计算机学院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的公式的公式, ,则是则是 )( )(.,., 11ippBBiAvAvnn)( )( ),.,( ()(),.,)()(1.,.,1.,.,1,.,., 11, 1111AvAvAvFAvAvFAvkppBBkppBBppBBnnnnnn计算机学院59计算机学院59 定理定理1.31.3设设A A是公式。是公式

44、。 若若A A是永真式，则是永真式，则A A的每个替换实例都是的每个替换实例都是永真式永真式。 若若A A是永假式，则是永假式，则A A的每个替换实例都是的每个替换实例都是永假式永假式。 证明证明 任取永真式任取永真式A A的替换实例的替换实例 ，对于每个真值，对于每个真值赋值赋值v v， 所以所以 是永真式。是永真式。 可同样证明。可同样证明。 证毕证毕nnppBBA,.,.,111)(/),.(/)(11,.,.,11ABvpBvpvAvnnppBBnnnnppBBA,.,.,11计算机学院60计算机学院60 p ( q p)是永真式是永真式 设设A,B是任意公式是任意公式 p/A, q/

45、B A= p q , B=(p r) ( p q ) (p r) ( p q ) )是永真式是永真式计算机学院61计算机学院611.31.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 q0001111011010010100101110000计算机学院62计算机学院62等值式模式等

46、值式模式 零律零律 A1A11 A01 A00 0 幂等律幂等律 AAAAA A AAAAA 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 计算机学院63计算机学院63等值式模式等值式模式 德德 摩根律摩根律 (AB)(AB) AA B B (AB)(AB) AA B B 交换律交换律ABABBABAABABBABAA AB BB BA A 计算机学院64计算机学院

47、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) 计算机学院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)计算机学院66计算机学院66

48、定理：设定理：设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。计算机

49、学院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( p/v(RQ)= v( p/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

50、 R2 2，有，有Q Q R R1 1/R/R2 2QQ计算机学院68计算机学院68 例例1.51.5证明证明p(qr)p(qr)pqrpqr 证明：证明： p(qr)p(qr) p(p(qr) ABqr) ABABAB ( (ppq)r q)r 结合律结合律 (pq)r (pq)r 摩根律摩根律 pqr ABpqr ABABAB计算机学院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 吸收律吸