第11章命题逻辑

1、离散数学离散数学discrete mathematicsdiscrete mathematics什么是离散数学？为什么要学习离散数学？离散数学主要学习那些内容？什么是离散数学？什么是离散数学？研究离散量的结构及关系的一门科学。研究离散结构的数学分科。 （辞海）（辞海）培养个人理解和构造数学证明的能力为学习计算机科学课程提供必要的数学基础为什么学习离散数学？为什么学习离散数学？后继课程：后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、离散数学的内容：离散数学的内容： 数理逻辑（mathematics logic) 集合论(sets)图论（graph theory)代数结构（alg

2、bra structure)线性代数(linear algbra )概率论(离散部分)（propobility theory)组合论（combination)学习方法:理解概念、掌握方法、注重应用课程特点：逻辑性、抽象性1、离散数学（左孝琳、李为槛、刘永才，上海科技文献版）2、离散数学-计算机数学基础学习（陈德人，浙大版）3、discrete mathematics（ forth edition: richard johnsonbaugh)4、 discrete mathematics（ revised edition:biggs ) 5、discrete math. elements（ li

3、u chuang laung)逻辑学逻辑学：研究人的思维形式及规律的学科。 分为形式逻辑、辩证逻辑、数理逻辑。数理逻辑的提出：数理逻辑的提出：17世纪，有人提出计算的方法代替人们思维中的推理过程。 莱布尼兹 ：“通用的科学语言”，把推理过程变成象 数学一样利用公式计算，得出正确结论。现代数理逻辑部分内容的萌芽。1847年，数学家布尔（英）发表逻辑的数学分析，建立”布尔代数“，创建了一套符号体系，和一套运算规则，利用代数的方法研究逻辑问题。奠定了数理逻辑的基础。1884年，数学家弗雷格（德）出版数论的基础一书，引入量词符号，使得数理逻辑中的符号体系更加完备，皮尔斯（美），又引入逻辑符号。数理逻辑

4、理论基础逐渐形成，称为一门独立的学科。“两个演算两个演算”+“四论四论”命题演算，谓词演算命题演算，谓词演算递归论，证明论，模型论，公理集合论递归论，证明论，模型论，公理集合论数理逻辑是应用数学方法研究推理中前提与结论之间的形式关系的科学。 数理逻辑的核心是把逻辑推理符号化逻辑推理符号化，即把推理变成象数学演算一样完全形式化。数理逻辑又叫符号逻辑符号逻辑，因为它的主要工具是 符号体系。第1篇 数理逻辑mathematics logic - 一套符号体系一套符号体系 + 一组规则一组规则第第1-1章章 命题逻辑命题逻辑1-1-1 命题、逻辑联结词与真值表命题、逻辑联结词与真值表 1-1-2 命题

5、公式与真值函数命题公式与真值函数 proposition logic1-1-1 命题、逻辑联结词与真值表命题、逻辑联结词与真值表p一、命题的基本概念一、命题的基本概念 能判断真假而不是可真可假的陈述句。能判断真假而不是可真可假的陈述句。p真值：真值：命题表达的判断结果。真值只取两个值：真或假。p真值为真的命题称为真命题真命题，真值为假的命题称为假命题假命题。p真命题表达的判断正确，假命题表达的判断错误。p任何命题的真值都是唯一的。任何命题的真值都是唯一的。 p例例1 判断下列句子是否为命题。 (1) 人总是要死的。 (4) 中国人民是勤劳和勇敢的。 (7) 今天没有下雨。 (9) 太阳系以外的

6、星球上有人。 (10) 他喜欢读书也喜欢运动。 (11) 他在机房里或在图书馆里。 (13) 如果a和b都是正数，则ab也是正数。(14) xy0当且仅当x和y都大于0。 陈述句，真值唯一。陈述句，真值唯一。 (16) 天气多好啊！ (17) 他来了吗？ (21) 我正在说假话。 不是命题不是命题 不是命题不是命题 不是命题不是命题 若(21)的真值为真，即“我正在说假话”为真， 表明我说的是假话，则又推出(21)的真值应为假；反之，若(21)的真值为假，即“我正在说假话”为假，表明我说的是真话，则又推出(21)的真值应为真。于是(21)既不为真又不为假，因此它不是命题。 像(21)这样由真推

7、出假，又由假推出真的陈述句称为悖论悖论。 命题符号化命题符号化用大写英文字母p,q,r，pi ,qi ,ri 表示命题用“1”表示真，用“0”表示假如：p: 人总是要死的。 真值为1q: 是有理数。 真值为05不能再被分解的命题为简单命题（原子命题）。简单命题（原子命题）。命题标识符命题标识符命题标识符代表一个确定的命题，称为命题常元命题常元；代表一个非确指的命题，称为命题变元。命题变元。用一个确定的命题代入命题标识符p，称为对p的指派（赋值，或解释）指派（赋值，或解释）。 3是素数是不对的。 他喜欢读书也喜欢运动。 他在机房里或在图书馆里。 如果a和b都是正数，则ab也是正数。 xy0当且仅

8、当x和y都大于0。 复合命题复合命题p：3是素数。非非pq：他喜欢读书。 r：他喜欢运动q并且并且rs：他在机房。 t：他在图书馆。s或者或者tu：a和b都是正数。v： ab是正数。如果如果u则则v。 w：xy0。 z：x和y都大于0。 w当且仅当当且仅当z。 联结词联结词定义定义1.3 设p为命题，复合命题“非p”(或“p的否定”) 称为p的否定式否定式,记作p，符号称作否定联结词否定联结词。并规定p为真当且仅当p为假。 是有理数是不对的； 2pppp011001“2是偶素数” 。 定义定义1.4 设p,q二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式合取式，记作pq，称作合

9、取联结词合取联结词。并规定pq为真当且仅当p与q同时为真。 p: 2是偶数q: 2是素数pq111pqpq111000010100 “2或4是素数”定义定义1.5 设p，q为二命题，复合命题“p或q”称作p与q的析取式析取式，记作pq，称作析取联结词析取联结词。并规定pq为假当且仅当p与q同时为假。 p: 2是素数q: 4是素数pq101pqp q000011101111注意：注意：在自然语言中，“或”具有二义性，用它联接的两个命题有时具有相容性（即两命题可以同时为真），有时具有排斥性（即两命题不能同时为真）。前者称为可兼容或（相容或）可兼容或（相容或），后者称为不可兼不可兼容或（排斥或）容或

10、（排斥或）。 张红喜欢唱歌或者跳舞。张红是安徽人或者江苏人。(13) 如果如果a和和b都是正数，则都是正数，则ab也是正数。也是正数。定义定义1.6 设p，q为二个命题，复合命题“如果p，则q”称作p与q的条件式条件式，记作pq，称作条件联结词条件联结词。称p为前件前件，q为后件后件。并规定pq为假当且仅当p为真q为假。pq的逻辑关系的逻辑关系:p是是q的充分条件，的充分条件，q是是p的必要条件。的必要条件。 注意：注意： 在使用联结词时，要特别注意以下几点： 1在自然语言里，特别是在数学中，q是p的必要条件有许多不同的叙述方式。 例如：“只要p，就q”，“因为p，所以q”，“p仅当q”，“只

11、有q才p”，“除非q才p”，“除非q，否则非p”等等。 上述各种叙述方式都应符号化为pq. 2在自然语言中，“如果p，则q”中的前件p与后件q往往具有某种内在联系。而在数理逻辑中，p与q可以无任何内在联系。 若河水泛滥，则周围的庄稼被毁。p:河水泛滥。 q：周围的庄稼被毁。pq若23，则今天阳光明媚。a：20当且仅当x和y都大于0。 ” 定义定义1.5 设p，q为二个命题，复合命题“p当且仅当q” 记作p q， 称作双条件联结词双条件联结词。并规定pq为真当且仅当p与q同时为真或同时为假。 p q的逻辑关系为的逻辑关系为p与与q互为充分必要条件。互为充分必要条件。 pqp q001010100

12、111p q与(pq)(qp)的逻辑关系完全一致的逻辑关系完全一致例1.6 将下列命题符号化，并讨论它们的真值(1) 是无理数当且仅当加拿大位于亚洲(2)2+3=5的充要条件是是 无理数(3)若两圆o1，o2的面积相等，则它们的半径相等， 反之亦然。33解解：令p: 是无理数，真值为1 q: 加拿大位于亚洲，真值为03则(1)符号化为p q，真值为0 令r:2+3=5，真值为1，则(2)符号化为r p，真值为1 令 s:两圆o1，o2的面积相等 t:两圆o1，o2的半径相等则(3)符号化为s t真值为1 以上定义了五种最基本、最常用、也是最重要的联结词， ，将它们组成一个集合， ，称为一个联结

13、词联结词集集。其中为一元联结词，其余的都是二元联结词。 说明：1.由联结词集， 中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，称为基本复合命题。基本复合命题。p q ppqpqpqp q0 0100110 1101101 0001001 101111基本复合命题的真值2. 多次使用联结词集中的联结词，可以组成更为复杂的复合命题，求复杂复合命题的真值时，还要规定联结词的优先顺序，将括号也算在内，本书规定的联结词优先顺序为（），（），例 令 p:北京比天津人口多 q: 2+2=4 r: 乌鸦是白色的求下列复合命题的真值： (1) (pq) (p q) r (2) (qr)

14、(p r) (3) (pr) (p r) 1101101-1-2 命题公式与真值函数命题公式与真值函数 一、命题演算公式一、命题演算公式定义2.1 由命题变元、联结词、括号按下列规则形成的符号串。命题合式公式（命题合式公式（wff） (1)单个原子命题变元是wff(原子命题公式原子命题公式)。 (2)若a是wff，则(a)也是wff。 (3)若a，b是wff，则(ab)，(ab)，(ab)， (a b)也是wff。 (4)只有有限次地应用(1)(3)形式的符号串才是wff。如：(pq)(qr)，(pq)r，p(qr) pqr，（p(rq) 不是wff。 注意：注意：合式公式的定义方式称为归纳定

15、义方式， 本书中还将多次出现这种定义方式。 公式的赋值公式的赋值 例如，公式(pq)rpqr(pq)r00010100定义定义2.2 设p1,p2,pn是出现在公式a中的全部命题符号，给p1,p2,pn各指定一个真值，称为对a的一个指派指派（赋值赋值或解释解释）。若指定的一组值使a的真值为1，则称这组值为a的成真赋值成真赋值；若使a的真值为0，则称这组值为a的成假赋值成假赋值。 (p1p2p3)(p1p2) 000(p10，p20，p30)，110(p11，p21，p30)都是成真赋值成真赋值;001(p10，p20，p31)，011(p10，p21，p31)都是成假赋值成假赋值。 含含n(n

16、1)个命题变项的公式共有个命题变项的公式共有 组组不同的赋值。不同的赋值。 2n真值表真值表 定义定义1.8 将命题公式a在所有赋值下取值情况列成表，称作a的真值表真值表。 构造真值表的步骤：构造真值表的步骤： (1) 找出公式中所含的全体命题变项p1,p2,pn (若无下角标就按字典顺序排列)，列出2n个赋值。规定，赋值从000开始，然后按二进制加法依次写出各赋值，直到111为止。 (2) 计算出公式在每个赋值下的真值。例例2.1 求下列公式的真值表，并求成真赋值和成假赋值。 (1)（pq）（qp） (2)（pq）pq (3)（pq）（p q） pq(pq)(qp)00011011(pq)p

17、q(pq)(p q)110011110000公式(1)成真赋值：00，11，成假赋值：01，10公式(2)所有赋值都是成真赋值，无成假赋值。公式(3)所有赋值都是成假赋值，无成真赋值。重言式（永真式）重言式（永真式）矛盾式（永假式）矛盾式（永假式）公式分类公式分类 根据公式的取值情况对公式进行如下分类:定义定义2.4 设a为任一命题公式。 (1)若a在它的各种赋值下取值均为真,则称a是重言式重言式或永真式，永真式，记为记为t。(2) 若a在它的各种赋值下取值均为假,则称a是矛盾式矛盾式或永假式，永假式，记为记为f。(3) 若a不是矛盾式,则称a是可满足式可满足式。 说明： 1. a是可满足式的

18、等价定义是：a至少存在一个成成真赋值真赋值。 2. 重言式一定是可满足式，但反之不真。因而，若公式a是可满足式，且它至少存在一个成假赋值成假赋值，则称a为非重言式的可满足式非重言式的可满足式。3. 真值表可用来判断公式的类型: (1) 若真值表最后一列全为1，则公式为重言式重言式。 (2) 若真值表最后一列全为0，则公式为矛盾式矛盾式。 (3) 若真值表最后一列中至少有一个1，则公式为可满足式可满足式。 定理定理2.1 任意两个重言式（矛盾式）的合取或析取仍是任意两个重言式（矛盾式）的合取或析取仍是 重言式（矛盾式）。重言式（矛盾式）。下列各公式均含两个命题变元p与q，列出它们的真值表。 (1

19、) pq (2) pq (3) (pq)(4) (pq)(qp)(5) pq 公式形式不同，公式形式不同，真值表可能相同真值表可能相同公式公式(1)(3)(5)真值表相同真值表相同公式公式(2)(4)真值表相同真值表相同等价式等价式二、真值函数定义2.3 以真，假为定义域和值域的函数为真值函数真值函数 。所有的wff都是真值函数。一个wff对应一个真值表，反之，由真值表也可以写出对应的真值函数例2.4 设f (p,q,r) 是3个包含命题变元p，q，r的真值函数（wff），它们的真值表如下，请确定它们的表达式。pqrf1(p,q,r)f2(p,q,r)00001001100 100001100

20、10010101101100011111f1(p,q,r)= (pqr) (pq r) (pq r)(pqr)f2(p,q,r)= (pq r)(pqr)f1(p,q,r)和f2(p,q,r)的形式是否唯一？由真值表确定的真值函数不一定是最简单的由真值表确定的真值函数不一定是最简单的wff，也不一定只对应一个表达式。也不一定只对应一个表达式。pqrf1(p,q,r)000000110 10001101001101111001111f3(p,q,r)11110000等价式等价式f3(p,q,r)= (pqr) (pq r)(q p)例例 下列公式中,哪些具有相同的真值表? (1) pq(2) q

21、r(3) (pq)(pr)p)(4) (qr)(pp) 公式公式(1)(3)真值表相同真值表相同公式公式(2)(4)真值表相同真值表相同pqrf (p,q,r)000100110 10001111000101111001111f (p,q,r)=形式是否唯一？形式是否唯一？(pq)r(p q) r(p r) (q r)由同一个真值表确定的真值函数的形式不唯一。由同一个真值表确定的真值函数的形式不唯一。等价式等价式问：关于问：关于n个命题变元个命题变元p1,p2,pn,可以构造多少个可以构造多少个真值表不同的命题公式呢真值表不同的命题公式呢? n个命题变元共产生个命题变元共产生2n个不同赋值个不

22、同赋值,在每个赋值下在每个赋值下,公式公式的值只有的值只有0和和1两个值。于是两个值。于是n个命题变元构造的公式的个命题变元构造的公式的真值表共有真值表共有 种不同情况。种不同情况。1-1-3 公式的等价与蕴涵公式的等价与蕴涵 pq pq (pq)(pq)(qp) 与 p q公式形式不同，但真值表相同。公式形式不同，但真值表相同。等价式等价式定义定义3.1 设p1,p2,pn是出现在两个wffa和b中的原子命题变元，如果对p1,p2,pn的任意真值指派，a和b的真值都相同，则称a和b逻辑相等逻辑相等或a和和b等价等价。记为 ab (a=b)ab 是重言式是重言式定理定理3.3 公式公式a和和b

23、等价当且仅当等价当且仅当ab 是重言式。是重言式。基本等价式基本等价式(1) p p (对合律对合律)(2) pp p pp p (幂等律幂等律)(3) pq qp pq qp (交换律交换律)(4) p(q r) (pq) r p(q r) (p q) r (结合律结合律)(5) p(q r) (pq)(pr) p(q r) (pq)(pq) (分配律分配律)(6) p(p q) p p(p q) p (吸收律吸收律)(7) (p q) p q (p q) p q (德德摩根律摩根律)(8) pf p pt p (同一律同一律)(9) pt t pf f (零一律零一律)(10) pp t

24、pp f (否定律否定律)(11) pq pq (条件等价式条件等价式)(12) pq (pq) (qp) (双条件等价式双条件等价式)等价可看做是两个公式之间的关系，此关系具有自反性、对称性、传递性(1)自反性自反性 a a(2)对称性对称性 若ab，则 ba(3)传递性传递性 若ab且 bc，则有ac定义定义3.2 子公式子公式若wffx是wffa的子串，则称是的子公式。p(q r)q r是子公式是子公式因为因为 qr qr所以所以 p(q r) p (qr)定理定理3.1 替换规则替换规则设是wffa的一个子公式，且yx，则将a中x用y取代后得到的公式与a等价。例1 q(p (pq) p

25、 吸收律吸收律 qp 等价演算等价演算例2 证明 (p (pq) q t 例4 证明: pq qp 等价演算证明公式等价关系例5 证明: p(q r) (pq)r 重言式，真值始终为重言式，真值始终为1，与公式中变元取值无关。，与公式中变元取值无关。等价演算判断公式类型证明证明 (ab) (bc) (ca) (ab)(bc)(ca)证明：证明：(ab) (bc) (ca) (b(ac) (bc)(ba)(acc) (aca)(ca) (bc)(ba)(ac) (ac) (ab)(bc)(ca)等价演算解决实际逻辑判断问题等价演算解决实际逻辑判断问题例2.12 某科研所要从3名科研骨干a,b,c

26、中挑选12名出国进修,选派时要满足以下条件: (1) 若a去,则c同去. (2) 若b去,则c不能去. (3) 若c不去,则a或b可以去.问所里应如何选派他们去? 解解: : 设设 p:p:派派a a去去 q:q:派派b b去去 r: r: 派派c c去去 由已知条件可得此问题的逻辑表达式为由已知条件可得此问题的逻辑表达式为 (pr(pr) () (qqr) r) (r r (p(pq)q)问题转换为求该式的成真赋值问题转换为求该式的成真赋值001，010，101所以选派方案有三种:(1) c去,而a,b都不去(2) b去,而a,c都不去(3) a,c同去,而b不去定义定义3.3 设p1,p2

27、,pn是出现在两个wffa和b中的原子命题变元，如果对p1,p2,pn的任意真值指派，都不会出现a为1而b为0的情况，则称a蕴涵蕴涵b（b是是a的逻辑结果的逻辑结果）。记为记为 a b ba b是重言式是重言式定理定理3.4 公式公式 a b b 当且仅当当且仅当a b是重言式。是重言式。判断公式间蕴含关系的问题转换为判断公式类型问题。例6 证明 p pqpq用定义（采用真值表）例7 证明 (pq) pq) (qr) qr) pr例8 证明 q(pq) (pq) p举例证明蕴涵关系用定理3.4 (pq) pq) (qr) qr) (pr) ) t性质：自反性、反对称性、传递性性质：自反性、反对

28、称性、传递性l若若a b b且且a c c，则，则a bcl若若a b b且且c b b，则，则ac ba (bc)a (bc)( (ab) ( (ac)( (a b) ( (a c)蕴涵也可以看做公式间的一种关系。证明蕴涵关系常借助基本蕴涵式基本蕴涵式基本蕴涵式(1) p pq q p p pq q q 化简律化简律 (2) p pp pq q q pq pq q 附加附加律律 (3) p pp p q q(4) q p p q q(5) (p p q) p q) p (p p q) q) q q(6) p p (p p q) q q) q 分离规则（假言推理）分离规则（假言推理）(7) q

29、 q (p p q) q) p 拒取式拒取式(8) p p (p pq) q q) q 析取三段论析取三段论(9) (p p q) q) (q q r)r) p p r r 假言三段论假言三段论(10) (p (pq) q) (p p r) r) (q q r)r) r r(11) (p p q) q) (r r s s) ) (p (pr) ( (q qs)s)(12) (p pq) q) (q q r)r) p p r r 等价等价三段论三段论2.不构造真值表证明下列蕴涵式不构造真值表证明下列蕴涵式(2)(pq)qpq(3) pqps(6) (qp)(r(rp) r(pq)3.若 ac b

30、c，是否有，是否有a b错误。错误。c取1，a取0，b取1时， ac bc，但但 a b若 ac bc，是否有，是否有a b1-1-4 命题逻辑的推理理论命题逻辑的推理理论什么样的推理是有效的？ 由给定的前提经过有效的推理有效的推理得出的结论，称为有效结论有效结论。定义定义4.1 a1，a2， an和和b为合式公式，若为合式公式，若 a1a2 an b，则称，则称b为前提为前提a1，a2， an 的的有效结论有效结论，或说，或说 b为前提为前提a1，a2， an 的的逻辑结果逻辑结果，或说，或说a1，a2， an 共同蕴涵共同蕴涵b。 注意：推理的有效性与结论的真实性不是等同的。注意：推理的有

31、效性与结论的真实性不是等同的。有效的推理不一定产生真实的结论。有效的推理不一定产生真实的结论。推理有效指结论是所给前提的合乎逻辑的结果。推理有效指结论是所给前提的合乎逻辑的结果。例1 证明 rs是p(qs)， rp，q的有效结论。(p(qs) (rp) q rs(p(qs)(rp)q( rs)是重言式真值表，等价演算(p(qs)(rp)q( rs)( (p(qs)(rp)q(rs) )(p(qs)(rp)q)( (rs) )(p(qs) (rp) qrs(p(qs) (rp) (qs)r(p (qs) p rt t(p q s) p r 证明 rs是p(qs)， rp，q的有效结论。r pp(

32、qs)r p r(qs) rqs(rs) qq rsrs中间结论演绎法演绎法基本蕴涵式等价式证证明明过过程分解成一步一步，以基本程分解成一步一步，以基本蕴蕴涵式或等价式涵式或等价式作作为为推理依据，中推理依据，中间结论间结论作作为为前提使用。前提使用。定义4.2 设s为若干公式的集合(称为前提集合)，如果有公式的有限序列a1，a2， an ，其中ais或ai是a1，a2， ai-1中某些公式的有效结论,且an=b，则称b是是s的逻辑结果的逻辑结果或有效结论有效结论,或者说s演绎出演绎出b。基本蕴涵式、基本等价式是演绎方法论证的根据，除此之外还必须遵循下列推理规则：p规则规则：在推演过程中可以随

33、时使用前提。t规则规则：在推演过程中可以任意使用前面演绎的某些公式的逻辑结果（中间结论），当借助于等价式时记为te，当借助于蕴涵式时记为ti。cp规则规则：如果需要演绎的公式为bc，那么将b作为附加前提，设法演绎出c来。附加前提证明法，定理4.1证明其正确性例1 证明 rs是p(qs)， rp，q的有效结论。证明： p(qs) r p r(qs) rqs(rs)q q rs rpptepti假言三段论假言三段论tepti析取三段论析取三段论 rste定理4.1 若a1a2 an b c，则，则 a1a2 an b c当且仅当当且仅当若若(a1a2 an b) c是重言式是重言式则则(a1a2

34、an ) (b c)也是重言式也是重言式(a1a2 an b) c(a1a2 an ) (b c)(p(qs) (rp) q rs(p(qs) (rp) q r s例1 证明 rs是p(qs)， rp，q的有效结论。证明： p(qs) p qs q s rpptipti分离规则分离规则pti rscp rp（附加前提）（附加前提）分离规则分离规则附加前提证明法例1 证明 rs是p(qs)， rp，q的有效结论。令 s=p(qs)， rp，q证明s演绎出rsr pp(qs)r p r(qs) rqs(rs) qq rsrs中间结论s演绎出rs的过程 演绎法与证明(p(qs) (rp) q rs是

35、等价的。基本蕴涵式等价式定理定理4.2 设设s为公式集，为公式集，b是一个公式，是一个公式，s能演绎能演绎出出b的充要条件是：的充要条件是：b是是s的逻辑结果。的逻辑结果。定理定理4.3 设设s为前提公式集合，为前提公式集合，b和和c是两个公式，是两个公式，若若sb能演绎能演绎c，则，则s演绎出演绎出b c。设s=a1，a2， an ，则sb= =a1，a2， ，an ，b，说明如果证明的结论是一个条件式，则可以将前件作为前提之一，后件作为结论。前件b称为附加前提，附加前提引入反证法（归谬法）反证法（归谬法）定义定义4.3 设a1，a2， an是n个命题公式，若a1a2 an 是矛盾式，则称a

36、1，a2， ，an是不相容不相容的。否则，称其为相容相容的。取取结论结论的否定作的否定作为为前提引入到前提引入到证证明中，希望推出明中，希望推出矛盾的矛盾的结论结论。定理定理4.4 a1a2 an b当且仅当当且仅当a1，a2， ，an ，b是不相容的。是不相容的。a1a2 an b t ta1a2 an b f f反证法（归谬法）的理论依据反证法（归谬法）的理论依据 (a1a2 an)b (a1a2 an b) t t t t例3 证明 s=ab， (bc)演绎出a采用反证法（归谬法）采用反证法（归谬法）证明： abp ap(否定结论引入否定结论引入) bti(bc)pbc tebti bb

37、 f f tea定理定理4.4例例2 证明证明 (pq) (pr) (qs) sr pq证明：证明： pqpte qsp psti假言三段论假言三段论 spte pr p srti假言三段论假言三段论 srte使用反证法使用反证法 (sr)p s rte p r p s r qsp pt i qtititi p q (p q) p q (p q) p q f f例例2 反证法反证法证明证明 (pq) (pr) (qs) sr论证的方法可以分为：真值表法，直接法，间接法直接法直接法：由一组前提经p规则，t规则演绎出有效结论间接法间接法: (1)附加前提证明法 (2)反证法（归谬法）定义定义4.3

38、 设p1,p2,pn是a1，a2， am中出现的原子命题变元，若a1a2 am 是矛盾式，则称a1，a2， ，am是不相容不相容的。否则，称其为相容相容的。 pr p pqrq ti qsp rqrs ti pqrs ti pqp rsti例例2 证明证明 (pq) (pr) (qs) sr证明证明:例5 “如果天下雨，春游就改期，如果没有球赛，春游就不改期。结果没有球赛，所以没有下雨。”证明这是有效的论断。证明： 令 a:天下雨； b：春游改期； c：没有球赛符号化前提和结论，前提： ab， cb，c结论： a例6 “如果学生学习努力，他们的父亲或母亲就高兴。若母亲高兴，学生就不努力学习。若

39、老师只表扬学生，则父亲就不高兴。故如果学生学习努力，老师就不只是表扬学生。”证明这是有效的论断。证明： 令 a:学生学习努力； b:学生的父亲高兴； c:学生的母亲高兴；d:老师只表扬学生符号化前提和结论，前提： a(bc)， ca， db结论： ad前提： a(bc)， ca， db结论： ad证明： ap(附加前提附加前提) a(bc) p bcti cap cti bti dbpdti例7 证明下列命题是不容的：“如果他因病缺课，那么他考试不及格。如果他考试不及格，他就受不到教育。若他读了许多书，则他受到了教育，但是，虽然他因病缺课，他还是读了许多书。”证明： 令 p:他因病缺课； q:

40、他考试不及格； r:他就受不到教育；s:他读了许多书问题符号化为pqqrsrps不相容不相容(pq) (qr) (sr) (ps)f(pq) (qr) (sr) (ps)t(pq) (qr) (sr) (ps)1-1-5 对偶与范式对偶与范式定义5.1 在只含有逻辑联结词, 的公式a中，将换成， 换成，如果a中有t或f就分别换成f或t，所得到的公式记为a*,称为a的对偶式。 a*和和a互为对偶式互为对偶式 (a*)*=ap(q r)p(q r)例5.1 求 (1) (pq)f (2) p(qt) (3) (pq) r的对偶式。对偶性质对偶性质定理5.1 设p1,p2,pn是公式a和a*中出现的

41、原子命题变元，分别记为a(p1,p2,pn)和a*(p1,p2,pn)，则a(p1,p2,pn) a*(p1,p2,pn)a(p1,p2,pn)a*(p1,p2,pn)a=p(q r)a*=p(q r)a=p (q r)a*()= p(qr)定理5.2 设a，b为两个合式公式，若ab， 则a*b* p(q r) (pq)(pr)p(q r) (pq)(pq) (p q) p q (p q) p q pq ， pq ， (pq) ，qp 找出一种统一的形式表示一组等价式，希望这种形式惟一化。主范式（正则范式）主范式（正则范式）定义5.2 文字（句节）文字（句节）原子命题公式或它的否定。定义5.3

42、 子句，短语子句，短语子句子句：有限个文字（句节）的析取式（简单析取式）简单析取式）短语短语：有限个文字（句节）的合取式（简单合取式）简单合取式）一个文字既是子句又是短语。p1 ，p2 ，q子句：p1p2p3 ，pq ，r短语：p1p2p3 ，pq ，r定义5.4 范式范式合取范式合取范式：有限个子句（简单析取式）的合取式。析取范式析取范式：有限个短语（简单合取式）的析取式。(p1p2p3) (pq) r(p1p2p3) (pq) r一个子句（短语）既是合取范式，又是析取范式。一个子句（短语）既是合取范式，又是析取范式。 定理定理5.3 （范式存在定理）（范式存在定理）任一命题公式都有与之等价

43、的合取范式和析取范式。任一命题公式都有与之等价的合取范式和析取范式。证明:范式中出现的联结词只能是， ，设a为任一个命题公式若a中含有，可以通过等价式消去pq pqpq (pq) (qp) (pq) (qp)再对a使用分配、结合、交换、德摩根律化成范式。例： 求 (p q ) r 的合取的合取(析取析取)范式范式解：解： (p q ) r (pq)r (pq) r (p q) r (pr) (q r) 合取范式合取范式析取范式析取范式公式公式 c= (pqr) (pqr) (pqr) ) (pqr)析取范式c(pqr) (pqr) (pqr) (pqr) (pqr) (pqr)c(pq) (p

44、r)(qr)析取范式析取范式不惟一析取范式不惟一范式范式并并不是惟一的不是惟一的 定义定义5.5 （极大项，极小项）（极大项，极小项） 按顺序取按顺序取n个原子命题变元中每一个句节一次个原子命题变元中每一个句节一次 且仅一次且仅一次 构成的子句（短语），称为关于这构成的子句（短语），称为关于这 n个变元的极大项（极小项）。个变元的极大项（极小项）。例如:3个命题变元p，q，r短语： pqr , pq, pqr q极小项极小项子句： pq, pqp , pqrq， pq r极大项极大项写出两个原子命题变元写出两个原子命题变元p,qp,q能够成的所有极大项、能够成的所有极大项、极小项极小项两个原子

45、命题变元能构成的所有极大项、极小项 每一个极大项有且只有一组成假赋值；不同每一个极大项有且只有一组成假赋值；不同极大项成假赋值不同。极大项成假赋值不同。 每一个极小项有且只有一组成真赋值；不同每一个极小项有且只有一组成真赋值；不同极小项成真赋值不同。极小项成真赋值不同。pqpqpqpq极大项：极大项：极小项：极小项：pqpqpqpq(1)任两个极大项的析取式为重言式。任两个极大项的析取式为重言式。(2)全体极大项的合取式为矛盾式。全体极大项的合取式为矛盾式。(1)任两个极小项的合取式为矛盾式。任两个极小项的合取式为矛盾式。(2)全体极小项的析取式为重言式。全体极小项的析取式为重言式。n个命题变

46、元能构成个命题变元能构成 多少多少 个极大项（极小项）？个极大项（极小项）？2npq rpqrpqrp qr写出写出3个命题变元个命题变元p、q、r构成的所有极大项构成的所有极大项p qrpqrpqrpqr000001010011100101110111m0m1m2m3m4m5m6m7定义定义5.6，5.7 主范式（正则范式）主范式（正则范式）设设a是包含原子命题变元是包含原子命题变元p1,p2,pn的的公式，若公式，若a的一个合取范式中每个子句都是极大项，则称该合的一个合取范式中每个子句都是极大项，则称该合取范式是取范式是a的主合取范式（正则合取范式）。若的主合取范式（正则合取范式）。若a的

47、的一个析取范式中每个短语都是极小项，则称该析取一个析取范式中每个短语都是极小项，则称该析取范式是范式是a的主析取范式（正则析取范式）。的主析取范式（正则析取范式）。a=(pq) (qr) (pr)是合取范式，是合取范式，不是主合取范式不是主合取范式能否求出能否求出a的主范式？的主范式？等价演算法求主范式等价演算法求主范式例6 求a=(pq) (qr) (pr)的主合取范式和主析取范式。a=(pq) (qr) (pr)(q(pr) )(pr)(qp)(qr)(prp)(prr) (qp)(qr)(pr)合取范式合取范式析取范式析取范式与主合取范式的差异在哪里？与主合取范式的差异在哪里？与主析取范

48、式的差异在哪里？与主析取范式的差异在哪里？m2 m3 m5 m7m0 m1 m4 m6主合取范式：主合取范式：主析取范式：主析取范式：a=(pq) (qr) (pr)a a有且只有有且只有4 4组成假赋值：组成假赋值：000000，001001，100100，110110a a有且只有有且只有4 4组成真赋值：组成真赋值：010010，011011，101101，111111从主范式可以得出公式从主范式可以得出公式的成真、成假赋值的成真、成假赋值反之呢？反之呢？pqra00000010010101111000101111001111主范式与真值表之间的关系：主范式与真值表之间的关系：定理定理5

49、.4 在公式在公式a的真值表中，使的真值表中，使a的成假赋值的成假赋值所对应的所对应的a的极大项的合取式就是的极大项的合取式就是a的主合取范式。的主合取范式。定理定理5.8 在公式在公式a的真值表中，使的真值表中，使a的成真赋值的成真赋值所对应的所对应的a的极小项的析取式就是的极小项的析取式就是a的的主析取范式。主析取范式。例 真值表法求a= (p q ) r的 主合取范式和主析取范式。真值表法真值表法求主范式求主范式解：列真值表，找出成假赋值和成真赋值 。a(pqr)(pqr)(pqr) 成假赋值(pqr)：000,010,110对应极大项：m000=pqr =m0m010=pqr=m2m1

50、10=pqr =m6a m0 m2 m6a m1 m3 m4 m5 m7a= (p q ) rpqra00000011010001111001101111001111主合取范式主合取范式主析取范式主析取范式定理定理5.5,5.7，5.9 （主范式存在惟一性）（主范式存在惟一性）任何公式都有与之等价的主合取（析取）范式，任何公式都有与之等价的主合取（析取）范式，且惟一。且惟一。矛盾式和重言式的主合取范式、主析取范式。矛盾式和重言式的主合取范式、主析取范式。矛盾式的主合取范式包含每一个极大项矛盾式的主合取范式包含每一个极大项a(p1,p2,pn) f mm0 mm1 mm2 mm2n n-1 重言

51、式的主析取范式包含每一个极小项重言式的主析取范式包含每一个极小项a(p1,p2,pn) t mm0 mm1 mm2 mm2n n-1 矛盾式无成真赋值，其主析取范式不包含极小项，矛盾式无成真赋值，其主析取范式不包含极小项，记做记做f。重言式无成假赋值，其主合取范式不包含极大项，重言式无成假赋值，其主合取范式不包含极大项，记做记做t。1-1-6 其他逻辑联结词其他逻辑联结词定义定义 6.1 不可兼或不可兼或由命题公式由命题公式p和和q产生的新命题产生的新命题pq，称为，称为p和和q的不可兼或的不可兼或。pqpq000011101110pq qp(pq)r p ( (qr) p(qr) ( (pq

52、) ( (pr)pq (pq) (pq) pq (pq)ppf f pfp ptp定义定义 6.2 “与非与非”，“或非或非”由命题公式由命题公式p和和q产生的新命题产生的新命题pq， pq称为称为p和和q的的“与非式与非式”和和“或非式或非式”。pq (pq)pq (pq)和和互为对偶互为对偶例例6.1 a=p(q(rp)，求求a*解：解： a* =p(q(rp)例例6.2 a=(pq)q)(qq)，求求a*解：解： a (pq)q)(qq)a* = =(pq) q) (qq)可得可得p pp(pq) (pq)pqpq(pp) (qq)对偶性质对偶性质 若 ab ，则 a*b* 逻辑联结词逻辑联结词， ， 均可由均可由 和和表示表示ppq(pq)(pq)(pq)(pq) p