离散数学(1) 逻辑命题

命题逻辑

命题

命题 (Proposition)是一个定义事物和现象的陈述句。

比如说:

  1. 我刚吃完饭 (命题)

  2. 雪是白色的 (命题)

  3. 太阳从西边升起 (命题)

  4. 1 + 1 = 1 (命题)

  5. 你吃饭了吗? (非命题)

  6. 这真是个好主意!(非命题)

  7. 今天下雨了(命题)

  8. 我带雨伞出门(命题)

所有命题都有一个属性,或真或假。比如上面的例子中命题3,4基于事实是个假命题。

如果一个命题是真命题,他的真值就是__真(T)__;相反,如果一个命题是假命题,他的真值就是 假(F)

逻辑

我们可以用字母来表示这些命题,并且加入逻辑运算符来将两个命题合并起来,我们称他们为复合命题


我们可以用 \neg , ~, 或上划线 \overline{p} 符号来表示和命题相反的事实。

例如:

让 p = “1 + 1 = 1”, 那么 \neg p 的意思就是"1 + 1 \not = 1"

让 q = “雪是白色的”, 那么 \neg q 表示"雪不是白色的"

可以发现, 经过"非" 这个逻辑运算符,命题的真值会被改变。下面是该逻辑运算符的真值表(truth table)

| p | \neg p |

| — | — |

| T | F |

| F | T |


我们可以用 \wedge 来表示表示"p 并且 q"。

例如:

p: “他是男生”

q: “他是个程序员”

p \wedge q 的意思就是 “他是个男生,并且他是个程序员”

真值表中,只有当两个命题的真值为真的时候才是真,其余为假。

| p | q | p \wedge q |

| — | — | — |

| T | T | T |

| T | F | F |

| F | T | F |

| F | F | F


我们可以用 \vee 来表示表示"p 或者 q"。

例如:

p: “他是男生”

q: “他是女生”

p \vee q 的意思就是 “他是个男生或者女生”

真值表中,任何一个命题为真都能使整个复合命题的真值成真。

| p | q | p \vee q |

| — | — | — |

| T | T | T |

| T | F | T |

| F | T | T |

| F | F | F | |


我们可以用 \rightarrow 来表示 “如果A 则 B”

例如:

p: “他感冒了”

q: “他不能喝冷饮”

p \rightarrow q 的意思就是 “如果他感冒了,他就不能喝冷饮”

真值表中,只有当条件为真的时候,结果才为真。

| p | q | p \rightarrow q |

| — | — | — |

| T | T | T |

| T | F | T |

| F | T | F |

| F | F | F | |


我们可以用 \leftrightarrow 来表示"A 当且仅当 B"

例如:

p: “小明和小红是朋友”

q: “小明和小红经常一起玩耍”

p \leftrightarrow q 的意思就是 “小明和小红是朋友,当且仅当小明和小红经常一起玩耍”。

不必怀疑中文水平,这句话的意思表达了两个意思

  1. 如果小明和小红是朋友,则他们两个经常一起玩耍

  2. 如果小明和小红互相认识,他们两个就是朋友。

换句话说, p \leftrightarrow q = (p \rightarrow q) \wedge (q \rightarrow p)

他的真值表长这样

| p | q | p \leftrightarrow q |

| — | — | — |

| T | T | T |

| T | F | F |

| F | T | F |

| F | F | T | |


另外还有其他复合命题如逻辑异或等就不一一列举了。知道两个以上的命题组成的命题叫复合命题之后,我们可以给那些不能再分解成更小的命题的命题下定义了

原子命题不包含其他命题作为其组成部分的命题,即在结构上不能再分解出其他命题的命题.又称简单命题。原子命题不能带有非,或,且,如果,那么等联结词。 (百度百科)

如何判断复合命题的真值?

我们知道给出一个原子命题,它的真值非真即假。那复合命题的真值怎么确定呢?

真值表

经过上面对复合命题的介绍,我们知道真值表是一个表格,它将命题的所有真值都列了出来。假设一个复合命题有n个子命题,那么这个复合命题的真值表就有$2^n$行。

例如 (p \rightarrow q) \wedge (q \rightarrow p) 有p和q两个子命题。那么这个复合命题的表格就有 2^2 = 4 行。

| p |q |

| — | — |

| | |

| | |

| | |

| | |

我们将表格第一列对半分填上真和假两种类型的值(第一种真值类型必须填真)

| p |q |

| — | — |

| T | |

| T | |

| F | |

| F | |

然后第二列在第一列的基础上再对半分写出真和假两种值

| p | q |

| — | — |

| T | T |

| T | F |

| F | T |

| F | F |

以此类推,不管有多少子命题,最后一列真值总能是真假互换地将表格填完的。

接下来我们将上面的逻辑表达式填到新加的列中。

| p | q | (p \rightarrow q) \wedge (q \rightarrow p) |

| — | — | — |

| T | T | |

| T | F | |

| F | T | |

| F | F | |

逻辑表达式的先后顺序总是有括号先算括号内,其余按照以下的优先规则:¬高于∧,∧高于∨,∨高于→。我们先看括号内的逻辑表达式, p \rightarrow q 在 p和q都为真的情况下真值为真 q \rightarrow p 同理。

我们再看括号外的的$\vee$, 在前后两个命题为真的情况下 T \wedge T ,真值为真, 所以第一行我们填真

| p | q | (p \rightarrow q) \wedge (q \rightarrow p) |

| — | — | — |

| T | T | T |

| T | F | |

| F | T | |

| F | F | |

依此类推,我们将整个表格填完

| p | q | (p \rightarrow q) \wedge (q \rightarrow p) |

| — | — | — |

| T | T | T |

| T | F | F |

| F | T | F |

| F | F | T |

如此,复合命题的真值就确定了。给出子命题的真值后,复合命题的真值也能推算出来。

两种特殊命题

当复合命题的真值永远为真,即子命题的真假不影响复合命题的真假时,我们说这个复合命题叫永真式(tautology);当复合命题的真值永远为假的时候,我们称这个复合命题叫永假式(contradiction),也叫矛盾式

另外,当两个命题的真值一样的时候,我们说两个命题相等。在上面的阅读中,我们讲到
p \leftrightarrow q = (p \rightarrow q) \wedge (q \rightarrow p)

同时我们也看到他们的真值是一样的。事实上我们应该用 \equiv 符号来表示两个命题相等。

课后作业

让p = “今天下雨了”, q = “我要带伞出门”, r = “今天天气不错”

请写出以下句子的符号

  1. “如果今天下雨,我就带伞出门”

  2. “今天天气不错,今天没有下雨”

  3. ”今天没有下雨,所以我不用带伞出门"

  4. ”我不带伞出门,但是如果我带了,说明今天会下雨"

找出下列句子中的命题并符号化(注明所用字母所代表的命题)

  1. 2大于1且3大于2, 所以3大于1

  2. 我只有早上错过公交车以后才用嘀嘀打车

  3. 为什么这么简单的道理他都不懂?

  4. 谁知道呀!

  5. 我首先是个女生,然后才是个护士。

  6. 我是个程序员而且是个企业高管。

用真值表证明 (p \rightarrow q) \vee (q \vee p) 是一个永真式。

用真值表证明 p \rightarrow q \equiv \neg p \vee q

"这句话的真值是假的"是一个命题吗?

1 个赞

:sweat_smile:好像坛子的markdown还不支持表格…大家翻翻书看看真值表吧。Google也行

先码后看,欢迎伊洛老师讲课.