离散数学01命题逻辑基本概念

《离散数学01命题逻辑基本概念》由会员分享，可在线阅读，更多相关《离散数学01命题逻辑基本概念（46页珍藏版）》请在金锄头文库上搜索。

1、离 散 数 学,第1章 命题逻辑基本概念,本章内容,1.1 命题与联结词 1.2 命题公式及其赋值,1.1 命题与联结词,数理逻辑研究的中心问题是推理。 推理的前提和结论都是表达判断的陈述句。 表达判断的陈述句构成了推理的基本单位。,基本概念,称能判断真假而不是可真可假的陈述句为 命题（proposition）。 作为命题的陈述句所表达得的判断结果称为命题的真值。 真值只取两个：真与假。 真值为真的命题称为真命题。 真值为假的命题称为假命题。,概念,例1.1 判断下列句子是否为命题。,(1) 4是素数。 (2) (3) x大于y，其中x和y是任意两个数。 (4) 充分大的偶数等于两个素数之和。

2、 (5) 今天是星期一。 (6) (7) 请不要吸烟！ (8) 这朵花真美丽啊！ (9) 我正在说假话。,(1) 是，假命题 (2) 是，真命题 (3) 不是，无确定的真值 (4) 是，真值客观存在 (5) 是，真值根据具体情况而定 (6) 不是，疑问句 (7) 不是，祈使句 (8) 不是，感叹句 (9) 不是，悖论,命题和真值的符号化,用小写英文字母 p, q, r, pi ,qi , ri 表示命题 用“1”表示真，用“0”表示假,不能被分解成更简单的陈述句，称这样的命题为简单命题或原子命题。 由简单陈述句通过联结词而成的陈述句，称这样的命题为复合命题。,概念,例1.2,将下面这段陈述中所

3、出现的原子命题符号化，并指出它们的真值，然后再写出这段陈述。,是有理数是不对的；2是偶素数；2或4是素数；如果2是素数，则3也是素数；2是素数当且仅当3也是素数。,p： 是有理数 q：2是素数 r：2是偶数 s：3是素数 t：4是素数,0 1 1 1 0,非p q并且(与)r q或t 如果q，则s q当且仅当s,例1.2的讨论,半形式化形式 数理逻辑研究方法的主要特征是将论述或推理中的各种要素都符号化。即构造各种符号语言来代替自然语言。 形式化语言：完全由符号所构成的语言。 将联结词（connective）符号化，消除其二义性，对其进行严格定义。 例如： 他是100米或400米赛跑的冠军。 鱼

4、香肉丝或锅包肉，加一碗汤。,否定(negation),例如： p：哈尔滨是一个大城市。 p：哈尔滨是一个不大城市。 p：哈尔滨不是一个大城市。,合取(conjunction),例1.3 将下列命题符号化,(1)吴颖既用功又聪明。 (2)吴颖不仅用功而且聪明。 (3)吴颖虽然聪明，但不用功。 (4)张辉与王丽都是三好学生。 (5)张辉与王丽是同学。,p: 吴颖用功。 q: 吴颖聪明。 r: 张辉是三好学生。 s: 王丽是三好学生。 t: 张辉与王丽是同学。,(1) pq (2) pq (3) qp (4) rs (5) t,合取举例,p：我们去看电影。 q：房间里有十张桌子。 pq：我们去看电影

5、并且房间里有十张桌子。,析取(disjunction),例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) 原子命题，

6、因为“或”只表示了习题的近似数目。,蕴涵(implication),例1.5 将下列命题符号化，并指出其真值,(1) 如果3+36，则雪是白的。 (2) 如果3+36，则雪是白的。 (3) 如果3+36，则雪不是白的。 (4) 如果3+36，则雪不是白的。,解：令 p：3+36，p 的真值为1。 q：雪是白色的，q 的真值也为1。 (1) pq (2)pq (3) pq (4) pq,1 1 0 1,例1.5 将下列命题符号化，并指出其真值,以下命题中出现的 a 是一个给定的正整数： (5) 只要 a 能被 4 整除，则 a 一定能被 2 整除。 (6) a 能被 4 整除，仅当 a 能被 2

7、 整除。 (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 整除是 a 能被 4 整除的必要条件，因而都符号化为 rs。其真值为 1 在(10)中，将 a 能被 4 整除看成了 a 能被 2 整除的必要条件，因而应符号化为 sr。 a 值不定时，真值未知。,关于蕴含的进一步说明,作为一种规定，当p为假

8、时，无论 q 是真是假，pq均为真。也就是说，只有 p 为真 q 为假这一种情况使得复合命题pq为假。称为实质蕴含。 例：如果 x5，则 x2。 (1) x=6 如果 65，则 62。 (2) x=3 如果 35，则 32。 (3) x=1 如果 15，则 12。 例：如果我有车，那么我去接你。 例：如果太阳从西边出来，我就不姓张。 常出现的错误，没有分清充分条件与必要条件。,等价(two-way-implication),例1.6 将下列命题符号化，并讨论它们的真值,(1) 是无理数当且仅当加拿大位于亚洲。 (2) 2+35 的充要条件是 是无理数。 (3) 若两圆A,B的面积相等，则它们的

9、半径相等；反之亦然。 (4) 当王小红心情愉快时，她就唱歌；反之，当她唱歌时，一定心情愉快。,设 p： 是无理数，q：加拿大位于亚洲。 符号化为 pq，真值为0。 设 p：2+35， q：是无理数。 符号化为 pq，真值为1。 设 p：两圆A,B的面积相等， q：两圆A,B的半径相等。 符号化为 pq，真值为1。 设 p：王小红心情愉快， q：王小红唱歌。 符号化为 pq，真值由具体情况而定。,关于基本联结词的说明,，称为一个联结词集。 由联结词集,中的一个联结词联结一个或两个原子命题组成的复合命题是最简单的复合命题，可以称它们为基本的复合命题。 基本复合命题的真值见下表：,关于基本联结词的说

10、明,多次使用联结词集中的联结词，可以组成更为复杂的复合命题。 求复杂复合命题的真值时，除依据上表外，还要规定联结词的优先顺序，将括号也算在内。 本书规定的联结词优先顺序为：( ), , , , , ，对于同一优先级的联结词，先出现者先运算。,例1.7,令 p: 北京比天津人口多。 q : 2+24。 r : 乌鸦是白色的。 求下列复合命题的真值： (1)(pq)(pq)r (2)(qr)(pr) (3)(pr)(pr),解： p,q, r 的真值分别为 1、1、0 (1) 1 (2) 1 (3) 0,1.2 命题公式及其赋值,简单命题是真值唯一确定的命题逻辑中最基本的研究单位，所以也称简单命题

11、为命题常项或命题常元。 (proposition constant) 称真值可以变化的陈述句为命题变项或命题变元 (proposition variable)。也用 p, q, r,表示命题变项。 当 p, q, r,表示命题变项时，它们就成了取值 0 或 1 的变项，因而命题变项已不是命题。 这样一来，p, q, r,既可以表示命题常项，也可以表示命题变项。在使用中，需要由上下文确定它们表示的是常项还是变项。 将命题变项用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式或命题公式。,合式公式( wff ),合式公式：Well Formed Formula,关于合式公式的说明,定义

12、1.6 给出的合式公式的定义方式称为归纳定义或递归定义方式。 定义中引进了 A, B 等符号，用它们表示任意的合式公式，而不是某个具体的公式，这与 p, pq, (pq)r 等具体的公式是有所不同的。 A, B 等符号被称作元语言符号。p,q 等被称作对象语言符号。 所谓对象语言是指用来描述研究对象的语言，而元语言是指用来描述对象语言的语言，这两种语言是不同层次的语言。 例如中国人学习英语时，英语为对象语言，而用来学习英语的汉语则是元语言。,关于合式公式的说明,(A)、(AB) 等公式单独出现时，外层括号可以省去，写成 A、AB 等。 公式中不影响运算次序的括号可以省去， 如公式 (pq)(r

13、) 可以写成 pqr。 合式公式的例子： (pq)(q r) (pq)r p(qr) 不是合式公式的例子 pqr (p(rq),定义1.7 公式层次,(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 的层次为

14、 k，则称 A 是 k层公式。 例如：(pq)r，(pq)(rs)p) 分别为3层和4层公式,公式的解释,在命题公式中，由于有命题符号的出现，因而真值是不确定的。当将公式中出现的全部命题符号都解释成具体的命题之后，公式就成了真值确定的命题了。 (pq)r (1)若 p：2是素数，q：3是偶数，r：是无理数， 则 p 与 r 被解释成真命题，q 被解释成假命题， 此时公式 (pq)r 被解释成：若 2 是素数或 3 是偶数，则 是无理数。（真命题） (2)r 被解释为： 是有理数，则 (pq)r 被解释成： 若 2 是素数或 3 是偶数，则 是有理数。（假命题） 将命题变项 p 解释成真命题，相

15、当于指定 p 的真值为 1，解释成假命题，相当于指定 p 的真值为 0。,定义1.8 赋值或解释,设 p1, p2, pn是出现在公式 A 中的全部命题变项，给p1,p2,pn各指定一个真值，称为对 A 的一个赋值或解释。 若指定的一组值使 A 的真值为 1，则称这组值为A的成真赋值； 若使 A 的真值为 0，则称这组值为 A 的成假赋值。 对含 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。,赋值举例,在公式(p1p2p3)(p1p2)中， 000 (p10，p20，p30)， 110 (p11，p21，p30) 都是成真赋值， 001 (p10，p20，p31)， 011 (p10，p21，p31) 都是成假赋值。 在 (pq)r 中， 011 (p10，p21，p31) 为成真赋值， 100 (p11，p20，p30) 为成假赋值。 重要结论： 含 n (n1) 个命题变项的公式共有 2n 个不同的赋值