谓词逻辑与命题推理

谓词符号化

一般而言这类题目不难，思路是设出$R(x)$:x为xxx,$S(x)$:x为xxx 然后注意对$\forall ,\exists$的使用

• 谓词符号化：所有的人都是要死的，苏格拉底是人，所以苏格拉底是要死的。
  • 设$M(x)$:$x$是人
  • 设$R(x)$:$x$会死
  • 设$s$:$s$是苏格拉底
  • 有：因为$(\forall x)(M(x)\to R(x))\wedge M(s)$故$R(s)$
• 谓词符号化:所有的大学生都会说英语，有一些大学生会说法语
  • 设$E(x)$:$x$会说英语
  • 设$F(x)$:$x$会说法语
  • 设$S(x)$:$x$是大学生
  • 有1.$(\forall x)(S(x)\to E(x))$ 2.$(\exists x)(S(x)\wedge F(x))$
  • 注意，在使用$\exists$时候，我们需要使用合取来表示含义而不是蕴含
  • 同时两个陈述并列的时候应该不要使用$\vee$链接

命题推理

以题目形式表现

• 证明下列推理形式的有效性:今天或者是晴天,或者会下雨。如果是晴天,我就会去打球;如果我去打球,那么我就不读书。所以如果我在读书,那么天就在下雨。
  • 命题符号化
    • 设$p$为今天是晴天
    • 设$q$为今天是雨天
    • 设$b$表示我去打球
    • 设$r$表示我在读书
  • 符号化有:

$$\begin{array}{rlr}& p\vee q,p\to b,b\to \neg r& \Rightarrow r\to q\\ & & \\ & (1)r& P(附加)\\ & (2)b\to \neg r& P\\ & (3)\neg b& T(1)(2)I\\ & (4)p\to b& P\\ & (5)\neg p& T(3)(4)I\\ & (6)p\vee q& P\\ & (7)q& T(5)(6)I\\ & (8)r\to q& CP\end{array}$$

• 主要逻辑规则

  • 如果有$p\to q$和$p$,则可以推出$q$
  • 如果有$p\to q$和$\neg q$,则可以推出$\neg p$
  • 如果有$p\vee q$和$\neg q$ 则可以推出$p$,反之亦然
  • 如果有$p$和$q$,则可以推出$p\wedge q$ ,反之亦然
  • 如果有$p\to q$和$q\to r$，则可以推出$p\to q$
  • 如果有$(p\to q)\wedge (r\to s)$和$p\vee r$，则可以推出$q\wedge s$

• 反证法例子

  • 一个具体的例子:证明 $p\to q\Rightarrow \neg q\to \neg p$

\begin{align*} & (1) \quad p \to q & P \\ & (2) \quad \neg (\neg q \to \neg p) & P \quad (\text{反证假设}) \\ & (3) \quad \neg q \land \neg (\neg p) & T(2) \quad (\text{由 } \neg (A \to B) \equiv A \land \neg B \text{}) \\ & (4) \quad \neg q \land p & T(3) \quad (\text{由双重否定 } \neg(\neg p) \equiv p \text{}) \\ & (5) \quad p & T(4) \quad (\text{由合取消除}) \\ & (6) \quad \neg q & T(4) \quad (\text{由合取消除}) \\ & (7) \quad q & T(1)(5) \quad (\text{由 } p \to q \text{ 和 } p \text{，通过肯定前件}) \\ & (8) \quad q \land \neg q & T(6)(7) \quad (\text{由 } q \text{ 和 } \neg q \text{，得到矛盾}) \\ & (9) \quad \neg \neg (\neg q \to \neg p) & IP(2-8) \quad (\text{由矛盾，推导出假设的否定}) \\ & (10) \quad \neg q \to \neg p & DN(9) \quad (\text{由双重否定，得到原结论}) \end{align*} $$ - 显然反证法没有CP好用