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 为例:
- AL、BL 是原子,单独一个原子就是句子。
- AL、BL 都是句子,所以 AL ∨ BL 是句子。
- AL ∨ BL 是句子,所以 ¬(AL ∨ BL) 是句子。
- ¬(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,从最紧的往外套括号:
-
¬ 先结合紧挨着的原子:¬Q、¬W。
-
再 ∧:P ∧ (¬Q)。
-
再 ∨:(P ∧ (¬Q)) ∨ R。
-
再 ⇒:((P ∧ (¬Q)) ∨ R) ⇒ S。
-
最后 ⇔ 把整句劈成两半,右边是 ¬W。
怎么算
结果是 (((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 年就画过类似的矩阵。
直觉
一个解释就是给每个原子各发一张「真」或「假」的牌。牌发定了,整句的真假就跟着定了,没有别的自由度。
两个原子,每个两种牌,一共四种发法;n 个原子就是 2ⁿ 种。真值表就是把这 2ⁿ 种发法一行一行列出来。其中让整句为真的那些行,叫这句话的模型。
五条语义规则里,前四条都符合直觉。最反直觉的是 ⇒:前件为假时,整个蕴含算真。「如果我是校长,就给全校放假」,我不是校长时,这句话不算说谎。这叫空真(vacuous truth)。
一步一步看
目标:在 S1、S2 的四种组合上逐个算五个连接词,尤其看 ⇒ 为什么只在前真后假那行为假。
-
列出 S1、S2 的四种组合:真真、真假、假真、假假。
-
¬S1 把 S1 反过来。
-
S1 ∧ S2 只有两个都真才真;S1 ∨ S2 只要有一个真就真。
-
S1 ⇒ S2 只在「前真后假」那一行为假,其余三行都真。
-
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))。两个原子,四个解释,逐行算:
-
AL 为真、BL 为真:AL ∨ BL 为真,第一项是 T ⇒ F,为假,整句为假。
-
AL 为真、BL 为假:AL ∨ BL 仍为真,第一项还是 T ⇒ F,整句为假。
-
AL 为假、BL 为真:第一项前件为假,空真;第二项 T ⇒ T,为真。整句为真。
-
AL 为假、BL 为假:AL ∨ BL 为假,第二项 T ⇒ 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 分钟怎么用:合上页面,先默写优先级顺序和 ⇒ 的四行真值;再在纸上从定原子开始,把岛民第一句完整做一遍;最后做变式题。回查最容易错的地方:只写了一条蕴含就去画真值表。
必背
- 一个逻辑系统 = 语法(结构)+ 语义(含义)+ 推理规则;只看符号形状的是语法,要代入真值判断的是语义
- 连接词优先级 ¬ > ∧ > ∨ > ⇒ > ⇔,恰好是它们在课件符号表里出现的顺序
- S1 ⇒ S2 在 S1 为假时为真(空真),且 S1 ⇒ S2 ≡ ¬S1 ∨ S2——这条等价是转 CNF 的关键
- 解释 = 给每个原子赋真值,n 个原子有 2ⁿ 个解释;模型 = 让句子为真的解释
- 岛民第一句要写两条蕴含 (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 为假。
解法:
- 定原子。选「是不是骗子」,不选「话真不真」,两者由岛规绑定。
- 翻译 A 的话。至少一个骗子 = AL ∨ BL。
- 分两种情况套岛规。A 是骗子,话为假:AL ⇒ ¬(AL ∨ BL)。A 不是骗子,话为真:¬AL ⇒ (AL ∨ BL)。
- 两种情况同时成立,用且连起来:(AL ⇒ ¬(AL ∨ BL)) ∧ (¬AL ⇒ (AL ∨ BL))。
- 列真值表,两个原子,四个解释:
| 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 |
- 结论。只有第三行成立,只有一个模型:¬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。
个人整理的学习笔记,不是官方材料;数字与结论以课件和讲师为准。