工科离散数学-第1章-命题逻辑

iS离散数学DiscreteMathematicsrCDDiscretemathematicsisthestudyofmathematicalstructuresthatarefundamentallydiscreteratherthancontinuous.Incontrasttorealnumbersthathavethepropertyofvarying"smoothly",theobjectsstudiedindiscretemathematics–suchasintegers,graphs,andstatementsinlogic–donotvarysmoothlyinthisway,buthavedistinct,separatedvalues..ete工科目录08图论06运算与代数系统02谓词逻辑03集合的概念与运算04关系05函数01命题逻辑07环、域、格、布尔代数索引第一章命题逻辑命题，逻辑联结词，命题公式的翻译，命题公式的值与等价，范式，推理理论1.1

命题1.2

逻辑联结词1.3

命题公式与真值表1.4

命题翻译1.6

范式1.7

推理理论1.5

命题翻译1.1

命题

概念：是指反映事物的本质属性的思维形式，是思维的基本单位。判断：是指对事物是否具有某种属性，即是否符合某概念进行肯定或否定的回答。推理：是指由一个或几个判断推出另一个判断的思维形式。两类逻辑：逻辑分为辩证逻辑和形式逻辑两种。形式逻辑所研究的思维的形式结构，就是指概念、判断和推理之间的结构和关系。现代形式逻辑利用数学方法或者说借助符号体系进行推理规律的研究，因此，也称其为数理逻辑或符号逻辑，是指利用数学方法或者说借助符号体系研究推理规律的科学，目的就是利用计算的方法来代替人们思维中的逻辑推理过程。

1.1命题[定义1-1：命题]表达判断的可判别真假的陈述句称为命题(proposition,statement)。一个命题所表达判断的或“真”、“假”结果称为命题的值或真值(truth)。命题一般用字母表示，如p或P。如，p：沈阳是一个大城市。若命题的值为真，可用T、1或“真”表示；若值为假用F、0或“假”表示。代表一个固定的命题的p是命题常量（propositionconstant）。在p可以任意指代时称为命题变元（propositionvariable）。不可再拆分的命题称为原子命题（atom）或简单命题，由原子命题与联结词构成的命题称为复合命题（compoundproposition）。

1.1命题[例1-1]将下述命题用符号表示：(1)日本人民是伟大的。(2)雪是黑的。(3)1+101=110。(4)火星上有生物。(5)一个偶数可表示成两个素数之和。

(6)x+y=z。(7)(a)动作快点！

(b)天安门真雄伟啊！(c)请给我一杯茶。

(d)你掌握命题的概念了吗？(8)我正在说谎。

(9)我只给不给自己刮胡子的人刮胡子。(10)如果天气好，我就去散步。解：(1)是，1；(2)是，0；(3)是，？；(4)是，？；(5)是，？；(6)否；(7)、(8)、(9)否，悖论；(10)是，复合命题。

1.1命题在逻辑学中，命题与判断是两个既有联系又有区别的概念，命题是对事物情况的陈述，判断是对思维对象有所断定的思维形式，是断定者在一定时空条件下对一个命题是真或假的断言。因此，判断一定是命题，而命题不一定是判断。例如，“火星上有生物。”是命题，但没有经过证实，不是判断。1.2

逻辑联结词

[否定┐]。若p为命题，新命题┐p是对p的否定（negation，not）。┐p的值与p相反，读作“非P”。1.2.1

基本联结词[例1-2]令p：沈阳是一个大城市。则p的否定为┐p。可以叙述为：(a)沈阳不是一个大城市。

(b)沈阳是一个不大的城市。(c)沈阳是一个大城市不真。思考：自然语言表示不唯一，符号表示才是唯一的。C语言中的!1.2.1

基本联结词

[否定┐]。若p为命题，新命题┐p是对p的否定（negation，not）。┐p的值与p相反，读作“非p”。[例1-2]令p：沈阳是一个大城市。则p的否定为┐p。可以叙述为：(a)沈阳不是一个大城市。

(b)沈阳是一个不大的城市。(c)沈阳是一个大城市不真。思考：自然语言表示不唯一，符号表示才是唯一的。C语言中的!

1.2.1基本联结词[合取∧]（逻辑积）。命题p和q的合取（conjunction，and）构成新命题p∧q，读作“p与q”或“p与q的合取”。当且仅当p和q都为1时，p∧q为1，否则为0。

p∧q表示按逻辑求积，即p∧q=p×q，规则是：1×1=1，1×0=0，0×1=1，0×0=0[例1-3]令p：sinx是奇函数，q：ex是奇函数。p：道路曲折，q：前途光明。（转折）则命题“不仅sinx是奇函数，ex也是奇函数”、“道路虽然曲折，但前途光明”可表示为p∧q。C语言中的&&

1.2.1基本联结词[析取⋁]（逻辑和）。命题p和q的(可兼)析取（inclusiveor）构成新命题p∨q，读作“p或q”或“p与q的析取”。当且仅当p和q都为0时，p∨q为0，否则为1。

p∨q表示按逻辑求和，即p∨q=p+q，规则是：1+1=2（逻辑意义仍是1），1+0=1，0+1=1，0+0=0[例1-4]令p：马云是阿里巴巴集团主席，q：马云是阿里巴巴集团首席执行官。则命题“马云是阿里巴巴集团主席或首席执行官”可表示为p∨q。C语言中的||

1.2.1基本联结词[不可兼析取¯

∨]。命题p和q的不可兼析取（exclusiveor，或不可兼或、排斥或）构成新命题

p¯

∨q

，用于描述两者不能兼有的情况，即p、q都为1或0时，p¯

∨

q

为0。否则为1。[应用]

绘图软件中拉伸线条的橡皮筋等功能。例=>明天晴天或下雨。

不可兼析取¯⋁与著名的异或运算（XOR）相对应，也可用⨁表示。对于任意的命题P，它有非常好的性质：p¯

∨

0=p，p

¯

∨

1=┐p，p¯

∨

p=0

1.2.1基本联结词[条件→]。命题p条件q（conditional）构成新命题p→q。读作“p则q”，或“p条件q“，或“如果p那么q“，或“只要p就q“。当且仅当p为1而q为0时，p→q为0，否则为1。例=>

令p：函数f(x)在x0处可导，q：f(x)在x0处连续。则命题“如果函数f(x)在x0处可导，则f(x)在x0处连续”表示成p→q。思考：

真值的规定被称为善意的推断：前件为0时，不须考虑后件。[示例]“如果我中了彩票，我把一半奖金分给你”。当我没中彩票时，无论分给你与否都不食言。假设不成立，一切休提。

1.2.1基本联结词[双条件↔]。命题p双条件q（biconditional）构成新命题p↔q。读作“p双条件q“或“p当且仅当q“。当且仅当p和q的值相同时p

↔q为1，否则为0。

命题p↔q表示p和q互为充分必要条件。[例1-6]>令：p：你可以坐飞机，q：你买了机票。则命题“你可以坐飞机当且仅当你买了机票”可表示为p↔q。

1.2.1基本联结词

在以上6个联结词中，┐、∧、∨是最基本的联结词，其他联结词都可由它们表示出来。两种重要的转换关系是：试一试：

逻辑联结词的用处广泛，网页中普遍采用逻辑运算进行信息检索，也称作布尔逻辑搜索。

p¯

∨

q=(p⋀┐q)⋁(┐p⋀q)

p¯

∨

q

=┐(p↔q)

[与非↑]命题p与非q(notand)构成新命题p↑q，含义是p↑q=┐(p⋀q)。[或非↓]命题p与或q（notor）构成新命题p↓q，含义是p↓q=┐(p⋁q)。[条件否定

→C

]命题p条件否定q（notifthen）为新命题

p

→C

q，含义是：

p

→C

q

⇔┐(p→q)分析真值的情况可说明，合取、析取、不可兼析取、与非、或非都满足交换律和结合律。1.2.2

其他联接词1.3

命题公式与真值表

1.3.1命题公式

[定义]命题演算的合式公式（well-formedformula，wff）定义为：(1)单个命题变元或常量本身是一个合式公式。(2)如果

A是合式公式，那么是合式公式。(3)如果

A和

B是合式公式，那么

A⋀B、A⋁B、

A¯⋁

B

、A→B和A↔B、A↑B、A↓B和A

→C

B都是合式公式。(4)当且仅当能够有限次地应用(1)、(2)、(3)所得到的包含命题变元、联结词和括号的符号串是合式公式。组成合式公式的命题变元可称为公式的“分量”。

1.3.1命题公式

[不严格解释]由命题常量、变元和联结词组成的有意义式子就是合式公式。[联结词（运算符）的优先次序]┐优先于⋀优先于⋁优先于→优先于↔。比较：因为含有值未知的命题变元，导致命题公式的值不确定，不能称为命题。一个含有n个原子变元的命题公式A与n元数学函数f意义相同：A(p1,p2,…,pn)=(p1⋁p2)→⋯f(x1,x2,…,xn)=(x1+x2)*⋯它们没有本质区别，但x1~xn通常取连续区间的实数，f亦然。相对地，p1~pn仅取值为1或0，A本身亦如此。

从这一点上说，命题公式比一般数学表达式更简单。同时，命题公式也称为“命题函数”，公式中的分量就是函数的自变量。例=>p⋁q→r等同于(p⋁q)→r，但不等同于p⋁(q→r)。1.3.2

真值表

[定义]若p1,p2,...,pn是出现在命题公式A中的所有原子变元，任意指定p1,p2,...,pn的一组真值称为A的一个解释（Interpretation），也称指派或赋值（assign）。简言之，对一个命题公式的一次解释就是对其所有原子变元的一次赋值。

n个原子变元组成的命题有2n种赋值。例=>命题公式p⋀q的2个原子变元共有22=4个解释，分别是11、10、01和00。

1.3.2真值表

pq┐p┐q┐p→┐q11000101100111000011[定义]将一个命题中原子变元的所有赋值与对应命题的真值汇聚成表称为真值表（truthtable）=>运算表。pqp⋀q111100010000表1-1公式p⋀q的真值表表1-2公式┐p→┐q的真值表用于规定一个联结词组成的复合命题公式的真值表就是程序语言中的运算表。

1.3.2

真值表pq┐pp⋀qp⋁qp→qp↔qp¯

∨

q

p↑qp↓qp

→C

q11011110000100010011010110110110000100110110注意：

若有

n个命题变元，应按2n-1

0或0

2n-1的顺序将这些整数转换为

n位二进制串排列即可，如11、10、01、00。表1-39个联接词的真值表1.4

命题翻译

1.4.1合取命题

自然语言中的典型合取联接词：和、且、既-又、不但-而且、并列句、转折句等。[例1-7]将下述命题用符号表示。(1)黄渤既聪明又勤学苦练。 (2)黄渤聪明，而且勤学苦练。(3)中国人民是勤劳和勇敢的。 (4)你是好人，他不是好人。(并列)(5)他虽然聪明但不用功。(6)我努力了，可是没有达到理想的效果。(转折)(7)张三或李四都可以做这件事。(用“或”，但重在“都”，不规范说法)

1.4.1合取命题解：均应表示为两个命题的合取。如(3)，令p：中国人民是勤劳的，q：中国人民是勇敢的。则原命题表示为：p⋀q。注意：原子命题中不能含联结词，且需要根据上下文补足句子中省略的成分。

1.4.1合取命题注意：汉语的“和”、“与”有特殊用法，仅表示原子命题，不能用合取表示。例=>(1)中国和巴基斯坦是全天候战略合作伙伴。(2)吾与汝毕力平险。思考：怎么衡量“p与q”、“p和q”这样的命题是原子还是复合命题呢？

如果句子的谓语部分反映的是人或物（如

p和q）之间的关系或者共同完成的事情则是原子命题，否则是复合命题。思考：“科比和詹姆斯都是NBA明星。”是什么命题？1.4.2析取命题

自然语言中的典型析取联接词：或、或者、亦或等。[例1-8]将下述命题用符号表示。(1)王学东爱听音乐或爱看电影。(2)张朝阳昨天一口气做了20或30道习题。解：(1)可表示为两个原子命题p和q的析取p⋁q。(2)这里的“或”表示不确定估计，代表一个模糊的量，视为原子命题更合适。注意：在遇到联接词“或”时，第一件要做的事情不是符号表示，而是分析它是可兼或还是不可兼或。

1.4.2析取命题[例1-9]将下述命题用符号表示：(1)马拉松比赛在明天上午9点或者下午2点举行。(2)我要出去看电影或者在家看电视。(3)黄渤可能是100米赛跑或400米赛跑的冠军（如果每人只限于一项）。(4)黄渤住在202或203房间。解：

因为两个原子命题不能同时为真，应表示为两原子p和q的不可兼析取p¯

∨

q

从意义或值的角度出发，也可以表示为(p⋀┐q)⋁(┐p⋀q)，或┐(p↔q)。1.4.3条件命题

[自然语言中的典型条件分两类](1)只要-就型。联接词有：当、如果-那么、因为-所以等，表示充分条件。(2)只有-才型。联接词有：仅当、除非等，表示必要条件。1.只要-就型[例1-10]将下述命题用符号表示：(1)因为感染了病毒，所以系统运行不正常。(2)只要努力，就一定会成功。 (3)当山花开的时候，你爹就回来了。解：

若p表示前件，分别是：(1)p：感染了病毒，(2)p：努力，(3)p：山花开的时候。q表示后件，分别是：(1)q：系统运行不正常，(2)q：一定会成功，(3)q：你爹回来了。上述复合命题均可符号表示为：p→q。

1.4.3条件命题[例]将下述命题用符号表示：(1)只有通过基础测试才能参加正式比赛。

(2)爱拼才会赢。(3)仅当你尽了全力，才能打赢这一仗。

(4)除非你尽了全力，才能打赢这一仗。(5)除非你尽了全力，否则不能打赢这一仗。2.只有-才型解：若p表示后件，分别是：(1)通过基础测试，(2)爱拼，(3)尽了全力。令q表示前件，分别为：(1)才能参加正式比赛，(2)会赢，(3)打赢这一仗。符号化为：q→p。

1.4.3条件命题思考：(1)当且仅当（ifandonlyif，或iff）当p就q+仅当p才q=当且仅当p则q当=只要就仅当=只有才(2)除非除非=如果不表述：除非p，否则非q（则q）。直译为：┐p→┐q等同于q→p1.4.4多联结词命题

[例1-12(1)]我们要做到身体好、学习好、工作好，为祖国繁荣昌盛而奋斗。解：记p：我们要做到身体好。q：我们要做到学习好。r：我们要做到工作好。s：我们要为祖国繁荣昌盛而奋斗。命题可形式化为(p⋀q⋀r)↔s[例1-12(2)]春天来了，燕子飞回来了。解：

记p：春天来了。q：燕子飞回来了。命题可形式化为p↔q

1.4.4多联结词命题[例1-12(3)]我没收到他的信。可见，要么他没给我写信，要么信在邮寄途中丢失了。[例1-12(4)]假如上午不下雨，我去图书馆，否则就在家里读书或写作业。解：

记p：上午下雨。q：我去图书馆。r：我在家里读书或写作业。符号化为(┐p→q)⋀(p→r)思考：为什么不能表示成不可兼析取(┐p→q)¯

∨

(p→r)呢？解：

记p：我没收到他的信。q：他没给我写信。r：信在邮寄途中丢失了。命题可形式化为p→(p¯

∨

q

)

1.4.4多联结词命题[例1-12(5)]人不犯我，我不犯人；人若犯我，我必犯人。解：

记p：人犯我。q：我犯人。命题可形式化为(┐p→┐q)⋀(p→q)[例1-12(6)]一个人起初说，“占据空间的、有质量的而且不断变化的叫做物质”。后来他改说，“占据空间的有质量的叫做物质，而物质是不断变化的”。符号化这两个命题以反映出二者的差异。解：

记p：某种东西占据空间。q：某种东西有质量。r：某种东西不断变化。s：某种东西叫做物质。两次说法可分别形式化为

(p⋀q⋀r)↔s(p⋀q↔s)⋀(s→r)注意：

给一个概念下定义要用双条件来形式化，即“描述↔概念”。

1.4.4多联结词命题[例1-12(7)]如果你来了，那么他唱不唱歌将看你是否伴奏而定。解：

记p：你来了。q：他唱歌。r：你伴奏。命题可分别形式化为

p→(q↔s)1.5

命题公式的值与等价

1.5.1命题公式的种类

[定义]假设

A是一个命题公式。若无论原子变元如何赋值，A都为真，则

A是永真式或重言式（tautology）。若对原子变元的任何赋值，A都为假，则

A是永假式或矛盾式（contradiction）。若至少存在一组赋值使A都为真，则A是可满足式（contingency）。例=>无论p和q表示什么命题，p⋀┐p、(p⋁q)⋀┐(p⋁q)都是永假式，p⋁┐p、(p→q)⋁┐(p→q)都是永真式。比较：

一个命题公式A：A(p1,p2,...,pn)=(p1⋁p2)→⋯与一个数学函数f一致：f(x1,x2,...,xn)=(x1+x2)∗⋯

1.5.1命题公式的种类[永真式代入定理]若命题A(p1,p2,…,pn)为永真式，则分别用q1,q2,…,qn替换A中的命题变元p1,p2,…,pn，所得到的公式仍为永真式。定理本质是反映永真式的真值与命题变元的取值无关。例=>命题┐(p∧q)⋁(p∧q)为永真式，用r、s替换p、q得到的命题┐(r∧s)⋁(r∧s)仍为永真式。1.5.2命题公式的等价

[定义]若命题公式A(p1,p2,…,pn)和B(p1,p2,…,pn)有相同的原子变元，且对p1,p2,…,pn的每组赋值，A和B的值都相同，则公式A和B相等，称为A和B等价（logicalequivalence）或等值，记做A⟺B，或A≡B。思考：命题公式等价就是命题函数相等。[结果]若A(p1,p2,…,pn)⟺B(p1,p2,…,pn)，有A(┐p1,┐p2,…,┐pn)⟺B(┐p1,┐p2,…,┐pn)主要有3种证明两公式等价的方法。

1.5.2命题公式的等价(1)真值表法[例]

证明公式p→q⟺┐p∨q和p¯

∨

q⟺(p⋀┐q)⋁(┐p⋀q)。pqp→q┐p∨qp¯

∨

qp⋀┐q┐p⋀q(p⋀┐q)⋁(┐p⋀q)11110000100011010111101100110000[说明]利用真值表法很容易验证一些基本的算律，如交换律、结合律、分配律，德•摩根律等。

1.5.2命题公式的等价(2)等价变换法如果一个公式中的一部分也是命题公式，一般称其为原公式的“子公式”。[等价置换规则]若X是A的子公式，且X⟺Y。若在A中用Y部分或全部替换X得到B，则A⟺B。实质：利用对命题公式本身或其子公式进行等价替换不改变原公式的值。[例1-13]证明p→(q→r)⟺q→(p→r)。证明：

p→(q→r)⇔(原公式等价变换)┐p∨(q→r) ⇔(子公式等价变换)┐p∨(┐q∨r)⇔(交换律、结合律)┐q∨(┐p∨r)⇔(子公式等价变换、原公式等价变换)q→(p→r)

1.5.2命题公式的等价(3)双条件式永真法[定理]对于命题公式A和B，A⟺B当且仅当A↔B为永真式。

A↔B只在A与B具有相同值时为真，结论显然。

这是一个需要熟悉的定理，可以作为“命题公式等价的判定定理”。[定理的等价描述]由于A↔B⟺(A→B)⋀(B→A)，定理可等价叙述为：

A⟺B当且仅当A→B和B→A均为永真式。

1.5.2命题公式的等价序号等价关系含义E1┐┐p

p对合律（双重否定律）E2p∧q

q∧p交换律E3p∨q

q∨pE4(p∧q)∧r

p∧(q∧r)结合律E5(p∨q)∨r

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

(p∧q)∨(p∧r)分配律E7p∨(q∧r)

(p∨q)∧(p∨r)E8┐(p∧q)

┐p∨┐q德•摩根律E9┐(p∨q)

┐p∧┐q基本等价关系表1-5

1.5.2命题公式的等价

序号等价关系含义（续表）E10p∨p

p等幂律E11p∧p

pE12q∨(p∧┐p)

q同一律E13q∧(p∨┐p)

qE14q∨(p∨┐p)

1零律E15q∧(p∧┐p)

0E16p

q

┐p∨q蕴含等值E17┐(p

q)

p∧┐qE18p

q

┐q

┐p假言易位E19p

(q

r)

(p∧q)

r

1.5.2命题公式的等价

序号等价关系含义（续表）E20p↔q

(p

q)∧(q

p)等价等值E21p↔q

(p∧q)∨(┐p∧┐q)E22┐(p↔q)

p↔┐qE23p↔q

┐p↔┐q等价否定等值E24(p

q)∧(p

┐q)

┐p归谬论E25p¯

∨

q

┐(p↔q)E26p¯

∨

q

(p∧┐q)∨(┐p∧q)1.5.3联结词功能完备集

因为2个原子变元有4种赋值，而对应每组赋值，命题的值有2种可能，故共有24种可能。通过列表可说明，9个联结词组成的联结词集合是联结词功能完备集（completegroupofconnectives）。联结词功能完备集就是指任何命题可以由此集合中的联结词表示出来。

由p→q⟺┐p⋁q，p

→C

q⟺┐(p→q)，

p¯

∨

q⟺┐(p↔q)，

p↔q⟺(p→q)⋀(q→p)，p↑q⟺┐(p⋀q)，p↓q⟺┐(p⋁q)说明其他联结词均可由┐、⋀、⋁表示，故{┐,⋀,⋁}是功能完备的。

由p↑p⟺┐p，(p↑p)↑(q↑q)⟺p⋁q，(p↑q)↑(p↑q)⟺p⋀q，

p↓p⟺┐p，(p↓p)↓(q↓q)⟺p⋀q，(p↓q)↓(p↓q)⟺p⋁q说明{↑}、{↓}都是联结词功能完备集。1.5.4由德•摩根律到对偶原理

命题运算中的德•摩根律：┐(p⋀q)⟺┐p⋁┐q，┐(p⋁q)⟺┐p⋀┐q思考：公式成对，变元也不止2个，下述公式会如何？┐((p⋀q)⋁r)⟺?，┐((p⋁q)⋀r)⟺?[定义]将一个公式A中所有的∧换成∨，∨换成∧，1换成0，0换成1，得到的公式A*称为A的对偶式。其实，A和A*互为对偶。例=>1与0互为对偶，(p⋀q)⋁r与(p⋁q)⋀r互为对偶，p↑q⟺┐(p⋀q)与┐(p⋁q)⟺p↓q互为对偶。实质：求对偶式没有否定什么事！

1.5.4由德•摩根律到对偶原理[对偶原理]设A和A*是对偶式，p1，p2，...，pn是公式中包含的原子变元，则┐A(p1，p2，...，pn)⟺A*(┐p1，┐p2，...，┐pn)。[定理]若A⟺B，则A*⟺B*。证明：因为A⟺B，有A(┐p1，┐p2，...，┐pn)⟺B(┐p1，┐p2，...，┐pn)，于是，有┐A(┐p1，┐p2，...，┐pn)⟺┐B(┐p1，┐p2，...，┐pn)，即A*⟺B*。定理说明，同一个公式不可能有两个不一样的对偶式，换言之，两个公式相等则它们的对偶式相等。推广的德摩根律1.6

范式

有一种重要的衡量公式是否等价的方法是将各公式转换成标准形式，这种标准形式称为“范式”（normalform）。1.6.1简单的范式

[定义：文字]原子命题变元或它的否定称为文字。如

p和

┐p。例=>(p⋁┐q⋁r)⋀(┐p⋁q)⋀┐q)为合取范式，┐p⋁(p⋀q)⋁(p⋀┐q⋀r)是析取范式。[定义：合取范式]一个命题公式称为合取范式，如果它具有形式：A1⋀A2⋀⋯⋀An，n≥1其中，每个Ai都是由文字组成的析取式。[定义：析取范式]一个命题公式称为析取范式，如果它具有形式：A1⋁A2⋁⋯⋁An，n≥1其中，每个Ai都是由文字组成的合取式。积范式和范式

1.6.1简单的范式思考：单个文字如p和┐p，单个合取式p∧q或析取式p∨┐q是什么范式？

注意：

否定只能作用在原子前，绝不能置于括号前联结词转换为∧、∨及┐；(2)用德•摩根律（对偶原理）将否定符号

┐直接移到各个命题变元之前；(3)用分配律、结合律归约为合取范式或析取范式。

1.6.1简单的范式[例1-16]求(p∧(q→r))→s的合取范式。解：

(p⋀(q→r))→s⇔(规范联结词)┐(p⋀(┐q⋁r))⋁s ⇔(否定深入)┐p⋁(q⋀┐r)⋁s ⇔(交换律、结合律、分配律)(┐p⋁s⋁q)⋀(┐p⋁s⋁┐r))

一个命题公式的合取范式与析取范式是唯一的吗？答：否。例如：A=p⇔p⋁(q⋀┐q)⇔(p⋁q)⋀(p⋁┐q)

不唯一的原因是？答：组成合取式或析取式的原子变元不全。1.6.2小项与大项

[定义：小项]n个命题变元的合取式称作（极）小项或布尔合取(minimalterm)，如果它包含每个变元的文字一次且仅一次。

n个命题变元有2n个小项。如两个命题变元的小项为p∧q、┐p∧q、p∧┐q、┐p∧┐q[编码]由于每个小项只有一种赋值使其为1，可用其作对它的编码，如：m11=p⋀q=m3、m10=p⋀┐q=m2、m01=┐p⋀q=m1、m00=┐p⋀┐q=m0[性质]

每个小项，只有变元赋值与其二进制编码相同时小项为真，其余全假；任何一组赋值，能使唯一的一个小项为真，其余全假，即2个小项不能同时为真。有：(1)mi⋀mj=0，0≤i，j≤2n-1； (2)∑ni=1

mi=1。

1.6.2小项与大项[定义：大项]n个命题变元的析取式称作（极）大项或布尔析取(maximalterm)，如果它包含每个变元的文字一次且仅一次。

n个命题变元有2n个大项。如两个命题变元的大项为p⋁q、┐p⋁q、p⋁┐q、┐p⋁┐q[编码]由于每个大项只有一种赋值使其为0，可用其作对它的编码，如：M11=┐p

⋁┐q=M3、M10=┐p⋁q=M2、M01=p⋁┐q=M1、M00=p⋁q=M0[性质]每个大项，只有变元赋值与其二进制编码相同时其值为假，其余全真；任何一组赋值，能使唯一的一个大项为假，其余全真，即2个大项不能同时为假。有：(1)Mi⋁Mj=1，0≤i，j≤2n-1； (2)∏ni=1

Mi=0。

1.6.2小项与大项[定理]┐mi=Mi，┐Mi=mi，0

i

2n-1。

如何计算小项或大项呢？答：添加与1的合取、与0的析取，再将1和0用缺少的变元替换，施以分配律就可以了。例=>共3个变元p、q和r。A=p⋀┐q是析取式，但不是小项，缺少r。添上：A

=p⋀┐q⇔(p⋀┐q)⋀1⇔(p⋀┐q)⋀(r⋁┐r)⇔(p⋀┐q⋀r)⋁(p⋀┐q⋀┐r)这就将A

转换成了2个小项的析取。1.6.3主析取范式与主合取范式

[定义]

仅由小项的析取所组成的命题公式称为主析取范式(majordisjunctiveform)，仅由大项的合取所组成的命题公式称为主合取范式（majorconjunctiveform）。[简化记法]通常，主析取范式

mi1⋁mi2

⋁…⋁

mit

简记为

∑i1,i2,…,it或

∑{i1,i2,…,it}

主合取范式

Mi1⋀Mi2

⋀…

⋀Mit简记为

∏i1,i2,…,it或

∏{i1,i2,…,it}

1.6.3主析取范式与主合取范式[例1-17]求p→((p→q)⋀┐(┐q⋁┐p))的主析取范式和主合取范式。解：原式⇔┐p⋁((┐p⋁q)⋀(q⋀p))⇔┐p⋁((┐p⋀q⋀p)⋁(q⋀q⋀p)) ⇔┐p⋁(p⋀q) （注：析取范式） ⇔(┐p⋀(q⋁┐q))⋁(p⋀q) （注：缺q的项上添加1=q⋁┐q） ⇔(┐p⋀q)⋁(┐p⋀┐q))⋁(p⋀q) （注：主析取范式）原式⇔┐p⋁((┐p⋁q)⋀(q⋀p))⇔┐p⋁(p⋀q)⇔1⋀(┐p⋁q)⇔┐p⋁q（注：主合取范式）

1.6.3主析取范式与主合取范式[定理]在真值表中，使公式值为1的赋值作编码对应小项的析取是公式的主析取范式，使公式值为0的赋值作编码对应大项的合取是公式的主合取范式。证明：对公式A，假设使A为1的赋值对应的小项为mi1、mi2、…

、mit，记B=∑i1,i2,…,it则A

B。

因为若一组赋值使A为1，则对应的小项在B中，B也为1。若一组赋值使A为0，则B中的小项都为0，故B为0。

主合取范式的证明类似。

1.6.3主析取范式与主合取范式例=>计算公式A=p→((p→q)⋀┐(┐q⋁┐p))的主范式。解：pqp→q┐q⋁┐p(p→q)⋀┐(┐q⋁┐p)Am或M001101M00011101m01100000m10111111M11表1-7公式A=p→((p→q)⋀┐(┐q⋁┐p))的真值表主析取范式为：m00⋁m01⋁m11=Σ{0,1,3}。主合取范式为：M10=Π{2}。

1.6.3主析取范式与主合取范式[析取与合取转换定理]若公式A的主析取范式为

∑{i1,i2,…,ik}，主合取范式为

∏{0,

1,…,2n-1}-{i1,i2,…,ik}反之亦然。证明：若A=

∑{i1,i2,…,ik}，因A与┐A的值相反，故┐A=∑{0,

1,…,2n-1}-{i1,i2,…,ik}有A=┐┐A=∏{0,

1,…,2n-1}-{i1,i2,…,ik}。对右端取非后，∧与∨互换，Σ与Π

互换，┐mi恰好转换为Mi，结论成立。[范式存在定理]任一命题公式的主析取范式和主合取范式都存在且唯一。注意：Σ{0,1,2,…,2n-1}和Π{0,1,2,…,2n-1}分别用1和0表示，称为空范式。

1.6.3主析取范式与主合取范式[例*]利用范式解决有限情况的判定问题。若有一次竞赛，要求在p、q、r和s这4人中指派两人参加，但必须满足如下条件：(1)p和q仅一个人参加； (2)若r参加，则s也参加；(3)q和s至多参加一人； (4)若s不参加，则p也不参加。问应如何指派？解：令p、q、r和s分别表示命题p参加、q参加、r参加和s参加，约束条件为C=(p¯

∨

q)∧(r→s)∧┐(q∧s)∧(┐s→┐q)计算命题C的主析取范式：C=m1000∨m1001∨m1011∨m1011

由于哪个mi为1都能保证C为1，故每个mi都代表一种可能的选择。因指派2人参加，故只有m1001=p∧┐q∧┐r∧s是正确选派方式，即派p和s参加。1.7推理理论

从假设前提（条件、定理和定律）得到另外的命题，即形成结论的过程就是推理，这是研究逻辑的主要目标。1.7.1蕴含与论证

1.推理的含义与形式[定义]当且仅当p

q时，称为p蕴含q（logicalimplication），记作p⟹q。此时，称p为前提，q为p的有效结论或逻辑结论，也称为q可由p逻辑推出。得出此逻辑关系的过程称为论证。

所有逻辑推理的实质就是证明p⟹q，也就是证明p

q为永真式。通常的逻辑推理问题都会由一组前提H1，H2，...，Hn来推断一个逻辑结论，论证要求可写作H1⋀H2⋀⋯⋀Hn⇒C，或H1,H2,...,Hn⇒C，或H1,H2，...,Hn⊢C

1.7.1蕴含与论证[比较示例]一个简单的初等数学证明题目：已知a、b、c为实数，且a2-b2=bc，c≠0，证明a2/c=b(b/c+1)。如果记p：a2-b2=bc，q：c≠0，r：a2/c=b(b/c+1)上述论证要求可描述为：p⋀q⇒r证明的目的就是说明：若前提p⋀q正确，则结论r也正确，即证明p⋀q→r为永真式。

1.7.1蕴含与论证2.常规的推理方法真值表法列出公式H1⋀H2⋀⋯⋀Hn

C的真值表。若表中所有行全为1则得证。变元较多时较麻烦。(2)叙述型推理说明不存在H1⋀H2⋀⋯⋀Hn为1且C为0的情况。可以有两种叙述形式：(a)假定H1⋀H2⋀⋯⋀Hn为1推导C必为1。(b)假定C为0推导H1⋀H2⋀⋯⋀Hn必为0。

1.7.1蕴含与论证

证法(a)：若前件┐q⋀(p

q)为1。那么，┐q和p

q都为1，从而q为0。因此，p为0，故┐p为1。结论成立。[例1-20]证明┐q⋀(p

q)⇒┐p。证法(b)：

若假定后件┐p为0。于是，有p为1。若q为1，则┐q为0，故┐q⋀(p→q)为0。若q为0，则p→q为0，故┐q⋀(p→q)为0。总之，前件┐q⋀(p→q)为0。结论成立。

1.7.1蕴含与论证[例1-21]用符号描述推理过程并验证论证的有效性：如果6是偶数，则7被2除不尽。或5不是素数，或7被2除尽。但5是素数。所以6是奇数。解：记p：6是偶数，q：7被2除尽，r：5是素数，则原推理过程符号化为：p→┐q，┐r⋁q，r⇒┐p

假定前提为1。则p→┐q，┐r⋁q，r都为1，知┐r为0。再由q为1知┐q为0，故p为0。于是，┐p为1。论证有效。注意：论证有效并不代表结论是客观真实的，因为并不研究前提是否具有客观真实性，仅假定其逻辑意义为真，从而进行形式上的推导。

1.7.1蕴含与论证(3)等值演算法利用等价变换说明条件式为永真式。例如，通过演算可推出((p→┐q)∧p)→┐q⇔1这说明((p→┐q)∧p)⇒┐q。(4)主析取范式法说明条件式的主析取范式包含所有的小项。例如，由((p→┐q)∧p)→┐q⇔Σ0,1,2,3⇔1同样可说明((p→┐q)∧p)⇒┐q。注意：条件式是非对称性的：(1)q→p：p→q的逆换式（逆命题）；(2)┐p→┐q：p→q的反换式（反命题）；(3)┐q→┐p：p→q的逆反式（逆否命题），且p→q⇔┐q→┐p。

1.7.1蕴含与论证3.等价与蕴含的关系[定理]对任意的命题公式

p和

q，p

q的充分必要条件是

p

q且

q

p。证明：p

q等同于p↔q是永真式，等同于(p→q)⋀(q→p)是永真式，等同于p→q和q→p都是永真式，等同于p⇒q且q⇒p。[例1-22]设A、B、C是任意命题公式，证明：(1)若A⇒B且A是永真式，则B为永真式。(2)若A⇒B且B⇒C，则A⇒C。(3)若A⇒B且A⇒C，则A⇒(B⋀C)，A⇒(B⋁C)。(4)若A⇒C且B⇒C，则(A⋁B)⇒C。略证(4)：

由条件，A→C和B→C永真，┐A⋁C和┐B⋁C永真，(┐A⋁C)⋀(┐B⋁C)⟺(┐A⋀┐B)⋁C⟺(A⋁B)→C永真，结论成立。1.7.2自然推理系统

严格的论证过程可以采用自然推理系统或公理推理系统。自然推理系统是指不引入公理，仅确定一些推理规则，从前提出发，利用推理规则构造出严格的命题序列，推导出最终的结论。称为“自然推理”、“构造证明法”、“演绎法”或“形式证明”。1.推理定律可以将基本等价关系和蕴含关系称为推理定律，或称前者为推理定律，后者为推理规则。

如果你有口令(p)，那么，你就能登录网络(q)。

你有了口令。

因此，你能登录网络。∵p→q

p

∴qp→q,p⇒q，

(p→q)⋀p⇒q

1.7.2自然推理系统序号蕴含关系含义I1p⋀q⇒p

化简律I2p⋀q⇒q

I3p⇒p⋁q附加律I4q⇒p⋁qI5┐p⇒p→qI6q⇒p→qI7┐(p→q)⇒pI8

┐(p→q)⇒┐qI9p,q⇒p⋀q

I10┐p,p⋁q⇒q析取三段论序号蕴含关系含义I11p,p→q⇒q

假言推理I12┐q,p→q⇒┐p

拒取式I13p→q,q→r⇒p→r假言三段论I14p↔q,q↔r⇒p↔r等价三段论I15p⋁q,p→r,q→r⇒rI16p→q⇒(p⋁r)→(q⋁r)I17p→q⇒(p⋀r)→(q⋀r)I18p→q,p→r⇒p→(q⋁r)I19p→q,p→r⇒p→(q⋀r)表1-8注意：肯定形式与否定形式同样有效!

1.7.2自然推理系统2.利用推理定律实现形式证明

形式逻辑推理的本质是说明一个蕴含关系，或者说，总是假定前提是真的，利用表1-5和1-8所示的基本等价和蕴含关系，说明结论也为真即告完成。这种推理就是“因为+所以”组成的步骤，只是每次的“所以”都要由推理定律来保证。

推理形式描述为以下2条规则：

(1)P规则：前提引入规则，指在证明的任何步骤都可引入前提；

(2)T规则：推理定律引用规则，指在证明中，如一个或几个公式满足推理定律，则其结论或等价公式可引入。

利用P（premise）规则和T（tautology）规则实现的证明方法称为“直接证明法”。

1.7.2自然推理系统[例]已知a、b、c为实数，且a2-b2=bc，c≠0，证明a2/c=b(b/c+1)。证明：(1)∵a2-b2=bc

P前提

(2)∴(a2-b2)+b2=bc+b2

T推理定律：x=y⇒x+z=y+z

(3)∴a2+(-b2+b2)=b2+bc

T推理定律：(x+y)+z=x+(y+z)，x+y=y+x

(4)∴a2+0=b(b+c) T推理定律：x+(-x)=0，x(y+z)=xy+xz

(5)∴a2=b(b+c) T推理定律：x+0=x

(6)∵c≠0 P前提

(7)∴a2/c=b(b+c)/c

T推理定律：x=y⋀z≠0⇒x/z=y/z。

(8)∴a2/c=b(b/c+1) T推理定律：(x+y)/z=x/z+y/z，x/x=1

代之以说明采用的定律和原因!

1.7.2自然推理系统3.直接证法的形式推理证明示例[例1-24]证明(p⋁q)⋀(p→r)⋀(q→s)⇒s⋁r。证明：(1)p⋁q

P

∵(2)┐p→q

T(1)E∴(3)q→s

P

∵(4)┐p→s

T(2),(3)I∴(5)┐s→p

T(4)E∴(6)p→r

P

∵(7)┐s→r

T(5),(6)I∴(8)s⋁r

T(7)E∴存在问题的证法：(1)p→r

P(2)(p⋁q)→(r⋁q)

T(1)I(3)q→s

P(4)(q⋁r)→(s⋁r)

T(3)I(5)(p⋁q)→(s⋁r) T(2),(4)I(6)p⋁q

P(7)s⋁r

T(5),(6)I

1.7.2自然推理系统[例1-25]证明(p⋁q)→v,v→(r⋁s),s→u,┐r⋀┐u⇒┐p。证明：(1)┐r⋀┐u

P(2)┐u

T(1)I(3)s→u

P(4)┐s

T(2),(3