第一部分 数理逻辑 数理逻辑又称符号逻辑、理论逻辑。它既是数学的一 个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或

Presentation on theme: "第一部分 数理逻辑 数理逻辑又称符号逻辑、理论逻辑。它既是数学的一 个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或"— Presentation transcript:

1

2 第一部分 数理逻辑 数理逻辑又称符号逻辑、理论逻辑。它既是数学的一 个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或
形式逻辑的学科。其研究对象是对证明和计算这两个直观 概念进行符号化以后的形式系统。数理逻辑是数学基础的一 个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属 于单纯逻辑学范畴。 所谓数学方法就是指数学采用的一般方法，包括使用符 号和公式，已有的数学成果和方法，特别是使用形式的公理 方法。

3 第一部分 数理逻辑 数理逻辑的产生 利用计算的方法来代替人们思维中的逻辑推理过程，这种想
法早在十七世纪就有人提出过。莱布尼茨就曾经设想过能不能创 造一种“通用的科学语言”，可以把推理过程象数学一样利用公 式来进行计算，从而得出正确的结论。由于当时的社会条件，他 的想法并没有实现。但是它的思想却是现代数理逻辑部分内容的 萌芽，从这个意义上讲，莱布尼茨可以说是数理逻辑的先驱。 1847年，英国数学家布尔发表了《逻辑的数学分析》，建立了 “布尔代数”，并创造一套符号系统，利用符号来表示逻辑中的 各种概念。布尔建立了一系列的运算法则，利用代数的方法研究 逻辑问题，初步奠定了数理逻辑的基础。

4 第一部分 数理逻辑 十九世纪末二十世纪初，数理逻辑有了比较大的发展，1884 年，德国数学家弗雷格出版了《数论的基础》一书，在书中引入
量词的符号，使得数理逻辑的符号系统更加完备。对建立这门学 科做出贡献的，还有美国人皮尔斯，他也在著作中引入了逻辑符 号。从而使现代数理逻辑最基本的理论基础逐步形成，成为一门 独立的学科。 数理逻辑包括哪些内容呢？ 它的两个最基本的也是最重要的组成部分，就是 “命题演算”和“谓词演算”。

5 第一部分 数理逻辑 主要内容 命题逻辑基本概念 命题逻辑等值演算 命题逻辑推理理论 一阶逻辑基本概念 一阶逻辑等值演算与推理

6 第一章 命题逻辑的基本概念 退出 命题逻辑，也称命题演算，以逻辑运算符结合原子命题来构
成代表“命题”的公式，以及允许某些公式建构成“定理”的一 套形式“证明规则”。 命题逻辑是研究由命题为基本单位构成的前提和结论之间的 可推导关系。 主要内容 命题与联结词 命题及其分类 联结词与复合命题 命题公式及其赋值 退出

7 研究中心 推理 数理逻辑 前提和结论 基本单位 能判断真假 命题 陈述句

8 1.1 命题与联结词 命题与真值 命题：判断结果惟一的陈述句，即是指具有非真必假的陈 命题的真值：判断的结果，
述句； 命题的真值：判断的结果， 真值的取值：仅有两种可能的真值——真和假，且二者只能 居其一。由于命题只有两种真值，所以称这种逻辑为二值逻辑。 命题的真值是具有客观性质的，而不是由人的主观决定的。。 真命题与假命题 注意： 感叹句、祈使句、疑问句都不是命题 陈述句中的悖论，判断结果不惟一确定的不是命题

9 判断给定句子是否为命题，分两步： 首先判定它是否为陈述句， 其次判断它是否有唯一的真值。 例1.1 下列句子中那些是命题？ (1)明年10月1日是晴天. (2) 地球外的星球上也有人. （3）11＋1＝100. 解 （1）、（2）的真值虽然现在还不知道，但它的真值是 唯一的，因而是命题。 （3）在二进制中为真，在十进制中为假，需根据上下文才能 确定其真值，因而不是命题。

10 命题概念 例1.2 下列句子中那些是命题？ (1) 是有理数. (2) 2 + 5 = 7. 假命题 (3) x + 5 > 3.
(1) 是有理数. (2) = 7. (3) x + 5 > 3. (4) 你去教室吗？ (5) 这个苹果真大呀！ (6) 请不要讲话！ (7) 2050年元旦下大雪. 假命题 真命题 不是命题 不是命题 不是命题 不是命题 命题，但真值现在不知道 （8）我正在说假话 悖论 若（8）为真，即“我正在说假话”是真的，则我正在说真话，因而（8）的真值应为假，矛盾；若（8）为假，即“我正在说假话”是假的，则我正在说假话，因而（8）的真值应为真，矛盾，（8）既不能为真也不能为假。悖论

11 命题的分类 1.简单命题(原子命题) 简单构成的命题 (不能分解成更简单的陈述句) 简单命题的真值是确定的，又称为命题常项或命题常元
2.复合命题 由简单命题与联结词按一定规则复合而成的命题 3.命题变项（命题变元） 真值不确定的陈述句，如:x+3>5 注意：命题变元不是命题！

12 简单命题符号化 用小写英文字母 p, q, r, … , pi，qi，ri，… (i≥1）表示 简单命题。 用“1”表示真，用“0”表示假
例如1.2中的（1）、（2），令 p： 是有理数，则 p 的真值为 0 q：2 + 5 = 7，则 q 的真值为 1 称为这些命题的符号化。 命题变项： 也用小写英文字母 p, q, r, … , pi，qi，ri，… (i≥1）表示

13 例1.3 先将下面各陈述句中出现的原子命题符号化，并指出它们的真值，然后再写出这些陈述：
（1） 是有理数是不对的. （2） 2是偶素数. （3） 2或4是素数. （4） 如果2是素数, 则3也是素数. （5） 2是素数当且仅当3也是素数.  

14 将上述原子命题分别符号化为： p： 是有理数； q：2是素数； r：2是偶数； s：3是素数； t：4是素数。 其中 p，t 的真值为0，其余的真值为1： 将 符号代入： (1) “非p”（p不成立）； (2)“q并且（与）r”； （3）“q或t”； （4）“如果q，则s”； （5）“q当且仅当s”。

15 否定、合取、析取联结词 定义1.1 设 p为命题，复合命题“非p”(或“p的否定”)称为p的否定式，记作p，符号  称作否定联结词. 规定p 为真当且仅当p为假. 表1 p  p 1

16 否定、合取、析取联结词 定义1.2 设p,q为两个命题，复合命题“p并且q”(或“p与 q”)称为p与q的合取式，记作p∧q，∧称作合取联结词. 规定p∧q为真当且仅当p与q同时为真. 表2 p q p∧q 1

17 注意： “既……又……”、“不但……而且……”、“虽然……但是……”、“一面……一面……”等联结词都可以符号化为∧.而不要见到与或和就使用联结词∧ . 见下例子 (1)—(3) 说明描述合取式的灵活性与多样性 (4)—(5) 要求分清 “与” 所联结的成分

18 合取联结词的实例 例1.4 将下列命题符号化 （1）吴颖既用功又聪明. （2）吴颖不仅用功而且聪明. （3）吴颖虽然聪明，但不用功.
（4）张辉与王丽都是三好生. （5）张辉与王丽是同学. 解 令 p:吴颖用功, q:吴颖聪明 (1) pq (2) pq (3) pq (4) 设 p:张辉是三好生, q:王丽是三好生 pq (5) p:张辉与王丽是同学

19 否定、合取、析取联结词 定义1.3 设p, q为两个命题，复合命题“p或q”称作p与q的析取式，记作p∨q，∨称作析取联结词. 规定p∨q为假当且仅当p与q同时为假. 如下表3 p q p ∨ q 1

20 注意： 以上定义的吸取式联结词∨与自然语言中的“或” 不完全一样，自然语言中的“或”具有二意性，它有时 具有相容性（即：它联结的两个命题可以同时为真时， p∨q 为真），有时具有排斥性（即：只有当一个为 真，另一个为假时， p∨q才为真），对应的分别称 为相容性和排斥性。

21 析取联结词的实例 例1.5 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数.
例1.5 将下列命题符号化 (1) 2 或 4 是素数. (2) 2 或 3 是素数. (3) 4 或 6 是素数. (4) 小元元只能拿一个苹果或一个梨. (5) 王小红生于 1975 年或 1976 年. 解 先给出原子命题，将其符号化，再将复合命题符号化 (1) 令p:2是素数, q:4是素数, pq ，真 (2) 令p:2是素数, q:3是素数, pq，真 (3) 令p:4是素数, q:6是素数, pq，假

22 析取联结词的实例 (4) 令p:小元元拿一个苹果, q:小元元拿一个梨 取值有4种可能：同真，同假，一真一假（两种）。如果符号化
为 pq，则当p和q同为真时pq为真，即小元元可能同时拿一个苹 果和一个梨，原意是小元元只能挑选苹果和梨中的一个，所以不 能符号化为：pq。 可以使用多个联结词 ，符号化为：(pq)(pq)，此复合命 题为真当且仅当p和q中的一个为真。 (5) p:王小红生于 1975 年, q:王小红生于1976 年, (pq)(pq) ，但在这里，王小红既不可能生于 1975 年又 生于1976 年， p和q不能同时为真，因为也可以符号化为 pq (1)—(3) 为相容或 (4)—(5) 为排斥或, 符号化时(5)可有两种形式，而(4)则不能

23 蕴涵联结词 定义1.4 设p, q为两个命题，复合命题“如果p, 则q”称作p与q的蕴涵式，记作pq，并称p是蕴涵式的前件，q为蕴涵式的后件，称作蕴涵联结词. 规定：pq为假当且仅当p为真q为假. (1) pq 的逻辑关系：q为 p 的必要条件 (2) 在数学中， “如果 p, 则 q” 有很多不同的表述方法： “只要p，就q”； “若p，就q”； “因为p，所以q”； “ p仅当q”； “只有q 才 p”； “ 除非q 才 p ”； “除非q，否则非p”，…． 以上表现形式不一样，但都表示q为 p 的必要条件，因而都 应使用，符号化为pq。

24 蕴涵联结词 (3) 作为“如果 p, 则 q” 的形式化，当p为真q为真时， pq为真； 当p为真q为假时， pq为假；
例：“如果太阳从西边出来，我就不姓张”。前件为假，不管后件是真是 假，，这句话都是对的。 (4)自然语言中， “如果 p, 则 q” 的前件p与后件q 往往有联系，而，数理逻辑是研究抽象的推理，前件p与后件q 可以毫无任何联系。 例：“因为2<3，所以1+1=2”，形式化为pq，且p和q都为真，故pq为真。

25 表4 p q p → q 1

26 蕴涵联结词的实例 例1.5 设 p：天冷，q：小王穿羽绒服，将下列命题符号化 (1) 只要天冷，小王就穿羽绒服. pq
(2) 因为天冷，所以小王穿羽绒服. (3) 若小王不穿羽绒服，则天不冷. (4) 只有天冷，小王才穿羽绒服. (5) 除非天冷，小王才穿羽绒服. (6) 除非小王穿羽绒服，否则天不冷. (7) 如果天不冷，则小王不穿羽绒服. (8) 小王穿羽绒服仅当天冷的时候. pq pq qp qp qp pq pq qp 注意： pq 与 qp 等值（真值相同）

27 等价联结词 定义1.5 设 p, q为两个命题，复合命题“p当且仅当q”称作p与q的等价式，记作pq，称作等价联结词. 规定pq为真当且仅当p与q同时为真或同时为假. pq 的逻辑关系：p与q互为充分必要条件。如下表5 p q p  q 1

28 等价联结词 例1.7 求下列复合命题的真值 (1) 2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6. 1
(1) ＝ 4 当且仅当 ＝ (2) ＝ 4 当且仅当 3 是偶数 (3) ＝ 4 当且仅当 太阳从东方升起 (4) =4 当且仅当 美国位于非洲

29 使用这些联结词有什么好处呢？ 可以将复杂命题表示成简单的符号公式.
以上定义了五种最基本、最常用、也是最重要的联结词┐, ∧, ∨, →, , 将它们组成一个集合{┐, ∧, ∨, →,  }, 称为一个联结词集. 其中┐为一元联结词, 其余的都是二元联结词.   使用这些联结词有什么好处呢？ 可以将复杂命题表示成简单的符号公式. 

30 例1.8 将下列命题符号化, 并讨论它们的真值.    (1) 是无理数当且仅当加拿大位于亚洲.    (2) 2+3＝5的充要条件是 无理数.    解 令 p： 是无理数, 真值为1,    q：加拿大位于亚洲, 真值为0,  (1)符号化为p  q, 其真值为0.    令 r：2＋3＝5, 其真值为1,  (2)符号化为r  p, 真值为1.

31 (3) 若两圆A, B的面积相等, 则它们的半径相等；反之亦然.    (4) 当王小红心情愉快时, 她就唱歌；反之, 当她唱歌时, 一定
心情愉快.  解 令 s：两圆A, B面积相等,    t：两圆A, B的半径相等,  (3)符号化为s  t, 虽然不知道s, t的真值, 但由s与t的内在联 系可知, s  t的真值为1.     令u：王小红心情愉快,  v：王小红唱歌,   则将(4)符号化为u  v.其真值要由具体情况而定.

32 3.复合命题真假值 通常用1表示真, 用0表示假, 复合命题的真假值如表6. 表6 基本复合命题的真值
通常用1表示真, 用0表示假, 复合命题的真假值如表6. 表6 基本复合命题的真值       联结词可以嵌套使用, 在嵌套使用时, 规定如下优先顺序： ( ), ┐, ∧, ∨, →,  , 对于同一优先级的联结词, 先出现者先运算.

33 求下列复合命题的真值： (1) ((┐p∧q)∨(p∧┐q))→r (2) (q∨r)→(p→┐r) (3) (┐p∨r)(p∧┐r)

34 小　结 本小节中p, q, r, … 均表示命题. 联结词集为{, , , , }，p, pq, pq, pq, pq为基本复合命题. 其中要特别注意理解pq的涵义. 反复使用{, , , , }中的联结词组成更为复杂的复合命题. 设 p: 是无理数，q: 3是奇数， r: 苹果是方的， s: 太阳绕地球转 则复合命题 (pq)  ((rs) p) 是假命题. 联结词的运算顺序：, , , , , 同级按先出现者先运算.

35 1.2 命题公式及其赋值 命题变项与合式公式 命题变项 合式公式 合式公式的层次 公式的赋值 公式赋值 公式类型 真值表

36 命题变项与合式公式 命题公式的定义 由于简单命题是真值唯一确定的命题逻辑中最基本的研究单位, 所以也称简单命题为命题常项或命题常元. 从本节开始对命题进一步抽象, 首先称真值可以变化的陈述句为命题变项或命题变元, 也用p,q,r,…表示命题变项. 当p, q, r, …, pi, qi, ri, …,表示命题变项时, 它们就成了取值0或1的变项, 因而命题变项已不是命题. 这样一来, p, q, r, …, pi, qi, ri, …,既可以表示命题常项, 也可以表示命题变项. 在使用中, 需要由上下文确定它们表示的是常项还是变项. 

37 命题变项与合式公式 定义1.6 合式公式（简称公式）:将命题变项用连接词和圆括 按一定的逻辑关系联结起来的符号串。 递归定义：
(1) 单个命题变项和命题常项是合式公式, 称作原子命题公式 (2) 若A是合式公式，则 (A)也是 (3) 若A, B是合式公式，则(AB), (AB), (AB), (AB)也是 (4) 只有有限次地应用(1)—(3) 形成的符号串是合式公式 设A为合式公式，则B为A中的一部分，若B也是合式公 式，称B为A 的子公式。

38 命题变项与合式公式 说明： 1）定义1.6给出的合式公式的定义方式称为归纳或递归定义，
2）定义中引进了A,B等符号，用他们表示任意的合式公式，称作元语言符号；而某个具体的公式，如p,q∨s,(q∨r)→p等称作对象语言符号； 3）(A),(A ∨B）等公式单独出现时，外层括号可以省去，公式中不影响运算次序的括号也可以省去。

39 合式公式的层次 定义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=BC, 其中B,C 的层次及 n 同(b)； (e) A=BC, 其中B,C 的层次及 n 同(b). (3) 若公式A的层次为k, 则称A为k层公式. 例如 公式 A=p, B=p, C=pq, D=(pq)r, E=((pq) r) (rs) 分别为0层，1层，2层，3层，4层公式.

40 公式就代表命题,但代表的命题是真还是假呢？
     在命题公式中, 由于有命题符号的出现, 因而真值是不确定的. 当将公式中出现的全部命题符号都解释成具体的命题之后, 公式就成了真值确定的命题了. 例如, 在公式(p∨q)→r中, 若将p解释成：2是素数, q解释成：3是偶数, r解释成： 是有理数, 则p与r被解释成真命题, q被解释成假命题了, 此时公式(p∨q)→r被解释成：若2是素数或3是偶数, 则 是无理数. 这是一个真命题. 若p, q的解释不变, r被解释为： 是有理数, 则(p∨q)→r被解释成：若2是素数或3是偶数, 则 是有理数. 这是个假命题. 其实, 将命题符号p解释成真命题, 相当于指定p的真值为1, 解释成假命题, 相当于指定p的真值为0.

41 公式赋值 定义1.8 设p1, p2, … , pn是出现在公式A中的全部命题变项,
A为1, 则称这组值为A的成真赋值; 若使A为0, 则称这组值为A的 成假赋值. 几点说明： A中仅出现 p1, p2, … , pn，给A赋值12…n是指 p1=1,p2=2, …, pn=n, i=0或1, i之间不加标点符号 A中仅出现 p, q, r, …, 给A赋值123…是指 p=1, q=2 , r=3 … 含n个命题变项的公式有2n个赋值. 如 000, 010, 101, 110是(pq)r的成真赋值 001, 011, 100, 111是成假赋值.

42 真值表 定义1.9 将命题公式A在所有赋值下取值的情况列成表, 称作 A的真值表. 构造真值表的步骤:
(1) 找出公式中所含的全部命题变项p1, p2, … , pn(若无下角标 则按字母顺序排列), 列出2n个全部赋值, 从000开始, 按 二进制加法, 每次加1, 直至111为止. (2) 按从低到高的顺序写出公式的各个层次. (3) 对每个赋值依次计算各层次的真值, 直到最后计算出公式 的真值为止.

43 真值表 例1.9 写出下列公式的真值表, 并求它们的成真赋值和成假赋值: (1) (pq) r (2) (qp) qp
例 写出下列公式的真值表, 并求它们的成真赋值和成假赋值: (1) (pq) r (2) (qp) qp (3)  (pq) q

44 真值表1 (1) A = (pq) r p q r pq r (pq)r 0 0 0 0 0 1 0 1 0 0 1 1
1 成真赋值:000,001,010,100,110; 成假赋值:011,101,111

45 真值表2 p q qp (qp)q (qp)qp 0 0 0 1 1 0 1 1 1 (2) B＝(qp)qp
0 0 0 1 1 0 1 1 1 成真赋值:00,01,10,11; 无成假赋值

46 真值表3 p q p pq  (pq)  (pq)q 0 0 0 1 1 0 1 1 1
(3) C＝ (pq)q的真值表 p q p pq  (pq)  (pq)q 0 0 0 1 1 0 1 1 1 成假赋值:00,01,10,11; 无成真赋值

47 公式的类型 定义1.10 (1) 若A在它的任何赋值下均为真, 则称A为重言式或永真式;
由例1可知, (pq) r, (qp) qp,  (pq) q 分别为非重言式的可满足式, 重言式, 矛盾式. 注意：重言式是可满足式，但反之不真.

48 从定义不难看出以下几点：   1. A是可满足式的等价定义是：A至少存在一个成真赋值.   2. 重言式一定是可满足式, 但反之不真. 因而, 若公式A是可满 足式, 且它至少存在一个成假赋值, 则称A为非重言式的可满足式.    3. 真值表可用来判断公式的类型:    (1) 若真值表最后一列全为1, 则公式为重言式.     (2) 若真值表最后一列全为0, 则公式为矛盾式.    (3) 若真值表最后一列中至少有一个1, 则公式为可满足式. 

49 注：关于n个命题变元P1,P2,…,Pn,可以构造多少个真值表呢. n个命题变元共产生2n个不同赋值,在每个赋值下,公式的值只有0和1两个值
注：关于n个命题变元P1,P2,…,Pn,可以构造多少个真值表呢? n个命题变元共产生2n个不同赋值,在每个赋值下,公式的值只有0和1两个值. 于是n个命题变元的真值表共有 种不同情况. 因而必有无穷多个公式具有相同的真值表。 真值表的用途: 求出公式的全部成真赋值与成假赋值, 判断公式的类型。

50 例1. 10 下列各公式均含两个命题变项p与q, 它们中哪些具有相同的真值表
例 下列各公式均含两个命题变项p与q, 它们中哪些具有相同的真值表?        (1) p→q        (2) p  q        (3) ┐(p∧┐q)        (4) (p→q)∧(q→p)        (5) ┐q∨p

51  解 表给出了这5个公式的真值表. 从表中可看出,(1),(3)具有相同的真值表,(2),(4)具有相同的真值表. 

52 例1.11 下列公式中,哪些具有相同的真值表?       (1) p→q       (2) ┐q∨r       (3) (┐p∨q)∧((p∧r)→p)       (4) (q→r)∧(p→p)
  解 本例中给出的4个公式,共同含有3个命题变项, r在公式(1)中不出现, 称为(1)的哑元, p是公式(2)中的 哑元, 讨论它们是否有相同的真值表时, 均按三个命题 变项写出它们的真值表.

53 下面列出这4个公式的真值表, 中间过程省略了. 从表中看出, (1)与(3)有相同的真值表, (2)与(4)有相同的真值表.  4个公式的真值表

54 第一章 习题课 主要内容 命题、真值、简单命题与复合命题、命题符号化 联结词, , , , 及复合命题符号化 命题公式及层次
公式的类型 真值表及应用 基本要求 深刻理解各联结词的逻辑关系, 熟练地将命题符号化 会求复合命题的真值 深刻理解合式公式及重言式、矛盾式、可满足式等概念 熟练地求公式的真值表，并用它求公式的成真赋值与成假赋值及判断公式类型

55 练习1 1. 将下列命题符号化 (1) 豆沙包是由面粉和红小豆做成的. (2) 苹果树和梨树都是落叶乔木.
(3) 王小红或李大明是物理组成员. (4) 王小红或李大明中的一人是物理组成员. (5) 由于交通阻塞，他迟到了. (6) 如果交通不阻塞，他就不会迟到. (7) 他没迟到，所以交通没阻塞. (8) 除非交通阻塞，否则他不会迟到. (9) 他迟到当且仅当交通阻塞.

56 练习1解答 提示： 分清复合命题与简单命题 分清相容或与排斥或 分清必要与充分条件及充分必要条件
答案: (1) 是简单命题 (2) 是合取式 (3) 是析取式（相容或）(4) 是析取式（排斥或） 设 p: 交通阻塞，q: 他迟到 (5) pq, (6) pq或qp (7) qp 或pq, (8) qp或pq (9) pq 或pq 可见(5)与(7)，(6)与(8) 相同（等值）

57 练习2 2. 设 p : 2是素数 q : 北京比天津人口多 r : 美国的首都是旧金山 求下面命题的真值 (1) (pq)r
(2) (qr)(pr) (3) (qr)(pr) (4) (qp)((pr)(rq)) 1

58 练习3 3. 用真值表判断下面公式的类型 (1) pr(qp) (2) ((pq) (qp)) r
(3) (pq) (pr)

59 练习3解答 (1) pr(qp) p q r qp (qp) pr(qp) 0 0 0 0 0 1 0 1 0
1 矛盾式

60 练习3解答 (2) ((pq) (qp)) r 1 0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1
((pq) (qp)) r qp pq p q r 永真式

61 练习3解答 (3) (pq) (pr) p q r pq pr (pq) (pr) 0 0 0 0 0 1 0 1 0
1 非永真式的可满足式