第一章命题逻辑全

离散数学DiscreteMathematics授课学时:48学时教学目标:知识、能力、素质授课老师：张莉考试类型:闭卷成绩组成:20(平时成绩)+80%*卷面成绩联系方式:45231135@

教材：离散数学(第四版)----耿素云，屈婉玲，张立昂参考资料：离散数学习题解答与学习指导－清华大学出版社离散数学-计算机数学基础学习－陈德人，浙大版

DiscreteMathematics（ForthEdition:RichardJohnsonbaugh)

离散数学是随着计算机科学的发展而逐步建立的，它形成于七十年代初期，是一门新兴的工具性学科。

离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础，所以又称为计算机数学，是计算机科学与技术专业的核心、骨干课程。它以研究离散量的结构和相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此它充分描述了计算机科学离散性的特点。内容包含：数理逻辑、集合论、代数结构与布尔代数、图论等。

离散数学课程的学习方法:

强调：逻辑性、抽象性；注重：概念、方法与应用离散数学的学习要领：概念（正确）必须掌握好离散数学中大量的概念判断（准确）根据概念对事物的属性进行判断推理（可靠）根据多个判断推出一个新的判断

离散数学与计算机的关系第一部分

数理逻辑计算机是数理逻辑和电子学相结合的产物第二部分集合论集合：一种重要的数据结构关系：关系数据库的理论基础函数：所有计算机语言中不可缺少的一部分第三部分代数系统计算机编码和纠错码理论数字逻辑设计基础计算机使用的各种运算第四部分图论数据结构、操作系统、编译原理计算机网络原理的基础离散数学课程设置：计算机系核心课程信息类专业必修课程其它类专业的重要选修课程离散数学的后继课程：数据结构、编译技术、算法分析与设计、人工智能、数据库、……第一章命题逻辑

数理逻辑是用数学方法来研究推理的形式结构和推理规律的数学学科.它采用数学符号化的方法来研究逻辑，因此也称为符号逻辑。从广义上讲，数理逻辑包括四论、两演算——即集合论、模型论、递归论、证明论和命题演算、谓词演算，但现在提到数理逻辑，一般是指命题逻辑和一阶逻辑(谓词逻辑)。本书也只研究这两个逻辑演算。数理逻辑的创始人是Leibniz，为了实现把推理变为演算的想法，他把数学引入了形式逻辑。其后，又经多人努力，逐渐使得数理逻辑成为一门专门的学科。上个世纪30年代以后，数理逻辑进入一个崭新的发展阶段，逻辑学不仅与数学结合，还与计算机科学等密切关联。

1931年Godel不完全性定理的提出，以及递归函数可计算性的引入，促使了1936年Turing机的产生，十年后，第一台电子计算机问世。数理逻辑发展历史

数理逻辑与计算机学、控制论、人工智能的相互渗透推动了其自身的发展，模糊逻辑、概率逻辑、归纳逻辑、时态逻辑等都是目前比较热门的研究领域。本章和下一章我们只从语义出发，对数理逻辑中的命题逻辑与谓词逻辑(一阶逻辑)等作一简单的、直接的、非形式化的介绍，将不涉及任何公理系统。§1.1命题符号化及联结词基本概念

命题：能够判断真假的陈述句。

命题的真值：命题的判断结果。真值只取两个值：真（1）、假（0）。

真命题：真值为真的命题。

假命题：真值为假的命题。判断命题的两个步骤：

1、是否为陈述句；2、是否有确定的、唯一的真值。注意:

感叹句、祈使句、疑问句都不是命题.陈述句中的悖论以及判断结果不惟一确定的也不是命题例1.1

下列句子中那些是命题？

(1)

是无理数.

(2)2+5＝8.(3)x+5＞

3.(4)今年春节大家看春晚了吗？

(5)刘谦的魔术真是精彩呀！

(6)请不要讲话！

(7)我正在说谎话.真命题假命题真值不确定疑问句感叹句祈使句悖论(3)~(7)都不是命题(8)明年2月16号是晴天。命题及其真值的抽象化在本书中，用小写英文字母p,q,r,…p1,p2,p3…

等表示命题,用“1”、“0”分别表示真值的真、假。

例1.2：

q：5是负数。

p3：明天天气晴。皆为符号化的命题，其真值依次为0、1或0。若令

p：是有理数，则p的真值为0q：2+5=7，则q的真值为1命题及其真值的抽象化在本书中，用小写英文字母p,q,r,…p1,p2,p3…

等表示命题,用“1”、“0”分别表示真值的真、假。

例1.2：

q：5是负数。

p3：明天天气晴。皆为符号化的命题，其真值依次为0、1或0。若令

p：是有理数，则p的真值为0q：2+5=7，则q的真值为1命题及其真值的抽象化在本书中，用小写英文字母p,q,r,…p1,p2,p3…

等表示命题,用“1”、“0”分别表示真值的真、假。

例1.2：

q：5是负数。

p3：明天天气晴。皆为符号化的命题，其真值依次为0、1或0。若令

p：是有理数，则p的真值为0q：2+5=7，则q的真值为1命题的分类1:简单/原子命题：不能再分解为更简单的陈述句的陈述句。2:复合命题：由简单命题通过联结词联结而成的陈述句。例1.3

(1)若三角形等腰，则两底角相等.(2)只要今天没有大雾，飞机就不会晚点。

在命题逻辑的符号化过程中，通常的要求是每一个引进的表示命题的符号都表示一个原子命题。

例如：将下列命题符号化(1)成都不是中国的首都。(2)李平虽然聪明，但不用功。

解(1)令p：成都是中国的首都。则命题“成都不是中国的首都”符号化为：┐P(2)令p：李平聪明。q：李平用功则命题“李平虽然聪明，但不用功。”符号化为：p∧┐q。

由此我们进一步明确指出：原子命题是用肯定语气表达的具有真假意义的简单陈述句。上述例题中。直接令p表示“成都不是中国的首都”。来做符号化，是不符合要求的。常用联结词定义1.1设p为命题，复合命题“非p”（或“p的否定”）称为p的否定式，记作p，符号称为否定联结词。运算规则：属于单目运算符定义1.2设p,q为二命题，复合命题“p并且q”（或“p与q”）称为p与q的合取式，记作p∧q，符号∧称为合取联结词。运算规则：属于双目运算符合取运算特点：只有参与运算的二命题全为真时，运算结果才为真，否则为假。自然语言中的表示“并且”意思的联结词，如“既…又…”、“不但…而且…”、“虽然…但是…”、“一面…一面…”等都可以符号化为∧。注意：不要见到“与”或“和”就使用联结词∧

！例1.4下列命题符号化(1)北京不仅是中国的首都而且是一个故都

p：北京是中国的首都。q：北京是一个故都。

p∧q：北京是中国的首都并且是一个故都。(2)张老师和周老师是好朋友。

p:张老师和周老师是好朋友

p是简单命题定义1.3设p,q为二命题，复合命题“p或q”称为p与q的析取式，记作p∨q，符号∨称为析取联结词。运算规则：属于双目运算符例1.5将下列命题符号化

(1)2或4是素数.(2)2或3是素数.解令p:2是素数,q:3是素数,r:4是素数,则(1),(2)均为相容或.

分别符号化为:p∨r,p∨q,

它们的真值分别为1,1.

(3)小元元只能拿一个苹果或一个梨.(4)王晓红生于1975年或1976年.而(3),(4)为排斥或.令t:小元元拿一个苹果，u:小元元拿一个梨，则(3)符号化为(t∧u)∨(t∧u).令v:王晓红生于1975年,w:王晓红生于1976年,则(4)符号化为(v∧w)∨(v∧w)定义1.4设p,q为二命题,复合命题“如果p则q”称为p与q的蕴涵式，记作pq,并称p为蕴涵式的前件，q为蕴涵式的后件，符号称为蕴涵联结词。与自然语言的不同：前件与后件可以没有任何内在联系！运算规则：属于双目运算符pq的逻辑关系：q为p的必要条件“如果p，则q”的不同表述法很多：若p，就q

只要p，就qp仅当q

只有q才p

除非q,才p，当p为假时，pq为真常出现的错误：不分充分与必要条件

一定要注意到蕴涵式的前件和后件!例1.5将下列命题符号化(5)如果22=5，则雪是黑的令p：22=5，q：雪是黑的，

于是命题符号化为pq

这是和人们日常生活中语言不一致的地方，这就是在逻辑中可以将两个没有关联的事情用连接词连接进行讨论。(6)如果我得到这部小说，那么我今夜就读它令p1：我得到这部小说q1：我今夜就读完它于是命题符号化为p1

q1定义1.5设p,q为二命题，复合命题“p当且仅当q”称为p与q的等价式，记作pq，符号称为等价联结词。说明:(1)pq的逻辑关系:p与q互为充分必要条件

(2)pq为真当且仅当p与q同真或同假运算规则：属于双目运算符例1.6

求下列复合命题的真值

(1)2+2＝

4当且仅当3是奇数.(2)2+2＝

4当且仅当3是偶数.(3)2+2＝

4当且仅当太阳从东方升起.(4)2+2＝

4当且仅当美国位于非洲.(5)函数

f(x)在x0

可导的充要条件是它在

x0连续.

它们的真值分别为1，0，1，0，0.以上例子充分说明:等价运算pq表示的逻辑关系是：p与q互为充分必要条件。相当于(pq)∧(qp).以上5种最基本、最常用、最重要的联结词可以组成一个集合{

，∧，∨，，}，成为一个联结词集，其运算的优先级为：，∧，∨，，

，对于同一级者，先出现者先运算。例1.8

求命题公式(pq)

pq真值表.

pqpqp

pq

pq

pq

00

11

1

1

01

1

1

1

1

1

0

0

0

0

1

1

1

1

0

1

1

§1.2命题公式及其分类基本概念简单命题/命题常项/命题常元：真值唯一确定的陈述句。命题变项/命题变元：真值可以变化的陈述句。命题常项与命题变项都可以用p,q,r…等表示，具体情况由上下文确定。

合式公式/命题公式：将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串。

当使用联结词集{，∧，∨，，}时，合式公式定义如下：定义1.6（1）单个命题常项或变项是合式公式，并称为原子命题公式。（2）若A是合式公式，则(A)也是合式公式。（3）若A，B是合式公式，则(A∧B)，(A∨B)(AB)，(AB)也是合式公式。（4）只有有限次地应用(1)~(3)形成的符号串才是合式公式。合式公式也称为命题公式或命题形式，并简称为公式。(pq),(r∧t)∨e,p，(p)等是合式公式，而pq∨t,(p)∧q)等不是合式公式。上述归纳定义方式中的符号A,B不同于具体公式里面的p,q,r等符号，可以用来表示任意的合式公式,属于元语言符号。定义1.7——公式层次（1）若公式A是单个的命题变项，则称A为0层合式公式。（2）称A是n+1(n≥0)层公式是指下列情况之一：

(a)A=B,B是n层公式；

(b)A=B∧C,其中B,C分别为i层和j层公式,

且n=max(i,j)；

(c)A=B∨C,其中B,C的层次及n同(b);(d)A=BC,其中B,C的层次及n同(b);(e)A=BC,其中B,C的层次及n同(b);（3）若公式A的层次为k，则称A是k层公式。例:公式

p0层

p1层

pq2层

(pq)r3层

((pq)r)(rs)4层定义1.8——公式赋值设p1，

p2，

…，pn是出现在公式A中的全部的命题变项，给p1，

p2，

…，pn各指定一个真值，称为对A的一个赋值或解释。比如：对公式(pq)∧r，指定一组赋值：011(即令p=0,q=1,r=1)则公式的真值为1；指定另一组赋值：010可得真值为0；还有000，001，111……

考虑：含有n个命题变项的公式共有多少个不同的赋值？2n个赋值.

若指定的一组值使A的真值为1，则称这组值为A的成真赋值。(使公式为真的赋值)

如对公式(pq)∧r赋值011，还有…???

若指定的一组值使A的真值为0，则称这组值为A的成假赋值。(使公式为假的赋值)

如对公式(pq)∧r赋值010，还有…???真值表将命题公式A在所有赋值下取值情况列成表称做A的真值表。对公式A构造真值表的具体步骤为：（1）找出公式中所有的全体命题变项p1，

p2，

…，pn，列出2n个赋值。（2）按从低到高的顺序写出公式的各个层次。（3）对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。例1.9(1)求命题公式(pq)∧r的真值表公式的另一种分类方式定义1.9设A为任一命题公式，（1）若A在其各种赋值下的取值均为真，则称A是重言式或永真式。（2）若A在其各种赋值下的取值均为假，则称A是矛盾式或永假式。（3）若A至少存在一组赋值是成真赋值，则称A为可满足式。可知,重言式一定是可满足式,但反之不成立.真值表的作用：（1）表示出公式的成真或成假赋值。（2）判断公式类型：

(a)若真值表最后一列全为1，则为重言式；

(b)若真值表最后一列全为0，则为矛盾式；

(c)若真值表最后一列至少有一个1，则为可满足式；有很多公式具有相同的真值表。如：还有p∨q、pq等§1.3等值演算定义1.10

设A,B是两个命题公式，若A，B构成的等价式AB为重言式，则称A与B是等值的记作AB.

即AB的充要条件是AB为重言式判断两个公式等值的方法1：真值表法。例1.10

判断公式p(qr)与(p∧q)r是否等价等值演算：由已知的等值式推演出另外一些等值式的过程。等值演算中使用的一条重要规则：置换规则定理1.1

设Φ(A)是含公式A的命题公式,Φ(B)是用公式B置换了Φ(A)中所有的A后得到的命题公式，若BA，则Φ(A)Φ(B)。双重否定律:AA等幂律：AAA,AAA交换律:ABBA,ABBA结合律:(AB)CA(BC)(AB)CA(BC)分配律:A(BC)(AB)(AC)

A(BC)(AB)(AC)德·摩根律

:(AB)AB

(AB)AB吸收律:A(AB)A,A(AB)A零律:A11,A00同一律:A0A,

A1A排中律:AA1矛盾律:AA0蕴涵等值式:ABAB等价等值式:AB(AB)(BA)假言易位:ABBA等价否定等值式:ABAB归谬论:(AB)(AB)A等值演算与置换规则

等值演算:

由已知的等值式推演出新的等值式的过程置换规则：若AB,则(B)(A)

等值演算的基础：

(1)等值关系的性质：自反、对称、传递

(2)基本的等值式

(3)置换规则等值演算的用途一：证明等值式。例1.10验证p(qr)(p∧q)r

右(p∧q)∨r

蕴涵等值式

p∨q∨r德摩根律

p∨(q∨r)结合律

p∨(qr)蕴涵等值式

p(qr)蕴涵等值式注:ABA∨B

例1.14：判断公式

(pq)r的类型(自学)

解：列出真值表如下，可知其是可满足式的等值演算的用途三：文字断案问题。例：参见教材p11

例1.11解：设pi,qi,ri,si分别表示A第i名,B第i名,C第i名,D第i名,由题意可知下列命题成立。①(r1∧¬q2)∨(¬r1∧q2)1②(r2∧¬s3)∨(¬r2∧s3)1③(p2∧¬s4)∨(¬p2∧s4)11①∧②[(r1∧¬q2)∨(¬r1∧q2)]∧[(r2∧¬s3)∨(¬r2∧s3)][(r1∧¬q2)∧(r2∧¬s3)]∨[(¬r1∧q2)∧(r2∧¬s3)]∨[(r1∧¬q2)∧(¬r2∧s3)]∨[(¬r1∧q2)∧(¬r2∧s3)]这里用到分配率公式(A∨B)∧(C∨D)=[(A∧C)∨(B∧C)]∨[(A∧D)∨(B∧D)

]由于C不能既第一又第二,又B和C不能都第二,故(r1∧¬q2)∧(r2∧¬s3)0(¬r1∧q2)∧(r2∧¬s3)0①(r1∧¬q2)∨(¬r1∧q2)1②(r2∧¬s3)∨(¬r2∧s3)1③(p2∧¬s4)∨(¬p2∧s4)11①∧②④(r1∧¬q2)∧(r2∧¬s3)∨(¬r1∧q2)∧(¬r2∧s3)11③∧④⑤

1p2∧¬q2∧r1∧¬r2∧s3∧¬s4由上式可知r1,

p2,s3是真命题，即C第一，A第二，D第三，B只能第四了。例：参见教材p11

例1.11解：设pi,qi,ri,si分别表示A第i名,B第i名,C第i名,D第i名,由题意可知下列命题成立。Theend§1.4联结词全功能集定义1.11

设p，q是两个命题，复合命题“p,q之中恰有一个成立”称为p与q的排斥或或异或，记作pq，称作排斥或或异或联结词。Pq为真当且仅当p，q中恰有一个为真。Pqpq00001101110例：小李现在在宿舍或在图书馆里令p:小李在宿舍

q:小李在图书馆里该命题可表示为Pq定义1.12

设p，q是两个命题，复合命题“p与q的否定”称为p与q的与非式，记作pq。“”称作与非联结词。pq为真当且仅当p，q不同时为真.

由定义可知：

pq=(pq)。

pqpq

001011101110定义1.13

设p，q是两个命题，复合命题“p或q的否定”称为p与q的或非式，记作pq，

称作或非联结词。pq为真当且仅当p，q同时为假。由定义可知：

pq=(pq)

pqpq

001010100110定义1.14

一个n(n1)维卡氏积{0,1}n到{0,1}的函数称为一个n元真值函数。设F是一个n元真值函数，则可记为F：{0,1}n{0,1}n个命题变项，共有2n个可能的赋值，对于每个赋值真值函数的函数值非0即1，于是n个命题变元共可以形成22个不同的真值函数。见教材P13表1.6

n命题公式与真值函数

对于任何一个含n个命题变项的命题公式A，都存在惟一的一个n元真值函数F为A的真值表.等值的公式对应的真值函数相同.下表给出所有2元真值函数对应的真值表,每一个含2个命题变项的公式的真值表都可以在下表中找到.

例如：pq,pq,(pq)((pq)q)等都对应表中的2元真值函数对应的真值表其实，每个真值函数可对应无穷多个命题公式，它们彼此都是等值的，有很多公式具有相同的真值表。如：……………还有p∨q、pq等定义1.15

在一个联结词的集合中，如果一个联结词可由集合中的其他联结词定义，则称此联结词为冗余的联结词，否则称为独立的联结词。前面给出的5个联结词组成的联结词集为{，，，，}，由于

pqp

q

p

q(pq)(qp)(p

q)(q

p

)所以，都是冗余的，又{，，，}中，由于p

q(pq)(pq)所以可看成是冗余的，但在{,}中无冗余的联结词定义1.16

若任一真值函数都可以用仅含某一联结词的命题公式表示，则称该联结词集为全功能集。若一个联结词集的全功能集中不含冗余的的联结词，则称它为极小全功能集例1.13

若已知{，}是全功能集，证明{，}也是

全功能集证明由于{，}是全功能集，因而任一真值函数均可由仅含{，}中的联结词的命题公式表示，而对于任意的命题形式A，B，有

ABAB因而任一真值函数均可由含{，}中的联结词的命题公式表示，所以它是全功能集。联结词的全功能集实例

(1)S1={,,,}(2)S2={,,,,}

(3)S3={,}(4)S4={,}(5)S5={,}(6)S6={}(7)S7={}

定义1.1.7

在仅含联结词,,的命题公式A中，将换成，换成,若A中含0或1，就将0换成1，1换成0，所得命题公式称为A的对偶式，记作A*。从定义不难看出，(A*)*=A如:公式P(QF)的对偶公式为P(QF)定理1.2

设A和A*互为对偶式，设p1,…,pn是出现在A和A*

中的全部的命题变项，若将A和A*

写成n元函数形式，则①

A(P1,P2,…,Pn)A*(P1,P2,…,Pn);②

A(P1,P2,…,Pn)A*(P1,P2,…,Pn).§1.5对偶与范式定理1.3

(对偶原理)

设A、B为两命题公式，若AB，则A*B*

其中A*，B*

分别为A，B的对偶式。由对偶原理可知，若A为重言式，则A*必为矛盾式，反之亦然.

给定一个命题公式，判断它是重言式、矛盾式、还是可满足式，这类问题称为判定问题。

判定的方法都有哪些？析取范式与合取范式

———含n个命题变项的公式两种规范表示方法定义1.18文字：命题变项及其否定统称为文字。如：p,

q简单析取式：仅有有限个文字组成的析取式。如：p,

q,p∨q,p∨

q∨r简单合取式：仅有有限个文字组成的合取式。如：p,

q,p∧q,p∧

q∧r

命题公式是千变万化的，这给研究命题演算带来困难，这里我们研究如何由一个命题公式化归为一个标准形式的问题，这样命题演算的研究问题就归结为对标准形式的研究问题，这种标准形式就叫范式。析取范式(参考课本上的定义)

它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个析取式，式中的每个析取项是个合取式，每个合取式中只包含命题变元或命题变元的否定。例如p∨(p∧q)∨(q∧r)

此式即具有析取范式之形式注意:一个公式的析取范式并不唯一，如p∨(r∧q),可以写成(p∧p)∨(r∧q)合取范式它是这样一种标准形式，在此式内不出现联结词及，否定符号只出现在命题变元前。它是一个合取式，式中的每个合取项是个析取式，每个析取式中只包含命题变元或命题变元的否定。例如p∧(p∨q)∧

(q∨r)

此式即具有合取范式之形式注意:一个公式的合取范式并不唯一，如p∧

(r∨

q)

可以写成(p∨p)∧(r∨

q)定义1.9析取范式：由有限个简单合取式构成的析取式。如：p∨

q,(p

∧q)∨(p∧

q∧r)合取范式：由有限个简单析取式构成的合取式。如：p∧q,（p∨q）∧（

p∨q∨r）范式：析取范式与合取范式统称为范式。设Ai(i=1,2,3,…n)为简单合取式，则A=A1∨A2∨……∨An

就是析取范式，而B=A1∧A2∧……∧An

就是合取范式。析取范式和合取范式有下列性质：

（1）一个析取范式是矛盾式它的每个简单合取式都是矛盾式。（2）一个合取范式是重言式它的每个简单析取式都是重言式。定理1.4(范式存在定理)

任一个命题公式都存在着与之等值的析取范式与合取范式。求范式的具体步骤：（1）消去对{,∧,∨,}来说冗余的联结词，即{，}。利用下列等值式：

AB(A∨B)AB(A∨B)∧(A∨

B)（2）否定词的消去或内移。

利用下列等值式：

AB(A∨B)

(A∨B)A∧B

(A∧B)A∨B（3）利用分配律：

C∧(A∨B)（C∧A）∨（C∧B）

C∨(A∧B)（C∨A）∧（C∨B）例1.14求下列公式的析取范式与合取范式(1)A=(pq)r解(pq)r(pq)r

（消去）

pqr

（结合律）

这既是A的析取范式（由3个简单合取式组成的析取式），又是A的合取范式（由一个简单析取式组成的合取式）(2)B=(pq)r解(pq)r(pq)r

（消去第一个）

(pq)r

（消去第二个）

(pq)r

（否定号内移——德摩根律）这一步已为析取范式（两个简单合取式构成）继续：(pq)r

(pr)(qr)（对分配律）这一步得到合取范式（由两个简单析取式构成）(3)

求(pq)∧(pr)的析取范式。解：(pq)∧(pr)

(p∨q)∧(p∨r)((p∨q)∧p)

∨((p∨q)∧r)((p∧p)∨(q∧p))∨((p∧r)∨(q∧r))(q∧p)∨(p∧r)∨(q∧r)(4)

求(pq)∧(pr)的合取范式。解：(pq)∧(pr)

(p∨q)∧(p∨r)定义1.20极小项/极大项在含有n个命题变项的简单合取式(简单析取式)中，若每个命题变项均以文字的形式在其中出现且仅出现一次，而且第i（1in）个文字出现在左起第i位上，称这样的简单合取式（简单析取式）为极小项（极大项）.由p,q两个命题变项形成的极小项与极大项

M0M1M2M3

p

qp

qp

qp

q名称公式

00011011p

q

p

q

p

q

p

q

m0m1m2m3

00011011成假赋值公式名称成真赋值极大项

极小项

说明：

1:n个命题变项产生2n个极小项和2n个极大项

2:2n个极小项（极大项）均互不等值

3:用mi表示第i个极小项，其中i是该极小项成真赋值的十进制表示;4:用Mi表示第i个极大项，其中i是该极大项成假赋值的十进制表示;

mi(Mi)称为极小项(极大项)的名称.

由p,q,r三个命题变项形成的极小项与极大项

极小项与极大项关系设mi和Mi是命题变项p1

，

p2

，…pn形成的极小项和极大项，则

mi

Mi

，

Mi

mi定义1.21

设由n个命题变项构成的析（合）取范式中所有的简单合（析）取式都是极小（大）项，则称该析（合）取范式为主析（合）取范式。由不同最小项所组成的析取式称为主析取范式由不同最大项所组成的合取式称为主合取范式定理

1.5任何命题公式都存在着与之等值的主析取范式和主合取范式,并且是惟一的.

用等值演算法求公式的主范式的步骤：

(1)先求析取范式（合取范式）

(2)将不是极小项（极大项）的简单合取式（简单析取式）化成与之等值的若干个极小项的析取（极大项的合取），需要利用同一律（零律）、排中律（矛盾律）、分配律、幂等律等.(3)极小项（极大项）用名称mi（Mi）表示，并按角标从小到大顺序排序.

例1.15某公司要从赵、钱、孙、李、周五名新毕业的大学生中选派一些人出国学习.选派必须满足以下条件：

(1)若赵去，钱也去；

(2)李、周两人中至少有一人去；

(3)钱、孙两人中有一人去且仅去一人；

(4)孙、李两人同去或同不去；

(5)若周去，则赵、钱也去.

试用主析取范式法分析该公司如何选派他们出国？解此类问题的步骤为：①将简单命题符号化②写出各复合命题③写出由②中复合命题组成的合取式④求③中所得公式的主析取范式解

①

设p：派赵去，q：派钱去，r：派孙去，s：派李去，u：派周去.②(1)(pq)(2)(su)(3)((qr)(qr))(4)((rs)(rs))(5)(u(pq))

③(1)~(5)构成的合取式为

A=(pq)(su)((qr)(qr))((rs)(rs))(u(pq))

④A(pqrsu)(pqrsu)结论：由④可知，A的成真赋值为00110与11001，因而派孙、李去（赵、钱、周不去）或派赵、钱、周去（孙、李不去）.

A的演算过程如下:A

(pq)((qr)(qr))(su)(u(pq))((rs)(rs))（交换律)B1=(pq)((qr)(qr))((pqr)(pqr)(qr))(分配律)B2=(su)(u(pq))((su)(pqs)(pqu))（分配律）B1B2(pqrsu)(pqrsu)(qrsu)(pqrs)(pqru)再令

B3=((rs)(rs))得A

B1B2B3(pqrsu)(pqrsu)注意：在以上演算中多次用矛盾律要求：自己演算一遍

例1.17

求(pq)∧(pr)的主析取范式。解法1：

Pqrppqpr(pq)∧(pr)00010100

0

11010010111101111111000100101011111001001110111所以：(pq)∧(pr)m2∨m3∨m5∨m7(2,3,5,7)解法2：

(pq)∧(pr)(q∧p)∨(p∧r)∨(q∧r)(析取范式)((p∧r)∧(q∨q))∨((p∧q)∧(r∨r))

∨((q∧r)∧(p∨p))……(p∧q∧r)∨

(p∧q∧r)∨(p∧q∧r)∨(p∧q∧r)

(主析取范式)m2∨m3∨m5∨m7(2,3,5,7)例1.20判断命题公式(p∨(q∧r))(p∨q∨r)的类型解：(p∨(q∧

r))(p∨

q

∨

r)(p∨(q∧

r))∨(p∨

q

∨

r)(

p∧

(q∧

r))∨p∨

q

∨

r(

p∧(q

∨

r))∨p∨

q

∨

r((

p∧

q)

∨

(

p∧

r))

∨p∨

q

∨

rm0∨m1∨m2∨m3

∨m4∨m5

m6∨m7成真赋值：000、001、010、011、100、101、110、111该命题公式为重言式提示:用真值表判断命题公式的类型是最常用的方法主析取范式的用途（主合取范式类似讨论）：1、求公式的成真/成假赋值：若公式A中含有n个命题变项，且A的主析取范式含s个极小项，则A有s个成真赋值，有2n-s个成假赋值。2、判断公式的类型：设公式A中含有n个命题变项，则：（1）A为重言式A的主析取范式含全部2n个极小项。（2）A为矛盾式A的主析取范式不含任何极小项，记A的主析取范式为0。（3）A为可满足式A的主析取范式至少含一个极小项。3、判断两个命题是否等值：设公式A、B中共含有n个命题变项，按n个命题变项求出A、B的主析取范式A`、B`。若A`=B`，则AB，否则A、B不等值。例1.21

判断下列命题公式是否等值

(1)(pq)∧(p

r)与

p(q∧r)(2)p(q∧r)与p∨(qr)

pqr

q∧r

pqp

r(pq)∧(p

r)

p(q∧r)

0000111100101111010011110111111110000000101001001100100011111111命题公式(pq)∧(p

r)与p(q∧r)等值

pqr

q∧rqr

p(q∧r)

p∨(qr)

00001110010111010001001111111000101101010111000011111111命题公式p(q∧r)与p∨(qr)不等值注意：

AB

当且仅当

A、B含有相同的真值表或A、B有相同的主析（合）取范式。§1.6推理理论

推理是从前提推出结论的思维过程，前提是指已知的命题公式，结论是从前提出发应用推理规则推出的命题公式，前提可多个.由前提A1，A2，…Ak推出结论B的严格定义如下：定义1.24

若(A1∧A2∧…∧Ak)B为重言式，则称A1，A2，…Ak，推出结论B的推理正确，B是A1，A2，…Ak，的逻辑结论或有效结论，称(A1∧A2∧…∧Ak)B为由前提A1，A2，…Ak推结论B的推理的形式结构。用“AB”表示“AB”是重言式，由前提A1，A2，…Ak推B的推理正确,也记:(A1∧A2∧…∧Ak)B

对于任一组赋值，前提和结论的取值有以下四种情况：

①{A1，A2，…Ak}为0，B为0。√②{A1，A2，…Ak}为0，B为1。√③{A1，A2，…Ak}为1，B为0。×④{A1，A2，…Ak}为1，B为1。√推理的另一种形式：命题公式A1，A2，…Ak推B的推理正确当且仅当

(A1∧

A2∧

…∧Ak)B为重言式。于是推理的一般形式可转化为：

(A1

∧A2

∧…∧Ak)B推理正确转化为：

A1

∧A2

∧…∧Ak

B于是，以后推理的形式就写作：前提：p,pq

结论：q推理的形式结构：

(p

∧(pq))q即只需证明蕴涵式(p∧(pq))q为重言式。三种方法：

1、真值表法；

2、等值演算法；

3、主析取范式法。例1.23：判断下列推理是否正确。1.今天小张或去网吧或去教室。他没去教室，所以他去网吧了。设p：小张去网吧。q：小张去教室。则，前提：p∨q,¬q

结论：p

推理的形式结构：

((p∨q)

∧¬q)p解法1：真值表法该命题公式为重言式，说明推理正确，所以小张去网吧解法2：等值演算法：((p∨q)

∧¬q)p

((p∧¬q)∨(q∧¬q))p(p∧

¬

q)p

¬

(p∧

¬

q)∨

p

¬p

∨

q

∨

p

1所以，推理正确，即（(p∨q)

∧¬q)

p推理定律——重言蕴涵式

重要的推理定律

(1)A

Þ(AÚB)附加律

(2)(AÙB)Þ

A

化简律

(3)(A®B)ÙA

Þ

B

假言推理

(4)(A®B)ÙØB

Þ

ØA

拒取式

(5)(AÚB)ÙØB

Þ

A

析取三段论

(6)(A®B)Ù(B®C)Þ(A®C)假言三段论

(7)(A«B)Ù(B«C)Þ(A«C)等价三段论

(8)(A®B)Ù(C®D)Ù(AÚC)Þ(BÚD)构造性二难(3)(¬A∨B)∧A(¬A∧A)∨(A∧B)(A∧B)A推理定律(续)(9)(A®B)Ù(ØA®B)Ù(AÚØA)Þ

B

构造性二难（特殊形式）(10)(A®B)Ù(C®D)Ù(ØBÚØD)Þ(ØAÚØC)破坏性二难说明：

A,B,C为元语言符号若某推理符合某条推理定律，则它自然是正确的AÛB产生两条推理定律:AÞB,BÞA构造证明——直接证明法例1.27构造下面推理的证明：若明天是星期一或星期三，我就有课.若有课，今天必备课.我今天下午没备课.所以，明天不是星期一和星期三.解

设p：明天是星期一，q：明天是星期三，

r：我有课，s：我备课形式结构为前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq

形式结构为前提：(pÚq)®r,r®s,Øs

结论：ØpÙØq证明

①r®s

前提引入

②Øs

前提引入

③Ør①②拒取式

④(pÚq)®r

前提引入

⑤Ø(pÚq)③④拒取式

⑥ØpÙØq⑤置换直接证明法(续)根据前面八条推理定律，可得下面推理规则。用A1，A2，…Ak|=B表示B是A1，A2，…Ak的逻辑结论。(1)A

B,

A|=

B假言推理规则(2)A|=

A∨B附加规则(3)A∧B|=

A化简规则(4)A

B,

¬

B

|=

¬

A

拒取式规则(5)AB,BC|=AC假言三段论规则(6)A∨

B,

¬

A

|=

B析取三