Name: Password: Sign in

[Lecture 1] 命题

(该系列文章主要为 《离散数学及其应用》 快速回顾所作的记录。期望有更深理解的同学欢迎参考原书并与我交流讨论:)

1 命题与复合命题

  • 命题是一个或真或假的陈述,不能既真又假
  • 命题可以由字母表示,例如 p,q,r,s,值为真即 T, 否则为 F
  • 复合命题由命题组合而来,以下是几种逻辑运算符,用于产生复合命题
    • (非)命题 p 产生其否定命题 ¬p, ¬pp 值相反
    • (与)命题 pq 合取 pq,当且仅当 pq 均为 TpqT
    • (同或)命题 pq 析取 pq, 当且仅当 pq 均为 FpqF
    • (异或)命题 pq 异或 pq, 当且仅当 pq 一真一假时为 T

2 条件语句

2.1 条件语句

  • (蕴含)pq 均为命题, pq 是命题 “若 pq”,当 pTqFpq 为假,否则为真。 其中 p 是前提, q 是结论。条件语句有如下种表述方式 :

注意到,如果 pF,那么无论 q 的结果如何命题 pq 都为 T,对于理解这样推导的含义,我们有以下荒诞的命题:

如果今天星期六, 那么 2 + 3 = 6

只有在今天星期六的情况下我们才来判断这个命题的真假(取决于 q)。如果今天不是星期六(注意到我们以整个命题本身作为判断的标准)这句话并没有说错,所以值为真。

(另外,条件语句之间可以不存在任何联系)

(注意到逻辑中的条件语句与程序语言中的 if p then S 不同, S 并不是命题)

2.2 条件语句的衍生

  • 由条件语句 pq 可以衍生出其他三种命题:
    • (逆蕴含,逆命题):qp, 结论反推前提,原命题为真逆命题不一定为真
    • (倒置蕴含,逆否命题):¬q¬p,即只有 ¬q 为真(qF), ¬p 为假(pT)命题为假,即该命题与原命题等价(两个复合命题总是具有相同的真值表的时候我们说他们 等价),具有相同的值
    • (反蕴含,否命题):¬p¬q, 前提为假则结论为假,原命题为真否命题不一定为真;可以证明其与逆命题等价

2.3 双条件语句

  • (双蕴含)pq : 两个命题具有相同真值时为真,否则为假

双条件语句还有其他几种表述,例如 「 pq 的充分必要条件」、「 p 当且仅当 q 」、「 (pq)(qp)

双条件语句为真时,pq 等价。

3 复合命题真值表

一旦我们掌握了简单命题与逻辑连接词(运算符) 「和取(与) 、析取(同或) ,异或 ,条件 、 双条件 、 否定(非) ¬ 」,我们就可以用它们构造复杂的复合命题。

3.1 简单复合命题真值表

我们先来看一些已经讨论过的简单复合命题的真值表:

p q pq pq pq pq pq ¬p
F F F F F T T T
F T F T T T F T
T F F T T F F F
T T T T F T T F

这些是我们构造复杂复合命题真值表的基础。

3.2 复杂复合命题真值表

我们以 (¬pq)(p¬q) 为例来说明一个较为复杂的复合命题该如何确定真值表。

  • 有 2 个命题变元,因此共 4 种真值组合 FF, FT, TF, TT,列表 4 行
  • 第 3 列 ¬p 真值由第 1 列确定,第 4 列 ¬q 真值由第 2 列确定
  • 第 5 列 ¬pq 真值由第 2, 3 列确定,第 6 列 p¬q 真值由第 1, 4 列确定
  • 第 7 列 (¬pq)(p¬q) 真值由第 5, 6 列确定
p q ¬p ¬q ¬pq p¬q (¬pq)(p¬q)
F F T T T T T
F T T F T T F
T F F T F T F
T T F F T F F

整个过程就像搭积木一样,有了原料(简单命题)与搭建方式(逻辑运算符)就可以一步步搭建复杂复合命题并由上面的方法来确定真值表。

3.3 逻辑运算符的优先级

理论上我们可以用括号来指明所有优先级的顺序。当然,在减少括号的情况下有一些约定俗成的优先级规则,优先级(由高到低)顺序如下:

  • ()
  • ¬

4 翻译自然语句

由于自然语言很多时候具有二义性,因而要判断一个语句的真值,我们需要将其翻译为由命题变量和逻辑运算符组成的表达式(还是一个命题),考虑以下句子:

如果你可以访问校园网,那么你主修计算机或者不是新生。

(不要在意上面这个句子的黑点:)

我们可以将基本逻辑变元提取出来,假设 acf 分别代表 「你可以访问校园网」、「你主修计算机」、「你不是新生」,那么以上句子可以翻译为:

a(c¬f)

5 系统规范说明的一致性

在我们构造硬件或软件系统(或者其他系统)时,我们希望将系统规范说明翻译为没有歧义的逻辑表达式,按照上面的讨论我们已经能做到这一点。以此同时,我们也希望这样一套系统本身不存在冲突,即存在保证所有规范说明为真的一组逻辑变元,在此情况下我们说系统规范说明是一致的。考虑以下说明:

  • 诊断消息存储在缓冲区中或者被重传
  • 诊断消息没有存储在缓冲区中
  • 如果诊断消息存储在缓冲区中,那么它被重传

假设 pq 为 「诊断消息存储在缓冲区中」、「诊断消息被重传」,那么上述规范说明可以被翻译成 pq¬ppq。要使所有规范说明为真,参考以下真值表:

p q pq ¬p pq
F F F T T
F T T T T
T F T F F
T T T F T

可以看到,根据第 2 行,当 pF, qT 时所有规范说明均为真,该规范说明是一致的。

但如果此时我们将规范说明添加进 「诊断消息不被重传」,即 ¬q,真值表变为:

p q pq ¬p pq ¬q
F F F T T T
F T T T T F
T F T F F T
T T T F T F

观察到没有任何一组 pq 能使得所有规范说明为真,所以此时系统规范说明并不一致。

6 逻辑运算与位运算

6.1 位运算

计算机用「位」表示信息,一个位可以包含两种状态: 0 或 1,习惯上我们将 0 对应 「假」,1 对应 「真」,这样的变量我们称之为 「布尔变量」,对应的是逻辑变元。

计算机同样有位运算对应的逻辑运算符,AND 代表与 OR 代表同或 XOR 代表异或 , 假设有布尔变量 xy, 我们同样有真值表:

x y xy xy xy
0 0 0 0 0
0 1 0 1 1
1 0 0 1 1
1 1 1 1 0

于是我们就可以利用「位运算符」对任意一位信息进行处理。

6.2 位串运算

位串是 0 个或多个位序列,例如 0000 1111, 将位运算的概念扩展,相同长度的位串可以定义 按位 AND, 按位 OR, 按位 XOR 运算,即对位串中相同位置的每一位进行位运算,得到一个新的位串:

有两个位串 1 00111 1001 ,那么按位 AND1 0001, 按位 OR1 1011, 按位 XOR0 1010

Copyright (c) 2014-2016 Kyles Light.
Powered by Tornado.
鄂 ICP 备 15003296 号