Chapter 1 Tutorials

标签：Chapter 算符 land neg lor forall Tutorials rightarrow

T1

今有一逻辑表达式\(F_0\)为：

\[(p\rightarrow r)\rightarrow ((q\rightarrow r) \rightarrow (p\lor q)\land \neg r) \]

其中的联结词运算优先级与命题逻辑合式公式完全相同。观察\(F_0\)的形式，完成以下两个题目

(1)补全真值表

p	q	r	\(p\rightarrow r\)	\(q\rightarrow r\)	\((p\lor q)\land \neg r\)	\((q\rightarrow r)\rightarrow (p\lor q)\land\neg r \)	\(F_0\)
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

解

推荐做法是背算符/联结词的真值，把整个题拆成每一步只加一个算符，然后口算填表。

比如这个题当中，

• 要从\((p\lor q)\land \neg r\)里拆出\(p\lor q\)和\(\neg r\)，

• 并注意到\(q\rightarrow r\)和\((p\lor q)\land \neg r\)是\((q\rightarrow r)\rightarrow (p\lor q)\land\neg r\)的左右两边

• 而\(p\rightarrow r\)和\((q\rightarrow r)\rightarrow (p\lor q)\land\neg r\)又是\(F\)的左右两边

然后口算出答案即可

熟练情况下这道题应该能在3分钟以内搞定，但从考场情况来看，过半数同学在同类型题目上花费了超过10分钟，希望大家多加练习以避免这种局面

p	q	r	\(p\rightarrow r\)	\(q\rightarrow r\)	\((p\lor q)\land \neg r\)	\((q\rightarrow r)\rightarrow (p\lor q)\land\neg r \)	\(F_0\)
0	0	0	1	1	0	0	0
0	0	1	1	1	0	0	0
0	1	0	1	0	1	1	1
0	1	1	1	1	0	0	0
1	0	0	0	1	1	1	1
1	0	1	1	1	0	0	0
1	1	0	0	0	1	1	1
1	1	1	1	1	0	0	0

T2

形如\(L\Delta R\equiv F\)的表达式被称作缩写定义。其中，\(L,R\)是变量/变元，\(F\)是表达式/公式，\(\Delta\)是被定义的算符/联结词。可以通过缩写定义，使用已知算符/联结词定义新的算符/联结词。

<1> 下面请使用\(0,1,L,R,\neg,\oplus\)和括号构造\(F\)，不考虑优先级，通过缩写定义来定义8个「本质不同的」二元算符。Hint：没有要求必须是新算符

• 例：\(L\Delta_1 R \equiv 1\)

<2> 推断能否用这些符号定义更多「本质不同的」二元算符，并简要说明理由，言之有理即可。

解

这道题用到了数理逻辑中一种常见而又独特的方法——通过「归类」解决问题。这种方法在这里的具体表现就是：

站在更高的高度，讨论算符本身具有什么性质，以及它们之间如何互相转化

\(L\)	\(R\)	\(L\Delta R\)
0	0	?
0	1	?
1	0	?
1	1	?

首先你应该注意到二元算符的总数是有限的，因为真值表一共只有四行，真值情况一共只有\(2^4=16\)种。而算符的真值表相同意味着不论两边的\(L,R\)怎么变化，最终算出的结果都保持一致，也就是「本质相同」。所以尽管你可以把\(F\)构造得非常复杂，但你能表达的本质不同的二元算符不可能多于\(16\)个。

进一步，你会发现我给你的符号在真值表里都拥有偶数个\(1\)，于是自然产生假设：

这些符号的组合可能无法表达有奇数个\(1\)的情况

因而表出的上限应该减半，变成\(8\)个。实际上，我们在第二章最后一个小结将严格证明这一点——只用真值表里有偶数个\(1\)的联结词永远无法表达有奇数个\(1\)的情况。

<1> \(0,1, L,\neg L, R, \neg R, L\oplus R, L\leftrightarrow R\Leftrightarrow \neg(L\oplus R)\)

<2> 注意到所给符号只能构造出真值表中有偶数个1的二元联结词，而这种联结词一共\({4 \choose 0} + {4\choose 2} + {4\choose4} = 8\)个

T3

以下对算符/联结词的优先级排序，正确的是

• A: $[\neg] > [\oplus] > [\land] > [\lor] > [\rightarrow] > [\leftrightarrow] $

• B: \([\neg] > [\land] > [\lor] > [\oplus] > [\rightarrow] > [\leftrightarrow]\)

• C: \([\neg] > [\land] > [\oplus]> [\lor] > [\rightarrow] > [\leftrightarrow]\)

• D: \([\neg] > [\land] > [\lor] > [\rightarrow] >[\oplus] > [\leftrightarrow]\)

解

B，记住就行，异或的优先级比或/析取更低

T4

代换式、替换式

• 求代换式\((P\rightarrow(Q\rightarrow P))[P/P\rightarrow R]\)

• 求替换式\((P\lor R \rightarrow P\lor R\land S)[(P\lor R)/(P\land R)]\)

• 已知\(P,Q,R,S\)是命题逻辑合式公式，\(P\)是\(Q\)的子公式，\(R\)不是\(Q\)的子公式，用\(Q^1\equiv Q[P/R]\)和「替换操作」表达\(Q^2\equiv Q[P/S]\)

  考虑另一边，一定可以用\(Q^2\)和替换操作表达\(Q^1\)吗？

  • 替换操作例：\(A[B/C][C/D]\cdots[Y/Z] \equiv_? A[B/Z]\)

解

• \((P\rightarrow R)\rightarrow(Q\rightarrow(P\rightarrow R))\) 记得加括号

• \(P\land R\rightarrow P\lor R \land S\) 小心被省略的括号

• \((Q^1[R/P])[P/S]\) 或\(Q^1[R/S]\)

• \(Q^2\)不能通过替换变成\(Q^1\)，因为\(S\)可能是\(Q\)的子公式。

  • 比如假设\(Q\equiv P\land S\)，则\(Q^2\equiv S \land S\)，从而\(Q^2[S/R]\equiv R\land R \not\equiv Q^1=R\land S\)

T5

计算下列逻辑合式公式的复杂度

1. \(P\land P\land P \land \neg P\)

2. \(0\lor 1 \oplus 0 \lor 1\)

3. \(\neg\forall x\neg P(x, y, z) \land \exists z Q(a,b,c)\)

解

注意原子公式的复杂度是 \(0\)

<1>

<2>

<3>

T6

与我们的课程不同，另一种优先级约定如下：

1. \(\forall, \exists\)等量词可与联结词比较优先级，且它们的优先级与\(\neg\)相同

2. 优先级相同时优先计算右侧算符

请完成以下几个问题：

<1> 使用题给约定计算 \(P\land P\land P \land \neg P\)的复杂度

<2> 分别基于题给约定和课程约定补全\(P\rightarrow P\rightarrow P\)中省略的括号，并借助相应的逻辑表达式\(p\rightarrow p\rightarrow p\)的真值情况讨论二者是否等价

<3> 简述两种约定下如何确定量词的辖域(当然更严谨的说法是确定变元出现的辖域)，并简单比较两者的差异

解

<1>

<2>

• 题给： \(P\rightarrow(P\rightarrow P)\)

• 课程： \((P\rightarrow P)\rightarrow P\)

• 不等价，题给约定下是永真式，课程约定下则不是

<3>

• 题给：将量词看成特殊的联结词，求出相应的子公式即可，参见T5(3)

• 课程：量词右侧第一个语法正确的合式公式

• （个人觉得题给更简洁，笑）

T7

判断下列说法的正确性

• 谓词逻辑中\(0,1\)通常被看作个体常元而非合式公式，因此属于非逻辑符号 ✔️ 谓词逻辑确实很少有\(0,1\)作为逻辑符号的情况，而举例说明的时候却常常把\(\{0, 1\}\)当作个体对象

• 若\(c\)是常元，\(t\)是项，则\([c/t]\)是代入实例 ✖️ \([x/t]\)才是，其中\(x\)是变元

• 闭公式拥有它的代入 ✖️ 没有自由变元，所以没有代入

• 当可以讨论取值时，函词的值是个体，谓词的值不是个体 ✔️ 注意二者的差别，在可以讨论取值的情况下，谓词的值是逻辑真值

• 若\(f^n\)是\(n\)元函词，\(t_1, t_2, \cdots, t_m\)是项，则必有\(f^n(t_1, t_2, \cdots, t_m)\)是项 ✖️ 当且仅当\(m=n\)

T8

指出以下谓词逻辑合式公式中

• 变元的出现情况和辖域

• 变元\(x\)对公式中自由变元的可代入情况

<1> \(\forall x \exists y P(x,y,z)\)

<2> \(\exists y \forall x Q(x,y,z)\)

<3> \(\forall x(\forall x P(x) \rightarrow Q(x))\)

解

注意我们认为 \(\forall x P(x)\) 中的两个 \(x\) 属于同一次出现

<1> \(x,y\)是约束出现。\(x\)出现的辖域是\(\exists y P(x,y,z)\)；\(y\)出现的辖域是\(P(x,y,z)\)。\(z\)是自由出现。\(x\)关于\(z\)不可代入

<2> \(x,y\)是约束出现。\(x\)出现的辖域是\(Q(x,y,z)\)；\(y\)出现的辖域是\(\forall x Q(x,y,z)\)。\(z\)是自由出现。\(x\)关于\(z\)不可代入

<3> \(x\)是约束出现。\(x\)第一次出现的辖域是\(\forall x P(x)\rightarrow Q(x)\)；\(x\)第二次出现的辖域是\(P(x)\)。没有自由变元

T9

• “比目鱼有两只眼睛。”是命题 ✔️

• “y目鱼有四只眼睛。”是命题 ✖️ 命题形式不是命题

• “这句话是假的。”是命题 ✖️ 悖论语句不是命题

• “如果比目鱼有两只眼睛，那么独角兽有两只角。”是命题 ✔️ 两原子命题用联结词联结

• “抛开事实不谈，比目鱼难道不是只有两只眼睛吗？”是命题 ✖️

T10

以下诗句和解释是\(P\rightarrow (Q\rightarrow R), Q\models P\rightarrow R\)的实例，请指出其中\(P,Q,R\)的具体含义。

“花近高楼伤客心，万方多难此登临。” 时局多难是诗人感到伤心的根本原因，正是多难的时局才导致诗人见到楼台花开却感到伤心。

解

P：“万方多难”诗人身处多难时局

Q：“花近高楼”诗人见到楼台花开

R：“伤客心”诗人感到伤心

T11

以下文言和解释是\(P\rightarrow Q, Q\rightarrow R \models P\rightarrow R\)的实例，请指出其中\(P,Q,R\)的具体含义。

“王侯将相宁有种乎？”秦朝的残酷统治引发了一系列农民起义，这些农民起义严重动摇了秦朝的统治根基并最终瓦解了秦帝国。

解

P：秦朝施行残酷统治

Q：秦末农民起义四起

R：秦朝统治根基被动摇/帝国土崩瓦解

T12

以下数学语句不是推论式\(P\rightarrow Q, Q\rightarrow R\models P\rightarrow R\)的实例，请说明为何该语句不是题给推论式的实例

因为 1<2, 2<3 所以 1<3

解

言之有理即可

这个例子默认了「小于关系」的传递性，因此前件总共有三个，与题目要求不符。在这个例子中还无法提取出对应的P,Q,R，这是本例的另一个错误点。实际上，本例只是说明了「小于关系」和「蕴含关系」都具有传递性，与题目要求并无太大关系，同学们需要避免出现这种情况。

T13

将命题符号化，不要使用\(\exists !,\exists!!\)

<1>

设论域为全体学生，将「李华是我们班学习最好的学生」符号化。其中：

1. 常元\(a\)代表李华

2. 谓词\(S(x)\)表示\(x\)是我们班的学生

3. 谓词\(G(x,y)\)表示\(x\)成绩比\(y\)好

4. 谓词\(D(x,y)\)表示\(x,y\)是同一个人

<2>

设论域为全体实数，将「存在唯一偶素数」符号化。其中：

1. 谓词\(E(x)\)表示\(x\)是偶数

2. 谓词\(P(x)\)表示\(x\)是素数

3. 谓词\(x=y\)表示\(x,y\)相等

解

<1>

1. 首先，李华是我们班的学生：\(S(a)\)

2. 学习最好的学生：\(\forall x \big(S(x) \land \neg D(x, a) \rightarrow G(a, x)\big)\)

3. 注意，\(G(x,y)\)表示成绩严格好，因此\(\forall x \big(S(x) \land G(x, a) \rightarrow D(a, x)\big)\)不正确

于是答案为

\[S(a) \land \forall x \big( S(x) \land \neg D(a, x) \rightarrow G(a, x) \big) \]

注意： 不少同学漏掉了第一点

<2>

1. 存在性：\(\exists x \big(E(x) \land P(x)\big)\)

2. 唯一性：\(\forall x \forall y \big(E(x)\land P(x)\land E(y)\land P(y) \rightarrow x=y \big)\)

于是答案为

\[\exists x \bigg( E(x) \land P(x) \land \forall y \bigg( E(y)\land P(y) \rightarrow x = y \bigg) \bigg) \]

注意： 不少同学漏掉了存在性。

此外，还出现了含有\(x=2\)的答案，显然不能得分。需要指出的是，数域的定义并不是一件显然的事，在未给出严格定义时，并不能认为素偶数是2。

T14

用合适的联结词将以下函数项级数收敛的定义符号化

对于\(\forall \epsilon>0\)有

对于\(\forall x\in X\)，\(\exists N\in \mathbb N^*\)，使得

对于\(\forall n>N\)，都有\(|S_n(x) - S(x)| < \epsilon\)成立

请将\(\epsilon > 0\)、\(x\in X\)、\(N\in \mathbb N^*\)、\(|S_n(x) - S(x)| < \epsilon\)分别看作关于\(\epsilon\)的一元谓词、关于\(x\)的一元谓词、关于\(N\)的一元谓词和关于\(n,x,\epsilon\)的三元谓词直接使用。

解

\[\forall \epsilon \bigg( \epsilon > 0 \rightarrow \forall x \big( x\in X \rightarrow \exists N (N \in \mathbb N^* \land \forall n (n>N \rightarrow |S_n(x) - S(x)| < \epsilon)) \big) \bigg) \]

注意避坑：

1. 漏掉对某些变元的约束，尤其以漏掉约束\(x\)和\(n\)的量词最为常见
2. 辖域错误，比如将\(N\in \mathbb N^*\)放进\(\forall n\)的辖域里，最后一个蕴含号的左半部分变成\(N\in \mathbb N^* \land n>N\)。显然只要\(N\notin \mathbb N^*\)就能使整个式子成立
3. 联结词错误，较低级的错误例如直接把各个谓词用\(\land\)联结，较高级的错误例如将\(N\in \mathbb N^*\)后面的\(\land\)写成\(\rightarrow\)

T15

1. 给出一个属于肯定前件的论证式的实例 (\(P\rightarrow Q, P \models Q\))
2. 给出一个属于否定后件的论证式的实例 (\(P\rightarrow Q, \neg Q \models \neg P\))
3. 举一反例说明否定前件的论证式的谬误 (\(P\rightarrow Q, \neg P \models \neg Q\))
4. 举一反例说明肯定后件的论证式的谬误 (\(P\rightarrow Q, Q \models P\))

解

参照分步答案，举出的实例中应有\(P,Q\)明确的对应，言之有理即可

• <3> 中，如果下雨P，我就带伞Q；没下雨；则我没带伞。这个论证是谬误，但有同学给出了错误理由：“没带伞可能是时间紧迫等其他原因，所以不能推出”。显然这里应该指出“我没带伞”这个结果可能不对，即“就算没下雨，我也带伞”的可能性

标签：Chapter,算符,land,neg,lor,forall,Tutorials,rightarrow
From： https://www.cnblogs.com/fallqs/p/18086577