← COMP5511 全部讲次
L03b-1 · 第 3 周

L03b-1 命题逻辑的语法与语义:把一句话写成符号,再用真值表一行一行算

从零讲命题、五个连接词、优先级、解释与真值表,最后把岛民 A 的一句话翻成式子,用四行真值表算出谁在说谎。

一句话版

命题逻辑把一句话拆成只能取真或假的小符号,用五个连接词把它们接起来;给每个符号定一个真假,整句的真假就能一行一行算出来。

这一讲的前半段只做两件事:规定符号串怎么写才合法(语法),规定它在每种真假组合下取什么值(语义)。下一页 L03b-2 再按「有几行为真」给句子分类。

先认识这几个词

词 全称 / 读法 一句人话
命题 / 原子 proposition / atom 能判真假、在当前写法里不再拆开的一句话,记成 P、Q 这样的字母
¬ ∧ ∨ 读「非」「且」「或」 取反;两边都真才真;有一边真就真
⇒ / ⇔ 读「蕴含」/「当且仅当」 「如果…那么…」/ 两边真假必须相同
语法 / 语义 syntax / semantics 管句子长什么样 / 管句子什么时候为真
解释 interpretation 给每个原子各定一个真假,一种定法就是一个解释
模型 model 让整句为真的那些解释
真值表 truth table 把所有解释逐行列出来,一行一行算整句真假

一个类比:一间审讯室,证词全都只能是真或假

你面前坐着两个人。规矩是:每个人要么句句实话,要么句句谎话,没有中间态。你要从他们的话里推出一个确定的结论。

语法管笔录该怎么写才合规:哪些符号能接在一起,没有括号时先算哪个。语义管把具体真假代进去之后,整句成不成立。判据很干脆:只看形状的归语法,要代值的归语义。

有了这两层,审讯就能机械地做。把某人说的话翻成符号,把「要么全真要么全假」这条规矩也翻成符号,两边用「且」连起来,然后穷举所有真假组合,看哪几行成立。

成立的行数就是答案。只剩一行,你能锁定谁在说谎;剩好几行,这句证词信息量很小;一行都不剩,这句话在规矩下根本说不出口。

类比在哪里失效:

  • 真实证人可以半真半假,命题逻辑只有 True 和 False 两个值。
  • 笔录里的「如果…就…」带因果,逻辑里的 ⇒ 不管因果,只管真假组合。

从零讲起

1. 命题和五个连接词

它解决什么问题

日常语言含糊。「下雨而且刮风」「如果你努力就能拿 A+」这种话,要让机器去推,先得把它们变成形状固定、能一步步拆开检查的符号串。命题逻辑给出最小的积木(命题)和把积木接起来的五种接头(连接词)。

直觉

一个命题就是一个只能回答「对」或「错」的陈述句,比如「Snow is white」。问句和命令句不行,「关上门」没有真假。

在命题逻辑里,一个命题被整个当成一个字母,比如 P。「所有人都会死」也只能是一个字母,拆不出「人」和「死」,那是后面一阶逻辑(FOL)才做的事。课件说命题逻辑是一阶逻辑的特例,指的就是这个:它只有整句的真假,没有对象、谓词和量词。

五个连接词是 ¬(非)、∧(且)、∨(或)、⇒(如果…那么)、⇔(当且仅当)。

一步一步看

目标:从两个原子出发一层层套上连接词,看 ¬(AL ∨ BL) ⇔ AL 怎样按递归规则长成合法句子。

合法句子是从原子出发、一层层套连接词「长」出来的。以 ¬(AL ∨ BL) ⇔ AL 为例:

  1. AL、BL 是原子,单独一个原子就是句子。
  2. AL、BL 都是句子,所以 AL ∨ BL 是句子。
  3. AL ∨ BL 是句子,所以 ¬(AL ∨ BL) 是句子。
  4. ¬(AL ∨ BL) 和 AL 都是句子,所以 ¬(AL ∨ BL) ⇔ AL 是句子。
连接词 英文名 读法 构造规则
¬ negation not S 是句子 ⟹ ¬S 是句子
∧ conjunction and S1、S2 是句子 ⟹ S1 ∧ S2 是句子
∨ disjunction or S1、S2 是句子 ⟹ S1 ∨ S2 是句子
⇒ implication if…then S1、S2 是句子 ⟹ S1 ⇒ S2 是句子
⇔ biconditional if and only if S1、S2 是句子 ⟹ S1 ⇔ S2 是句子

这种「如果 S 是句子,那么 ¬S 也是句子」的写法叫递归定义,套多少层都合法。

怎么判断

给你一个说法,问它属于语法层还是语义层,只问一句:要不要代入真值?

「P ∧ ¬Q ∨ R 是合法句子」只看形状,是语法。「P ∧ ¬Q ∨ R 在 P 为真、Q 为假、R 为假时为真」要代值,是语义。课件把一个逻辑系统分成三层:语法、语义,再加上后半讲的推理规则(怎么从已知推出未知)。

常见误解

以为原子就是「很短的句子」

原子的标准是「在你选定的写法里不再拆」,和长短无关。「香港冬天比北京冷」很长,在命题逻辑里也只是一个原子。

以为 ∨ 是「二选一」

命题逻辑的 ∨ 是相容或:两边都真,整句也真。日常说「喝茶或咖啡」常带「只选一个」的意思,逻辑里没有这层。

试一下

下面哪些是命题:「Snow is white」「把门关上」「2 比 3 大」「今天会下雨吗」?

「Snow is white」和「2 比 3 大」是命题,前者真、后者假,假的命题也是命题。「把门关上」是命令,「今天会下雨吗」是问句,都没有真假,不是命题。

2. 没有括号时先算哪个:优先级

它解决什么问题

P ∧ Q ∨ R 到底是 (P ∧ Q) ∨ R,还是 P ∧ (Q ∨ R)?两种读法在 P 为假、R 为真时结果不同。优先级规定了唯一的读法,就像算术里先乘除后加减。

直觉

优先级越高,抓得越紧。¬ 最紧,只抓紧挨着它的那一个;⇔ 最松,最后才把整句劈成两半。

从高到低:¬ > ∧ > ∨ > ⇒ > ⇔。这个顺序正好是五个连接词在课件符号表里出现的顺序,背符号表就背下了优先级。

一步一步看

目标:按优先级从最紧的连接词往外加括号,看 P ∧ ¬Q ∨ R ⇒ S ⇔ ¬W 只剩一种读法。

拿课件的例子 P ∧ ¬Q ∨ R ⇒ S ⇔ ¬W,从最紧的往外套括号:

  1. ¬ 先结合紧挨着的原子:¬Q、¬W。

  2. 再 ∧:P ∧ (¬Q)。

  3. 再 ∨:(P ∧ (¬Q)) ∨ R。

  4. 再 ⇒:((P ∧ (¬Q)) ∨ R) ⇒ S。

  5. 最后 ⇔ 把整句劈成两半,右边是 ¬W。

    一串没有括号的式子 P ∧ ¬Q ∨ R ⇒ S ⇔ ¬W,下方五层括号线从内到外依次套住 ¬Q 和 ¬W、P ∧ ¬Q、再加 ∨ R、再加 ⇒ S,最外层青绿线是 ⇔ 把整句劈成两半,底部写出加满括号的结果

怎么算

结果是 (((P ∧ (¬Q)) ∨ R) ⇒ S) ⇔ (¬W)。

意思是:先找优先级最低的 ⇔,从它那里劈成左右两块;左块里再找最低的 ⇒ 劈开,依此类推,一直劈到只剩原子。从外往里劈和从里往外套,得到的括号完全一样,考场上从外往里更快。

常见误解

以为 ¬ 会管到后面一整串

¬ 只抓紧挨着的那一个。¬P ∧ Q 是 (¬P) ∧ Q,不是 ¬(P ∧ Q)。要否定一整块,必须自己加括号。

试一下

给 ¬A ∨ B ∧ C ⇒ D ⇔ E 加上全部括号。

先 ¬A;再 B ∧ C;再 (¬A) ∨ (B ∧ C);再 ⇒ D;最后 ⇔ E。结果是 ((((¬A) ∨ (B ∧ C)) ⇒ D) ⇔ E)。注意 ∧ 比 ∨ 紧,所以是 B ∧ C 先结合,不是 ¬A ∨ B 先结合。

3. 解释与真值表:句子什么时候为真

它解决什么问题

语法只说句子长什么样,没说它对不对。要判断一句话的真假,得先知道每个原子取什么值,再按规则一层层往上算。语义就是这套规则。

从哪来(补充)

把所有真假组合排成一张表逐行算,这个方法一般归功于哲学家 Ludwig Wittgenstein,他在 1918 年完成、1921 年出版的《逻辑哲学论》里用它并让它流行起来。同一年 Emil Post 也独立提出了同样的方法。更早的 C. S. Peirce 在 1883 年就画过类似的矩阵。

出处:Wikipedia: Truth table

直觉

一个解释就是给每个原子各发一张「真」或「假」的牌。牌发定了,整句的真假就跟着定了,没有别的自由度。

两个原子,每个两种牌,一共四种发法;n 个原子就是 2ⁿ 种。真值表就是把这 2ⁿ 种发法一行一行列出来。其中让整句为真的那些行,叫这句话的模型。

五条语义规则里,前四条都符合直觉。最反直觉的是 ⇒:前件为假时,整个蕴含算真。「如果我是校长,就给全校放假」,我不是校长时,这句话不算说谎。这叫空真(vacuous truth)。

一步一步看

目标:在 S1、S2 的四种组合上逐个算五个连接词,尤其看 ⇒ 为什么只在前真后假那行为假。

  1. 列出 S1、S2 的四种组合:真真、真假、假真、假假。

  2. ¬S1 把 S1 反过来。

  3. S1 ∧ S2 只有两个都真才真;S1 ∨ S2 只要有一个真就真。

  4. S1 ⇒ S2 只在「前真后假」那一行为假,其余三行都真。

  5. S1 ⇔ S2 在两边真假相同时为真。

    五个连接词的真值表:S1、S2 四种组合下 ¬S1、S1∧S2、S1∨S2、S1⇒S2、S1⇔S2 的取值,S1 为假的两行里 S1⇒S2 都是 T,用青绿框标出,注明这叫空真,并提示这一列和 ¬S1∨S2 四行相同

怎么算

课件的例子:算 (P ∧ Q) ∨ R 在两个解释下的真值。

  • 解释一 P=T、Q=F、R=F:(T ∧ F) ∨ F = F ∨ F = F。
  • 解释二 P=F、Q=F、R=T:(F ∧ F) ∨ T = F ∨ T = T。

意思是:同一个句子,换一组牌就换一个结果;句子本身没有固定的真假,真假永远是「在某个解释下」的真假。

还有一条马上要用的等价:把 S1 ⇒ S2 那一列和 ¬S1 ∨ S2 并排算,四行完全相同,所以 S1 ⇒ S2 ≡ ¬S1 ∨ S2。后面转 CNF 消掉 ⇒,靠的就是它。

常见误解

以为 ⇒ 表示因果

⇒ 只管真假组合,唯一被禁止的是「前真后假」。「如果 1+1=2,那么月亮是圆的」在逻辑里为真,两件事之间没有任何因果。

以为解释和模型是一回事

解释是任意一种发牌方式,模型是其中让句子为真的那几种。n 个原子永远有 2ⁿ 个解释,模型可以是 0 个,也可以是全部。

试一下

P=F、Q=T 时,P ⇒ Q、Q ⇒ P、¬P ∨ Q 各是什么?

P ⇒ Q:前件 P 为假,空真,T。Q ⇒ P:前件 Q 为真、后件 P 为假,前真后假,F。¬P ∨ Q:¬P 为真,T。第一个和第三个一样,正好验证了 P ⇒ Q ≡ ¬P ∨ Q。

4. 把一句话翻成式子,再查表:岛民 A 说了什么

它解决什么问题

前三节给齐了工具。这一节把它们用在一道完整的题上:岛上每个人要么永远说真话、要么永远说假话。你遇到 A 和 B,A 说「At least one of us is a liar」(我们至少有一个骗子)。能推出什么?

直觉

难点不在算,在翻译。光把 A 的话写成符号不够,还得把「骗子说的话为假、老实人说的话为真」这条岛规也写进去。A 要么是骗子要么不是,两种情况各写一条蕴含,再用「且」连起来。

只写一条,另一种情况就没人管,真值表会多出不该有的行。

一步一步看

目标:把岛民 A 的话翻成式子再逐行查四个解释,看最后只剩「A 说真话、B 是骗子」这一行为真。

先定原子:AL 表示「A 是骗子」,BL 表示「B 是骗子」。A 的话是 AL ∨ BL。

  • A 是骗子,他的话为假:AL ⇒ ¬(AL ∨ BL)。
  • A 不是骗子,他的话为真:¬AL ⇒ (AL ∨ BL)。

整句是 (AL ⇒ ¬(AL ∨ BL)) ∧ (¬AL ⇒ (AL ∨ BL))。两个原子,四个解释,逐行算:

  1. AL 为真、BL 为真:AL ∨ BL 为真,第一项是 T ⇒ F,为假,整句为假。

    岛民真值表第 1 帧:表头是 AL、BL、AL∨BL、两条蕴含和整句,第一行 AL、BL 都为 T,第一项 T⇒F=F,整句 F,用青绿框标出,其余三行显示问号

  2. AL 为真、BL 为假:AL ∨ BL 仍为真,第一项还是 T ⇒ F,整句为假。

    岛民真值表第 2 帧:第二行 AL 为 T、BL 为 F,第一项仍是 T⇒F=F,整句 F,用青绿框标出,注明 AL 为真的两行第二项不用看

  3. AL 为假、BL 为真:第一项前件为假,空真;第二项 T ⇒ T,为真。整句为真。

    岛民真值表第 3 帧:第三行 AL 为 F、BL 为 T,第一项空真,第二项 T⇒T=T,整句 T 用青绿标出

  4. AL 为假、BL 为假:AL ∨ BL 为假,第二项 T ⇒ F,为假,整句为假。

    岛民真值表第 4 帧:第四行 AL、BL 都为 F,AL∨BL 为 F,第二项 T⇒F=F,整句 F;底部注明四行里只有第三行为真

怎么判断

四行里只有第 3 行为真,这句话只有一个模型:¬AL ∧ BL。结论是 A 说真话,B 是骗子。

判断时先看 AL:AL 为真的两行,第一项永远是 T ⇒ F,不用看第二项就判假;AL 为假的两行,第一项永远空真,只看第二项。四行只要真算两次。

两条蕴含合起来,其实就是 AL ⇔ ¬(AL ∨ BL):A 是骗子,当且仅当他的话为假。课件写成两条,是为了把两种情况摆在明处。

常见误解

只写「A 是骗子则他的话为假」这一条

少了 ¬AL ⇒ (AL ∨ BL),第 4 行(两人都不是骗子)会变成真,答案就多出一个。岛规是双向的,两条都要写。

把原子定成「A 的话为真」

原子要选「A 是不是骗子」。话的真假由岛规和身份决定,选错原子会让岛规写不进式子。

试一下

同一个岛,这次 A 说「B is a liar」(B 是骗子)。只写式子,不用列表:整句是什么?

A 的话就是 BL。A 是骗子则话为假:AL ⇒ ¬BL;A 不是骗子则话为真:¬AL ⇒ BL。整句是 (AL ⇒ ¬BL) ∧ (¬AL ⇒ BL)。完整的真值表放在下面的变式题里。

把它们串起来

这半讲只做一件事:把一句自然语言变成可以机械检查的东西。

起点是一个承诺。符号之间的「推出」(entail)要对应现实之间的「随之发生」(follow),逻辑推理靠得住,全靠这条对应。所以翻译要小心,翻错了,后面算得再对也没用。

有了承诺,需要一套精确的符号语言。命题是积木,五个连接词是接头,递归定义说明怎么接都合法;优先级说明没有括号时怎么读。

语义接着给每个句子定真假。规则只有五条,最容易错的是 ⇒:前件为假时整句为真。有了语义,任何句子都能用真值表逐行算出来。

岛民题把这些串成一条完整的流水线:定原子、翻译原话、把岛规写成两条蕴含、列四行表、数成立的行。第一句话只剩一行,所以结论唯一。

这条路的代价也露出来了:n 个原子要 2ⁿ 行。下一页先用「数成立的行」给句子分类,后半讲再换成只碰相关句子的推理规则。

课件里的坑

  • [课件留白] 课件只把岛民第一句形式化并列了真值表,另外两句留成练习不给答案;它们放在下一页(p.6、p.16)
  • [易漏] 岛民式子要写两条蕴含,只写一条锁不住唯一解;两条合起来等价于 AL ⇔ ¬(AL ∨ BL)(p.11)
  • [易错] ⇒ 列在前件为假的两行都是 T,验算岛民真值表时最容易在这两行算错(p.14、p.15)
  • [读图] 课件 p.11 右下角的「True or False?」是提示下一步要列真值表,不是问这句话本身真不真(p.11)

课后 10 分钟:考点复习

这 10 分钟怎么用:合上页面,先默写优先级顺序和 ⇒ 的四行真值;再在纸上从定原子开始,把岛民第一句完整做一遍;最后做变式题。回查最容易错的地方:只写了一条蕴含就去画真值表。

必背

  1. 一个逻辑系统 = 语法(结构)+ 语义(含义)+ 推理规则;只看符号形状的是语法,要代入真值判断的是语义
  2. 连接词优先级 ¬ > ∧ > ∨ > ⇒ > ⇔,恰好是它们在课件符号表里出现的顺序
  3. S1 ⇒ S2 在 S1 为假时为真(空真),且 S1 ⇒ S2 ≡ ¬S1 ∨ S2——这条等价是转 CNF 的关键
  4. 解释 = 给每个原子赋真值,n 个原子有 2ⁿ 个解释;模型 = 让句子为真的解释
  5. 岛民第一句要写两条蕴含 (AL ⇒ ¬(AL ∨ BL)) ∧ (¬AL ⇒ (AL ∨ BL)),只写一条锁不住答案;唯一模型是 ¬AL ∧ BL,A 说真话、B 是骗子

课件例题

例 1(课件 p.6、p.11、p.15):岛民 A 说「At least one of us is a liar」,形式化并求结论

见下方完整例题。

例 2(课件 p.12):给 P ∧ ¬Q ∨ R ⇒ S ⇔ ¬W 加上全部括号

题面:按连接词优先级,把这串没有括号的式子补成唯一的读法。

提示

先找优先级最低的 ⇔,从那里劈成两半。

解答

(((P ∧ (¬Q)) ∨ R) ⇒ S) ⇔ (¬W)。顺序是先 ¬ 结合最近的原子(¬Q、¬W),再 ∧(P ∧ ¬Q),再 ∨(… ∨ R),再 ⇒(… ⇒ S),最后 ⇔ 把整句劈成两半。

例 3(课件 p.13):求 (P ∧ Q) ∨ R 在两个解释下的真值

题面:解释一是 P=T、Q=F、R=F,解释二是 P=F、Q=F、R=T,分别算整句真假。

提示

括号里的 ∧ 先算,再和 R 做 ∨。

解答

解释一:(T ∧ F) ∨ F = F ∨ F = F。解释二:(F ∧ F) ∨ T = F ∨ T = T。同一个句子换一组真假就换了结果,句子的真值完全由解释决定。

完整例题

题面(课件 p.6、p.11、p.15):岛上每个人要么永远说真话,要么永远说假话。你遇到 A 和 B,A 说「At least one of us is a liar」。能推出什么?

约定:AL = A is a liar,BL = B is a liar;T 为真,F 为假。

解法:

  1. 定原子。选「是不是骗子」,不选「话真不真」,两者由岛规绑定。
  2. 翻译 A 的话。至少一个骗子 = AL ∨ BL。
  3. 分两种情况套岛规。A 是骗子,话为假:AL ⇒ ¬(AL ∨ BL)。A 不是骗子,话为真:¬AL ⇒ (AL ∨ BL)。
  4. 两种情况同时成立,用且连起来:(AL ⇒ ¬(AL ∨ BL)) ∧ (¬AL ⇒ (AL ∨ BL))。
  5. 列真值表,两个原子,四个解释:
AL BL AL ∨ BL AL ⇒ ¬(AL∨BL) ¬AL ⇒ (AL∨BL) 整句
T T T T ⇒ F = F 前件 F,空真 T F
T F T T ⇒ F = F 前件 F,空真 T F
F T T 前件 F,空真 T T ⇒ T = T T
F F F 前件 F,空真 T T ⇒ F = F F
  1. 结论。只有第三行成立,只有一个模型:¬AL ∧ BL,A 说真话,B 是骗子。

要点:两条蕴含缺一不可;AL 为真的两行看第一项就能判假,AL 为假的两行只看第二项。

答题格式:先写原子定义,再写整句式子,再画完整四行真值表(每个中间列都写出来),最后一句话写结论并点明「only one model」。

变式题(先自己做)

(1) 改编自课件 p.11–15:岛规不变,A 说的是「B is a liar」。形式化,列真值表,数模型并写出结论。 (2) 改编自课件 p.12:给 P ⇒ Q ∧ R ∨ ¬S ⇔ T 加上全部括号。 (3) 改编自课件 p.13:算 ¬P ∨ Q ∧ R 在 P=T、Q=T、R=F 下的真值(注意优先级)。

提示

(1) A 的话就是 BL,照样写两条蕴含。(2) 先劈 ⇔,再劈 ⇒,∧ 比 ∨ 紧。(3) 先加括号再代值。

判分点与答案(非官方评分标准)

判分点:① (1) 两条蕴含都要写,四行都要算;② (1) 结论要写成 A、B 之间的关系;③ (2)(3) 括号位置对才给分。

(1) 整句 (AL ⇒ ¬BL) ∧ (¬AL ⇒ BL)。

AL BL AL ⇒ ¬BL ¬AL ⇒ BL 整句
T T T ⇒ F = F 空真 T F
T F T ⇒ T = T 空真 T T
F T 空真 T T ⇒ T = T T
F F 空真 T T ⇒ F = F F

2 个模型,结论不唯一:AL 和 BL 一真一假,也就是 AL ⇔ ¬BL。A、B 恰好一个是骗子,但分不出是谁。

(2) (P ⇒ ((Q ∧ R) ∨ (¬S))) ⇔ T。

(3) 读作 (¬P) ∨ (Q ∧ R) = F ∨ (T ∧ F) = F ∨ F = F。

闪卡自测

1. 一个逻辑系统由哪三部分组成?怎么区分语法和语义?

语法(结构)、语义(含义)、推理规则(怎么推)。只看形状的是语法,要代真值的是语义(p.8)。

2. 「PL 是 FOL 的特例」具体差在哪?

PL 的原子只有整句话的真假,没有对象、谓词和量词。「所有人都会死」在 PL 里只能是一个符号,FOL 里才能写成带 ∀ 的形式(p.3)。

3. 五个连接词的优先级从高到低是什么?

¬ > ∧ > ∨ > ⇒ > ⇔,和它们在符号表里出现的顺序相同(p.10、p.12)。

4. S1 ⇒ S2 什么时候为假?

只有 S1 为真、S2 为假这一行。S1 为假时整句为真,叫空真(p.14)。

5. 解释和模型的区别是什么?n 个原子有几个解释?

解释是给每个原子各定一个真值,n 个原子有 2ⁿ 个;模型是其中让句子为真的那些(p.13)。

6. 岛民第一句为什么要写两条蕴含?结论是什么?

A 要么是骗子要么不是,两种情况各对应一条岛规,缺一条会多出错误的模型。结论 ¬AL ∧ BL,只有一个模型(p.11、p.15)。

下一讲

同样是数真值表里成立的行,下一页按行数给句子分出可满足、不可满足、有效三类,再用整列对比判断两句话是否等价。见 L03b-2。

下一讲 →
L03b-2 L03b-2 可满足、有效与等价:数真值表里有几行为真

个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。