\[ \def\A{\mathfrak{A}} \]
本节知识点
表达式是符号的任意有限序列。大多数表达式没有意义，项和合式公式是具有特定意义的表达式。
项定义为在常数符号和变量之前加上函数符号构成的表达式。
原子公式的做工相当于命题逻辑中的命题符号，原子公式是具有如下形式的表达式： \[ Pt_1t_2\dots t_n \] 合式公式（或公式）是指由原子公式通过使用 0 次或多次连接符号和量词符号构成的表达式。
自由变量是“没有量词约束”的变量。
以上都是语法概念，与语义无关。
教材 2.2 真值与模型
习题 3：证明：\(\set{\forall x(\alpha \to \beta), \forall x\alpha} \models \forall x \beta\)
证明：对每个结构 \(\mathfrak{A}\) 和每个函数 \(s: V \to | \A |\)，有 \(\models_\A \forall x(\alpha \to \beta)[s]\) 和 \(\models_\A \forall x \alpha[s]\)，即 \(\models_\A \forall x((\alpha \to \beta) \land \alpha)[s]\)。因此 \[ \models_\A \forall x((\alpha \to \beta) \land \alpha)[s] \\ \iff \forall d \in \A. \models_\A((\alpha \to \beta) \land \alpha)[s(x|d)] \\ \iff \forall d \in \A. \models_\A(\beta \land \alpha)[s(x|d)] \\ \iff \models_\A \forall x(\beta \land \alpha)[s] \\ \iff \models_\A \forall x(\beta)[s] \land \models_\A \forall x(\alpha)[s] \\ \] \(Q.E.D.\)
习题 4：证明：如果 \(x\) 在 \(\alpha\) 中不是自由出现的，那么 \(\alpha \models \forall x \alpha\)。
证明：对每个结构 \(\mathfrak{A}\) 和每个函数 \(s: V \to | \A |\)，由定理 22A，有： \[ \models_\A\forall x \alpha[s] \iff \forall d \in |\A|. \models_\A \alpha[s(x|d)] \\ \iff \models_\A \alpha[s] \\ \]
习题 9：设语言具有相等和二元谓词符号 \(P\)。对下面的条件中的每一个，找出一个句子 \(\sigma\) 使得结构 \(\A\) 是 \(\sigma\) 的模型，当且仅当条件被满足。
- 中恰好有两个元素
下面的句子 \(\sigma\) 满足要求 \[ \exists x \exists y x \neq y \land \forall x \forall y \forall z (x = y \lor y = z \lor z = x) \] 该句子用自然语言描述，即集合中存在至少两个不相等的元素，且任意三个元素中都至少有两个相等，因此集合中只存在两个不相等的元素。
习题 11：给出能够在 \((\mathbb{N}; +, \cdot )\) 中定义如下每个关系的公式，假设语言具有相等符号和参数 \(\forall, +, \cdot\)。
\(\set{0}\)
\(\set{1}\)
\(\set{\langle m, n\rangle | n 是 \mathbb{N} 中 m 的后继}\)
\(\set{\langle m, n\rangle | 在 \mathbb{N} 中 m < n}\)
\(\forall x y \cdot x = y\)
\(\forall x y \cdot x = y\)
\(\exists x (n = m + x \land \forall y x \cdot y = y)\) 即 \(n = m + 1\)
\(\exists x (n = m + x \land \exists y x \cdot y \ne x)\) 即 \(n=m+x \land x \neq 0\)
