Skip to content

Knowledge & Logic

Logic

  • 语义：定义了语句在每个可能世界（模型）的真值

如\(m\)是\(\alpha\)的一个模型，表示语句\(\alpha\)在模型\(m\)中为真。用\(M(\alpha)\)表示所有的模型。

  • 逻辑蕴涵(entailment): 某语句在逻辑上跟随另一个语句. 如
\[ \alpha |=\beta \]

表示语句\(\alpha\)蕴涵语句\(\beta\)。上句当且仅当，在使\(\alpha\)为真的每个模型中，\(\beta\)也为真。即

\[ \alpha|=\beta \Leftrightarrow M(\alpha)\subset M(\beta) \]

注意，这表示\(\alpha\)是比\(\beta\)更强的断言，排除了更多可能性。

我们可以使用蕴涵来实现逻辑推理。通过枚举所有可能的模型来检验KB为真时\(\alpha\)均为真。这样的过程称为推理算法，是可靠的。

命题逻辑

用大写字母表示命题。复合句由简单语句用括号和逻辑连接词构造而成。

Basic notation

\(\land\) 表示"与"，看起来和"And"中的"A"很像，\(W_{1,3}\land P_{3,1}\)被称为合取式。

\(\lor\) 表示"或"，来源于拉丁文"vel"，\(W_{1,3}\lor P_{3,1}\)被称为析取式。

\(\Rightarrow\) 表示蕴涵(implication)。\(P\Rightarrow Q\) 表示，如果\(P\)为真，那我主张\(Q\)为真，否则无可奉告。

定理证明

  • 逻辑等价: \(\equiv\), 如 \(P\land Q\equiv Q\land P\). 也可以表示成相互蕴涵
\[ \alpha\equiv \beta \quad\text{iff}\quad (\alpha|=\beta) \land (\beta|=\alpha) \]

  • 有效性：一个语句是有效的，如果在所有的模型中都为真。

  • 可满足性：一个语句是可满足的，如果在某些模型中为真。可以通过枚举进行，是一个SAT问题，NP完全问题。

两者的关系可以推出反证法的思路。

\[ \alpha|=\beta \quad \text{iff} \quad (\alpha\land \neg \beta)\text{不可满足} \]
  • 推导与证明

推理规则

  • 假言推理规则(Modus Ponens)

Given \(\alpha\Rightarrow \beta\) and \(\alpha\), we can deduce \(\beta\).

\[ \frac{\alpha\Rightarrow \beta,\quad \alpha}{\beta} \]
  • 消去合取词

extract subsentence from 合取式

\[ \frac{\alpha \land \beta}{\alpha} \]
  • 归结(resolution)

types of Resolution

  • 单元归结(unit resolution)

if \(m=\neg l_i\), then

\[ \frac{l_1\lor \cdots \lor l_k, \quad m}{l_1\lor\cdots \lor l_{i-1}\lor l_{i+1}\lor \cdots\lor l_k} \]
  • 全归结(full reosolution)

if \(m_j=\neg l_i\), then

\[ \frac{l_1\lor \cdots \lor l_k, \quad m1\lor\cdots\lor m_n}{l_1\lor\cdots \lor l_{i-1}\lor l_{i+1}\lor \cdots\lor l_k\lor m_1\lor \cdots\lor m_{j-1}\lor m_{j+1}\lor\cdots\lor m_n} \]

Q1. Given

\[ \begin{align*} &R_1: \quad\neg P_{1,1}\\ &R_2: \quad B_{1,1}\Leftrightarrow (P_{1,2}\lor P_{2,1})\\ &R_3: \quad B_{2,1}\Leftrightarrow (P_{1,1}\lor P_{2,2} \lor P_{3,1})\\ &R_4: \quad \neg B_{1,1}\\ &R_5: \quad B_{2,1} \end{align*} \]

Simplify \(R_1\land R_2\land R_3\land R_4\land R_5\)

Notice that...

任何基于归结的定理证明器，都能确定\(\alpha |=\beta\) 是否成立。其本质就是反证法。若目标命题为\(\alpha\), 已知知识库为\(KB\), 然后使用\(KB\land \neg \alpha\)，若不可满足(对所有模型都为假)，则\(KB |=\alpha\).

  • 合取范式: 子句的连接符是\(\land\)

对所有子句的可能的两两组合（含有互补语句）进行归结，产生新子句。如果该子句没有出现过，则将他装入子句集。直到：

（i） 没有新语句(new \(\subset\) clauses), 则\(KB \land \neg\alpha\) 可满足，

（ii） 产生空语句(like \(P\land \neg P\)), 则\(KB \land \neg\alpha\) 不可满足，原命题可推出\(\alpha\).

This is the following theorem.

Basic Resolution Theorem

If the set \(S\) of sub clauses is not satisfiable, then the resolution closure \(RC(S)\) must contain empty clause.

By prove its converse-negative proposition. That is, if \(RC(S)\) does not contain empty clause, then \(S\) is satisfiable. ?