1、第1章 命题逻辑基本概念离 散 数 学本章说明q本章的主要内容 命题、联结词、复合命题 命题公式、赋值、命题公式的分类q本章与后续各章的关系 本章是后续各章的准备或前提数理逻辑概述数理逻辑概述 数理逻辑是用数学的方法研究思维规律的一门学科。由于它使用了一套符号，简洁的表达出各种推理的逻辑关系，因此数理逻辑一般又称为符号逻辑。数理逻辑和计算机的发展有着密切的联系，它为机器证明、自动程序设计、计算机辅助设计等计算机应用和理论研究提供必要的理论基础。数理逻辑的发展前期前史时期古典形式逻辑时期：亚里斯多德的直言三段论理论初创时期逻辑代数时期（17世纪末）(1)资本主义生产力大发展，自然科学取得了长足的
2、进步，数学在认识自然、发展技术方面起到了相当重要的作用。(2)人们希望使用数学的方法来研究思维，把思维过程转换为数学的计算。数理逻辑的发展前期 (3)莱布尼兹(Leibniz,16461716)完善三段论，提出了建立数理逻辑或者说理性演算的思想：提出将推理的正确性化归于计算，这种演算能使人们的推理不依赖于对推理过程中的命题的含义内容的思考，将推理的规则变为演算的规则。使用一种符号语言来代替自然语言对演算进行描述，将符号的形式和其含义分开。使得演算从很大程度上取决与符号 的组合规律，而与其含义无关。数理逻辑的发展前期 (4)布尔(G.Boole,18151864)代数：将有关数学运算的研究的代数
3、系统推广到逻辑领域，布尔代数既是一种代数系统，也是一种逻辑演算。数理逻辑的奠基时期弗雷格(G.Frege,18481925)：概念语言一种按算术的公式语言构成的纯思维公式语言(1879)的出版标志着数理逻辑的基础部分命题演算和谓词演算的正式建立。皮亚诺(Giuseppe Peano,18581932)：用一种新的方法陈述的算术原理(1889)提出了自然数算术的一个公理系统。数理逻辑的奠基时期罗素(Bertrand Russell,18721970)：数学原理(与怀特黑合著，1910,1912,1913)从命题演算和谓词演算开始，然后通过一元和二元命题函项定义类和关系的概念，建立了抽象的类演算和
4、关系演算。由此出发，在类型论的基础上用连续定义和证明的方式引出了数学（主要是算术）中的主要概念和定理。数理逻辑的奠基时期逻辑演算的发展：甘岑(G.Gentzen)的自然推理系统(Natural Deduction System)，逻辑演算的元理论：公理的独立性、一致性、完全性等。各种各样的非经典逻辑的发展：路易斯(Lewis,18831964)的模态逻辑，实质蕴含怪论和严格蕴含、相干逻辑等，卢卡西维茨的多值逻辑等。命题逻辑研究的是以原子命题为基本单位的推理演算，其特征在于，研究和考查逻辑形式时，我们把一个命题只分析到其中所含的原子命题成分为止。通过这样的分析可以显示出一些重要的逻辑形式，这种形
5、式和有关的逻辑规律就属于命题逻辑。1.1 命题与联结词p数理逻辑研究的中心问题是推理。p推理的前提和结论都是表达判断的陈述句。p表达判断的陈述句构成了推理的基本单位。1.1 命题与联结词p称能判断真假而不是可真可假的陈述句为命题（proposition）。p作为命题的陈述句所表达得的判断结果称为命题的真值。p真值只取两个：真与假。p真值为真的命题称为真命题。p真值为假的命题称为假命题。q感叹句、疑问句、祈使句都不能称为命题。q判断结果不唯一确定的陈述句不是命题。q陈述句中的悖论不是命题。说明(1)4是素数。(2)(3)x大于y。(4)充分大的偶数等于两个素数之和。(5)今天是星期二。(6)(7
6、)请不要吸烟！(8)这朵花真美丽啊！(9)我正在说假话。例1.1 判断下列句子是否为命题。(1)是，假命题(2)是，真命题(3)不是，无确定的真值(4)是，真值客观存在(5)是，真值根据具体情况而定。(6)不是，疑问句(7)不是，祈使句(8)不是，感叹句(9)不是，悖论是无理数2吗？大于2q一个陈述句能否分辨真假和我们是否知道它的真假是两回事！例：小李去过长城。q判断结果不唯一确定的陈述句不是命题。q陈述句中的悖论不是命题。即：要把“自指谓的陈述句”排除命题之外。例：本页这一行的这句话是假。说明命题和真值的符号化p用小写英文字母p,q,r,pi,qi,ri 表示命题p用“1”表示真，用“0”表
7、示假 r：充分大的偶数等于两个素数之和。s：今天是星期二。是无理数2p：4是素数。q：q不能被分解成更简单的陈述句，称这样的命题为简单命题或原子命题。q由简单陈述句通过联结词而成的陈述句，称这样的命题为复合命题。例1.2将下面这段陈述中所出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。2p：是有理数q：2是素数；r：2是偶数s：3是素数；t：4是素数201110非p；q并且(与)r；q或t；如果q，则s；q当且仅当s。例1.2的讨论p半形式化形式p数理逻辑研究方法的主要特征是将论述或
8、推理中的各种要素都符号化。即构造各种符号语言来代替自然语言。p形式化语言：完全由符号所构成的语言。p将联结词（connective）符号化，消除其二义性，对其进行严格定义。p例如：他是是100100米或米或400400米赛跑的冠军。米赛跑的冠军。鱼香肉丝或锅包肉，加一碗汤。鱼香肉丝或锅包肉，加一碗汤。定义1.1否定(negation)p设p为命题，复合命题“非p”(或“p的否定”)称为p的否定式,记作p，符号称作否定联结词，并规定p为真当且仅当p为假。例如：p：哈尔滨是一个大城市。p：哈尔滨是一个不大城市。p：哈尔滨不是一个大城市。pp1001定义1.2合取(conjunction)p设p,q
9、为二命题，复合命题“p并且q”(或“p与q”)称为p与q的合取式，记作pq，称作合取联结词，并规定pq为真当且仅当p与q同时为真。使用合取联结词时要注意的两点：1)描述合取式的灵活性与多样性。自然语言中的“既又”、“不但而且”、“虽然但是”、“一面一面”等联结词都可以符号化为。2)分清简单命题与复合命题。不要见到“与”或“和”就使用联结词。pqpq111100010000例1.3 将下列命题符号化(1)吴颖既用功又聪明。(2)吴颖不仅用功而且聪明。(3)吴颖虽然聪明，但不用功。(4)张辉与王丽都是三好学生。(5)张辉与王丽是同学。p:吴颖用功。q:吴颖聪明。r:张辉是三好学生。s:王丽是三好学
10、生。t:张辉与王丽是同学。(1)pq(2)pq(3)qp(4)rs(5)t解题要点：正确理解命题含义。找出原子命题并符号化。选择恰当的联结词。合取举例pp：我们去看电影。q：房间里有十张桌子。pq：我们去看电影并且房间里有十张桌子。在数理逻辑中，关心的只是复合命题与构成复合命题的各原子命题之间的真值关系，即抽象的逻辑关系，并不关心各语句的具体内容。说明定义1.3析取(disjunction)p设p，q为二命题，复合命题“p或q”称作p与q的析取式，记作pq，称作析取联结词，并规定pq为假当且仅当p与q同时为假。自然语言中的“或”具有二义性，用它联结的命题有时具有相容性，有时具有排斥性，对应的联
11、结词分别称为相容或和排斥或(排异或)。说明pqpq111101011000例例1.4 1.4 将下列命题符号化将下列命题符号化(1)张晓静爱唱歌或爱听音乐。(2)张晓静只能挑选202或203房间。(3)张晓静是江西人或安徽人。(4)他昨天做了二十或三十道习题。(1)设 p：张晓静爱唱歌，q：张晓静爱听音乐。相容或，符号化为 pq(2)设t：张晓静挑选202房间，u：张晓静挑选203房间。排斥或，符号化为：(tu)(tu)(3)设r：张晓静是江西人，s：张晓静是安徽人。排斥或，符号化为：rs。(排斥或联结的两个命题事实上不可能同时为真)或符号化为：(rs)(rs)(4)原子命题，因为“或”只表示
12、了习题的近似数目。定义1.4蕴涵(implication)p设p，q为二命题，复合命题“如果p，则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词,并规定pq为假当且仅当p为真q为假。说明q pq的逻辑关系表示q是p的必要条件。q q是p的必要条件有许多不同的叙述方式 只要p，就q 因为p，所以q p仅当q只有q才p除非q才p除非q，否则非p pqp q111100011001例例1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值(1)如果3+36，则雪是白的。(2)如果3+36，则雪是白的。(3)如果3+36，则雪不是白的。(
13、4)如果3+36，则雪不是白的。解：令p：3+36，p的真值为1。q：雪是白色的，q的真值也为1。(1)pq(2)pq(3)pq(4)pq1101例例1.5 1.5 将下列命题符号化，并指出其真值将下列命题符号化，并指出其真值 以下命题中出现的a是一个给定的正整数：(5)只要a能被4整除，则a一定能被2整除。(6)a能被4整除，仅当a能被2整除。(7)除非a能被2整除，a才能被4整除。(8)除非a能被2整除，否则a不能被4整除。(9)只有a能被2整除，a才能被4整除。(10)只有a能被4整除，a才能被2整除。解：令r：a能被4整除 s：a能被2整除(5)至(9)五个命题均叙述的是a能被2整除是
14、a能被4整除的必要条件，因而都符号化为rs。其真值为1在(10)中，将a能被4整除看成了a能被2整除的必要条件，因而应符号化为sr。a值不定时，真值未知。关于蕴含的进一步说明p作为一种规定，当p为假时，无论q是真是假，pq均为真。也就是说，只有p为真q为假这一种情况使得复合命题pq为假。称为实质蕴含。p例：如果x5，则x2。(1)x=6x=6如果如果6565，则，则6262。(2)(2)x=3x=3 如果如果3535，则，则3232。(3)(3)x=1 x=1 如果如果1515，则，则1212。p例：如果我有车，那么我去接你 p常出现的错误，没有分清充分条件与必要条件。定义1.5等价(two-
15、way-implication)p设p，q为二命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词，并规定pq为真当且仅当p与q同时为真或同时为假。说明q“当且仅当”（if and only if）q p q的逻辑关系为p与q互为充分必要条件。q(pq)(qp)与p q的逻辑关系完全一致。pqp q111100010001例例1.6 1.6 将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值(1)是无理数当且仅当加拿大位于亚洲。(2)2+35的充要条件是是无理数。(3)若两圆A，B的面积相等，则它们的半径相等；反之亦然。(4)当王小红心情愉快时，她就唱歌
16、；反之，当她唱歌时，一定心情愉快。(1)设 p：是无理数，q：加拿大位于亚洲。符号化为 pq，真值为0。(2)设 p：2+35，q：是无理数。符号化为 pq，真值为1。例例1.6 1.6 将下列命题符号化，并讨论它们的真值将下列命题符号化，并讨论它们的真值(1)是无理数当且仅当加拿大位于亚洲。(2)2+35的充要条件是是无理数。(3)若两圆A，B的面积相等，则它们的半径相等；反之亦然。(4)当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。(1)设 p：两圆A，B的面积相等，q：两圆A，B的半径相等。符号化为 pq，真值为1。(2)设 p：王小红心情愉快，q：王小红唱歌。符号化为
17、pq，真值由具体情况而定。关于基本联结词的说明p,，称为一个联结词集。p由联结词集,中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为基本的复合命题。p基本复合命题的真值见下表：关于基本联结词的说明p多次使用联结词集中的联结词，可以组成更为复杂的复合命题。p求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。p本书规定的联结词优先顺序为：()，对于同一优先级的联结词，先出现者先运算。例1.7令 p：北京比天津人口多。q：2+2 4.r：乌鸦是白色的。求下列复合命题的真值：(1)(pq)(pq)r (2)(qr)(pr)(3)(pr)(
18、pr)解：p、q、r的真值分别为1、1、0 (1)1(2)1(3)0我们关心的是复合命题中命题之间的真值关系，而不关心命题的内容。说明1.2 命题公式及其赋值p简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题为命题常项或命题常元。(proposition constant)p称真值可以变化的陈述句为命题变项或命题变元(proposition variable)。也用p,q,r,表示命题变项。p当p,q,r,表示命题变项时，它们就成了取值0或1的变项，因而命题变项已不是命题。p这样一来，p,q,r,既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是
19、常项还是变项。p将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。定义1.3 合式公式(wff)(1)单个命题变项是合式公式，并称为原子命题公式。(2)若A是合式公式，则(A)也是合式公式。(3)若A，B是合式公式，则(AB)，(AB)，(AB)，(AB)也是合式公式。(4)只有有限次地应用(1)(3)形式的符号串才是合式公式。合式公式也称为命题公式或命题形式，并简称为公式。设A为合式公式，B为A中一部分，若B也是合式公式，则称B为A的子公式。合式公式：Well Formed Formula 关于合式公式的说明p定义1.3给出的合式公式的定义方式称为归纳定义或递
20、归定义方式。p定义中引进了A,B等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与p,pq,(pq)r等具体的公式是有所不同的。pA,B等符号被称作元语言符号。p,q等被称作对象语言符号。p所谓对象语言是指用来描述研究对象的语言，而元语言是指用来描述对象的语言，这两种语言是不同层次的语言。p例如中国人学习英语时，英语为对象语言，而用来学习英语的汉语则是元语言。关于合式公式的说明p(A)、(AB)等公式单独出现时，外层括号可以省去，写成A、AB等。p公式中不影响运算次序的括号可以省去，如公式(pq)(r)可以写成pqr。p合式公式的例子：(pq)(q r)(pq)rp(qr)p不是合式
21、公式的例子pqr(p(rq)定义1.7 公式层次(1)(1)若公式A是单个的命题变项，则称A为0层合式。(2)称A是n+1(n0)层公式是指下面情况之一：(a)AB，B是n层公式；(b)ABC，其中B,C分别为i层和j层公式，且n=max(i,j)；(c)ABC，其中B,C的层次及n同(b)；(d)ABC，其中B,C的层次及n同(b)；(e)ABC，其中B,C的层次及n同(b)。(3)若公式A的层次为k，则称A是k层公式。例如：(pq)r，(pq)(rs)p)分别为3层和4层公式 公式的解释p在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题
22、之后，公式就成了真值确定的命题了。p(pq)rp若p：2是素数，q：3是偶数，r：是无理数，则p与r被解释成真命题，q被解释成假命题，此时公式(pq)r被解释成：若2是素数或3是偶数，则是无理数。（真命题）pr被解释为：是有理数，则(pq)r被解释成：若2是素数或3是偶数，则是有理数。（假命题）p将命题变项p解释成真命题，相当于指定p的真值为1，解释成假命题，相当于指定p的真值为0。定义1.8 赋值或解释p设p1,p2,pn是出现在公式A中的全部命题变项，给p1,p2,pn各指定一个真值，称为对A的一个赋值或解释。若指定的一组值使A的真值为1，则称这组值为A的成真赋值；若使A的真值为0，则称这
23、组值为A的成假赋值。p对含n个命题变项的公式A的赋值情况做如下规定：(1)若A中出现的命题符号为p1,p2,pn，给定A的赋值1,2,n 是指p11，p22,，pnn。(2)若A中出现的命题符号为p，q，r.,给定A的赋值1,2,n是指p1，q2,，最后一个字母赋值n。上述i取值为0或1，i1,2,n。赋值举例p在公式(p1p2p3)(p1p2)中，000(p10，p20，p30)，110(p11，p21，p30)都是成真赋值，001(p10，p20，p31)，011(p10，p21，p31)都是成假赋值。p在(pq)r中，011(p10，p21，p31)为成真赋值，100(p11，p20，p
24、30)为成假赋值。p重要结论：含n(n1)个命题变项的公式共有2n个不同的赋值。定义1.9 真值表p将命题公式A在所有赋值下取值情况列成表，称作A的真值表。q 构造真值表的具体步骤如下：(1)找出公式中所含的全体命题变项p1,p2,pn(若无下角标就按字典顺序排列)，列出2n个赋值。本书规定，赋值从000开始，然后按二进制加法依次写出各赋值，直到111为止。(2)按从低到高的顺序写出公式的各个层次。(3)对应各个赋值计算出各层次的真值，直到最后计算出公式的真值。公式A与B具有相同的或不同的真值表，是指真值表的最后一列是否相同，而不考虑构造真值表的中间过程。说明例1.8 求下列公式的真值表，并求
25、成真赋值和成假赋值。(1)(pq)r(2)(pp)(qq)(3)(pq)qr 定义1.7 重言式、永真式、可满足式设A为任一命题公式(1)若A在它的各种赋值下取值均为真,则称A是重言式(tautology)或永真式。(2)若A在它的各种赋值下取值均为假,则称A是矛盾式(contradiction)或永假式。(3)若A不是矛盾式,则称A是可满足式（satisfactable formula）。定义1.7的进一步说明pA是可满足式的等价定义是：A至少存在一个成真赋值。p重言式一定是可满足式，但反之不真。因而，若公式A是可满足式，且它至少存在一个成假赋值，则称A为非重言式的可满足式。p真值表可用来判
26、断公式的类型:l 若真值表最后一列全为1，则公式为重言式。l 若真值表最后一列全为0，则公式为矛盾式。l 若真值表最后一列中至少有一个1，则公式为可满足式。说明qn个命题变项共产生2n个不同赋值q含n个命题变项的公式的真值表只有 种不同情况 n22例题例题1.9 下列各公式均含两个命题变项p与q，它们中哪些具有相同的真值表?(1)pq(4)(pq)(qp)(2)pq(5)qp(3)(pq)哑元p设公式A,B中共含有命题变项p1,p2,pn，而A或B不全含有这些命题变项，比如A中不含pi,pi+1,pn,称这些命题变项为A的哑元，A的取值与哑元的变化无关，因而在讨论A与B是否有相等的真值表时，将
27、A,B都看成p1,p2,pn的命题公式。例题 例1.10 下列公式中,哪些具有相同的真值表?(1)pq(2)qr(3)(pq)(pr)p)(4)(qr)(pp)本章主要内容q 命题与真值（或真假值）。q 简单命题与复合命题。q 联结词：，。q 命题公式（简称公式）。q 命题公式的层次和公式的赋值。q 真值表。q 公式的类型：重言式（永真式），矛盾式（永假式），可满足式。本章学习要求p在5种联结词中，要特别注意蕴涵联结的应用，要弄清三个问题：l pq 的逻辑关系 l pq 的真值 l pq 的灵活的叙述方法p写真值表要特别仔细认真，否则会出错误。p深刻理解各联结词的逻辑含义。p熟练地将复合命题符
28、号化。p会用真值表求公式的成真赋值和成假赋值。本章典型习题p命题符号化p求复合命题的真值与命题公式的赋值p判断公式的类型例题：命题符号化(1)我和他既是兄弟又是同学 p：我和他是兄弟，q：我和他是同学。故命题可符号化为：pq。(2)张三或李四都可以做这件事。p：张三可以做这件事。q：李四可以做这件事。故命题可符号化为：pq。(3)仅当我有时间且天不下雨，我将去镇上。对于“仅当”，实质上是“当”的逆命题。“当A则B”是AB，而“仅当A则B”是BA。p：我有时间。q：天不下雨。r：我将去镇上。故命题可符号化为：r(pq)。例题：命题符号化(4)(4)张刚总是在图书馆看书，除非图书馆不开门或张刚生病
29、。对于“除非”，只要记住，“除非”是条件。p：张刚在图书馆看书，q：图书馆不开门，r：张刚生病。故命题可符号化为：(qr)p。(5)风雨无阻，我去上学。可理解为“不管是否刮风、是否下雨，我都去上学”。p：天刮风，q：天下雨，r：我去上学。故命题可符号化为：(pqr)(pqr)(pqr)(pqr)或(pqr)(pqr)(pqr)(pqr)理解为“四种情况必居其一,而每种情况下我都去上学”命题符号化的要点p要准确确定原子命题，并将其形式化。p要选用恰当的联结词，尤其要善于识别自然语言中的联结词（有时它们被省略）。p否定词的位置要放准确。p需要的括号不能省略，而可以省略的括号，在需要提高公式可读性时亦可不省略。p要注意的是,语句的形式化未必是唯一的。例题：求公式(p(qr)的真值表。p pq qr r0 00 00 00 00 01 10 01 10 00 01 11 11 10 00 01 10 01 11 11 10 01 11 11 1qrqr0 00 00 01 10 00 00 01 1p(qr)p(qr)1 11 11 11 10 00 00 01 1(p(qr)p(qr)0 00 00 00 01 11 11 10 0本章作业习题一1、9、14、15、18、19
