计算机科学家逻辑/命题逻辑/语义

定义 3 (命题逻辑的语义)

对于我们命题形式语言的语义，我们不参考特定的意图解释。此外，我们只对真值感兴趣。我们假设对原子公式的真值的初始赋值，并在此基础上，我们定义更复杂公式的真值。真值的集合是集合$\{true,false\}$. 对于原子公式集$D$，赋值是一个函数

${\mathcal {A}}|D$$\to \{true,false\}$. 设$E$是包含$D$的公式集，即$E\supseteq D$，并且恰好是那些可以根据语法定义从$D$构造的公式。那么，${\mathcal {A}}$在$E$上的扩展，${\mathcal {A}}_{E}|E\to \{true,false\}$，给出如下

• $A\in D$ : ${\mathcal {A}}_{E}(A)={\mathcal {A}}(A)$

• ${\mathcal {A}}_{E}((F\land G))={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=true{\text{ and }}{\mathcal {A}}_{E}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {A}}_{E}((F\lor G))={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=true{\text{ or }}{\mathcal {A}}_{E}(G)=true\\\;\;\,false&otherwise\end{cases}}$

• ${\mathcal {A}}_{E}(\lnot F)={\begin{cases}\;\;\,true&{\text{if }}{\mathcal {A}}_{E}(F)=false\\\;\;\,false&otherwise\end{cases}}$

在下文中，我们将省略索引 $E$ 来指示赋值 ${\mathcal {A}}$ 的扩展。请注意，这是将类型为 $(F\land G)$ 的公式命名为合取式，将类型为 $(F\lor G)$ 的公式命名为析取式，将类型为 $\lnot F$ 的公式命名为否定式的正确位置。

以下是通过定义${\mathcal {A}}$进行的示例评估：假定给定${\mathcal {A}}(A)=true,{\text{ }}{\mathcal {A}}(B)=true$ 和 ${\mathcal {A}}(C)=false$，那么

${\mathcal {A}}(\lnot ((A\land B)\lor C))$

${\text{ }}={\begin{cases}\;\;\,true&{\text{ if }}{\mathcal {A}}((((A\land B))\lor C))=false\\\;\;\,false&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))\lor C))=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))))=true{\text{ or }}A(C)=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}((((A\land B))))=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}={\begin{cases}\;\;\,false&{\text{ if }}{\mathcal {A}}(A)=true{\text{ and }}{\mathcal {A}}(B)=true\\\;\;\,true&\;otherwise\end{cases}}$

${\text{ }}=false$

定义 4

令 ${\mathcal {A}}$ 是一个赋值，而 $F$ 是一个公式。 ${\mathcal {A}}$ 被称为 $F$ 的赋值，如果 ${\mathcal {A}}$ 对 $F$ 的每个子公式都有定义。如果 ${\mathcal {A}}$ 是 $F$ 的赋值，并且 ${\mathcal {A}}(F)=true$，我们称 ${\mathcal {A}}$ 是 $F$ 的模型，并写成 ${\mathcal {A}}\models F$ 如果 ${\mathcal {A}}$ 是 $F$ 的赋值，并且 ${\mathcal {A}}(F)=false$，我们写成 ${\mathcal {A}}\nvDash F$.

一个公式 $F$ 被称为可满足的，当且仅当存在一个模型 $F$ ，否则 $F$ 被称为不可满足的。 $F$ 被称为有效的（或为重言式）当且仅当对 $F$ 的每一个赋值都是一个模型。我们写作 $\models F$ 或者 $\nvDash F$ 。

定理 1

一个公式 $F$ 是有效的，当且仅当 $\lnot F$ 是不可满足的。

证明： $F$ 是一个重言式

当且仅当对 $F$ 的每一个赋值都是一个模型 $F$

当且仅当对 $F$ 的每一个赋值（当然，这也是对 $\lnot F$ 的赋值）不是模型 $\lnot F$

当且仅当 $\lnot F$ 没有模型

当且仅当 $\lnot F$ 是不可满足的。

定义 5 (结论)

如果对于公式 $G$ 和 $F_{1},\cdots ,F_{k}$ 的任何赋值 ${\mathcal {A}}$ 都成立：如果 ${\mathcal {A}}$ 是 $F_{1},\cdots ,F_{k}$ 的模型，那么 ${\mathcal {A}}$ 也是 $G$ 的模型。我们将这种情况记作 $\{F_{1},\cdots ,F_{k}\}\models G$.

以下定理是定义的一个简单推论。

定理 2

$G$ 被称为公式 $F_{1},\cdots ,F_{k}$ 的推论，

当且仅当 $((\bigwedge _{i=1}^{k}~F_{i})\to G)$ 是重言式

当且仅当 $((\bigwedge _{i=1}^{k}~F_{i})\land ~\lnot G)$ 是不可满足的。

很明显，一个公式的有效性只取决于其原子子公式的赋值：如果 ${\mathcal {A}}$ 和 ${\mathcal {A}}'$ 是 $F$ 的赋值，并且它们对每个出现的原子子公式都产生相同的值，那么 ${\mathcal {A}}(F)={\mathcal {A}}'(F)$ 成立。因此，我们可以说，为了检验一个公式 $F$ 的有效性，只需要检验其原子子公式的无限多个赋值。这种检验可以用下表的形式轻松地描述出来，其中 $F$ 是一个任意的公式，包含 $n$ 个不同的原子公式 ${\mathcal {A}}_{i}$。

	${\mathcal {A}}_{1}$	$\cdots$	${\mathcal {A}}_{n-1}$	${\mathcal {A}}_{n}$	$F$
${\mathcal {A}}_{1}$	false	$\cdots$	false	false	${\mathcal {A}}_{1}(F)$
${\mathcal {A}}_{2}$	false	$\cdots$	false	true	${\mathcal {A}}_{2}(F)$
${\mathcal {A}}_{2}n$	true	$\cdots$	true	true	${\mathcal {A}}_{n}(F)$

在应用此过程时，引入子公式的中间结果可能会有所帮助，如下面的示例所示。

$A$	$B$	$\lnot A$	$A{\text{ }}\to {\text{ }}B$	($\lnot {\text{ }}A{\text{ }}\to {\text{ }}(A{\text{ }}\to {\text{ }}B$ ))
false	false	true	true	true
false	true	true	true	true
true	false	false	false	true
true	true	false	true	true

请注意，我们只是描述了检查公式有效性的算法。假设公式包含 $n$ 个原子子公式，那么我们刚刚构建的表格将包含 $2^{n}$ 行。为了估计这种指数级算法的成本，假设计算一行需要 1 微秒。如果 $F$ 仅包含 100 个原子子公式，则计算表格将需要 $2^{100}$ 微秒。

真值表

命题公式是否可满足的问题称为 SAT，相应的重言式问题称为 TAUT。

SAT 是一个 NP 完全问题，因此目前尚不清楚 SAT 是否是易处理的。TAUT 是否属于 NP 仍然是一个开放问题。对于 TAUT，我们知道，它属于 NP 当且仅当 NP 在补运算下是封闭的。SAT 和 TAUT 都在复杂性理论研究中发挥着重要作用，特别是在关于 $P=NP$ 的问题方面。

问题

问题 1（命题）

计算以下公式的真值表。确定每个公式是否有效（重言式）、可满足或不可满足。

1. $(A\land B)\land (B\to C)$
2. $(A\land B)\leftrightarrow (\lnot A\lor \lnot B)$
3. $(\lnot A\lor \lnot (\lnot B\lor A))\lor A$
4. $(A\to (B\land C))\leftrightarrow ((A\to B)\land (A\to C))$
5. $(A\lor (B\land A))\land ((C\lor \lnot C)\to \lnot A)$
6. $((C\lor B)\land (C\lor \lnot B))\land \lnot C$
7. $\lnot (\lnot A\lor \lnot (\lnot B\lor \lnot A))$
8. $(A\to (B\to A))$
9. $(A\lor (B\land A))\land ((C\lor \lnot C)\to \lnot A)$
10. $((A\lor \lnot B)\lor ((\lnot A\land \lnot C)\land B))\leftrightarrow ((A\lor \lnot C)\lor \lnot B)$
11. $\lnot (A\land \lnot (B\land \lnot C))$

问题 2（命题逻辑）

“你长寿的秘诀是什么？”有人问一位百岁老人。他回答道：“我严格遵守以下饮食规则：如果我晚餐不喝酒，我就总是吃鱼。每当我晚餐吃鱼和酒，都是不放蒜的。如果我吃蒜或喝酒，我就会避免吃鱼”。

1. 用命题逻辑的形式化这些规则。
2. 尝试简化这位百岁老人的建议。

问题 3（命题逻辑）

通过对命题公式的构造进行归纳，递归地定义以下函数

1. $\alpha (F)$: $F$ 中的原子公式集
2. $\beta (F)$: $F$ 中的二元连接词 $\land$ 和 $\lor$ 的数量

注意：对于

$F$ = $(\lnot (A\lor B)\lor C)$ $\land$ $((\lnot A\lor B)\land C)$

$\alpha (F)=\{A,B,C\}$ 并且 $\beta (F)=5$ 成立。

问题 4（命题逻辑）

给定公式 $F_{n}$= $A_{1}$ ${\stackrel {\cdot }{\vee }}\cdots {\stackrel {\cdot }{\vee }}A_{n}$, 其中 $A_{1},\dots ,A_{n}$ 是原子公式（$n\geq 1$）其中 ${\stackrel {\cdot }{\vee }}$ 表示异或。证明对于所有的 $n\in \mathbb {N}$: 一個合适的赋值 ${\mathcal {A}}$ 对于 $F_{n}$ 是 $F_{n}$ 的模型（即 ${\mathcal {A}}\models F_{n}$）当且仅当 ${\mathcal {A}}(A_{i})=1$ 对奇数个 ${\mathcal {A}}_{i}$ 成立（$1\leq i\leq n$）。

问题 5（命题逻辑）

在下面，我们研究只包含原子 $A_{1},\dots ,A_{n}$ 的公式。

1. 最多有多少个具有不同真值表的公式？
2. 对于每一个真值表，是否存在一个对应的公式？如果存在，请给出构造方法！

问题 6（命题逻辑）

如果上校在谋杀案发生时不在房间里，那么他就无法知道凶手的武器。管家在撒谎，或者他知道凶手是谁。如果巴恩特里夫人是凶手，那么上校在谋杀案发生时就在房间里，或者管家在撒谎。管家知道凶手是谁，或者上校在谋杀案发生时不在房间里。警察得出结论，巴恩特里夫人是凶手。为论证中的每个语句赋予命题变量。将论证写成一组命题公式，其中包含前提和结论作为命题公式 $F$.

问题 7（命题）

将以下表达式形式化，然后简化相应的公式和口头命题。

1. 他的母亲不是英国人，而他的父亲也不是法国人，这是不正确的。
2. 他正在学习物理，但没有学习数学，这是不正确的。
3. 工资在下降，而价格在上涨，这是不正确的。
4. 既不冷也不下雨，这是不正确的。

问题 8（命题）

教授建议为大学餐厅的午餐制定一个新的方案。

1. 如果沒有甜點，每顿午餐都必须有面包。
2. 如果供应面包和甜點，则不供应汤。
3. 如果供应汤，则没有面包。

帮助管理层满足教授的愿望。为此，

1. 将三个命题形式化（作为蕴含式、析取式/合取式），并将它们组合成一个逻辑公式。
2. 为该逻辑公式提供真值表。该公式是否有模型？
3. 为该任务提供一个口语化的表达。